คุณรู้จักบริษัท Just Ordinary Inventions หรือไม่? งานของบริษัทนี้คือการสร้าง “สิ่งประดิษฐ์ธรรมดาเท่านั้น”

JOI 君 กำลังเล่นเกมล่าสุดที่พัฒนาโดยบริษัท Just Ordinary Inventions

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

ในเกมนี้ แต่ละห้องมีเครื่องหมายและแท่นเพื่อช่วยในการเล่น เส้นทางที่ออกจากห้องสามารถนับเป็นเส้นที่ 1, 2, $\ldots$ โดยอ้างอิงจากเครื่องหมาย โครงสร้างของดันเจียนไม่เปลี่ยนแปลงระหว่างเกม ดังนั้น เมื่อเดินทางจากห้องเดิมด้วยเส้นทางหมายเลขเดิม ก็จะไปถึงห้องเดิมเสมอ บนแท่นมีอัญมณีหนึ่งเม็ดที่ผู้เล่นเปลี่ยนสีได้ สีของอัญมณีเป็นสี $1,2,\ldots,X$ สีใดสีหนึ่ง และเมื่อเริ่มเกม อัญมณีในทุกห้องเป็นสี $1$ สีของอัญมณีจะไม่เปลี่ยนเว้นแต่ผู้เล่นจะดำเนินการเปลี่ยนเอง

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

งานที่ต้องทำ

จงเขียนโปรแกรมที่สำรวจดันเจียนและระบุโครงสร้างของมัน อย่างไรก็ตาม JOI 君 ไม่ต้องการให้เปิดเผยโครงสร้างทั้งหมด โปรแกรมจึงต้องไม่ตอบโครงสร้างโดยตรง แต่ต้องตอบค่าต่อไปนี้สำหรับจำนวนเต็ม $i$ ทุกค่าตั้งแต่ $1$ ถึง $R$: “มีคู่ของห้องกี่คู่ที่ต้องใช้เส้นทางอย่างน้อยพอดี $i$ เส้นเพื่อเดินทางระหว่างกัน” (การสลับลำดับห้องถือเป็นคู่เดียวกัน)

คุณจะได้รับไลบรารีสำหรับดำเนินการต่อไปนี้เพื่อสำรวจดันเจียน

• ทราบจำนวนเส้นทางที่ออกจากห้องปัจจุบัน
• ทราบสีของอัญมณีบนแท่นในห้องปัจจุบัน
• เปลี่ยนสีของอัญมณีบนแท่นในห้องปัจจุบันเป็นสีที่ระบุ (ระบุสีเดิมก็ได้) จากนั้นเลือกเส้นทางออกหนึ่งเส้น แล้วเดินทางไปห้องอื่นตามเส้นทางนั้น
• ทราบว่าเส้นทางที่ใช้ล่าสุดเป็นเส้นทางหมายเลขใดในบรรดาเส้นทางที่ออกจากห้องปัจจุบัน

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

คุณต้องเขียนโปรแกรมหนึ่งโปรแกรมที่ใช้วิธีตอบคำถามให้ JOI 君 โปรแกรมต้องรวมไฟล์ dungeon2.h

โปรแกรมต้องเขียนฟังก์ชันต่อไปนี้

void Inspect(int R)

ฟังก์ชันนี้จะถูกเรียกเพียงครั้งเดียวตอนเริ่มต้น

• พารามิเตอร์ $R$ ระบุว่าต้องตอบว่า “มีคู่ของห้องกี่คู่ที่ต้องใช้เส้นทางอย่างน้อยพอดี $i$ เส้นเพื่อเดินทางระหว่างกัน” สำหรับจำนวนเต็ม $i$ ทุกค่าตั้งแต่ $1$ ถึง $R$ (การสลับลำดับห้องถือเป็นคู่เดียวกัน)

นอกจากนี้ ต้องเรียกฟังก์ชันต่อไปนี้เพื่อตอบคำถาม

void Answer(int D, int A)

• พารามิเตอร์ $D,A$ ระบุว่าการเรียกครั้งนี้ตอบว่า “มีคู่ของห้อง $A$ คู่ที่ต้องใช้เส้นทางอย่างน้อยพอดี $D$ เส้นเพื่อเดินทางระหว่างกัน”

การเรียก Answer ต้องเป็นไปตามเงื่อนไขต่อไปนี้

• $D$ ต้องเป็นจำนวนเต็มตั้งแต่ $1$ ถึง $R$ มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [1]
• ห้ามเรียก Answer ตั้งแต่สองครั้งขึ้นไปด้วยค่า $D$ เดิม มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [2]
• ต้องเรียก Answer พอดี $R$ ครั้ง มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [3]
• $A$ ต้องเท่ากับจำนวนคู่ของห้องที่ต้องใช้เส้นทางอย่างน้อยพอดี $D$ เส้นเพื่อเดินทางระหว่างกัน มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [4]

หากการเรียก Answer ถูกตัดสินว่าคำตอบผิด ไม่รับประกันว่าโปรแกรมส่วนที่เหลือจะยังทำงานต่อ

นอกจากนี้ โปรแกรมสามารถเรียกฟังก์ชันต่อไปนี้ได้

void Move(int I, int C)

• พารามิเตอร์ $I$ คือหมายเลขเส้นทางที่ผู้เล่นเลือกใช้เดินทาง ทันทีหลังการเรียก ผู้เล่นจะเดินทางไปยังห้องอื่นผ่านเส้นทางออกหมายเลข $I$ ของห้องปัจจุบัน
• พารามิเตอร์ $C$ ระบุว่าก่อนเดินทางออกจากห้อง ให้เปลี่ยนสีของอัญมณีบนแท่นในห้องปัจจุบันเป็นสี $C$

การเรียก Move ต้องเป็นไปตามเงื่อนไขต่อไปนี้

• เมื่อให้ $K$ เป็นจำนวนเส้นทางที่ออกจากห้องปัจจุบัน พารามิเตอร์ $I$ ต้องเป็นจำนวนเต็มตั้งแต่ $1$ ถึง $K$ มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [5]
• เมื่อมีสีอัญมณี $X$ สี พารามิเตอร์ $C$ ต้องเป็นจำนวนเต็มตั้งแต่ $1$ ถึง $X$ ค่า $X$ กำหนดตามงานย่อย มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [6]
• ห้ามเรียก Move มากกว่า $1\,500\,000$ ครั้ง มิฉะนั้นจะถูกตัดสินว่าคำตอบผิด [7]

int NumberOfRoads()

• ฟังก์ชันนี้คืนจำนวนเส้นทางที่ออกจากห้องปัจจุบันของผู้เล่น

int LastRoad()

• ฟังก์ชันนี้คืนหมายเลขของเส้นทางที่ผู้เล่นใช้ล่าสุด เมื่อมองเป็นเส้นทางออกของห้องปัจจุบัน แต่หากเรียกก่อนที่จะเรียก Move แม้แต่ครั้งเดียว จะคืนค่า -1

int Color()

• ฟังก์ชันนี้คืนสีของอัญมณีบนแท่นในห้องปัจจุบันของผู้เล่น

หลังการเรียกฟังก์ชัน Inspect จะมีการตรวจคำตอบ

สามารถเขียนฟังก์ชันอื่นสำหรับใช้ภายใน หรือประกาศตัวแปรส่วนกลางได้อย่างอิสระ อย่างไรก็ตาม โปรแกรมที่ส่งต้องไม่สื่อสารกับข้อมูลนำเข้ามาตรฐาน ข้อมูลส่งออกมาตรฐาน หรือไฟล์อื่นด้วยวิธีใด ๆ

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

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

โปรแกรมตรวจตัวอย่างประกอบด้วยไฟล์เดียว คือ grader.c หรือ grader.cpp หากต้องการทดสอบโปรแกรม ให้รันคำสั่งดังต่อไปนี้

• สำหรับ C

gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• สำหรับ C++

g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

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

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

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

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

• บรรทัดแรกมีจำนวนเต็ม $N,X,R$ คั่นด้วยช่องว่าง หมายความว่าดันเจียนมีห้อง $N$ ห้อง คือห้อง $1,2,\ldots,N$ มีสีอัญมณี $X$ สี และมีค่าที่โปรแกรมต้องตอบ $R$ ค่า
• ใน $2N$ บรรทัดถัดมา บรรทัดที่ $2i-1$ ($1 \le i \le N$) มีจำนวนเต็ม $D_i$ ระบุว่ามีเส้นทางออกจากห้อง $i$ จำนวน $D_i$ เส้น บรรทัดที่ $2i$ ($1 \le i \le N$) มีจำนวนเต็ม $D_i$ จำนวน คือ $T_{i1},T_{i2},\ldots,T_{iD_i}$ คั่นด้วยช่องว่าง หมายความว่าเมื่อใช้เส้นทางออกหมายเลข $j$ ($1 \le j \le D_i$) ของห้อง $i$ จะไปถึงห้อง $T_{ij}$
• บรรทัดที่ $j$ ($1 \le j \le R$) ของ $R$ บรรทัดถัดมามีจำนวนเต็ม $A_j$ หมายความว่ามีคู่ของห้อง $A_j$ คู่ที่ต้องใช้เส้นทางอย่างน้อยพอดี $j$ เส้นเพื่อเดินทางระหว่างกัน กล่าวคือ สำหรับแต่ละ $j$ ($1 \le j \le R$) โปรแกรมตรวจตัวอย่างจะตัดสินว่าถูกต้องเมื่อเรียก Answer โดยกำหนดพารามิเตอร์ $D$ เป็น $j$ และพารามิเตอร์ $A$ เป็น $A_j$ และจะตัดสินว่าคำตอบผิดในกรณีอื่น

โปรแกรมตรวจตัวอย่างจะเรียกฟังก์ชันที่คุณเขียน โดยให้ตำแหน่งเริ่มต้นของผู้เล่นเป็นห้อง $1$

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

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

• หากถูกต้อง จะแสดงจำนวนครั้งที่เรียกฟังก์ชัน Move ในรูปแบบเช่น Accepted : #move = 8
• หากคำตอบผิด จะแสดงประเภทของคำตอบผิดในรูปแบบเช่น Wrong Answer [1]

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้ สำหรับความหมายของ $N,D_i,T_{ij}$ โปรดดูหัวข้อ “ข้อมูลนำเข้าของโปรแกรมตรวจตัวอย่าง”

• $2 \le N \le 200$
• $3 \le X \le 100$
• $1 \le R \le 200$
• $1 \le D_i \le N-1$ ($1 \le i \le N$)
• $1 \le T_{ij} \le N$ และ $T_{ij} \ne i$ ($1 \le i \le N$, $1 \le j \le D_i$)
• $T_{i1},T_{i2},\ldots,T_{iD_i}$ ($1 \le i \le N$) แตกต่างกันทั้งหมด
• สำหรับแต่ละ $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$) จะมี $k$ ($1 \le k \le D_{T_{ij}}$) ที่ทำให้ $T_{T_{ij}k}=i$
• สามารถเดินทางระหว่างห้องสองห้องใด ๆ ได้โดยใช้เส้นทางหลายเส้น

งานย่อย

ต่อไปนี้ ให้ $N$ เป็นจำนวนห้อง และ $M$ เป็นจำนวนเส้นทางของดันเจียนในข้อมูลนำเข้า

งานย่อย 1 [17 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N \le 50$
• $M \le 100$
• $X=100$

งานย่อย 2 [27 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N \le 50$
• $M \le 100$
• $X=3$

งานย่อย 3 [56 คะแนน]

• เป็นไปตาม $X=3$

คะแนนในงานย่อยนี้กำหนดดังต่อไปนี้

• ให้ $L$ เป็นค่าสูงสุดของค่าต่อไปนี้ในทุกกรณีทดสอบของงานย่อยนี้

  • $\frac{C}{M}$ เมื่อให้ $C$ เป็นจำนวนครั้งที่เรียก Move

• คะแนนของงานย่อยนี้คือ

  • 56 คะแนน เมื่อ $L \le 14$
  • $\lfloor 70-L \rfloor$ คะแนน เมื่อ $14<L\le32$
  • $\left\lfloor54-\frac{L}{2}\right\rfloor$ คะแนน เมื่อ $32<L\le64$
  • 0 คะแนน เมื่อ $64<L$

ในที่นี้ $\lfloor x\rfloor$ หมายถึงจำนวนเต็มที่มากที่สุดซึ่งไม่เกิน $x$

ในระบบตรวจคะแนน หากโปรแกรมสิ้นสุดอย่างถูกต้องและถูกตัดสินว่าถูกต้อง ช่องรายละเอียดจะแสดง Accepted อย่างไรก็ตาม โปรดทราบว่าในการตรวจงานย่อย 3 สำหรับกรณีทดสอบที่ $C,M$ ข้างต้นเป็นไปตาม $64<\frac{C}{M}$ ช่องผลลัพธ์จะแสดงว่าคำตอบผิด

ตัวอย่างการโต้ตอบ

ต่อไปนี้เป็นตัวอย่างข้อมูลนำเข้าที่โปรแกรมตรวจตัวอย่างอ่าน และตัวอย่างการเรียกฟังก์ชันที่สอดคล้องกัน

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

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

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

โปรดทราบว่าการเรียกฟังก์ชันในตัวอย่างนี้ไม่จำเป็นต้องเป็นการเรียกที่มีความหมาย