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

Birthday

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

• เค้กจะถูกวางบนพิกัด xy ที่จุดกึ่งกลางของเค้กอยู่ที่ (0,0)
• เค้กจะไม่มีความหนา
• ไม่มีการตัดครั้งใดทับกันพอดี
• จุดยอดของเส้นการตัดทั้งสองจุดของแต่ละเส้นจะอยู่นอกบริเวณเค้ก
• ทุกการตัดจะผ่านเค้ก (ดังนั้นจะมีจำนวนเค้กเป็นจำนวนบวกทั้งสองข้างของทุกการตัด)

การเขียนโปรแกรม คุณจะต้องเขียนฟังก์ชัน pieces(int R,int N,int *X1,int *Y1,int *X2,int *Y2) โดย R: รัศมีเค้ก N: จำนวนการตัด X1 Y1 X2 Y2 อาเรย์เก็บว่าตัดจากจุด (X1[i],Y1[i]) ไปยัง (X2[i],Y2[i]) และจะคืนค่าจะนวนชิ้นของเค้กหลังการตัด

ขอบเขตข้อมูล 1≤R≤500 1≤N≤1000 -500≤X1[i],X2[i],Y1[i],Y2[i]≤500

Citizen

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

เนื่องจากนักคณิตศาสตร์ได้ยึดครององค์การสหประชาชาติ กฎการขอสัญชาติจึงง่ายดายมาก แม้ว่าแต่ละประเทศมีกฎที่แตกต่างกันในการให้สัญชาติ ทุกประเทศจะปฏิบัติตามเงื่อนไขเดียวกัน

• คุณได้สัญชาติถ้าคุณอยู่ในประเทศนั้นอย่างต่อเนื่องเป็นเวลา p ปี
• ถ้าคุณออกจากประเทศเป็นเลา q ปีโดยไม่กลับมาเยี่ยมเลย สถานะสัญชาติจะหายไป

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

ตัวอย่าง สมมติว่ากฎของประเทศห้าประเทศเป็นดังนี้

• ออสเตรเลีย p=2 q=15
• บราซิล p=6 q=3
• ฝรั่งเศส p=6 q=11
• อินเดีย p=4 q=7
• สิงคโปร์ p=8 q=5

แผนของคุณอาจเป็นดังนี้

• ไปฝรั่งเศสและอยู่ที่นั่น 6 ปีเพื่อได้สัญชาติฝรั่งเศส
• ไปออสเตรเลียและอยู่ที่นั่น 2 ปีเพื่อได้สัญชาติออสเตรเลีย
• ไปอินเดียและอยู่ที่นั่น 4 ปีเพื่อได้สัญชาติอินเดีย
• แวะฝรั่งเศสอย่างรวดเร็วเพื่อรักษาสถานภาพสัญชาติฝรั่งเศส (ไม่นับเวลา)
• บินไปบราซิล 6 ปีเพื่อได้สัญชาติบราซิล

สังเกตได้ว่าหากคุณไม่แวะฝรั่งเศสหลังจากอินเดีย คุณจะเสียสัญชาติฝรั่งเศส (2+4+6 ปีในออสเตรเลีย อินเดีย และบราซิลมีค่ามากกว่า q=11 ของฝรั่งเศส) นี่คือจำนวนสัญชาติมากที่สุดที่คุณมีได้ หากคุณพยายามได้สัญชาติสิงคโปร์ คุณจะสูญเสียสัญชาติอินเดียและบราซิลระหว่างระยะเวลานั้น มีวิธีอีกมากมายที่จะได้ 4 สัญชาติในเวลาเดียวกันแต่ไม่มีวิธีที่จะได้มากกว่านั้น

การเขียนโปรแกรม คุณจะต้องเขียนฟังก์ชัน countries ดังนี้: int countries(int N,int *P,int *Q) โดยฟังก์ชันนี้จะคำนวณจำนวนที่มากที่สุดของสัญชาติที่คุณสามารถถือได้ในเวลาหนึ่ง

ตัวแปร N: จำนวนประเทศ P: อาเรย์ยาว N เก็บค่า P แต่ละประเทศ Q: อาเรย์ยาว N เก็บค่า Q แต่ละประเทศ

ขอบเขตข้อมูล 1≤N≤100000 2≤P[i]≤10000, P[i] เป็นเลขคู่ 1≤Q[i]≤9999, Q[i] เป็นเลขคี่

Fog

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

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

แม่น้ำมีตลิ่งบนและตลิ่งล่างแต่ละตลิ่งจะมีเกาะ N เกาะ ชื่อว่าเกาะ 1, 2, 3, …, N เรียงจากซ้ายไปขวา

คุณไม่รู้จำนวนของสะพาน อย่างไรก็ตามคุณรู้ว่า

• แต่ละสะพานจะเริ่มที่จุด 1, 2, 3, …, N ของตลิ่งบนและจบลงที่จุดๆหนึ่งของตลิ่งล่าง
• ไม่มีสะพานใดตัดกัน แม้ว่ามันจะสามารถเริ่มหรือสิ้นสุดที่จุดเดียวกัน

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

• พายจากจุด 1, 2, 3, …, N ของตลิ่งบนไปยังจุดๆหนึ่งของตลิ่งล่าง
• นับสะพานที่คุณลอด โดยคุณจะไม่นับสะพานที่เริ่มหรือสิ้นสุดที่จุดที่คุณเริ่มหรือสิ้นสุดการพายเรือ
• บางครั้ง การพายเรือครั้งนั้นจะทำให้คุณรู้ตัวว่าคุณอยู่ใต้สะพานตลอดเวลา (มีสะพานเชื่อมจากจุดเริ่มต้นการพายไปยังจุดสิ้นสุดการพาย)

แต่ละเส้นทางสามารถเริ่มและสิ้นสุดที่ไหนก็ได้ (คุณไม่จำเป็นต้องเริ่มที่จุดสิ้นสุดของครั้งที่แล้ว) แขนของคุณแข็งแรงเพียงพอที่จะให้คุณพายเรือได้อย่างมาก 250000 ครั้ง

การเขียนโปรแกรม คุณจะต้องสร้าง goSail() ซึ่งจะเรียก row() และ foundBridge() โดย int row(int top,int bottom) จะส่งคืนค่าจำนวนสะพานที่คุณลอดหากพายจากจุด top บนตลิ่งบนและจบที่จุด bottom บนตลิ่งล่าง หากคุณอยู่ใต้สะพานตลอดเวลา row จะคืนค่า -1

void foundBridge(int top,int bottom) จะส่งคำตอบว่าคุณได้เจอสะพานที่เริ่มจากจุด top บนตลิ่งบนและจบที่จุด bottom บนตลิ่งล่าง

goSail(int n) เป็นฟังก์ชันที่คุณเขียนและจะรับค่า n คือจำนวนจุดบนแต่ละตลิ่ง

ขอบเขตข้อมูล 1≤N≤100000

Barricades

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

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

• จากเมืองที่อยู่ในเขตปลอดภัย คุณจะสามารถเดินทางไปยังเมืองใดๆก็ได้ที่อยู่ในเขตปลอดภัยเช่นกัน
• คุณจะไม่สามารถเดินทางจากเมืองที่อยู่นอกเขตปลอดภัยไปยังเมืองที่อยู่ในเขตปลอดภัย
• มีเมือง k เมืองพอดีในเขตปลอดภัย

มีวิธีการเลือกเขตปลอดภัยหลากหลายวิธีถูกเสนอขึ้น แต่ละค่าของ k มันจำเป็นที่เราจะต้องรู้จำนวนถนนที่น้อยที่สุดที่จะต้องถูกทำลายเพื่อที่สร้างเขตปลอดภัยขนาด k หน้าที่ของคุณคือการช่วย Byteasar เขียนหาว่าสำหรับแต่ละค่า k จะต้องทำลายถนนอย่างน้อยกี่เส้นเพื่อสร้างเขตปลอดภัยนั้น

Task

จงเขียนโปรแกรมที่

• อ่านข้อมูลนำเข้าซึ่งจะอธิบายสภาพถนนใน Byteland และจำนวนครั้งของคำถาม
• สำหรับแต่ละคำถาม ค้นหาจำนวนการทำลายถนนที่น้อยที่สุดที่เพียงพอกับการสร้างเขตปลอดภัยในขนาดนั้นๆ
• แสดงผลคำตอบทางข้อมูลส่งออก

Input

บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งจำนวน n (1≤n≤3000) แสดงจำนวนเมืองใน Byteland เมืองจะถูกตั้งชื่อ 1, 2, 3, …, n

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

บรรทัดต่อมาประกอบด้วยจำนวนเต็มหนึ่งจำนวน m (1≤m≤n) แสดงจำนวนของคำถาม ต่อจากนั้น m บรรทัดประกอบด้วยจำนวนเต็มหนึ่งจำนวน k_i (1≤k_i≤n) แสดงคำถามลำดับที่ i ซึ่งหมายถึงจำนวนเมืองที่ต้องการจะมีในเขตปลอดภัย

Output โปรแกรมของคุณจะต้องแสดงจำนวนเต็ม m จำนวนแยกกัน m บรรทัด โดยแต่ละบรรทัดจะเป็น

• -1 ถ้าคุณไม่สามารถสร้างเขตปลอดภัยขนาด k_i ได้
• จำนวนการทำลายถนนที่น้อยที่สุดที่เพียงพอกับการสร้างเขตปลอดภัยในขนาด k_i

===Example

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

7
1 2
1 3
2 4
2 5
3 6
3 7
2
2
3

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

2
1