1057 : Include
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
เวลาเขียนโปรแกรมภาษา C เราสามารถเอาเนื้อหาของไฟล์หนึง่ ๆ เข้ามาใส่ในไฟล์อีกไฟล์หนึ่ง ได้ด้วยการใช้คำาสั่ง #include ยกตัวอย่างเช่น ถ้า main.c และ lib.h มีเนื้อหาดังต่อไปนี้
เวลาคอมไพล์ คอมไพเลอร์ภาษา C จะเขียนเนื้อหาของ main.c ใหม่ โดยเอาเนื้อหาของ lib.h ไปแทรกไว้ที่คำสั่ง #include “lib.h” ใน main.c ดังนั้น เนื้อหาใหม่ของ main.c คือ
อนึ่ง ในไฟล์ที่ถูกไฟล์อื่น include อาจมีคำาสั่ง #include อยู่ก็ได้ และในไฟล์หนี่งอาจมีการ include ไฟล์อื่นๆ มากกว่าหนึ่ง ไฟล์ได้ ยกตัวอย่างเช่น
จะได้ว่าเวลาคอมไพเลอร์ภาษา C จะเขียนเนื้อหาของ main.c ใหม่ ดังนี้
อย่างไรก็ดีหากผู้เขียนโปรแกรมไม่ระมัดระวังก็อาจทำให้เกิดปัญหาได้สองประการคือ
1. ไฟล์เดียวกันถูก include มากกว่าหนึ่งครั้ง เช่น
ในกรณีเมื่อคอมไพเลอร์ทำการคอมไพล์ main.c ไฟล์ lib2.c จะถูก include สองครั้ง ครั้งหนึ่ง จากไฟล์ lib1.h และอีกครั้ง จาก lib3.h ซึ่ง ทำให้ฟังก์ชัน f2() ถูกนิยามสองครั้ง ซึ่ง อาจทำาให้คอมไพล์ไม่ผ่านได้
2. ไฟล์ include กันเป็นวงกลม เช่น
สังเกตว่าเมื่อคอมไพเลอร์ภาษา C คอมไพล์ไฟล์ main.c แล้วไฟล์ lib1.h จะ include ไฟล์ lib2.h ซึ่ง include ไฟล์ lib3.h ซึ่ง include ไฟล์ lib1.h และสามารถวนไปเช่นนีเ้ รื่อยๆ โดยไม่จำากัด
งานของคุณ
กำหนดไฟล์โปรแกรมภาษา C มาให้ N ไฟล์ แต่ละไฟล์จะถูกระบุด้วยตัวเลขตั้ง แต่ 1 ถึง N พร้อมทัง้ ข้อมูลว่าไฟล์ใด include ไฟล์ได้บ้าง จงเขียนโปรแกรมเพื่อตอบคำถามว่าสำหรับไฟล์ทุกๆ ไฟล์ เมื่อคอมไพเลอร์ภาษา C ทำาการคอมไพล์ไฟล์นั้น แล้วจะเกิดปัญหาใดปัญหาหนึ่ง ในสองปัญหาที่กล่าวถึงข้างบนหรือไม่
ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็ม N (1 ≤ N ≤ 1,000)
บรรทัดที่ i+1 (สำาหรับทุก ๆ 1 ≤ i ≤ N ) บอกว่าไฟล์ i ทำาการ include ไฟล์ใดบ้าง ซึ่ง บรรทัดที่ i + 1 จะระบุในรูปแบบดังนี้
k a1 a2 … ak
โดยที่ k และทุก ๆ aj ที่ 1 ≤ j ≤ k เป็นจำนวนเต็มที่ไม่เป็นลบและมีค่าไม่เกิน N บรรทัดดังกล่าวมีความหมายว่าไฟล์ i ทำาการ include ไฟล์ a1, a2, …, และ ak เรารับประกันว่าเลข ajจะมีค่าไม่ซ้ำกัน (ในไฟล์หนึง่ ๆ จะไม่มีการ include ไฟล์เดียวกันซ้ำสองครั้ง ) และในบรรทัดที่ i + 1 จะไม่มี aj ใดๆ ที่มีค่าเท่ากับ i (ไฟล์แต่ละไฟล์จะไม่ include ตัวเอง) นอกจากนี้รับประกันว่าจำนวนการ include ทั้ง หมดจะไม่เกิน 3,000 ครั้ง
ข้อมูลส่งออก
มี N บรรทัด แต่ละบรรทัดมีข้อความ YES หรือ NO ถ้าเมื่อคอมไพเลอร์ภาษา C คอมไพล์ไฟล์ i แล้วเกิดปัญหาใดปัญหาหนึ่ง ในปัญหาสองข้อข้างต้น ให้พิมพ์ YES ในบรรทัดที่ i หากไม่เกิดปัญหาใดขึ้น เลยให้พิมพ์ NO
ที่มา: Young Thai Online Programming Competition 2008
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
เวลาคอมไพล์ คอมไพเลอร์ภาษา C จะเขียนเนื้อหาของ main.c ใหม่ โดยเอาเนื้อหาของ lib.h ไปแทรกไว้ที่คำสั่ง #include “lib.h” ใน main.c ดังนั้น เนื้อหาใหม่ของ main.c คือ
อนึ่ง ในไฟล์ที่ถูกไฟล์อื่น include อาจมีคำาสั่ง #include อยู่ก็ได้ และในไฟล์หนี่งอาจมีการ include ไฟล์อื่นๆ มากกว่าหนึ่ง ไฟล์ได้ ยกตัวอย่างเช่น
จะได้ว่าเวลาคอมไพเลอร์ภาษา C จะเขียนเนื้อหาของ main.c ใหม่ ดังนี้
อย่างไรก็ดีหากผู้เขียนโปรแกรมไม่ระมัดระวังก็อาจทำให้เกิดปัญหาได้สองประการคือ
1. ไฟล์เดียวกันถูก include มากกว่าหนึ่งครั้ง เช่น
ในกรณีเมื่อคอมไพเลอร์ทำการคอมไพล์ main.c ไฟล์ lib2.c จะถูก include สองครั้ง ครั้งหนึ่ง จากไฟล์ lib1.h และอีกครั้ง จาก lib3.h ซึ่ง ทำให้ฟังก์ชัน f2() ถูกนิยามสองครั้ง ซึ่ง อาจทำาให้คอมไพล์ไม่ผ่านได้
2. ไฟล์ include กันเป็นวงกลม เช่น
สังเกตว่าเมื่อคอมไพเลอร์ภาษา C คอมไพล์ไฟล์ main.c แล้วไฟล์ lib1.h จะ include ไฟล์ lib2.h ซึ่ง include ไฟล์ lib3.h ซึ่ง include ไฟล์ lib1.h และสามารถวนไปเช่นนีเ้ รื่อยๆ โดยไม่จำากัด
งานของคุณ
กำหนดไฟล์โปรแกรมภาษา C มาให้ N ไฟล์ แต่ละไฟล์จะถูกระบุด้วยตัวเลขตั้ง แต่ 1 ถึง N พร้อมทัง้ ข้อมูลว่าไฟล์ใด include ไฟล์ได้บ้าง จงเขียนโปรแกรมเพื่อตอบคำถามว่าสำหรับไฟล์ทุกๆ ไฟล์ เมื่อคอมไพเลอร์ภาษา C ทำาการคอมไพล์ไฟล์นั้น แล้วจะเกิดปัญหาใดปัญหาหนึ่ง ในสองปัญหาที่กล่าวถึงข้างบนหรือไม่
ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็ม N (1 ≤ N ≤ 1,000)
บรรทัดที่ i+1 (สำาหรับทุก ๆ 1 ≤ i ≤ N ) บอกว่าไฟล์ i ทำาการ include ไฟล์ใดบ้าง ซึ่ง บรรทัดที่ i + 1 จะระบุในรูปแบบดังนี้
โดยที่ k และทุก ๆ aj ที่ 1 ≤ j ≤ k เป็นจำนวนเต็มที่ไม่เป็นลบและมีค่าไม่เกิน N บรรทัดดังกล่าวมีความหมายว่าไฟล์ i ทำาการ include ไฟล์ a1, a2, …, และ ak เรารับประกันว่าเลข ajจะมีค่าไม่ซ้ำกัน (ในไฟล์หนึง่ ๆ จะไม่มีการ include ไฟล์เดียวกันซ้ำสองครั้ง ) และในบรรทัดที่ i + 1 จะไม่มี aj ใดๆ ที่มีค่าเท่ากับ i (ไฟล์แต่ละไฟล์จะไม่ include ตัวเอง) นอกจากนี้รับประกันว่าจำนวนการ include ทั้ง หมดจะไม่เกิน 3,000 ครั้ง
ข้อมูลส่งออก
มี N บรรทัด แต่ละบรรทัดมีข้อความ YES หรือ NO ถ้าเมื่อคอมไพเลอร์ภาษา C คอมไพล์ไฟล์ i แล้วเกิดปัญหาใดปัญหาหนึ่ง ในปัญหาสองข้อข้างต้น ให้พิมพ์ YES ในบรรทัดที่ i หากไม่เกิดปัญหาใดขึ้น เลยให้พิมพ์ NO
ที่มา: Young Thai Online Programming Competition 2008
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 2 1 2 0 | NO NO |
| 3 1 2 1 3 1 1 | YES YES YES |
| 4 2 2 3 1 4 1 4 0 | YES NO NO NO |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 3 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)