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)

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