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

Kalvin John Ian Helvik IV and Karl James Ingram Helvik III are second cousins and kings of neighbouring countries, Aastria and Abstria. One hundred years ago their countries constituted a single country, but the old king Helvik died and left his country to his twin sons, Ian and Ingram. Nobody knew what to do, until it was suggested to split the country into two equal parts. This was an overwhelmingly complex task, which the wisemen tried to cope with by calling the best minds from the future to solve. Unfortunately, five attempts to solve the problem had failed, and the bloody civil war broke out. It lasted for seven years and ended with the NEERC (Northeastern Enormously Ragged Combat). As the Final Ordinance said, there would be two new countries in the place of the old one, one for Ian and one for Ingram. But these two countries had unequal areas, so it took only three years for war to start again. After ninety years of war, all resources of two countries were exhausted. At the end of the year both kings had realized that they would not survive the next year if the war continued, so they simultaneously sent envoys with offers of peace. They had decided to unite their countries back and live in peace. The united land of Aastria and Abstria was named Aabstria. In the manuscripts of the old ages you had found several descriptions of boundaries of the countries. Each description is a sequence of locations of boundary monuments, which are listed in clockwise or counterclockwise order following the boundary. However, you suddenly realized that in different sources locations of boundary monuments differ. In some of them, the boundary does not even form a polygon. You decided to do an investigation to discover what the actual boundaries of the countries were. Given locations of the boundary monuments for each of three countries the following statements should hold: For each country, the polyline formed by the boundary monuments should be a polygon. A polyline is considered to be a polygon if it has at least three points, no self-intersections, self-touches or holes, and has a non-zero area. The interiors of Aastria and Abstria polygons should not intersect. The union of Aastria and Abstria should be precisely equal to Aabstria.

Your task is to write a program that checks if these facts are true.

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.