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

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

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

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

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

ดังตัวอย่างในรูป (ดูจาก link) มีจรวดอยู่สองอันซึ่งมีเส้นทางแสดงดังเส้นทึบ และมีเพดานบินปลอดภัยต่ำสุดของเที่ยวบินต่าง ๆ แสดงดังเส้นประ เส้นแนวตั้งระบุขอบเขตของช่วงตำแหน่งของเที่ยวบิน ส่วนช่วงเวลาของเที่ยวบินในตัวอย่างนี้ รวมเวลายิงของจรวดทั้งสองอยู่

ข้อมูลนำเข้า:

บรรทัดแรกระบุจำนวนแผนการยิงจรวด n (1 <= n <= 50,000)

หลังจากนั้นอีก n บรรทัดเป็นข้อมูลการยิงจรวด โดยที่แต่ละบรรทัด ประกอบด้วยจำนวนเต็ม 3 ตัว คือ p ซึ่งระบุตำแหน่งที่ยิงจรวด และตำแหน่งสูงสุดของเส้นทางของจรวด x y (0 <= p <= x <= 50,0000; 0 < y <= 50) โดยที่ p และ x เป็นตำแหน่งบนเส้นตรงสนามฝึกซ้อม และ y เป็นความสูงของจุดสูงสุดของเส้นทางของจรวด

จรวดจะถูกยิงที่ละลูกในแต่ละนาที ตามลำดับที่ปรากฎในข้อมูลนำเข้า

บรรทัดถัดมาจะระบุจำนวนเที่ยวบิน m (1 <= m <= 20,000)

หลังจากนั้นอีก m บรรทัดเป็นข้อมูลเที่ยวบินโดยที่แต่ละบรรทัด ประกอบด้วยจำนวนเต็ม 4 ตัว t1 t2 x1 x2 โดยที่ t1 t2 คือช่วงเวลาของเที่ยวบิน ส่วน x1 x2 คือช่วงตำแหน่งของเที่ยวบินบนเส้นตรงสนามฝึกซ้อม

ข้อมูลส่งออก:

สำหรับแต่ละเที่ยวบิน ให้พิมพ์ข้อมูลหนึ่งบรรทัดประกอบด้วยค่าเพดานบินปลอดภัย โดยที่มีค่าความผิดพลาดสมบูรณ์ไม่เกิน 10^-4