JOI2013
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 ที่มีค่าน้อยที่สุด
