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] เป็นเลขคี่

Oz

ในฐานะหัวหน้าของเกาะ 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 บนตลิ่งล่าง

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

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

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