Thepsint

Fuel

(http://main.edu.pl/en/archive/pa/2011/pal) *323

ในวันคืนเก่าๆ เมืองทั้ง n เมืองใน Byteland ถูกเชื่อมต่อด้วยถนนสองทิศทางมากมาย ราชาแห่ง Byteland ตัดสินใจที่จะลดจำนวนถนน หลังจากที่เขาปรึกษาหัวหน้าภาคคอมพิวเตอร์เขาได้ลดจำนวนถนนในเมือง Byteland เหลือ n-1 เส้นเชื่อมต่อในเมืองโดยที่จะมีเส้นทางการเดินทางเพียงเส้นเดียวเท่านั้นสำหรับคู่เมืองใดๆ ถนนทั้งหมดจะมีความยาวเท่ากัน

Byteasar ต้องการจะสร้างทัวร์ที่จำนวนเมืองที่แตกต่างกันมากที่สุด เขามีรถที่มีแก๊สสำหรับขับบนถนน m เส้น เขาสามารถเริ่มการเดินทางที่เมืองในก็ได้ และในทำนองเดียวกัน เขาสามารถจบการเดินทางที่เมืองใดก็ได้ไม่จำเป็นต้องเป็นเมืองเริ่มต้น Byteasar สามารถขับผ่านถนนเส้นเดิมซ้ำๆได้ หน้าที่ของคุณคือช่วย Byteasar หาจำนวนของเมืองที่เขาสามารถเยี่ยมชมเมื่อเขาเริ่มการเดินทางด้วยแก๊สเต็มถัง

Input บรรทัดแรกประกอบด้วยจำนวนเต็ม n และ m (1≤n≤500000, 1≤m≤200000000) เมื่อ n คือจำนวนเมือง (ที่จะถูกตั้งชื่อว่า 1, 2, 3, ..., n) และ m คือจำนวนถนนที่สามารถวิ่งได้ด้วยแก๊สเต็มถัง

ต่อจากนั้น n-1 บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็ม a และ b (1≤a, b≤n) บ่งบอกว่ามีถนนเชื่อต่อระหว่างเมือง a และ b

Output ประกอบด้วยจำนวนเต็มหนึ่งจำนวนเท่านั้น คือจำนวนเมืองสูงสุดที่สามารถเยี่ยมชมเมื่อเริ่มการเดินทางด้วยแก๊สเต็มถัง

Cakes

(http://main.edu.pl/en/archive/pa/2009/cia) *374

เทพเจ้าแห่งการอบจากทั่วประเทศได้มารวมตัวกันที่งานประชุมแห่ง Bytean ที่นั่นจะมีการแข่งขันอบเค้กของทีมสามคนโดยทุกๆสามคนจะอบเค้กหนึ่งชิ้น คนๆหนึ่งสามารถเป็นสมาชิกของทีมได้ไม่จำกัดจำนวนทีม อย่างไรก็ตามคนบางคู่จะเกลียดกันทำให้ไม่สามารถอยู่ทีมเดียวกันได้

เป็นที่รู้กันว่าแต่ละคนต้องการผงฟูกี่เดคากรัมสำหรับการอบเค้ก ทีมที่มีสามคนจะต้องใช้ผงฟูปริมาณเท่ากับจำนวนที่คนที่ต้องการมากที่สุดในทีมต้องการ จงหาจำนวนผงฟูที่จะต้องใช้ หากทุกทีมสามคนที่เป็นไปได้จะอบเค้กทีมละหนึ่งชิ้น

Input บรรทัดแรกประกอบด้วยจำนวนเต็ม n และ m (1≤n≤100000, 1≤m≤250000) แทนจำนวนของคนและจำนวนคู่คนที่ไม่ได้เกลียดกัน บรรทัดถัดมาประกอบด้วยจำนวนเต็ม n จำนวนแทนปริมาณผงฟูที่แต่ละต้องการหน่วยเป็นเดคากรัม (1≤pi≤1000000) ต่อมา m บรรทัดแต่ละบรรทัดประกอบด้วยจำนวนเต็ม ai และ bi (1≤ai, bi≤n, ai≠bi) แสดงว่าคนหมายเลข ai และ bi ไม่ได้เกลียดกัน

Output ประกอบด้วยจำนวนเต็มหนึ่งจำนวนเท่านั้น คือปริมาณผงฟูที่ต้องใช้หน่วยเป็นเคคากรัม

Afternoon Tea

(http://main.edu.pl/en/archive/amppz/2011/her) *216

ระหว่างเยี่ยมชมเกาะ Bytic นั้น คุณรู้สึกชื่นชอบอาหารประจำเกาะ นั่นคือชาและนม เครื่องดื่มนี้จะถูกปรุงในกฎที่เคร่งครัดนั่นคือตอนแรกในแก้วจะถูกเติมครึ่งหนึ่งด้วยชาและครึ่งหนึ่งด้วยนม หลังจากนั้นคำแห่งสวรรค์จะถูกประกาศออกมาโดยสำหรับ i=1, 2, 3, …, n หากคำแห่งสวรรค์คำที่ i คือ H คุณจะต้องดื่มน้ำครึ่งแก้ว เติมชาจนเต็มแก้ว แล้วคนจนเข้ากัน แต่หากคำแห่งสวรรค์คำที่ i คือ M คุณจะต้องดื่มน้ำครึ่งแก้ว เติมนมจนเต็มแก้ว แล้วคนจนเข้ากัน หลังจากคุณทำตามคำแห่งสวรรค์ทั้ง n คำแล้ว น้ำในแก้วจะถูกกำจัด

คุณต้องการทราบว่าหลังจากฟังคำแห่งสวรรค์ทั้งหมดแล้วคุณจะได้ดื่มอะไรมากกว่า ชา หรือ นม?

Input บรรทัดแรกระบุจำนวนเต็ม n (1≤n≤100000) บรรทัดที่สองระบุสตริงยาว n ประกอบด้วย H หรือ M เท่านั้น

Output บรรทัดเดียว แสดง H ถ้าคุณได้กินชามากกว่า M ถ้ากคุณกินนมมากกว่า หรือ HM ถ้าคุณกินทั้งสองอย่างนั้นเท่ากัน

ASCII Art

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25507#problem/A

ASCII art คือรูปที่สร้างจากตารางของอักขระ ASCII มีรูปแบบของ ASCII art จำนวนมากในโลก แต่เราสนใจเพียงรูปแบบที่มาตรฐานที่สุดซึ่งเพียงแค่ความหนาแน่นของอักขระเท่านั้นที่จะถูกใช้แสดงบริเวณที่ถูกแรเงาในรูป

คุณจะต้องเขียนโปรแกรมที่จะเปลี่ยนรูปปิดขั้นต้นเป็น ASCII art วิธีการทำนั้นจะถูกอธิบายต่อไป

กำหนดพิกัดสองมิติ OXY โดย OX ชี้ไปทางขวาและ OY ชี้ขึ้น รูปจะถูกตีกรอบด้วยสี่เหลี่ยมจาก (0,0) ถึง (w,h) แต่ละพิกเซลในรูปคือสี่เหลี่ยมจตุรัสจาก (x,y) ถึง (x+1,y+1) โดย 0≤x<w และ 0≤y<h รูปต้นแบบจะถูกสร้างด้วยรูปปิดที่จุดยอดจะไม่สร้างเส้นที่ตัดกัน (แต่สัมผัสกันได้) แต่ละช่องพิกเซลจะถูกเติมเมื่อรูปปิดถูกสร้างขึ้น แต่ละช่องของพิกเซลจะถูกแสดงด้วยอักขระ ASCII ตามอัตราส่วนของพื้นที่ที่ถูกแรเงา โดย

[0-25)% แสดง . (46 ASCII) [25-50)% แสดง + (43 ASCII) [50-75)% แสดง o (111 ASCII) [75-100)% แสดง $ (30 ASCII) 100% แสดง # (35 ASCII)

Driving Directions

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25507#problem/B

ตรงข้ามกับความเชื่อที่แสนฮิต เอเลี่ยนนั้นจริงๆแล้วไม่สามารถบินมั่วๆบนบรรยากาศโลก พวกมันเตะพื้นโลกและออกบินอีกครั้งด้วยความสิ้นเปลือพลังงาน ดังนั้นพวกมันวางแผมอย่างรอบคอบที่จะลงสู่พื้นโลก ทำภารกิจบริเวณนั้น และออกบินต่อ เนื่องจากอารยธรรมของมนุษย์นั้นอ่อนด๋อยมากพวกมันสามารถบินข้ามต้นไม้และสิ่งก่อสร้างส่งผลให้เส้นทางสั้นที่สุดระหว่างแต่ละจุดภารกิจคือเส้นตรงธรรมดาๆ อย่างไรก็ตามเมืองยุคใหม่มีตึกโคตรสูงที่พวกเอเลี่ยนไม่สามารถบินเหนือมันทำให้การทำภารกิจที่เมืองยุคใหม่ยากมาก คุณถูกจ้างด้วยพวกเอเลี่ยนเพื่อที่จะเขียนโปรแกรมสุดโหดที่จะบอกเส้นทางการบินในเมือง งานแรกของคุณ (เพื่อที่จะเพิ่มความน่าเชื่อถือในการทำงานกับพวกเอเลี่ยนต่อไป) คือการเขียนโปรแกรมที่จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังอีกจุดหนึ่ง โปรแกรมนี้จะช่วยเอเลี่ยนวางแผนการใช้พลังงาน

โปรแกรมนี้จะถูกทำให้ง่ายขึ้นด้วยข้อจำกัดหลายข้อ ข้อแรกเนื่องจากการเอเลี่ยนสามารถบินเหนือสิ่งก่อสร้างส่วนมาก สิ่งเดียวที่คุณต้องกังวัลคือตึกยุคใหม่โคตรสูงเท่านั้น ข้อสองปัญหานี้เป็นปัญหาสองมิติ คุณดูแผนที่จากมุมสูงและเสแสร้งว่าทุกวัตถุอยู่บินิิกัด xy เอเลี่ยนจะถูกแทนด้วยวงกลมรัศมี r และเนื่องจากตึกยุคใหม่โคตรสูงนั้นสร้างอย่างมีระบบ ตึกจะสามารถเขียนแทนด้วยรูปสี่เหลี่ยมมุมฉากที่ีด้านขนานกับแกน x และ y

ตามนิยามปกติ ตำแหน่งของเอเลี่ยนคือตรงกลางของแผนที่และระยะทางที่มันเดินทางคือระยะทางที่สุดศูนย์กลางของวงกลมเดินทาง ระหว่างภารกิจส่วนใดส่วนหนึ่งของวงกลมไม่สามารถสัมผัสตึกยุคใหม่โคตรสูง

ในรูปแรกเอเลี่ยนมีรัศมี r=1 และต้องการเดินทางจาก A ไป B เส้นตรงคือเส้นทางสั้นสุดหารไม่สนใจตึกยุคใหม่โคตรสูงหมายเลข 1 เส้นทางสั้นที่สุดที่หลบหลีกตึกโคตรสูงหมายเลขหนึ่งคือการการบินไปตามมุมบนขวา แต่ตึกหมายเลยสองอยู่ใกล้เกินไปที่จะบินไปทางนั้น ดังนั้นเส้นทางที่ดีที่สุดคือการบินไปตามมุมล่างซ้าย ทำให้ได้ระยะทาง 10.570796

ในรูปที่สองมันเป็นไปไม่ได้ที่จะบินหากเอเลี่ยนมีรัสมี r=2 จาก A ไป B เนื่องจากตึกยุคใหม่โคตรสูงทั้งหมดอยู่ใกล้เกินไป

ในรูปที่สามเอเลี่ยนรัศมี r=1 จะต้องบินโค้งไปมาระหว่างตึกทั้งสองเพื่อที่จะได้ระยะทางสั้นสุดจาก A ไป B คือ 11.652892

Input: บรรทัดแรก r (รัศมี) และ n (จำนวนตึก) ถัดมา n บรรทัดแต่ละบรรทัดระบุ x1 y1 x2 y2 ของแต่ละตึก

Output: บรรทัดเดียว คือระยะทางสั้นสุดเป็นทศนิยมหกตำแหน่ง หากหาไม่ได้ให้แสดง "no solution" โดยไม่ต้องมีเครื่องหายคำพูด

Kingdom Reunion

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25507#problem/C

เคลวิล และ คาร์ล เป็นลูกพี่ลูกน้องกันและเป็นราชาของเมืองสองเมืองคือ แอสเทรียและแอปส์เทรีย ร้อยปีที่แล้วประเทศทั้งสองเป็นประเทศเดียวกันแต่ราชาเก่า เฮลวิก ตายและทิ้งประเทศให้ลูกทั้งสอง เอียน และ อินกรัม ไม่มีใครรู้ว่าจะทำไงดีจนกระทั่วแผนการแบ่งประเทศเป็นสองส่วนเท่ากันได้ถูกเสนอขึ้น การแบ่งนี้โคตรยากจนต้องใช้คนจากอนาคต โชคร้ายยิ่งนักบุคคลทั้งห้าพยายามจะแก้ปัญหานี้แล้วไม่สำเร็จจึงทำให้เกิดสงครามกลางเมืองขึ้น สงครามนี้กินเวลาเจ็ดปีและสิ้นสุดด้วย NEERC (ไม่สำคัญ) ตามที่กฎหมายได้กล่าวประเทศจะต้องถูกแบ่งเป็นสองส่วนสำหรับ เอียน และ อินกรัม แต่ประเทศทั้งสองมีพื้นที่ไม่เท่ากัน สงครามจึงเริ่มต้นอีกครั้ง

หลังจากเก้าสิบปีแห่งสงคราม ทรัพยากรธรรมชาติทั้งหมดได้ถูกใช้จนหมดสิ้นทำให้ราชาทั้งสองตะหนักได้ว่าหากสู้กันต่อจะตายกันหมด ดังนั้นพวกเขาตัดสินใจนำสันติเข้าใช้ พวกเขาตัดสินใจที่จะรวมประเทศกลับซึ่งประเทศ แอสเทรียและแอปส์เทรียจะถูกรวมเป็นประเทศ แอแอปส์ทรีอา

ตามหนังสือโบราณ คุณได้ค้นพบคำอธิบายที่หลากหลายเกี่ยวกับเส้นแบ่งเขตของสองประเทศนี้ แต่ละคำอธิบายคือลำดับของเสาเขตแดนซึ่งจะถูกระบุตามเข็มหรือทวนเข็มนาฬิกา อย่างไรก็ตามคุณรู้ได้ทันทีว่าแต่ละจุดต้นของขอบเขตแตกต่างกัน ในบางหนังสือขอบเขตจะไม่ถูกกำหนดเป็นรูปหลายเหลี่ยม คุณต้องการที่จะค้นหาขอบเขตที่แท้จริงของสองประเทศนี้ กำหนดจุดของเส้นเขตแดนของทั้งสามประเทศมีสมบัติดังนี้

สำหรับแต่ละประเทศเส้นที่ถูกสร้างขึ้นด้วยเสาเขตแดนจะเป็นรูปหายเหลี่ยม เส้นขอบเหล่านั้นจะถูกพิจารณาเป็นรูปหลายเหลี่ยมถ้ามันมีอย่างน้อยสามจุดที่ไม่ตัดกันเอง ไม่สัมผัสกันเอง ไม่มีรู และมีพื้นที่ไม่เป็นศูนย์ พื้นที่ของ แอสเทรียและแอปส์เทรียไม่ซ้อนทับกัน พื้นที่ของ แอแอปส์ทรีอาจะต้องเป็นพื้นที่ของแอสเทรียและแอปส์เทรียรวมกันเป๊ะๆ

จงเขียนโปรแกรมพี่ดูว่าคุณสมบัติเหล่านี้ถูกต้อง

Flights

กองทัพนั้นงานยุ่ง การฝึกซ้อมทางการทหารนั้นเริ่มขึ้นเมื่อวาน หน่วยงานแต่ละหน่วยกำลังทำหน้าที่อย่างดีที่สุด (มั้ง) ตัวอย่างเช่น หน่วยปืนใหญ่ก็กำลังยิงจรวด ในขณะที่หน่วยอากาศยานก็กำลังส่งเสบียงให้ทหารราบ

สนามฝึกซ้อมนั้นเป็นเส้นตรง ฐานทัพอากาศและกองทหารราบนั้นอยู่บนจุดบางจุดบนเส้นตรงนี้ และหน่วยปืนใหญ่ก็กำลังยิงจรวดไปทุกที่ การยิงจรวดทุกครั้งนั้นมีการวางแผนไว้เรียบร้อยแล้ว ว่า ยิงเมื่อไร และ มีเส้นทางอย่างไร (อย่าลืมว่ามันเป็นเพียงการซ้อมรบ) แผนการบินของหน่วยอากาศยานก็ได้ทำไว้แล้วเช่นกัน ทุก ๆ อย่างควรจะไม่มีปัญหา แต่จรวดก็ช่างน่ากลัวอยู่ดี ซึ่งอาจจะเกิดปัญหาได้ถึงแม้จะเป็นการฝึกซ้อมก็ตาม

คุณจะต้องช่วยนายพลแห่งหน่วยอากาศยานเพื่อวางแผนเพดานบินปลอดภัยต่ำสุดสำหรับการบินต่าง ๆ จากข้อมูลช่วงเวลาการบินและช่วงตำแหน่งที่จะบิน เพดานบินปลอดภัยต่ำสุดสำหรับเที่ยวบินคือ ความสูงน้อยสุดที่ทางเดินของจรวดทั้งหมดในช่วงเวลาและช่วงตำแหน่งนั้นอยู่ต่ำกว่าหรือเท่ากับความสูงดังกล่าว ถ้าไม่มีจรวดอยู่ในช่วงเวลาและช่วงตำแหน่งดังกล่าวแล้ว เพดานบินปลอดภัยต่ำสุดคือ

You should help aviation generals to plan the minimal safe altitude for each flight. Given the information about flight's time and space intervals, the minimal safe altitude for a flight is the minimal altitude such that all missile trajectories in the corresponding time and space interval are at or below this altitude. If there are no missiles in the flight's time and space interval, then the minimal safe altitude is defined to be zero.

Ballistic missiles are launched from the ground, which is defined to have a zero altitude, and fly along a vertically symmetrical parabola. Missile speed is ignored for this problem, missiles are assumed to follow their trajectory instantaneously.

For example, the picture below shows trajectories of two ballistic missiles in solid lines, and the minimal safe altitudes for four different flights in dashed lines. Vertical lines delimit space intervals of each flight in this sample. Time intervals of the flights in this sample include the launch of both missiles.