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

ASCII art is an art of creating pictures with a grid of ASCII characters. There are many styles of ASCII art, but we are interested in the most primitive one, where just an overall character density is used to represent differently shaded areas of the picture.

You should write a proof-of-concept program that renders a filled closed polygon with a rectangular grid of ASCII characters. The whole process is explained in detail below.

Let OXY be a Cartesian coordinate system with OX pointing to the right and OY pointing up. Drawing canvas is bounded with (0, 0) – (w, h) rectangle. Pixels on the canvas are (x, y) – (x + 1, y + 1) squares where x and y are integers such that 0 ≤ x < w and 0 ≤ y < h. A filled closed polygon without self-intersections and self-touchings (but not necessarily convex) is drawn on the canvas. Pixels of the canvas become partially filled during the process. Each pixel is represented by an ASCII character depending on the percentage of its filled area according to the following table:

Pixel percentage area filled Character name Glyph ASCII code From 0% inclusive to 25% exclusive Full stop . 46 From 25% inclusive to 50% exclusive Plus sign + 43 From 50% inclusive to 75% exclusive Small letter o o 111 From 75% inclusive to 100% exclusive Dollar sign $ 36 100% Number sign # 35

The resulting ASCII characters for all pixels are printed top-to-bottom and left-to-right to get a visual representation of the drawing.

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" โดยไม่ต้องมีเครื่องหายคำพูด