เกมไพ่เกมหนึ่งที่ถูกกล่าวขานว่าเป็นบททดสอบแห่งสติปัญญา เกมนั้นชื่อว่า “แคง” ในเกมนี้ ไพ่แต่ละใบจะมีคะแนนเป็นจำนวนเต็มบวก เมื่อเริ่มต้นคุณจะได้รับไพ่เป็นจำนวน $N$ ใบมาเก็บไว้ในมือ และมีไพ่อีก $M$ ใบวางหงายอยู่บนโต๊ะเรียงจากซ้ายไปขวา โดยคุณเห็นคะแนนของไพ่ทุกใบทั้งที่ได้รับมาและที่วางอยู่บนโต๊ะ จากนั้นให้คุณหยิบไพ่บนโต๊ะมาเพิ่มได้อีก $k$ รอบ โดยจะต้องหยิบทีละใบเรียงจากซ้ายไปขวา หลังจากการหยิบไพ่แต่ละรอบ คุณสามารถทิ้งไพ่ในมือได้ 1 ครั้ง ที่มีคะแนนเท่ากันในมือกี่ใบก็ได้ คุณจะต้องวางแผนการเล่นเพื่อให้หลังจากหยิบไพ่บนโต๊ะและทิ้งไพ่ในมือไปครบ $k$ รอบแล้ว ไพ่ที่เหลือในมือมีคะแนนรวมน้อยที่สุด
พิจารณาตัวอย่างต่อไปนี้
ถ้าตอนเริ่มต้นคุณมีไพ่อยู่ห้าใบ โดยมีคะแนนเป็น $6, 3, 9, 6, 3$ และไพ่ที่วางอยู่บนโต๊ะมีคะแนนเรียงจากซ้ายไปขวาเป็น $4, 6, 9, 6$
กรณี $k = 1$ หากคุณหยิบไพ่บนโต๊ะได้เพียง 1 ใบ เมื่อคุณหยิบใบแรกมา คะแนนของไพ่ที่คุณมีจะเป็นดังนี้ $6, 3, 9, 6, 3, 4$ จากนั้นคุณสามารถเลือกหยิบไพ่ที่มีคะแนนเท่ากันทิ้งได้ 1 ครั้ง ซึ่งทางที่ดีที่สุดคือคุณจะต้องเลือกหยิบไพ่ที่มีคะแนนเท่ากับ $6$ ทิ้งไป 2 ใบ เพื่อให้คะแนนรวมของไพ่ที่เหลืออยู่มีค่าน้อยที่สุดเท่ากับ $3 + 9 + 3 + 4 = 19$
กรณี $k = 2$ หากคุณหยิบไพ่บนโต๊ะได้ 2 ใบ วิธีที่ดีที่สุดคือ หลังจากที่หยิบไพ่ใบแรกที่มีคะแนนเท่ากับ $4$ มาแล้ว คุณเลือกทิ้งไพ่ที่มีคะแนนเท่ากับ $9$ ออกหนึ่งใบ ไพ่ที่เหลือในมือมีคะแนนเป็น $6, 3, 6, 3, 4$ จากนั้นเมื่อหยิบไพ่ใบที่ 2 ที่มีคะแนนเท่ากับ $6$ คุณจะสามารถทิ้งไพ่ที่มีคะแนนเท่ากับ $6$ ออกไปได้ 3 ใบ ทำให้ไพ่ที่เหลือมีคะแนนรวมน้อยที่สุดเท่ากับ $3 + 3 + 4 = 10$
กรณี $k = 3$ หากคุณหยิบไพ่บนโต๊ะได้ 3 ใบ วิธีที่ดีที่สุดคือ เมื่อคุณหยิบไพ่ใบแรกมา คะแนนของไพ่ที่อยู่ในมือจะเป็น $6, 3, 9, 6, 3, 4$ จากนั้นเลือกไพ่ที่มีคะแนนเท่ากันทิ้งได้ 1 ครั้ง ซึ่งทางที่ดีที่สุดคือคุณจะต้องหยิบไพ่ที่มีคะแนนเท่ากับ $3$ ทิ้งทั้ง 2 ใบ จะเหลือไพ่ในมือเป็น $6, 9, 6, 4$ จากนั้น เมื่อหยิบไพ่ใบที่ 2 ที่มีคะแนนเท่ากับ $6$ คุณจะสามารถทิ้งไพ่ที่มีคะแนนเท่ากับ $6$ ออกไปได้ 3 ใบ จะมีไพ่ในมือเป็น $9, 4$ และเมื่อคุณหยิบไพ่ครั้งที่ 3 ที่มีคะแนนเท่ากับ $9$ คุณจะสามารถทิ้งไพ่ที่มีคะแนนเท่ากับ $9$ ออกได้ทั้ง 2 ใบ ทำให้ไพ่ที่เหลือมีคะแนนรวมเป็น $4$
กรณี $k = 4$ หากคุณหยิบไพ่บนโต๊ะได้ 4 ใบ วิธีที่ดีที่สุดคือ หลังจากที่หยิบไพ่ใบแรกที่มีคะแนนเท่ากับ $4$ มาแล้ว เลือกทิ้งไพ่ที่มีคะแนนเท่ากับ $4$ ออกหนึ่งใบ เหลือไพ่ในมือมีคะแนนเป็น $6, 3, 9, 6, 3$ จากนั้นหยิบครั้งที่ 2 ไพ่มีคะแนนเท่ากับ $6$ ซึ่งทางที่ดีที่สุดคือ คุณจะต้องหยิบไพ่ที่มีคะแนนเท่ากับ $3$ ทิ้งทั้ง 2 ใบจะเหลือไพ่ในมือเท่ากับ $6, 9, 6, 6$ เมื่อหยิบครั้งที่ 3 ไพ่มีคะแนนเท่ากับ $9$ เลือกทิ้งไพ่ที่มีคะแนนเท่ากับ $9$ ทั้ง 2 ใบ และในการหยิบไพ่ใบสุดท้ายที่มีคะแนนเท่ากับ $6$ คุณจะสามารถทิ้งไพ่ที่มีคะแนนเท่ากับ $6$ ออกไปได้ 4 ใบ ซึ่งในการทิ้งครั้งนี้ส่งผลให้ไม่เหลือไพ่ในมือ นั่นหมายความว่า คะแนนรวมของไพ่เป็น $0$
งานของคุณ (Your Task)
หา “ผลรวมคะแนนของไพ่ที่เหลือในมือที่น้อยที่สุด” หลังจากจบ $k$ รอบ เมื่อ $k = 1, 2, 3, \ldots, M$
ข้อนี้มีรูปแบบการเขียนโปรแกรมที่แตกต่างจากรูปแบบปรกติ ซึ่งจะมีใช้ในการแข่งขันจริง โปรดดูส่วนท้ายของโจทย์ข้อนี้เกี่ยวกับวิธีการใช้งาน
รายละเอียดการเขียนโปรแกรม
คุณจะต้องเขียนฟังก์ชันต่อไปนี้:
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)โดยมีพารามิเตอร์ คือ
- $A$ คือ อาร์เรย์ความยาว $N$ ระบุหมายเลขของไพ่ในมือตอนเริ่มต้น
- $B$ คือ อาร์เรย์ความยาว $M$ ระบุหมายเลขของไพ่ที่ใบวางอยู่บนโต๊ะ เรียงตามลำดับจากซ้ายไปขวา
- ฟังก์ชันดังกล่าวจะต้องคืนอาร์เรย์ $C$ ที่มีความยาว $M$ แทนผลรวมของคะแนนของไพ่ในมือที่มีค่าน้อยที่สุดที่เป็นไปได้ $k$ รอบ เมื่อ $k = 1, 2, 3, \ldots, M$
ตัวอย่างเช่น ถ้า $A = [6, 3, 9, 6, 3]$ และ $B = [4, 6, 9, 6]$ ฟังก์ชันจะต้องคืนค่าเป็นอาเรย์ $[19, 10, 4, 0]$
ข้อจำกัด
- $1 \le N, M \le 10^6$
- $1 \le A[i] \le 10^9$ สำหรับแต่ละ $i$ ที่ $1 \le i \le N$
- $1 \le B[i] \le 10^9$ สำหรับแต่ละ $i$ ที่ $1 \le i \le M$
งานย่อย
| กลุ่มชุดทดสอบที่ | คะแนนสูงสุดของกลุ่มชุดทดสอบนี้ | เงื่อนไข |
|---|---|---|
| 1 | 5% | $N, M \le 5$ |
| 2 | 7% | $N \le 1\,000$ และ $M = 1$ |
| 3 | 8% | $N, M \le 1\,000$ ไพ่ทุกใบ (ทั้งไพ่ที่มีในมือและไพ่ที่แสดงบนโต๊ะ) มีหมายเลขแตกต่างกันหมด |
| 4 | 12% | $N, M \le 1\,000$ ไพ่ที่รับมาเพิ่มทุกใบมีค่าเท่ากันหมด |
| 5 | 16% | $N, M \le 1\,000$ |
| 6 | 28% | $N, M \le 100\,000$ |
| 7 | 24% | ไม่มีเงื่อนไขเพิ่มเติม |
หมายเหตุ
คำแนะนำในการเขียนโปรแกรม
สำหรับข้อนี้ วิธีการเขียนโปรแกรมและส่งโปรแกรมเข้าสู่ระบบเกรดเดอร์ (Grader) จะเป็นรูปแบบที่แตกต่างจากรูปแบบทั่วไปของการเขียนโปรแกรม ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมในส่วนรับข้อมูลนำเข้า และส่วนแสดงผล โดยในข้อนี้ ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมเฉพาะส่วนการคำนวณที่จำเป็นลงในฟังก์ชันที่กำหนดให้ โดยข้อมูลนำเข้าต่าง ๆ จะสามารถใช้ได้ผ่านพารามิเตอร์ของฟังก์ชัน และผลการคำนวณจะต้องส่งกลับผ่านฟังก์ชันด้วยเช่นกัน โดยที่ผู้เข้าแข่งขันไม่ต้องเขียนโปรแกรมในส่วนรับข้อมูลนำเข้า และไม่ต้องเขียนส่วนแสดงผล
ผู้เข้าแข่งขันจะได้รับไฟล์ต่าง ๆ หลายไฟล์ดังนี้ ผู้เข้าแข่งขันจะต้องแก้ไขไฟล์เดียวตามที่โจทย์กำหนด และส่งไฟล์ดังกล่าวเข้าสู่ระบบ
grader.cppเป็นไฟล์หลักที่ทำหน้าที่รับข้อมูลนำเข้าและส่งออกkang.cppเป็นไฟล์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมคำนวณต่าง ๆ และเป็นไฟล์ที่ผู้เข้าแข่งขันส่งเข้าสู่ระบบ (ในไฟล์kang.cppห้ามมีฟังก์ชันmain()แต่มีฟังก์ชันอื่น ๆ ได้)run_cpp.shเป็นไฟล์ที่ผู้เข้าแข่งขันสามารถเรียกใช้เพื่อทำการรันโปรแกรมทั้งหมดได้compile_cpp.shเป็นไฟล์ที่ผู้เข้าแข่งขันสามารถเรียกใช้เพื่อทำการคอมไพล์โปรแกรมได้
ผู้เข้าแข่งขันจะได้รับไฟล์ .zip ซึ่งสามารถดาวน์โหลดได้จากระบบโดยในไฟล์ดังกล่าวเมื่อขยาย (extract) ออกมาแล้วจะมีไฟล์ทั้ง 4 อยู่ ผู้เข้าแข่งขันควรใช้ text editor หรือ IDE ในการแก้ไขไฟล์ kang.cpp และทำการคอมไพล์หรือรันโปรแกรมผ่านการเรียกใช้ฟังก์ชัน compile_cpp.sh หรือ run_cpp.sh
เมื่อผู้เข้าแข่งขันสามารถเรียกไฟล์ run_cpp.sh เพื่อทำการรันโปรแกรม โปรแกรมจะทำงานตามที่ได้ระบุไว้ในไฟล์ grader.cpp ซึ่งหัวข้อ “คำอธิบายไฟล์เกรดเดอร์” อธิบายถึงการทำงานของไฟล์ดังกล่าว