ผลต่างระหว่างรุ่นของ "Usaco2014"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย '== USACO 2013 November Contest == === Problem 1: Empty Stalls [Brian Dean, 2013] (GOLD) === Source: [http://www.usaco.org/index.php?p...')
 
แถว 12: แถว 12:
  
 
=== Problem 2: Line of Sight [Brian Dean and Chad Waters, 2013] (GOLD) ===
 
=== Problem 2: Line of Sight [Brian Dean and Chad Waters, 2013] (GOLD) ===
 +
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=347]
 +
 +
วัวของชาวนานจอห์นจำนวน N ตัว (1 <= N <= 50,000) อยู่ที่ตำแหน่งที่แตกต่างกันในทุ่งหญ้าสองมิติ  ที่จุดศูนย์กลางของทุ่งหญ้ามีฉางข้าว (ไซโล) ทรงกลมขนาดใหญ่  วัวที่อยู่คนละข้างของไซโลจะไม่สามารถมองเห็นกันได้ เนื่องจากไซโลนั้นบังอยู่  ให้หาจำนวนคู่ของวัวที่สามารถมองเห็นกันได้โดยตรง (direct line of sight)
 +
 +
ไซโลข้าวนั้นมีจุดศูนย์กลางอยู่ที่จุด (0,0) และมีรัศมี R ไม่มีวัวตัวใด ๆ ที่อยู่บนขอบหรืออยู่ภายในวงกลมที่แทนไซโล  นอกจากนี้ไม่มีวัวสองตัวที่อยู่บนเส้นที่สัมผัสกับวงกลมไซโล  ค่าของรัศมี R นั้นอยู่ระหว่าง 1..1,000,000 และวัวแต่ละตัวจะอยู่บนพิกัดที่เป็นจำนวนเต็มที่มีขอบเขต -1,000,000..+1,000,000
 +
 +
=== Problem 3: No Change [Brian Dean, 2013] (GOLD) ===

รุ่นแก้ไขเมื่อ 09:39, 23 มีนาคม 2557

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

Problem 3: No Change [Brian Dean, 2013] (GOLD)