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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 23 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 23: แถว 23:
 
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=348]
 
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=348]
  
Farmer John is at the market to purchase supplies for his farm. He has in
+
ชาวนาจอห์นอยู่ที่ตลาดเพื่อจะซื้อของไปยังฟาร์ม เขามีเงินในกระเป๋า K เหรียญ (1 <= K <= 16) แต่ละเหรียญมีมูลค่าในช่วง 1..100,000,000 ชจ.ต้องการจะซื้อของเป็นลำดับจำนวน N ครั้ง (1 <= N <= 100,000) โดยที่การซื้อครั้งที่ i จะต้องใช้เงิน c(u) หน่วย  (1 <= c(i) <= 10,000) ระหว่างที่ชจ.ซื้อของเขาสามารถหยุดและจ่ายเงินด้วยเหรียญหนึ่งเหรียญได้ เงินที่จ่ายนั้นจะจ่ายสำหรับของที่เขาซื้อทั้งหมดนับตั้งแต่การจ่ายครั้งสุดท้าย (แน่นอนเหรียญดังกล่าวนั้นจะต้องมีค่ามากพอที่จะจ่ายเงินสำหรับการซื้อนั้นได้) โชคไม่ดีที่คนขายที่ตลาดไม่มีเงินทอนเลย  ดังนั้นเมื่อชจ.จ่ายเหรียญที่มีมูลค่ามากกว่าเงินที่เขาต้องจ่าย เขาจะไม่ได้เงินทองกลับมาแต่อย่างใด
his pocket K coins (1 <= K <= 16), each with value in the range
 
1..100,000,000. FJ would like to make a sequence of N purchases
 
(1 <= N <= 100,000), where the ith purchase costs c(i) units of money
 
(1 <= c(i) <= 10,000).  As he makes this sequence of purchases, he can
 
periodically stop and pay, with a single coin, for all the purchases made
 
since his last payment (of course, the single coin he uses must be large
 
enough to pay for all of these). Unfortunately, the vendors at the market
 
are completely out of change, so whenever FJ uses a coin that is larger
 
than the amount of money he owes, he sadly receives no changes in return!
 
  
Please compute the maximum amount of money FJ can end up with after making
+
ให้คำนวณเงินที่มากที่สุดที่ ชจ. จะมีเหลือหลังจากการซื้อของครบ N ครั้ง  ให้แสดงผลลัพธ์ -1 ถ้าเป็นไปไม่ได้ที่ ชจ. จะซื้อของได้ทั้งหมด
his N purchases in sequenceOutput -1 if it is impossible for FJ to make
+
 
all of his purchases.
+
== USACO 2013 December Contest ==
 +
 
 +
=== Problem 1: Vacation Planning [Kalki Seksaria and Richard Peng, 2013] (GOLD) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=364]
 +
 
 +
บริษัทการบินโบวิเนียควบคุมเส้นทางการบินที่เชื่อมต่อ N ฟาร์มที่มีแม่วัวอาศัยอยู่ (1 <= N <= 20,000) ในจำนวนนี้มีฟาร์มทั้งสิ้น K ฟาร์มที่กำหนดให้เป็นสถานีเชื่อมต่อการบิน (hub) (1 <= K <= 200, K <= N)
 +
 
 +
ในปัจจุบันบริษัทการบินโบวิเนียได้ให้บริการเส้นทางการบินเที่ยวเดียว (one-way flights) ทั้งสิ้น M เส้นทาง (1 <= M <= 20,000) โดยเที่ยวบินที่ i จะบินจากฟาร์ม u_i ไปยังฟาร์ม v_i และมีค่าใช้จ่าย d_i บาท (1 <= d_i <= 10,000) สำหรับเที่ยวบินแต่ละเที่ยวนั้นจะต้องมีอย่างน้อยหนึ่งปลายทาง u_i หรือ v_i ที่เป็นสถานีเชื่อมต่อการบิน และจะมีอย่างมากเพียงหนึ่งเที่ยวบินเท่านั้นที่เชื่อมระหว่างสองฟาร์มสำหรับทิศทางหนึ่งๆ และไม่มีสองเที่ยวบินที่มีฟาร์มต้นทางและปลายทางเดียวกัน
 +
 
 +
เบซซี่เป็นดูแลการขายตั๋วของบริษัทการบินโบวิเนีย แต่ทว่าระหว่างที่เธอกำลังเคี้ยวหมากฝรั่งอย่างชิลชิลอยู่หลายชั่วโมงนั้น ได้เกิดมีการขอซื้อตั๋วแบบเที่ยวเดียวเกิดขึ้นพร้อมกันจำนวน Q รายการ (1 <= Q <= 50,000) เนื่องจากวันหยุดยาวของเหล่าแม่วัวกำลังจะมาถึง โดยรายการขอซื้อตั๋วที่ i จะระบุความต้องการเดินทางไปจากฟาร์ม a_i ไปยังฟาร์ม b_i
 +
 
 +
เบซซี่รู้สึกโดนงานทับใส่จนจัดการไม่ทัน เราจึงขอร้องให้คุณช่วยเบซซี่ในการประมวลผลว่าแต่ละรายการขอซื้อตั๋วสามารถทำได้หรือไม่ และค่าใช้จ่ายน้อยที่สุดที่ใช้ในการซื้อตั๋วถ้าสามารถตอบสนองรายการที่ต้องการได้
 +
 
 +
เพื่อลดขนาดของผลลัพธ์ ให้คุณแสดงเพียงจำนวนรายการขอซื้อที่มีเที่ยวบินรองรับ และค่าใช้จ่ายรวมน้อยที่สุดที่ใช้ในการซื้อตํ่วเหล่านั้น
 +
 
 +
หมายเหตุตัวเลขจำนวนนี้อาจไม่สามารถเก็บได้ด้วยจำนวนเต็มขนาด 32 บิต
 +
1
 +
 
 +
=== Problem 2: Optimal Milking [Brian Dean, 2013] (GOLD) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=365]
 +
 
 +
ชาวนาจอห์นได้ซื้อโรงนาใหม่ที่ประกอบไปด้วยเครื่องสกัดนมวัวทั้งหมด N เครื่อง (1 <= N <= 40,000) เพื่อความสะดวกให้ระบุด้วยหมายเลข 1 ถึง N และเรียงตัวกันเป็นแถวหนึ่งแถว
 +
 
 +
เครื่องสกัดนมเครื่องที่ i สามารถสกัดนมได้ M(i) หน่วยต่อวัน (1 <= M(i) <= 100,000) แต่ทว่าโชคร้ายเนื่องจากขณะติดตั้งเครื่องรีดนมแต่ละเครื่องถูกวางไว้ติดกันเกินไปจนทำให้ ถ้าเครื่องที่ i ใช้งานแล้วเครื่องสองเครื่องข้างๆ ที่ติดกันจะไม่สามารถใช้งานในวันเดียวกันได้ (เครื่องที่อยู่ที่ขอบจะมีเครื่องข้างๆ เพียงหนึ่งเครื่องเท่านั้น) จอห์นสามารถเลือกกลุ่มที่แตกต่างกันของเครื่องสกัดนมเพื่อให้ทำงานในวันที่แตกต่างกันได้อย่างอิสระ
 +
 
 +
จอห์นสนใจในการคำนวณหาปริมาณนมที่มากที่สุดที่เขาสามารถสกัดได้ในเวลา D วัน (1 <= D <= 50,000) ยามเริ่มต้นของแต่ละวันจอห์นจะมีเวลามากเพียงพอที่จะซ่อมบำรุงเครื่องสกัดนมเครื่องหนึ่ง เครื่องที่ i เพื่อให้ปริมาณนมที่สกัดได้เปลี่ยนจากเดิมไปเป็น M(i) หน่วยตั้งแต่วันนั้นเป็นต้นไป เมื่อกำหนดรายการซ่อมบำรุงที่ทำได้ในแต่ละวันมาให้ หน้าที่ของคุณคือให้ช่วยจอห์นหาว่าปริมาณนมที่เขาสามารถสกัดได้ในเวลา D วันเป็นเท่าไร (หมายเหตุตัวเลขอาจไม่สามารถเก็บด้วยจำนวนเต็มขนาด 32 บิตได้)
 +
 
 +
=== Problem 3: The Bessie Shuffle[Mark Gordon, 2013] (GOLD) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=366]
 +
 
 +
เบซซี่กำลังซ้อมเทคนิคไพ่อยู่ ขณะนี้เธอได้ชำนาญเทคนิคสลับไพ่แบบเบซซี่แล้ว การสลับไพ่ทำบนสำรับที่มีไพ่จำนวน M ใบ (2 <= M <= 100,000) ทำโดยการสลับไพ่ ไพ่ทุกใบจากตำแหน่งเดิมที่ i จากด้านบนจะกลายเป็นไพ่ในตำแหน่งที่ P[i] จากด้านบนแทน
 +
 
 +
ตอนนี้เบซซี่กำลังทดลองเทคนิคนี้พ่บนสำรับไพ่ที่มีขนาดใหญ่ โดยเธอมีสำรับไพ่ที่มีไพ่ทั้งหมด N ใบ (M <= N <= 1,000,000,000) เพื่อความสะดวกขอตั้งชื่อเป็น 1 ถึง N เธอใช้เทคนิคสลับไพ่โดยการหยิบไพ่ M ใบแรกออกมาและโชว์เทคนิคสลับไพ่แบบเบซซี่ จากนั้นวางไพ่ทั้ง M ใบไว้บนสำรับใหญ่ดังเดิม จากนั้นเธอจะหยิบไพ่ใบบนออกจากสำรับและคว่ำหน้าลงเพื่อสร้างสำรับใหม่ เธอจะทำเช่นนี้ไปเรื่อยๆ  คือเธอจะแสดงกลและหยิบไพ่ใบบนสุดคว่ำหน้าลงเรื่อยๆเพื่อสร้างสำรับใหม่ จนครบทุกใบหากทำได้ แต่หากไพ่ที่เหลือมีน้อยกว่า M ใบเธอจะไม่ใช้เทคนิคสลับไพ่แต่เธอก็ยังจะคว่ำไพ่ใบบนุสุดลงไปเหนือใบอื่นต่อไปจนไม่มีไพ่เหลืออยู่
 +
 
 +
เบซซี่รู้ตำแหน่งเริ่มต้นของไพ่ทั้งหมดตามลำดับคือ 1 จะอยู่บนสุด, ถัดมาเป็น 2, และ N จะอยู่ล่างสุด เมื่อกำหนดรายละเอียดของเทคนิคการสลับไพ่แบบเบซซี่ หน้าที่ของคุณคือช่วยเบซซี่หาว่าไพ่หมายเลขใดจะอยู่ในตำแหน่งที่ระบุ Q ตำแหน่งที่แตกต่างกัน (1 <= Q <= N, Q <= 5,000)
 +
 
 +
หมายเหตุ: ให้พิจารณาตัวอย่างในโจทย์เพื่อประกอบความเข้าใจ
 +
 
 +
== USACO 2014 US Open ==
 +
 
 +
=== Problem 1: Fair Photography [Brian Dean, 2014] (Gold) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=436]
 +
 
 +
วัวจำนวน N ตัว (1 <= N <= 100,000) ของ ชจ. ยืนอยู่ที่ตำแหน่งต่าง ๆ บนรั้วยาวหนึ่งมิติ  วัวตัวที่ i ยืนอยู่ที่ตำแหน่ง x_i (จำนวนเต็มในขอบเขต 0...1,000,000,000) และมีสายพันธุ์ b_i (จำนวนเต็มในขอบเขต 1..8) ไม่มีวัวสองตัวใด ๆ อยู่ที่ตำแหน่งเดียวกัน
 +
 
 +
ชจ. ต้องการจะถ่ายรูปของวัวในช่วงที่ติดกันเพื่อนำไปแสดงในงานประจำปี แต่เราต้องการให้วัวสายพันธุ์ต่าง ๆ กระจายอย่างเสมอภาคในรูปดังกล่าวนี้  ดังนั้น เขาต้องการที่จะรับประกันว่า สำหรับวัวสายพันธุ์ใด ๆ ในรูป วัวในสายพันธุ์ต่าง ๆ นั้น จะต้องปรากฏในรูปเป็นจำนวนเท่า ๆ กัน (ยกตัวอย่างเช่น รูปที่มีวัว 27 ตัวจากสายพันธุ์ 1 และ 27 ตัวจากสายพันธุ์ 3 นั้นใช้ได้;  รูปที่มี 27 ตัวจากสายพันธุ์ 1, 27 ตัวจากสายพันธุ์ 3, และ 27 ตัวจากสายพันธุ์ 4 นั้นก็ใช้ได้; แต่ถ้ามี 9 ตัวจากสายพันธุ์ 1, 10 ตัวจากสายพันธุ์ 3 นั้นใช้ไม่ได้)  นอกจากนี้ ชจ. ยังต้องการอย่างน้อย K (K >= 2) สายพันธุ์ (จากทั้งหมด 8 สายพันธุ์) ปรากฏในรูปดังกล่าว  ช่วย ชจ. ถ่ายรูปที่เสมอภาคนี้ โดยหาขนาดที่ใหญ่ที่สุดของรูปที่สอดคล้องกับเงื่อนไขของ ชจ.  ขนาดของรูปคือผลต่างระหว่างตำแหน่งที่มากที่สุดและน้อยที่สุดของวัวที่อยู่ในรูป
 +
 
 +
ถ้าไม่มีทางถ่ายรูปที่สอดคล้องกับเงื่อนไขของ ชจ. ได้ ให้ตอบ -1
 +
 
 +
'''PROBLEM NAME:''' fairphoto
 +
 
 +
'''INPUT FORMAT:'''
 +
 
 +
* Line 1: N และ K คั่นด้วยช่องว่าง
 +
* Lines 2..N+1: แต่ละบรรทัดระบุข้อมูลของวัวเป็นจำนวนเต็มสองจำนวนคั่นด้วยช่องว่าง คือ x(i) และหมายเลขสายพันธุ์
 +
 
 +
'''SAMPLE INPUT (file fairphoto.in):'''
 +
 
 +
<pre>
 +
9 2
 +
1 1
 +
5 1
 +
6 1
 +
9 1
 +
100 1
 +
2 2
 +
7 2
 +
3 3
 +
8 3
 +
</pre>
 +
 
 +
'''INPUT DETAILS:'''
 +
 
 +
Breed ids: 1 2 3 - 1 1 2 3 1 - ... - 1
 +
Locations: 1 2 3 4 5 6 7 8 9 10 ... 99 100
 +
 
 +
'''OUTPUT FORMAT:'''
 +
 
 +
* Line 1: จำนวนเต็มหนึ่งตัวระบุขนาดที่ใหญ่ที่สุดของรูป ถ้าไม่มีทางถ่ายได้ ให้ตอบ 1
 +
 
 +
'''SAMPLE OUTPUT (file fairphoto.out):'''
 +
 
 +
6
 +
 
 +
'''OUTPUT DETAILS:'''
 +
 
 +
ขอบเขต x = 2 ถึง x = 8 มีวัวสองตัวของพันธุ์ 1, 2, และ 3.  ขอบเขตตั้งแต่ x = 9 ถึง x = 100 มีวัวสองตัวของพันธุ์ 1 แต่นี่ขัดกับเงื่อนไขเพราะว่า K = 2 ดังนั้นเราจึงต้องมีวัวสองสายพันธุ์ที่แตกต่างกัน
 +
 
 +
=== Problem 2: Cow Optics [Brian Dean, 2014] (Gold) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=437]
 +
 
 +
วัวของชาวนาจอห์นต้องการจะจัดปาร์ตีเต้นรำในโรงวัวของพวกเขาพร้อมด้วยการแสดงแสงสีเสียงระบบเลเซอร์  โชคไม่ดีเลยที่เลเซอร์ที่ใช้งานได้นั้นอยู่ไกลจากโรงวัวและมีน้ำหนักมากกว่าที่จะเคลื่อนย้ายมาได้ ดังนั้นพวกเขาจึงวางแผนว่าจะเปลี่ยนทิศทางของเลเซอร์มายังโรงวัวโดยใช้ลำดับของกระจก
 +
 
 +
แผนผังของฟาร์มมีเลเซอร์อยู่ที่ตำแหน่ง (0,0) ชี้ไปด้านบน (ในทิศทางที่มีค่าแกน y เป็นบวก) และโรงวัวอยู่ที่ตำแหน่ง (Bx, By)  เราสามารถพิจารณาให้เลเซอร์และโรงวัวเป็นจุดในระนาบสองมิติ  มีวัวจำนวน N ตัว (1 <= N <= 100,000) ถือกระจกที่ทำมุม 45 องศากับแกนกระจายอยู่ทั่วฟาร์ม  ตัวอย่างเช่น กระจกที่วางตัวเช่น \ จะสะท้อนลำแสงที่วิ่งจากด้านล่างไปยังทิศทางซ้าย  เราก็สามารถพิจารณาว่ากระจกนี้เป็นจุดในระนายสองมิติได้เช่นเดียวกัน
 +
 
 +
ก่อนที่จะกดปุ่มแดงใหญ่เพื่อที่จะเริ่มเปิดเลเซอร์ เบสซี่สังเกตเห็นปัญหาใหญ่ในแผนการดังกล่าว  ด้วยตำแหน่งของวัวในปัจจุบันเลเซอร์จะไม่สามารถสะท้อนไปยังโรงวัวได้  ดังนั้นเธอจึงตั้งใจที่จะวิ่งไปยังสนามและใช้กระจกอีกอันหนึ่ง (เช่นเดียวกัน วางทำมุม 45 องศา) เพื่อที่จะสะท้อนเลเซอร์ไปยังโรงวัวให้ได้  ให้คุณนับตำแหน่งทั้งหมดในสนามที่เบสซี่จะสามารถไปยืนอยู่เพื่อทำให้เป้าหมายนี้สำเร็จได้
 +
 
 +
พิกัดทั้งหมดเป็นจำนวนเต็มระหว่าง -1,000,000,000 และ 1,000,000,000  รับประกันว่ากระจกทั้งหมดจะวางอยู่ในขอบเขตนี้เช่นเดียวกัน  วัวที่วางแผนกำหนดว่างเลเซอร์จะต้องไม่กลับมายังตำแหน่ง (0,0) หลังจากที่ถูกปล่อยออกไปแล้ว (และด้วยตำแหน่งของกระจกเมื่อเริ่มต้น เรารับประกันว่าเหตุการณ์นี้จะไม่เกิดขึ้น)  ไม่มีวัวสองตัวอยู่ที่ตำแหน่งเดียวกัน  และเบสซี่จะไม่สามารถไปอยู่ตำแหน่งเดียวกับวัวที่ยืนอยู่แล้วได้
 +
 
 +
'''PROBLEM NAME:''' optics
 +
 
 +
'''INPUT FORMAT:'''
 +
 
 +
* Line 1: จำนวนเต็ม N, Bx, และ By.
 +
* Lines 2..N + 1: บรรทัดที่ i+1 ระบุข้อมูลของกระจกอันที่ i ด้วยค่าสามค่าคือตำแหน่ง (x,y) และทิศทาง (มีค่าเป็น '\' or '/').
 +
 
 +
'''SAMPLE INPUT (file optics.in):'''
 +
 
 +
4 1 2
 +
-2 1 \ 
 +
2 1 /
 +
2 2 \
 +
-2 2 /
 +
 
 +
'''OUTPUT FORMAT:''' จำนวนเต็มหนึ่งจำนวนแทนตำแหน่งที่เบสซี่สามารถไปอยู่ได้เพื่อจะเปลี่ยนทิศทางของเลเซอร์เพื่อให้วิ่งไปยังโรงวัว
 +
 
 +
'''SAMPLE OUTPUT (file optics.out):'''
 +
 
 +
2
 +
 
 +
'''OUTPUT DETAILS:'''
 +
 
 +
กระจกที่ตำแหน่ง (0,1) หรือ (0,2) ไม่ว่าจะวางในทิศทางไหนก็ทำให้เลเซอร์วิ่งไปยังโรงวัวได้
 +
 
 +
=== Problem 3: Code Breaking [Jacob Steinhardt, 2014] (Gold) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=438]
 +
 
 +
เหล่าวัวนั้นชอบเกิดปัญหาเวลาที่ขึ้นไปขับรกแทรคเตอร์ของชาวนาจอห์น เขาจึงได้ซ่อนกุญแจรถไว้ในเซฟอันใหม่ในห้องทำงาน  ด้วยความมุ่งมั่น เหล่าวัวตั้งใจที่จะพยายามที่จะเจาะเซฟอันใหม่นี้ให้ได้
 +
 
 +
ตู้เซฟนี้ถูกป้องกันด้วยระบบรหัสผ่านที่ซับซ้อน  ระบบป้อนรหัสผ่านนั้นเรียงตัวเป็นต้นไม้ที่มีราก (rooted tree) ที่มีโหนด N โหนด (1 <= N <= 20,000) โดยแต่ละโหนดจะต้องการตัวเลขระหว่าง 0 ถึง 9  โหนดมีหมายเลขระหว่าง 0..N-1
 +
 
 +
สิ่งที่วัวทราบก็คือว่ามีบางลำดับความยาว 5 จะไม่ปรากฏขึ้นบนบางส่วนของเส้นทางจากบางโหนดไปยังรากของต้นไม้
 +
 
 +
พิจารณาตัวอย่างต่อไปนี้  สมมติว่าต้นไม้เป็นดังด้านล่าง (รากอยู่ที่ A)
 +
 
 +
A <- B <- C <- D <- E
 +
                ^
 +
                |
 +
                F
 +
 
 +
ถ้าวัวทราบว่าลำดับ 01234 จะไม่เกิดขึ้นเมื่อเริ่มที่ F และลำดับ 91234 จะไม่เกิดขึ้น เมื่อเริ่มที่ E  ข้อมูลดังกล่าวนี้ช่วยให้สามารถตัดรหัสผ่านทิ้งได้ 19 รหัส ซึ่งอยู่ในรูป
 +
 
 +
4 <- 3 <- 2 <- 1 <- *
 +
                ^
 +
                |
 +
                0
 +
 
 +
หรือ
 +
 
 +
4 <- 3 <- 2 <- 1 <- 9
 +
                ^
 +
                |
 +
                *
 +
 
 +
ซึ่งรวมแล้วได้ 19 แบบ เพราะว่าเรานับว่า
 +
 
 +
4 <- 3 <- 2 <- 1 <- 9
 +
                ^
 +
                |
 +
                0
 +
 
 +
ปรากฏขึ้นสองครั้ง
 +
 
 +
ให้ลำดับความยาว 5 จำนวน M (1 <= M <= 50,000) ลำดับ พร้อมด้วยจุดเริ่มต้นในต้นไม้  ช่วยวัวคำนวณหาจำนวนรหัสผ่านที่สามารถตัดทิ้งได้  คุณจะต้องคำนวณคำตอบของคุณ modulo 1234567
 +
 
 +
'''PROBLEM NAME:''' code
 +
 
 +
'''INPUT FORMAT:'''
 +
 
 +
* Line 1: จำนวนเต็มสองจำนวน N และ M คั่นด้วยช่องว่าง
 +
* Lines 2..N: บรรทัดที่ i+1 มีจำนวนเต็ม p(i) แทนหมายเลขของโหนดพ่อแม่ของ i ในต้นไม้ (0 <= p(i) < i).
 +
* Lines N+1..N+M: บรรทัดที่ N+i ระบุลำดับที่ i ที่ทราบว่าจะไม่อยู่ในรหัส  ในบรรทัดที่จะระบุ v(i) และ s(i) คั่นด้วยช่องว่าง โดยที่ v(i) คือโหนดเริ่มต้นของลำดับ และ s(i) คือสตริงประกอบด้วยตัวเลข 5 หลักที่ทราบว่าจะไม่ปรากฏในรหัส โดยจะเริ่มต้นที่ v(i) และไล่ไปตามโหนดต่างขึ้นไปยังรากของต้นไม้  รับประกันว่ารากของต้นไม้จะอยู่ห่างอย่างน้อย 4 ขั้นจาก v(i)
 +
 
 +
'''SAMPLE INPUT (file code.in):'''
 +
 
 +
6 2
 +
0
 +
1
 +
2
 +
3
 +
3
 +
4 01234
 +
5 91234
 +
 
 +
'''OUTPUT FORMAT:'''
 +
 
 +
* Line 1: A single integer giving the number of ruled-out configurations, modulo 1234567.
 +
 
 +
'''SAMPLE OUTPUT (file code.out):'''
 +
 
 +
19
 +
 
 +
=== Problem 4: Fair Photography [Brian Dean, 2014] (Silver) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=433]
 +
 
 +
วัวจำนวน N ตัว (1 <= N <= 100,000) ของ ชจ. ยืนอยู่ที่ตำแหน่งต่าง ๆ บนรั้วยาวหนึ่งมิติ วัวตัวที่ i ยืนอยู่ที่ตำแหน่ง x_i (จำนวนเต็มในขอบเขต 0...1,000,000,000) โดยวัวอาจจะเป็นวัวสีขาวล้วน หรืออาจจะเป็นวัวลายจุด ไม่มีวัวสองตัวใด ๆ อยู่ที่ตำแหน่งเดียวกันและมีวัวสีขาวอย่างน้อยหนึ่งตัว
 +
 
 +
ชจ. ต้องการจะถ่ายรูปของวัวในช่วงที่ติดกันเพื่อนำไปแสดงในงานประจำปี  เพื่อความแฟร์เขาต้องการรับประกันว่าจำนวนวัวสีขาวกับวัวลายจุดจะเท่ากันในรูปของเขา  ชจ. ต้องการหาว่าจะสามารถถ่ายรูปที่เสมอภาคนี้ โดยมีขนาดที่ใหญ่ที่สุดได้เป็นเท่าใด โดยขนาดของรูปคือผลต่างระหว่างตำแหน่งที่มากที่สุดและน้อยที่สุดของวัวที่อยู่ในรูป
 +
 
 +
เพื่อทำให้โอกาสการถ่ายรูปได้เพิ่มมากขึ้น ชจ. มีถังสีอยู่ ทำให้เขาสามารถระบายสีจุดลงบนสับเซตใด ๆ ของวัวสีขาวได้ เพื่อทำให้วัวเหล่านั้นกลายเป็นวัวลายจุดได้  ให้ขนาดที่ใหญ่ที่สุดของรูปที่แฟร์ที่ ชจ. สามารถถ่ายได้ ในกรณีที่ ชจ. สามารถเลือกที่จะระบายจุดลงบนวัวสีขาวบางตัว (และแน่นอน เขาจะไม่ระบายเลยก็ได้ ถ้านั่นเป็นทางเลือกที่ดีกว่า)
 +
 
 +
=== Problem 5: Dueling GPSs [Brian Dean, 2014] (Silver) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=434]
 +
 
 +
ชาวนาจอห์นเพิ่งจะซื้อรถยนต์ออนไลน์ ด้วยความรีบร้อน เข้าพลาดไปกดปุ่ม "Submit" สองครั้งตอนที่เลือกคุณสมบัติพิเศษของรถ ทำให้รถของเขามี GPS สองชุด!  แยกกว่านั้นคือชุด GPS ชอบแนะนำทางที่ขัดแย้งกันอีก
 +
 
 +
แผนที่ของบริเวณที่ ชจ. อยู่นั้นประกอบไปด้วยแยก N แยก (2 <= N <= 10,000) และถนนแบบที่มีทิศทางเดียว M เส้น (1 <= M <= 50,000)  ถนนที่ i เชื่อมแยก A_i (1 <= A_i <= N) และ B_i (1 <= B_i <= N)  ถนนหลายเส้นอาจจะเชื่อมระหว่างคู่ของแยกได้  และถนนที่วิ่งได้สองทางนั้นจะแทนเป็นถนนทางเดียวสองเส้นที่วิ่งกลับทิศกันแทน  บ้านของ ชจ. อยู่ที่แยกที่ 1 และฟาร์มของเขาอยู่ที่แยกที่ N สามารถไปจากบ้านถึงฟาร์มได้โดยเดินทางผ่านลำดับของถนนที่มีทิศทางเดียวเหล่านี้
 +
 
 +
เครื่อง GPS นั้น ใช้แผนที่เดียวกับที่อธิบายมาข้างต้น อย่างไรก็ตาม มันมีวิธีในการคิดเวลาการเดินทางบนถนนแตกต่างกัน กล่าวคือ ถนน i ใช้เวลา P_i ในการเดินทางบน GPS เครื่องแรก  และ Q_i ในเครื่อง GPS เครื่องที่สอง  (เวลาการเดินทางเป็นจำนวนเต็มในขอบเขต 1..100,000)
 +
 
 +
ชจ. ต้องการเดินทางจากบ้านไปที่ฟาร์ม  อย่างไรก็ตาม เครื่อง GPS จะร้องเสียงดังเมื่อ FJ เดินทางผ่านถนน (นั่นคือเดินทางจากแยก X ไปยังแยก Y) ที่เครื่อง GPS นั้นไม่เชื่อว่าเป็นส่วนของเส้นทางที่สั้นที่สุดจาก X ไปยังฟาร์ม (เป็นไปได้ที่เครื่อง GPS ทั้งสองจะร้องพร้อม ๆ กันถ้า ชจ.เลือกถนนที่ทั้งสองเครื่องไม่ชอบ)
 +
 
 +
ช่วยหาจำนวนครั้งที่เครื่อง GPS จะร้องที่น้อยที่สุดถ้า ชจ. เลือกเส้นทางที่ดีที่สุด  ถ้าเครื่อง GPS ทั้งสองเครื่องร้องพร้อมกัน เราจะนับจำนวนครั้งการร้องเพิ่ม +2
 +
 
 +
=== Problem 6: Odometer [Brian Dean, 2014] (Silver) ===
 +
 
 +
Source: [http://www.usaco.org/index.php?page=viewproblem2&cpid=435]
 +
 
 +
วัวของชาวนาจอห์นกำลังจะไปโร้ดทริป    เครื่องวัดระยะในรถของเขาจะแสดงระยะทางเป็นจำนวนเต็ม โดยเริ่มที่ X (100 <= X <= 10^18) และสิ้นสุดที่ Y (X <= Y <= 10^18)  เมื่อสิ้นสุดการเดินทาง  เมื่อใดที่เครื่องวัดระยะแสดงตัวเลขที่น่าสนใจ เหล่าวัวจะร้อง "มู"  จำนวนเต็มจะ "น่าสนใจ" ถ้าเมื่อคุณพิจารณาหลักเลขในจำนวนเต็มนนั้นโดยที่ไม่สนใจศูนย์ที่นำหน้าแล้ว อย่างน้อยครึ่งหนึ่งของตัวเลขจะต้องเหมือนกัน  ยกตัวอย่างเช่น จำนวน 3223 และ 110 ต่างเป็นจำนวนเต็มที่น่าสนใจ  แต่ 97791 และ 123 นั้นไม่
 +
 
 +
ช่วย ชจ. นับว่าเหล่าวัวร้องมูทั้งหมดกี่ครั้งระหว่างทริป

รุ่นแก้ไขปัจจุบันเมื่อ 09:14, 17 เมษายน 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)

Source: [3]

ชาวนาจอห์นอยู่ที่ตลาดเพื่อจะซื้อของไปยังฟาร์ม เขามีเงินในกระเป๋า K เหรียญ (1 <= K <= 16) แต่ละเหรียญมีมูลค่าในช่วง 1..100,000,000 ชจ.ต้องการจะซื้อของเป็นลำดับจำนวน N ครั้ง (1 <= N <= 100,000) โดยที่การซื้อครั้งที่ i จะต้องใช้เงิน c(u) หน่วย (1 <= c(i) <= 10,000) ระหว่างที่ชจ.ซื้อของเขาสามารถหยุดและจ่ายเงินด้วยเหรียญหนึ่งเหรียญได้ เงินที่จ่ายนั้นจะจ่ายสำหรับของที่เขาซื้อทั้งหมดนับตั้งแต่การจ่ายครั้งสุดท้าย (แน่นอนเหรียญดังกล่าวนั้นจะต้องมีค่ามากพอที่จะจ่ายเงินสำหรับการซื้อนั้นได้) โชคไม่ดีที่คนขายที่ตลาดไม่มีเงินทอนเลย ดังนั้นเมื่อชจ.จ่ายเหรียญที่มีมูลค่ามากกว่าเงินที่เขาต้องจ่าย เขาจะไม่ได้เงินทองกลับมาแต่อย่างใด

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

USACO 2013 December Contest

Problem 1: Vacation Planning [Kalki Seksaria and Richard Peng, 2013] (GOLD)

Source: [4]

บริษัทการบินโบวิเนียควบคุมเส้นทางการบินที่เชื่อมต่อ N ฟาร์มที่มีแม่วัวอาศัยอยู่ (1 <= N <= 20,000) ในจำนวนนี้มีฟาร์มทั้งสิ้น K ฟาร์มที่กำหนดให้เป็นสถานีเชื่อมต่อการบิน (hub) (1 <= K <= 200, K <= N)

ในปัจจุบันบริษัทการบินโบวิเนียได้ให้บริการเส้นทางการบินเที่ยวเดียว (one-way flights) ทั้งสิ้น M เส้นทาง (1 <= M <= 20,000) โดยเที่ยวบินที่ i จะบินจากฟาร์ม u_i ไปยังฟาร์ม v_i และมีค่าใช้จ่าย d_i บาท (1 <= d_i <= 10,000) สำหรับเที่ยวบินแต่ละเที่ยวนั้นจะต้องมีอย่างน้อยหนึ่งปลายทาง u_i หรือ v_i ที่เป็นสถานีเชื่อมต่อการบิน และจะมีอย่างมากเพียงหนึ่งเที่ยวบินเท่านั้นที่เชื่อมระหว่างสองฟาร์มสำหรับทิศทางหนึ่งๆ และไม่มีสองเที่ยวบินที่มีฟาร์มต้นทางและปลายทางเดียวกัน

เบซซี่เป็นดูแลการขายตั๋วของบริษัทการบินโบวิเนีย แต่ทว่าระหว่างที่เธอกำลังเคี้ยวหมากฝรั่งอย่างชิลชิลอยู่หลายชั่วโมงนั้น ได้เกิดมีการขอซื้อตั๋วแบบเที่ยวเดียวเกิดขึ้นพร้อมกันจำนวน Q รายการ (1 <= Q <= 50,000) เนื่องจากวันหยุดยาวของเหล่าแม่วัวกำลังจะมาถึง โดยรายการขอซื้อตั๋วที่ i จะระบุความต้องการเดินทางไปจากฟาร์ม a_i ไปยังฟาร์ม b_i

เบซซี่รู้สึกโดนงานทับใส่จนจัดการไม่ทัน เราจึงขอร้องให้คุณช่วยเบซซี่ในการประมวลผลว่าแต่ละรายการขอซื้อตั๋วสามารถทำได้หรือไม่ และค่าใช้จ่ายน้อยที่สุดที่ใช้ในการซื้อตั๋วถ้าสามารถตอบสนองรายการที่ต้องการได้

เพื่อลดขนาดของผลลัพธ์ ให้คุณแสดงเพียงจำนวนรายการขอซื้อที่มีเที่ยวบินรองรับ และค่าใช้จ่ายรวมน้อยที่สุดที่ใช้ในการซื้อตํ่วเหล่านั้น

หมายเหตุตัวเลขจำนวนนี้อาจไม่สามารถเก็บได้ด้วยจำนวนเต็มขนาด 32 บิต 1

Problem 2: Optimal Milking [Brian Dean, 2013] (GOLD)

Source: [5]

ชาวนาจอห์นได้ซื้อโรงนาใหม่ที่ประกอบไปด้วยเครื่องสกัดนมวัวทั้งหมด N เครื่อง (1 <= N <= 40,000) เพื่อความสะดวกให้ระบุด้วยหมายเลข 1 ถึง N และเรียงตัวกันเป็นแถวหนึ่งแถว

เครื่องสกัดนมเครื่องที่ i สามารถสกัดนมได้ M(i) หน่วยต่อวัน (1 <= M(i) <= 100,000) แต่ทว่าโชคร้ายเนื่องจากขณะติดตั้งเครื่องรีดนมแต่ละเครื่องถูกวางไว้ติดกันเกินไปจนทำให้ ถ้าเครื่องที่ i ใช้งานแล้วเครื่องสองเครื่องข้างๆ ที่ติดกันจะไม่สามารถใช้งานในวันเดียวกันได้ (เครื่องที่อยู่ที่ขอบจะมีเครื่องข้างๆ เพียงหนึ่งเครื่องเท่านั้น) จอห์นสามารถเลือกกลุ่มที่แตกต่างกันของเครื่องสกัดนมเพื่อให้ทำงานในวันที่แตกต่างกันได้อย่างอิสระ

จอห์นสนใจในการคำนวณหาปริมาณนมที่มากที่สุดที่เขาสามารถสกัดได้ในเวลา D วัน (1 <= D <= 50,000) ยามเริ่มต้นของแต่ละวันจอห์นจะมีเวลามากเพียงพอที่จะซ่อมบำรุงเครื่องสกัดนมเครื่องหนึ่ง เครื่องที่ i เพื่อให้ปริมาณนมที่สกัดได้เปลี่ยนจากเดิมไปเป็น M(i) หน่วยตั้งแต่วันนั้นเป็นต้นไป เมื่อกำหนดรายการซ่อมบำรุงที่ทำได้ในแต่ละวันมาให้ หน้าที่ของคุณคือให้ช่วยจอห์นหาว่าปริมาณนมที่เขาสามารถสกัดได้ในเวลา D วันเป็นเท่าไร (หมายเหตุตัวเลขอาจไม่สามารถเก็บด้วยจำนวนเต็มขนาด 32 บิตได้)

Problem 3: The Bessie Shuffle[Mark Gordon, 2013] (GOLD)

Source: [6]

เบซซี่กำลังซ้อมเทคนิคไพ่อยู่ ขณะนี้เธอได้ชำนาญเทคนิคสลับไพ่แบบเบซซี่แล้ว การสลับไพ่ทำบนสำรับที่มีไพ่จำนวน M ใบ (2 <= M <= 100,000) ทำโดยการสลับไพ่ ไพ่ทุกใบจากตำแหน่งเดิมที่ i จากด้านบนจะกลายเป็นไพ่ในตำแหน่งที่ P[i] จากด้านบนแทน

ตอนนี้เบซซี่กำลังทดลองเทคนิคนี้พ่บนสำรับไพ่ที่มีขนาดใหญ่ โดยเธอมีสำรับไพ่ที่มีไพ่ทั้งหมด N ใบ (M <= N <= 1,000,000,000) เพื่อความสะดวกขอตั้งชื่อเป็น 1 ถึง N เธอใช้เทคนิคสลับไพ่โดยการหยิบไพ่ M ใบแรกออกมาและโชว์เทคนิคสลับไพ่แบบเบซซี่ จากนั้นวางไพ่ทั้ง M ใบไว้บนสำรับใหญ่ดังเดิม จากนั้นเธอจะหยิบไพ่ใบบนออกจากสำรับและคว่ำหน้าลงเพื่อสร้างสำรับใหม่ เธอจะทำเช่นนี้ไปเรื่อยๆ คือเธอจะแสดงกลและหยิบไพ่ใบบนสุดคว่ำหน้าลงเรื่อยๆเพื่อสร้างสำรับใหม่ จนครบทุกใบหากทำได้ แต่หากไพ่ที่เหลือมีน้อยกว่า M ใบเธอจะไม่ใช้เทคนิคสลับไพ่แต่เธอก็ยังจะคว่ำไพ่ใบบนุสุดลงไปเหนือใบอื่นต่อไปจนไม่มีไพ่เหลืออยู่

เบซซี่รู้ตำแหน่งเริ่มต้นของไพ่ทั้งหมดตามลำดับคือ 1 จะอยู่บนสุด, ถัดมาเป็น 2, และ N จะอยู่ล่างสุด เมื่อกำหนดรายละเอียดของเทคนิคการสลับไพ่แบบเบซซี่ หน้าที่ของคุณคือช่วยเบซซี่หาว่าไพ่หมายเลขใดจะอยู่ในตำแหน่งที่ระบุ Q ตำแหน่งที่แตกต่างกัน (1 <= Q <= N, Q <= 5,000)

หมายเหตุ: ให้พิจารณาตัวอย่างในโจทย์เพื่อประกอบความเข้าใจ

USACO 2014 US Open

Problem 1: Fair Photography [Brian Dean, 2014] (Gold)

Source: [7]

วัวจำนวน N ตัว (1 <= N <= 100,000) ของ ชจ. ยืนอยู่ที่ตำแหน่งต่าง ๆ บนรั้วยาวหนึ่งมิติ วัวตัวที่ i ยืนอยู่ที่ตำแหน่ง x_i (จำนวนเต็มในขอบเขต 0...1,000,000,000) และมีสายพันธุ์ b_i (จำนวนเต็มในขอบเขต 1..8) ไม่มีวัวสองตัวใด ๆ อยู่ที่ตำแหน่งเดียวกัน

ชจ. ต้องการจะถ่ายรูปของวัวในช่วงที่ติดกันเพื่อนำไปแสดงในงานประจำปี แต่เราต้องการให้วัวสายพันธุ์ต่าง ๆ กระจายอย่างเสมอภาคในรูปดังกล่าวนี้ ดังนั้น เขาต้องการที่จะรับประกันว่า สำหรับวัวสายพันธุ์ใด ๆ ในรูป วัวในสายพันธุ์ต่าง ๆ นั้น จะต้องปรากฏในรูปเป็นจำนวนเท่า ๆ กัน (ยกตัวอย่างเช่น รูปที่มีวัว 27 ตัวจากสายพันธุ์ 1 และ 27 ตัวจากสายพันธุ์ 3 นั้นใช้ได้; รูปที่มี 27 ตัวจากสายพันธุ์ 1, 27 ตัวจากสายพันธุ์ 3, และ 27 ตัวจากสายพันธุ์ 4 นั้นก็ใช้ได้; แต่ถ้ามี 9 ตัวจากสายพันธุ์ 1, 10 ตัวจากสายพันธุ์ 3 นั้นใช้ไม่ได้) นอกจากนี้ ชจ. ยังต้องการอย่างน้อย K (K >= 2) สายพันธุ์ (จากทั้งหมด 8 สายพันธุ์) ปรากฏในรูปดังกล่าว ช่วย ชจ. ถ่ายรูปที่เสมอภาคนี้ โดยหาขนาดที่ใหญ่ที่สุดของรูปที่สอดคล้องกับเงื่อนไขของ ชจ. ขนาดของรูปคือผลต่างระหว่างตำแหน่งที่มากที่สุดและน้อยที่สุดของวัวที่อยู่ในรูป

ถ้าไม่มีทางถ่ายรูปที่สอดคล้องกับเงื่อนไขของ ชจ. ได้ ให้ตอบ -1

PROBLEM NAME: fairphoto

INPUT FORMAT:

  • Line 1: N และ K คั่นด้วยช่องว่าง
  • Lines 2..N+1: แต่ละบรรทัดระบุข้อมูลของวัวเป็นจำนวนเต็มสองจำนวนคั่นด้วยช่องว่าง คือ x(i) และหมายเลขสายพันธุ์

SAMPLE INPUT (file fairphoto.in):

9 2 
1 1 
5 1 
6 1 
9 1 
100 1 
2 2 
7 2 
3 3 
8 3 

INPUT DETAILS:

Breed ids: 1 2 3 - 1 1 2 3 1 - ... - 1 
Locations: 1 2 3 4 5 6 7 8 9 10 ... 99 100 

OUTPUT FORMAT:

  • Line 1: จำนวนเต็มหนึ่งตัวระบุขนาดที่ใหญ่ที่สุดของรูป ถ้าไม่มีทางถ่ายได้ ให้ตอบ 1

SAMPLE OUTPUT (file fairphoto.out):

6

OUTPUT DETAILS:

ขอบเขต x = 2 ถึง x = 8 มีวัวสองตัวของพันธุ์ 1, 2, และ 3. ขอบเขตตั้งแต่ x = 9 ถึง x = 100 มีวัวสองตัวของพันธุ์ 1 แต่นี่ขัดกับเงื่อนไขเพราะว่า K = 2 ดังนั้นเราจึงต้องมีวัวสองสายพันธุ์ที่แตกต่างกัน

Problem 2: Cow Optics [Brian Dean, 2014] (Gold)

Source: [8]

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

แผนผังของฟาร์มมีเลเซอร์อยู่ที่ตำแหน่ง (0,0) ชี้ไปด้านบน (ในทิศทางที่มีค่าแกน y เป็นบวก) และโรงวัวอยู่ที่ตำแหน่ง (Bx, By) เราสามารถพิจารณาให้เลเซอร์และโรงวัวเป็นจุดในระนาบสองมิติ มีวัวจำนวน N ตัว (1 <= N <= 100,000) ถือกระจกที่ทำมุม 45 องศากับแกนกระจายอยู่ทั่วฟาร์ม ตัวอย่างเช่น กระจกที่วางตัวเช่น \ จะสะท้อนลำแสงที่วิ่งจากด้านล่างไปยังทิศทางซ้าย เราก็สามารถพิจารณาว่ากระจกนี้เป็นจุดในระนายสองมิติได้เช่นเดียวกัน

ก่อนที่จะกดปุ่มแดงใหญ่เพื่อที่จะเริ่มเปิดเลเซอร์ เบสซี่สังเกตเห็นปัญหาใหญ่ในแผนการดังกล่าว ด้วยตำแหน่งของวัวในปัจจุบันเลเซอร์จะไม่สามารถสะท้อนไปยังโรงวัวได้ ดังนั้นเธอจึงตั้งใจที่จะวิ่งไปยังสนามและใช้กระจกอีกอันหนึ่ง (เช่นเดียวกัน วางทำมุม 45 องศา) เพื่อที่จะสะท้อนเลเซอร์ไปยังโรงวัวให้ได้ ให้คุณนับตำแหน่งทั้งหมดในสนามที่เบสซี่จะสามารถไปยืนอยู่เพื่อทำให้เป้าหมายนี้สำเร็จได้

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

PROBLEM NAME: optics

INPUT FORMAT:

  • Line 1: จำนวนเต็ม N, Bx, และ By.
  • Lines 2..N + 1: บรรทัดที่ i+1 ระบุข้อมูลของกระจกอันที่ i ด้วยค่าสามค่าคือตำแหน่ง (x,y) และทิศทาง (มีค่าเป็น '\' or '/').

SAMPLE INPUT (file optics.in):

4 1 2 
-2 1 \  
2 1 / 
2 2 \ 
-2 2 / 

OUTPUT FORMAT: จำนวนเต็มหนึ่งจำนวนแทนตำแหน่งที่เบสซี่สามารถไปอยู่ได้เพื่อจะเปลี่ยนทิศทางของเลเซอร์เพื่อให้วิ่งไปยังโรงวัว

SAMPLE OUTPUT (file optics.out):

2 

OUTPUT DETAILS:

กระจกที่ตำแหน่ง (0,1) หรือ (0,2) ไม่ว่าจะวางในทิศทางไหนก็ทำให้เลเซอร์วิ่งไปยังโรงวัวได้

Problem 3: Code Breaking [Jacob Steinhardt, 2014] (Gold)

Source: [9]

เหล่าวัวนั้นชอบเกิดปัญหาเวลาที่ขึ้นไปขับรกแทรคเตอร์ของชาวนาจอห์น เขาจึงได้ซ่อนกุญแจรถไว้ในเซฟอันใหม่ในห้องทำงาน ด้วยความมุ่งมั่น เหล่าวัวตั้งใจที่จะพยายามที่จะเจาะเซฟอันใหม่นี้ให้ได้

ตู้เซฟนี้ถูกป้องกันด้วยระบบรหัสผ่านที่ซับซ้อน ระบบป้อนรหัสผ่านนั้นเรียงตัวเป็นต้นไม้ที่มีราก (rooted tree) ที่มีโหนด N โหนด (1 <= N <= 20,000) โดยแต่ละโหนดจะต้องการตัวเลขระหว่าง 0 ถึง 9 โหนดมีหมายเลขระหว่าง 0..N-1

สิ่งที่วัวทราบก็คือว่ามีบางลำดับความยาว 5 จะไม่ปรากฏขึ้นบนบางส่วนของเส้นทางจากบางโหนดไปยังรากของต้นไม้

พิจารณาตัวอย่างต่อไปนี้ สมมติว่าต้นไม้เป็นดังด้านล่าง (รากอยู่ที่ A)

A <- B <- C <- D <- E 
               ^
               |
               F

ถ้าวัวทราบว่าลำดับ 01234 จะไม่เกิดขึ้นเมื่อเริ่มที่ F และลำดับ 91234 จะไม่เกิดขึ้น เมื่อเริ่มที่ E ข้อมูลดังกล่าวนี้ช่วยให้สามารถตัดรหัสผ่านทิ้งได้ 19 รหัส ซึ่งอยู่ในรูป

4 <- 3 <- 2 <- 1 <- *
               ^
               |
               0

หรือ

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               *

ซึ่งรวมแล้วได้ 19 แบบ เพราะว่าเรานับว่า

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               0

ปรากฏขึ้นสองครั้ง

ให้ลำดับความยาว 5 จำนวน M (1 <= M <= 50,000) ลำดับ พร้อมด้วยจุดเริ่มต้นในต้นไม้ ช่วยวัวคำนวณหาจำนวนรหัสผ่านที่สามารถตัดทิ้งได้ คุณจะต้องคำนวณคำตอบของคุณ modulo 1234567

PROBLEM NAME: code

INPUT FORMAT:

  • Line 1: จำนวนเต็มสองจำนวน N และ M คั่นด้วยช่องว่าง
  • Lines 2..N: บรรทัดที่ i+1 มีจำนวนเต็ม p(i) แทนหมายเลขของโหนดพ่อแม่ของ i ในต้นไม้ (0 <= p(i) < i).
  • Lines N+1..N+M: บรรทัดที่ N+i ระบุลำดับที่ i ที่ทราบว่าจะไม่อยู่ในรหัส ในบรรทัดที่จะระบุ v(i) และ s(i) คั่นด้วยช่องว่าง โดยที่ v(i) คือโหนดเริ่มต้นของลำดับ และ s(i) คือสตริงประกอบด้วยตัวเลข 5 หลักที่ทราบว่าจะไม่ปรากฏในรหัส โดยจะเริ่มต้นที่ v(i) และไล่ไปตามโหนดต่างขึ้นไปยังรากของต้นไม้ รับประกันว่ารากของต้นไม้จะอยู่ห่างอย่างน้อย 4 ขั้นจาก v(i)

SAMPLE INPUT (file code.in):

6 2 
0 
1 
2 
3 
3 
4 01234 
5 91234 

OUTPUT FORMAT:

  • Line 1: A single integer giving the number of ruled-out configurations, modulo 1234567.

SAMPLE OUTPUT (file code.out):

19

Problem 4: Fair Photography [Brian Dean, 2014] (Silver)

Source: [10]

วัวจำนวน N ตัว (1 <= N <= 100,000) ของ ชจ. ยืนอยู่ที่ตำแหน่งต่าง ๆ บนรั้วยาวหนึ่งมิติ วัวตัวที่ i ยืนอยู่ที่ตำแหน่ง x_i (จำนวนเต็มในขอบเขต 0...1,000,000,000) โดยวัวอาจจะเป็นวัวสีขาวล้วน หรืออาจจะเป็นวัวลายจุด ไม่มีวัวสองตัวใด ๆ อยู่ที่ตำแหน่งเดียวกันและมีวัวสีขาวอย่างน้อยหนึ่งตัว

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

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

Problem 5: Dueling GPSs [Brian Dean, 2014] (Silver)

Source: [11]

ชาวนาจอห์นเพิ่งจะซื้อรถยนต์ออนไลน์ ด้วยความรีบร้อน เข้าพลาดไปกดปุ่ม "Submit" สองครั้งตอนที่เลือกคุณสมบัติพิเศษของรถ ทำให้รถของเขามี GPS สองชุด! แยกกว่านั้นคือชุด GPS ชอบแนะนำทางที่ขัดแย้งกันอีก

แผนที่ของบริเวณที่ ชจ. อยู่นั้นประกอบไปด้วยแยก N แยก (2 <= N <= 10,000) และถนนแบบที่มีทิศทางเดียว M เส้น (1 <= M <= 50,000) ถนนที่ i เชื่อมแยก A_i (1 <= A_i <= N) และ B_i (1 <= B_i <= N) ถนนหลายเส้นอาจจะเชื่อมระหว่างคู่ของแยกได้ และถนนที่วิ่งได้สองทางนั้นจะแทนเป็นถนนทางเดียวสองเส้นที่วิ่งกลับทิศกันแทน บ้านของ ชจ. อยู่ที่แยกที่ 1 และฟาร์มของเขาอยู่ที่แยกที่ N สามารถไปจากบ้านถึงฟาร์มได้โดยเดินทางผ่านลำดับของถนนที่มีทิศทางเดียวเหล่านี้

เครื่อง GPS นั้น ใช้แผนที่เดียวกับที่อธิบายมาข้างต้น อย่างไรก็ตาม มันมีวิธีในการคิดเวลาการเดินทางบนถนนแตกต่างกัน กล่าวคือ ถนน i ใช้เวลา P_i ในการเดินทางบน GPS เครื่องแรก และ Q_i ในเครื่อง GPS เครื่องที่สอง (เวลาการเดินทางเป็นจำนวนเต็มในขอบเขต 1..100,000)

ชจ. ต้องการเดินทางจากบ้านไปที่ฟาร์ม อย่างไรก็ตาม เครื่อง GPS จะร้องเสียงดังเมื่อ FJ เดินทางผ่านถนน (นั่นคือเดินทางจากแยก X ไปยังแยก Y) ที่เครื่อง GPS นั้นไม่เชื่อว่าเป็นส่วนของเส้นทางที่สั้นที่สุดจาก X ไปยังฟาร์ม (เป็นไปได้ที่เครื่อง GPS ทั้งสองจะร้องพร้อม ๆ กันถ้า ชจ.เลือกถนนที่ทั้งสองเครื่องไม่ชอบ)

ช่วยหาจำนวนครั้งที่เครื่อง GPS จะร้องที่น้อยที่สุดถ้า ชจ. เลือกเส้นทางที่ดีที่สุด ถ้าเครื่อง GPS ทั้งสองเครื่องร้องพร้อมกัน เราจะนับจำนวนครั้งการร้องเพิ่ม +2

Problem 6: Odometer [Brian Dean, 2014] (Silver)

Source: [12]

วัวของชาวนาจอห์นกำลังจะไปโร้ดทริป เครื่องวัดระยะในรถของเขาจะแสดงระยะทางเป็นจำนวนเต็ม โดยเริ่มที่ X (100 <= X <= 10^18) และสิ้นสุดที่ Y (X <= Y <= 10^18) เมื่อสิ้นสุดการเดินทาง เมื่อใดที่เครื่องวัดระยะแสดงตัวเลขที่น่าสนใจ เหล่าวัวจะร้อง "มู" จำนวนเต็มจะ "น่าสนใจ" ถ้าเมื่อคุณพิจารณาหลักเลขในจำนวนเต็มนนั้นโดยที่ไม่สนใจศูนย์ที่นำหน้าแล้ว อย่างน้อยครึ่งหนึ่งของตัวเลขจะต้องเหมือนกัน ยกตัวอย่างเช่น จำนวน 3223 และ 110 ต่างเป็นจำนวนเต็มที่น่าสนใจ แต่ 97791 และ 123 นั้นไม่

ช่วย ชจ. นับว่าเหล่าวัวร้องมูทั้งหมดกี่ครั้งระหว่างทริป