JOI2013

disparity

การเลือกตั้งระดับชาติกำลังจะเริ่มขึ้นที่อาณาจักร JOI โดยที่อาณาจักร JOI ประกอบไปด้วย N จังหวัด

แผนที่ของอาณาจักร JOI จะเป็นตารางกริดสี่เหลี่ยม ประกอบไปด้วยช่อง H x W บล็อค โดยจะมีบล็อค H บล็อคในแนวดิ่ง และ W บล็อคในแนวนอน บล็อคจะติดกับบล็อคอื่น ๆ ที่ขอบทั้งสี่ด้าน (นั่นคือ ด้านซ้าย ขวา บน และล่าง) บล็อค H x W บล็อคจะถูกแบ่งเป็นจังหวัด N จังหวัด แต่ละจังหวัดจะเป็นบริเวณที่ติดกันที่ประกอบด้วยบล็อค โดยรวมแล้ว จะมีผู้มีสิทธิ์ลงคะแนน Pi คน ภายในจังหวัดที่ i (1 <= i <= N)

คุณเป็นประธานกกต. ของ JOI เป็นหน้าที่ของคุณที่จะต้องแบ่งจังหวัด N จังหวัดให้เป็น K หน่วยการเลือกตั้ง (1 <= K <= N) เพื่อที่จะเลือกสส. K คน แต่ละหน่วยการเลือกตั้งจะต้องมีอย่างน้อยหนึ่งจังหวัด และบล็อกที่อยู่ในแต่ละเขตการเลือกตั้งจะต้องเป็นบริเวณที่เชื่อมติดกัน สังเกตว่า บล็อคจะติดกับบล็อคอื่น ๆ เมื่อมีด้านติดกันเท่านั้น บล็อคที่มีจุดยอดร่วมกันเท่านั้นจะไม่ถือว่าติดกัน

สำหรับแต่ละหน่วยเลือกตั้ง อัตราส่วน 1/(จำนวนผู้มีสิทธิ์เลือกตั้ง) จะเรียกว่า น้ำหนักของการโหวต ของหน่วยการเลือกตั้งนั้น ค่า vote-value disparity จะถูกนิยามว่าเป็นอัตราส่วนระหว่างน้ำหนักของการโหวตที่มากที่สุดหารด้วยน้ำหนักของการโหวตที่น้อยที่สุดของหน่วยการเลือกตั้งทั้งหมด ค่าของ vote-value disparity เริ่มมีความสำคัญมากขึ้นเรื่อย ๆ คุณต้องการทำให้ค่านี้มีค่าน้อยที่สุดเท่าที่จะทำได้

synchronization

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

แต่ละเซอเวอร์มีความสามารถในการเชื่อมต่อที่สูงมากทำให้เซอเวอร์สองเซอเวอร์ที่มีข้อมูลที่แตกต่างกันและเชื่อมต่อกันอยู่จะแลกเปลี่ยนข้อมูลกันโดยอัติโนมัติ หลังจากการเชื่อมต่อระหว่าง A และ B, A และ B จะมีข้อมูลทั้งหมดที่เคยอยู่ใน A และ B อย่างใดอย่างหนึ่งก่อนการเชื่อมต่อ

เพื่อที่จะลดค่าใช้จ่าย เส้นเชื่อมจะถูกสร้างอย่างมากเพียง N-1 เส้นเท่านั้น หลังจากเส้นเหล่านั้นถูกสร้างมันจะมีเส้นทางเพียงเส้นทางเดียวที่จะเชื่อมจากเซอเวอร์หนึ่งไปยังอีกเซอเวอร์หนึ่งโดยจะไม่ผ่านเซอเวอร์ใดๆซ้ำกัน

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

เป็นที่รู้กันว่าที่เวลา j (1 ≤ j ≤ M) มีเพียงเส้นเชื่อมเส้นเดียวที่จะเปลี่ยนแปลงสถานะ

เราต้องการรู้จำนวนของข้อมูลที่บางเซอเวอร์มีที่เวลา M+1

watching

มีกิจกรรม (event) ทางวัฒนธรรมมากมายในออสเตรเลีย เช่น กีฬาและสัตว์นานาชนิต คุณพยายามจะเข้าชมกิจกรรมต่าง ๆ บนถนนใน Brisbane

ถนนถูกแบ่งเป็น 1 000 000 000 ส่วน แต่ละส่วนมีหมายเลข 1,2,...,1 000 000 000 จากทิศตะวันตกไปยังตะวันออก คุณต้องการดูกิจกรรม N กิจกรรม กิจกรรมที่ i อยู่ที่ส่วนที่ Ai

เพื่อที่จะได้ดูกิจกรรม คุณได้เตรียมกล้องขนาดเล็ก P กล้อง และกล้องขนาดใหญ่ Q กล้อง คุณสามารถเลือกจำนวนเต็มบวก w เพื่อกำหนดค่าพารามิเตอร์ของการถ่ายรูป เมื่อเลือก w แล้ว กล้องขนาดเล็กจะสามารถถ่ายรูปได้ส่วนที่ติดกัน w ส่วน และกล้องขนาดใหญ่สามารถถ่ายรูปได้ 2w ส่วนที่ติดกัน รูปของแต่ละส่วนจะสามารถถูกถ่ายได้โดยกล้องหลายกล้อง คุณต้องการถ่ายรูปให้ครบทุก ๆ ส่วนที่มีกิจกรรมเกิดขึ้น เนื่องจากในงานจะมีคนมากมายและคุณกลัวกล้องจะหาย คุณจึงต้องการกำหนดตำแหน่งของกล้องทุกกล้อง และคุณจะไม่ย้ายกล้องเหล่านี้ ค่าใช้จ่ายในการถ่ายรูปนั้นขึ้นกับค่าพารามิเตอร์ w ยิ่งมีค่ามาก ค่าใช้จ่ายก็ยิ่งมาก เป้าหมายของคุณคือการหาค่า w ที่มีค่าน้อยที่สุด