ผลต่างระหว่างรุ่นของ "Usaco2014"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
แถว 131: | แถว 131: | ||
พิกัดทั้งหมดเป็นจำนวนเต็มระหว่าง -1,000,000,000 และ 1,000,000,000 รับประกันว่ากระจกทั้งหมดจะวางอยู่ในขอบเขตนี้เช่นเดียวกัน วัวที่วางแผนกำหนดว่างเลเซอร์จะต้องไม่กลับมายังตำแหน่ง (0,0) หลังจากที่ถูกปล่อยออกไปแล้ว (และด้วยตำแหน่งของกระจกเมื่อเริ่มต้น เรารับประกันว่าเหตุการณ์นี้จะไม่เกิดขึ้น) ไม่มีวัวสองตัวอยู่ที่ตำแหน่งเดียวกัน และเบสซี่จะไม่สามารถไปอยู่ตำแหน่งเดียวกับวัวที่ยืนอยู่แล้วได้ | พิกัดทั้งหมดเป็นจำนวนเต็มระหว่าง -1,000,000,000 และ 1,000,000,000 รับประกันว่ากระจกทั้งหมดจะวางอยู่ในขอบเขตนี้เช่นเดียวกัน วัวที่วางแผนกำหนดว่างเลเซอร์จะต้องไม่กลับมายังตำแหน่ง (0,0) หลังจากที่ถูกปล่อยออกไปแล้ว (และด้วยตำแหน่งของกระจกเมื่อเริ่มต้น เรารับประกันว่าเหตุการณ์นี้จะไม่เกิดขึ้น) ไม่มีวัวสองตัวอยู่ที่ตำแหน่งเดียวกัน และเบสซี่จะไม่สามารถไปอยู่ตำแหน่งเดียวกับวัวที่ยืนอยู่แล้วได้ | ||
− | PROBLEM NAME: optics | + | '''PROBLEM NAME:''' optics |
− | INPUT FORMAT: | + | '''INPUT FORMAT:''' |
* Line 1: จำนวนเต็ม N, Bx, และ By. | * Line 1: จำนวนเต็ม N, Bx, และ By. | ||
* Lines 2..N + 1: บรรทัดที่ i+1 ระบุข้อมูลของกระจกอันที่ i ด้วยค่าสามค่าคือตำแหน่ง (x,y) และทิศทาง (มีค่าเป็น '\' or '/'). | * Lines 2..N + 1: บรรทัดที่ i+1 ระบุข้อมูลของกระจกอันที่ i ด้วยค่าสามค่าคือตำแหน่ง (x,y) และทิศทาง (มีค่าเป็น '\' or '/'). | ||
− | SAMPLE INPUT (file optics.in): | + | '''SAMPLE INPUT (file optics.in):''' |
4 1 2 | 4 1 2 | ||
แถว 146: | แถว 146: | ||
-2 2 / | -2 2 / | ||
− | OUTPUT FORMAT: จำนวนเต็มหนึ่งจำนวนแทนตำแหน่งที่เบสซี่สามารถไปอยู่ได้เพื่อจะเปลี่ยนทิศทางของเลเซอร์เพื่อให้วิ่งไปยังโรงวัว | + | '''OUTPUT FORMAT:''' จำนวนเต็มหนึ่งจำนวนแทนตำแหน่งที่เบสซี่สามารถไปอยู่ได้เพื่อจะเปลี่ยนทิศทางของเลเซอร์เพื่อให้วิ่งไปยังโรงวัว |
− | SAMPLE OUTPUT (file optics.out): | + | '''SAMPLE OUTPUT (file optics.out):''' |
2 | 2 | ||
− | OUTPUT DETAILS: | + | '''OUTPUT DETAILS:''' |
กระจกที่ตำแหน่ง (0,1) หรือ (0,2) ไม่ว่าจะวางในทิศทางไหนก็ทำให้เลเซอร์วิ่งไปยังโรงวัวได้ | กระจกที่ตำแหน่ง (0,1) หรือ (0,2) ไม่ว่าจะวางในทิศทางไหนก็ทำให้เลเซอร์วิ่งไปยังโรงวัวได้ |
รุ่นแก้ไขเมื่อ 11:12, 14 เมษายน 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