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

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