Anna และ Bruno เป็นนักโบราณคดี ทั้งสองกำลังสำรวจซากโบราณสถานในประเทศอิหร่าน

หน้าที่ของทั้งสองมีดังนี้: Anna เดินทางไปยังโบราณสถานและค้นพบโบราณวัตถุ ส่วน Bruno วิเคราะห์ผลที่ค่ายฐาน

การสำรวจมีกำหนด $Q\,(=1\,000)$ วัน ทุกวัน Anna ส่งผลการสำรวจให้ Bruno โดยใช้อุปกรณ์สื่อสาร ผลของแต่ละวันแทนด้วยจำนวนเต็ม $X$

Anna ใช้อุปกรณ์สื่อสารได้เพียงวันละครั้ง อุปกรณ์นี้ส่งลำดับความยาว $N\,(=150)$ ที่ประกอบด้วย $0$ หรือ $1$ ได้

อย่างไรก็ตาม อุปกรณ์เสีย มีบางตำแหน่งในลำดับความยาว $N$ ที่เสีย ตำแหน่งที่เสียจะส่งค่า $0$ เสมอ ไม่ว่าจะตั้งค่าจริงไว้เป็นเท่าใด เมื่อ Anna ส่งลำดับ เธอมองเห็นตำแหน่งที่เสีย แต่ Bruno ไม่ทราบตำแหน่งเหล่านั้น ตำแหน่งที่เสียและจำนวนตำแหน่งที่เสียอาจเปลี่ยนไปในแต่ละวัน

การสำรวจอาจล่าช้าได้ เนื่องจากคุณเป็นผู้สมัครเข้าร่วมการแข่งขันเขียนโปรแกรมนานาชาติในประเทศอิหร่าน Anna และ Bruno จึงขอให้คุณเขียนโปรแกรมสำหรับส่งผลการสำรวจ

งาน

เขียนโปรแกรมสองโปรแกรมเพื่อให้ Anna และ Bruno สื่อสารกันได้

• เมื่อกำหนดความยาวลำดับ $N$ จำนวนเต็มที่ต้องการส่ง $X$ จำนวนตำแหน่งที่เสีย $K$ และตำแหน่งที่เสีย $P$ โปรแกรมแรกกำหนดลำดับ $S$ ที่ Anna จะส่ง
• เมื่อกำหนดลำดับ $A$ ที่ Bruno ได้รับ โปรแกรมที่สองกู้คืนจำนวนเต็ม $X$

ในตำแหน่งที่อุปกรณ์สื่อสารทำงานได้ ลำดับ $S$ และลำดับ $A$ มีค่าเท่ากัน ในตำแหน่งที่เสีย ลำดับ $A$ มีค่า $0$ เสมอ ไม่ว่าค่าในลำดับ $S$ จะเป็นเท่าใด

รายละเอียดการเขียนโปรแกรม

คุณต้องส่งสองไฟล์ที่เขียนด้วยภาษาโปรแกรมเดียวกัน

ไฟล์แรกคือ Anna.c หรือ Anna.cpp ไฟล์นี้กำหนดลำดับที่ Anna ส่ง และต้องเขียนฟังก์ชันต่อไปนี้ โปรแกรมต้อง include Annalib.h

• void Anna( int N, long long X, int K, int P[] )

  ในแต่ละกรณีทดสอบ ฟังก์ชันนี้ถูกเรียก $Q=1\,000$ ครั้ง

  • พารามิเตอร์ N คือความยาวของลำดับที่จะส่ง
  • พารามิเตอร์ X คือจำนวนเต็มที่จะส่ง
  • พารามิเตอร์ K คือจำนวนตำแหน่งที่เสีย
  • พารามิเตอร์ P[] คือลำดับความยาว $K$ ที่ระบุตำแหน่งที่เสีย

ภายในฟังก์ชัน Anna ต้องเรียกฟังก์ชันต่อไปนี้

• void Set( int pos, int bit )

  ฟังก์ชันนี้กำหนดบิตหนึ่งในลำดับ $S$ ที่จะส่งด้วยอุปกรณ์สื่อสาร

  • พารามิเตอร์ pos คือตำแหน่งที่จะกำหนดค่า pos ต้องเป็นจำนวนเต็มตั้งแต่ $0$ ถึง $N-1$ รวมปลายทั้งสองด้าน โปรดทราบว่าตำแหน่งเริ่มนับจาก $0$ หากเรียกด้วยพารามิเตอร์นอกช่วงนี้ โปรแกรมจะถูกตัดสินว่า Wrong Answer[1] ห้ามเรียกฟังก์ชันนี้มากกว่าหนึ่งครั้งด้วยพารามิเตอร์ pos เดียวกัน หากเรียกมากกว่าหนึ่งครั้งด้วยพารามิเตอร์เดียวกัน โปรแกรมจะถูกตัดสินว่า Wrong Answer[2]
  • พารามิเตอร์ bit คือค่าที่จะกำหนดให้ตำแหน่ง pos ของลำดับ ค่า bit ต้องเป็น $0$ หรือ $1$ เท่านั้น หากเรียกด้วยค่าอื่น โปรแกรมจะถูกตัดสินว่า Wrong Answer[3]

ภายในฟังก์ชัน Anna ต้องเรียกฟังก์ชัน Set ทั้งหมด $N$ ครั้งพอดี เมื่อฟังก์ชัน Anna จบการทำงาน หากจำนวนครั้งที่เรียก Set ไม่เท่ากับ $N$ โปรแกรมจะถูกตัดสินว่า Wrong Answer[4]

โปรแกรมจะยุติการทำงานหากการเรียกฟังก์ชันโดย Anna ถูกตัดสินว่าไม่ถูกต้อง

ไฟล์ที่สองคือ Bruno.c หรือ Bruno.cpp ไฟล์นี้กู้คืนจำนวนเต็มที่แทนผลการสำรวจ และต้องเขียนฟังก์ชันต่อไปนี้ โปรแกรมต้อง include Brunolib.h

• long long Bruno( int N, int A[] )

  ในแต่ละกรณีทดสอบ ฟังก์ชันนี้ถูกเรียก $Q=1\,000$ ครั้ง

  • พารามิเตอร์ N คือความยาวของลำดับที่ Bruno ได้รับ
  • พารามิเตอร์ A คือลำดับจำนวนเต็มความยาว $N$ ซึ่งเป็นลำดับที่ Bruno ได้รับ
  • ฟังก์ชัน Bruno ต้องกู้คืนค่า $X$ และคืนค่านั้น

ขั้นตอนการตรวจให้คะแนน

การตรวจให้คะแนนดำเนินการดังต่อไปนี้ หากโปรแกรมถูกตัดสินว่า Wrong Answer โปรแกรมจะยุติการทำงานทันที

1. กำหนด cnt = 0
2. เรียกฟังก์ชัน Anna หนึ่งครั้ง
3. ให้ $S$ เป็นลำดับที่ฟังก์ชัน Anna กำหนด ในลำดับ $S$ ให้เปลี่ยนค่าที่ตำแหน่งใน $P$ เป็น $0$ เพื่อให้ได้ลำดับ $A$ เรียกฟังก์ชัน Bruno หนึ่งครั้งด้วยพารามิเตอร์ $A$
4. กำหนด cnt = cnt +1 หาก $\mathrm{cnt}<Q$ ให้กลับไปข้อ (2) หาก $\mathrm{cnt}=Q$ ให้ไปข้อ (5)
5. โปรแกรมจะได้รับคะแนน

ข้อควรทราบที่สำคัญ

• เวลาและหน่วยความจำที่ใช้คำนวณจากข้อ (1), (2), (3), (4) ในขั้นตอนการตรวจให้คะแนน
• โปรแกรมต้องไม่ถูกตัดสินว่า Wrong Answer ในการเรียก Anna ในข้อ (2) หรือ Bruno ในข้อ (3) และต้องทำงานโดยไม่มีข้อผิดพลาดขณะรัน
• โปรแกรมสามารถเขียนฟังก์ชันอื่นเพื่อใช้ภายใน หรือใช้ตัวแปรส่วนกลางได้ โปรแกรมที่ส่งจะถูกคอมไพล์ร่วมกับโปรแกรมตรวจเป็นไฟล์ปฏิบัติการเดียว ตัวแปรส่วนกลางและฟังก์ชันภายในทั้งหมดควรประกาศเป็น static เพื่อหลีกเลี่ยงการชนกับไฟล์อื่น เนื่องจากเมื่อตรวจให้คะแนน โปรแกรมของ Anna และ Bruno จะทำงานเป็น 2 โพรเซสแยกกัน ทั้งสองจึงไม่สามารถใช้ตัวแปรส่วนกลางร่วมกันได้
• ในแต่ละโพรเซส ฟังก์ชัน Anna และ Bruno แต่ละฟังก์ชันจะถูกเรียก $Q=1\,000$ ครั้ง ควรกำหนดค่าเริ่มต้นให้ตัวแปรที่โปรแกรมใช้อย่างเหมาะสม
• โปรแกรมต้องไม่ใช้ข้อมูลนำเข้ามาตรฐานและข้อมูลส่งออกมาตรฐาน และต้องไม่สื่อสารกับไฟล์อื่นด้วยวิธีใด ๆ

การคอมไพล์และการทดลองรัน

คุณสามารถดาวน์โหลดไฟล์บีบอัดจากหน้าเว็บการแข่งขัน ซึ่งมีโปรแกรมตรวจตัวอย่างสำหรับทดสอบโปรแกรมของคุณ และยังมีไฟล์ซอร์สตัวอย่างของโปรแกรมของคุณด้วย

โปรแกรมตรวจตัวอย่างประกอบด้วยไฟล์ซอร์สหนึ่งไฟล์ คือ grader.c หรือ grader.cpp ตัวอย่างเช่น หากโปรแกรมของคุณคือ Anna.c และ Bruno.c หรือ Anna.cpp และ Bruno.cpp ให้คอมไพล์ด้วยคำสั่งต่อไปนี้

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

เมื่อคอมไพล์สำเร็จ จะได้ไฟล์ปฏิบัติการ grader

โปรดทราบว่าโปรแกรมตรวจจริงแตกต่างจากโปรแกรมตรวจตัวอย่าง โปรแกรมตรวจตัวอย่างทำงานเป็นโพรเซสเดียว ซึ่งอ่านข้อมูลจากข้อมูลนำเข้ามาตรฐานและเขียนผลไปยังข้อมูลส่งออกมาตรฐาน

ข้อมูลนำเข้าสำหรับโปรแกรมตรวจตัวอย่าง

โปรแกรมตรวจตัวอย่างอ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $Q$
• จากนั้นเป็นข้อมูลของคำถาม $Q$ คำถาม

• ข้อมูลของแต่ละคำถามมีสองบรรทัดดังนี้

  • บรรทัดแรกมีจำนวนเต็มสามจำนวน $N,X,K$ คั่นด้วยช่องว่าง หมายความว่าลำดับที่จะส่งมีความยาว $N$ จำนวนเต็มที่ Anna จะส่งคือ $X$ และมีตำแหน่งที่เสีย $K$ ตำแหน่ง
  • บรรทัดที่สองมีจำนวนเต็ม $K$ จำนวน $P_0,P_1,\ldots,P_{K-1}$ คั่นด้วยช่องว่าง หมายความว่าสำหรับทุก $i$ ($0 \le i \le K-1$) ตำแหน่งที่ $P_i$ ในลำดับเสีย

ข้อมูลส่งออกของโปรแกรมตรวจตัวอย่าง

เมื่อโปรแกรมจบการทำงานสำเร็จ โปรแกรมตรวจตัวอย่างจะเขียนข้อมูลต่อไปนี้ไปยังข้อมูลส่งออกมาตรฐาน (ไม่ได้เขียนเครื่องหมายอัญประกาศจริง)

• หากโปรแกรมถูกตัดสินว่า Wrong Answer โปรแกรมตรวจตัวอย่างจะแสดงชนิดของข้อผิดพลาดในรูปแบบ “Wrong Answer [1]” และโปรแกรมจะยุติการทำงาน
• หากการเรียกฟังก์ชัน Anna ทุกครั้งไม่ถูกตัดสินว่า Wrong Answer โปรแกรมตรวจตัวอย่างจะเขียน “Accepted” และค่า $L^*$ สำหรับค่า $L^*$ ให้ดูหัวข้องานย่อย

หากโปรแกรมเข้าข่าย Wrong Answer หลายชนิด โปรแกรมตรวจตัวอย่างจะรายงานเพียงชนิดเดียว

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $Q=1000$
• $N=150$
• $0 \le X \le 1\,000\,000\,000\,000\,000\,000$
• $1 \le K \le 40$
• $0 \le P_i \le N-1$ ($0 \le i \le K-1$)
• $P_i<P_{i+1}$ ($0 \le i \le K-2$)

งานย่อย

• ให้ $L^*$ เป็นค่าต่ำสุดของค่าต่อไปนี้ เมื่อพิจารณากรณีทดสอบทั้งหมดของโจทย์นี้

  • จำนวนเต็ม $L \le 40$ ที่มากที่สุด ซึ่งทำให้ทุกคำถามที่มี $K \le L$ นั้น Bruno ตอบค่า $X$ ได้ถูกต้อง

• คะแนนของโจทย์นี้คำนวณดังต่อไปนี้

  • หาก $L^*=0$ ได้ 0 คะแนน
  • หาก $1 \le L^* \le 14$ ได้ 8 คะแนน
  • หาก $15 \le L^* \le 37$ ได้ $(L^*-15)\times 2+41$ คะแนน
  • หาก $38 \le L^* \le 40$ ได้ $(L^*-38)\times 5+90$ คะแนน

ตัวอย่างการสื่อสาร

ต่อไปนี้เป็นตัวอย่างข้อมูลนำเข้าสำหรับโปรแกรมตรวจและการเรียกฟังก์ชันที่สอดคล้องกัน โปรดทราบว่าตัวอย่างนี้ไม่เป็นไปตามข้อจำกัดของโจทย์ เนื่องจาก $Q=2,N=3$

ข้อมูลนำเข้า 1

2
3 14 1
2
3 9 2
0 1

การเรียกฟังก์ชันตัวอย่าง

พารามิเตอร์สำหรับ Anna(...), Bruno(...), Anna(...), Bruno(...) มีดังนี้