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

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

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 ดังนั้นเราจึงต้องมีวัวสองสายพันธุ์ที่แตกต่างกัน