Usaco2014

USACO 2013 November Contest

Problem 1: Empty Stalls [Brian Dean, 2013] (GOLD)

Source: [1]

ยุ้งฉางใหม่ของชาวนาจอห์นมีคอก (stall) จำนวน N คอกเรียงตัวกันเป็นวงกลม (2 <= N <= 3,000,000) โดยมีหมายเลข 0,...,N-1, โดยที่คอกที่ N-1 จะติดกับคอกที่ 0

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

ให้ข้อมูลของคอกที่วัวแต่ละตัวต้องการ ให้หาหมายเลขของคอกที่น้อยที่สุดที่ยังว่างอยู่ เมื่อวัวทุกตัวกลับเข้าคอกหมดแล้ว

Problem 2: Line of Sight [Brian Dean and Chad Waters, 2013] (GOLD)

Source: [2]

วัวของชาวนานจอห์นจำนวน N ตัว (1 <= N <= 50,000) อยู่ที่ตำแหน่งที่แตกต่างกันในทุ่งหญ้าสองมิติ ที่จุดศูนย์กลางของทุ่งหญ้ามีฉางข้าว (ไซโล) ทรงกลมขนาดใหญ่ วัวที่อยู่คนละข้างของไซโลจะไม่สามารถมองเห็นกันได้ เนื่องจากไซโลนั้นบังอยู่ ให้หาจำนวนคู่ของวัวที่สามารถมองเห็นกันได้โดยตรง (direct line of sight)

ไซโลข้าวนั้นมีจุดศูนย์กลางอยู่ที่จุด (0,0) และมีรัศมี R ไม่มีวัวตัวใด ๆ ที่อยู่บนขอบหรืออยู่ภายในวงกลมที่แทนไซโล นอกจากนี้ไม่มีวัวสองตัวที่อยู่บนเส้นที่สัมผัสกับวงกลมไซโล ค่าของรัศมี R นั้นอยู่ระหว่าง 1..1,000,000 และวัวแต่ละตัวจะอยู่บนพิกัดที่เป็นจำนวนเต็มที่มีขอบเขต -1,000,000..+1,000,000