พูดคุย:CERC12 - ประวัติรุ่นแก้ไข

Nattee เมื่อ 13:39, 15 พฤษภาคม 2556

2013-05-15T13:39:10Z

Nattee เมื่อ 13:36, 15 พฤษภาคม 2556

2013-05-15T13:36:55Z

Nattee: /* Graphic Madness (Problem K) */

2013-05-15T06:08:31Z

Graphic Madness (Problem K)

Nattee: หน้าที่ถูกสร้างด้วย '= ภาคค่ำ = == Conservation (Problem J) == มีภาพเขียนอยู่รูปหนึ่งที่เ...'

2013-05-15T05:44:49Z

หน้าที่ถูกสร้างด้วย '= ภาคค่ำ = == Conservation (Problem J) == มีภาพเขียนอยู่รูปหนึ่งที่เ...'

หน้าใหม่

= ภาคค่ำ =

== Conservation (Problem J) ==
มีภาพเขียนอยู่รูปหนึ่งที่เก่ามาก และเราต้องการที่จะซ่อมแซ่มมันให้กลับมาดีดังเดิม มีห้องปฏิบัติการสองแห่งที่ต้องช่วยกันทำการซ่อมแซมนี้ การซ่อมแซมนั้นมีหลายขั้นตอน และเรารู้ว่าขั้นตอนไหนต้องทำที่ห้องปฏิบัติการใด อย่างไรก็ตาม เราไม่อยากที่จะขนย้ายรูปภาพไปมา เพราะมันบอบบางมาก ดังนั้น เราต้องวางแผนการทำงานให้มีการเคลื่อนย้ายรูปน้อยที่สุด ถ้าเป็นไปได้ เราอยากที่จะทำทุก ๆ ขั้นตอนที่ต้องใช้ห้องปฏิบัติการแรกให้เสร็จให้หมดก่อน แล้วค่อยขนย้ายไปห้องปฏิบัติการอีกแห่งหนึ่งเพื่อทำขั้นตอนที่เหลือ โชคร้ายที่ขั้นตอนหลายขั้นตอนมีความเกี่ยวข้องกัน คือ เราต้องทำงานบางขั้นตอนให้เสร็จก่อน ถึงจะทำขั้นตอนที่เกี่ยวข้องได้

หน้าที่ของคุณคือคำนวณจำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ เราจะถือว่าตอนเริ่มต้นนั้นรูปอยู่ที่ห้องปฏิบัติการใดก็ได้

=== ข้อมูลนำเข้า ===
บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
* บรรทัดแรกประกอบด้วยเลขจำนวนเต็มสองตัวคือ N (1 <= N <= 1 000 000) ซึ่งระบุจำนวนของขั้นตอนทั้งหมด และ M (0 <= M <= 1 000 000) ซึ่งระบุจำนวนคู่ของขั้นตอนที่เกี่ยวข้องกัน
* บรรทัดถัดมามีจำนวนเต็ม N ตัว โดยตัวที่ i จะมีค่า 1 ก็ต่อเมื่องานชิ้นที่ i นั้นต้องทำที่ห้องปฏิบัติการแรก และมีค่า 2 ถ้าต้องทำที่ห้องปฏิบัติการแห่งที่ 2
* หลังจากนั้นอีก M บรรทัดจะเป็นข้อมูลความเกี่ยวข้องกันของขั้นตอนต่าง ๆ โดยแต่ละบรรทัดมีจำนวนเต็มสองตัวคือ i,j (1 <= i,j <= N) ซึ่งระบุว่า งานขั้นที่ i ต้องทำเสร็จก่อนขั้นที่ j
รับประกันว่าความเกี่ยวข้องนั้นจะไม่ทำให้เราไม่สามารถทำงานให้เสร็จได้
=== ข้อมูลส่งออก ===
สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์จำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ
=== ตัวอย่าง ===
{| class="wikitable"
|-
|ข้อมูลนำเข้า
|ข้อมูลส่งออก
|-
| style="vertical-align:top;"|
1 
5 6 
1 2 1 2 1 
1 2 
1 3 
2 4 
3 4 
2 5 
3 5 
| style="vertical-align:top;"|
2
|}

== Word equations (Problem E) ==
คุณมีสายอักขระสองตัวคือ T และ P เราอยากจะรู้ว่าเราสามารถลบอักขระบางตำแหน่งออกจาก T เพื่อทำให้ T มีหน้าตาเหมือน P ได้หรือไม่ ยกตัวอย่างเช่น จากคำว่า programming เราสามารถลบอักขระบางตัวจนกลายเป็นคำว่า pong หรือ program หรือ roaming ได้ แต่ไม่สามารถกลายเป็นคำว่า map ได้ (เพราะว่าเราไม่สามารถสลับที่ตัวอักษรได้) ทั้ง T และ P นั้นมีเฉพาะตัวอักษรพิมพ์เล็กในภาษาอังกฤษเท่านั้น

แน่นอนว่าแค่นี้มันง่ายเกินไป T ที่ให้มานั้นจะอยู๋ในรูปแบบของระบบสมการ สมการแต่ละอันจะใช้สัญลักษณ์พิเศษ (ซึ่งก็คือคำที่ประกอบด้วยตัวพิมพ์ใหญ่ในภาษาอังกฤษเท่านั้น) โดยสัญลักษณ์แต่ละอันนั้นจะหมายถึงคำซึ่งประกอบด้วยตัวพิมพ์เล็กเท่านั้น สมการแต่ละอันจะอยู่ในรูปแบบใดรูปแบบหนึ่งต่อไปนี้เท่านั้น
* A = สายอักขระตัวพิมพ์เล็ก
* A = B + C
โดยที่ A, B, C คือสัญลักษณ์พิเศษใด ๆ และ + หมายถึงการเอาสายอักขระมาต่อกัน
รับประกันว่าระบบสมการจะมีคุณสมบัติดังนี้
* Unambiguous กล่าวคือ สำหรับสัญลักษณ์พิเศษ A ใด ๆ จะมีไม่เกินหนึ่งสมการที่มี A อยู่ด้านซ้ายของเครื่องหมาย = เท่านั้น
* Acyclic กล่าวคือ ถ้าเราเริ่มจากสัญลักษณ์พิเศษ A ใด ๆ แล้วทำการแทนที่ค่าในสมการไปเรื่อย ๆ เราจะไม่เจอสมการที่มี A อยู่ภายในอีก
ตัวอย่างเช่น
* START = FIRST + SECND
* FIRST = D + E
* SECND = F + E
* D = good
* E = times
* F = bad
สัญลักษณ์ START นั้นจะหมายถึงคำว่า goodtimesbadtimes

กำหนดให้มีสายอักขระ P และสัญลักษณ์เริ่มต้น S จากระบบสมการ จงพิจารณาว่าเราสามารถสร้าง P จาก S ได้หรือไม่

=== ข้อมูลนำเข้า ===
บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
* บรรทัดแรกประกอบด้วยจำนวนเต็ม K (1 <= K <= 500) ซึ่งระบุถึงจำนวนของสมการทั้งหมดในระบบสมการ
* หลังจากนั้นอีก K บรรทัดเป็น ระบบสมการต่าง ๆ ตามรูปแบบที่กำหนดไว้ข้างต้น โดยจะมีช่องว่างหนึ่งตัวคั่นระหว่างเครื่องหมาย +, = และคำต่าง ๆ โดยที่คำต่าง ๆ นั้นมีความยาวอยู่ระหว่าง 1 ถึง 5 ตัวอักษร (รวมทั้งคำที่เป็นสัญลักษณ์พิเศษด้วย)
* บรรทัดถัดมาจะมีคำหนึ่งคำซึ่งหมายถึงสัษลักษณ์พิเศษ S
* บรรทัดสุดท้ายจะมีสายอักขระไม่ว่าง ที่ยาวไม่เกิน 2000 ตัวอักษร ซึ่งระบุถึงสายอักขระ P

=== ข้อมูลส่งออก ===
สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์คำว่า YES ถ้าเราสามารถสร้าง P จาก S ได้ และให้พิมพ์คำว่า NO ในกรณีอื่น ๆ
=== ตัวอย่าง ===
{| class="wikitable"
|-
|ข้อมูลนำเข้า
|ข้อมูลส่งออก
|-
| style="vertical-align:top;"|
1 
6 
START = FIRST + SECND 
FIRST = D + E 
SECND = F + E 
D = good 
E = times 
F = bad 
START 
debate 
| style="vertical-align:top;"|
YES 
|}

== Graphic Madness (Problem K) ==
=== ข้อมูลนำเข้า ===
=== ข้อมูลส่งออก ===
=== ตัวอย่าง ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:39, 15 พฤษภาคม 2556
แถว 1:		แถว 1:
−	~~= ภาคค่ำ =~~
−
−	~~== Conservation (Problem J) ==~~
−	มีภาพเขียนอยู่รูปหนึ่งที่เก่ามาก และเราต้องการที่จะซ่อมแซ่มมันให้กลับมาดีดังเดิม มีห้องปฏิบัติการสองแห่งที่ต้องช่วยกันทำการซ่อมแซมนี้ การซ่อมแซมนั้นมีหลายขั้นตอน และเรารู้ว่าขั้นตอนไหนต้องทำที่ห้องปฏิบัติการใด อย่างไรก็ตาม เราไม่อยากที่จะขนย้ายรูปภาพไปมา เพราะมันบอบบางมาก ดังนั้น เราต้องวางแผนการทำงานให้มีการเคลื่อนย้ายรูปน้อยที่สุด ถ้าเป็นไปได้ เราอยากที่จะทำทุก ๆ ขั้นตอนที่ต้องใช้ห้องปฏิบัติการแรกให้เสร็จให้หมดก่อน แล้วค่อยขนย้ายไปห้องปฏิบัติการอีกแห่งหนึ่งเพื่อทำขั้นตอนที่เหลือ โชคร้ายที่ขั้นตอนหลายขั้นตอนมีความเกี่ยวข้องกัน คือ เราต้องทำงานบางขั้นตอนให้เสร็จก่อน ถึงจะทำขั้นตอนที่เกี่ยวข้องได้
−
−	หน้าที่ของคุณคือคำนวณจำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ เราจะถือว่าตอนเริ่มต้นนั้นรูปอยู่ที่ห้องปฏิบัติการใดก็ได้
−
−	~~=== ข้อมูลนำเข้า ===~~
−	บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
−	* บรรทัดแรกประกอบด้วยเลขจำนวนเต็มสองตัวคือ N (1 <= N <= 1 000 000) ซึ่งระบุจำนวนของขั้นตอนทั้งหมด และ M (0 <= M <= 1 000 000) ซึ่งระบุจำนวนคู่ของขั้นตอนที่เกี่ยวข้องกัน
−	* บรรทัดถัดมามีจำนวนเต็ม N ตัว โดยตัวที่ i จะมีค่า 1 ก็ต่อเมื่องานชิ้นที่ i นั้นต้องทำที่ห้องปฏิบัติการแรก และมีค่า 2 ถ้าต้องทำที่ห้องปฏิบัติการแห่งที่ 2
−	* หลังจากนั้นอีก M บรรทัดจะเป็นข้อมูลความเกี่ยวข้องกันของขั้นตอนต่าง ๆ โดยแต่ละบรรทัดมีจำนวนเต็มสองตัวคือ i,j (1 <= i,j <= N) ซึ่งระบุว่า งานขั้นที่ i ต้องทำเสร็จก่อนขั้นที่ j
−	รับประกันว่าความเกี่ยวข้องนั้นจะไม่ทำให้เราไม่สามารถทำงานให้เสร็จได้
−	~~=== ข้อมูลส่งออก ===~~
−	สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์จำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ
−	~~=== ตัวอย่าง ===~~
−	~~{\| class="wikitable"~~
−	\|-
−	~~\|ข้อมูลนำเข้า~~
−	~~\|ข้อมูลส่งออก~~
−	\|-
−	~~\| style="vertical-align:top;"\|~~
−	~~1<br />~~
−	~~5 6<br />~~
−	~~1 2 1 2 1<br />~~
−	~~1 2<br />~~
−	~~1 3<br />~~
−	~~2 4<br />~~
−	~~3 4<br />~~
−	~~2 5<br />~~
−	~~3 5<br />~~
−	~~\| style="vertical-align:top;"\|~~
−	2
−	\|}
−
−	~~== Word equations (Problem E) ==~~
−	คุณมีสายอักขระสองตัวคือ T และ P เราอยากจะรู้ว่าเราสามารถลบอักขระบางตำแหน่งออกจาก T เพื่อทำให้ T มีหน้าตาเหมือน P ได้หรือไม่ ยกตัวอย่างเช่น จากคำว่า programming เราสามารถลบอักขระบางตัวจนกลายเป็นคำว่า pong หรือ program หรือ roaming ได้ แต่ไม่สามารถกลายเป็นคำว่า map ได้ (เพราะว่าเราไม่สามารถสลับที่ตัวอักษรได้) ทั้ง T และ P นั้นมีเฉพาะตัวอักษรพิมพ์เล็กในภาษาอังกฤษเท่านั้น
−
−	แน่นอนว่าแค่นี้มันง่ายเกินไป T ที่ให้มานั้นจะอยู๋ในรูปแบบของระบบสมการ สมการแต่ละอันจะใช้สัญลักษณ์พิเศษ (ซึ่งก็คือคำที่ประกอบด้วยตัวพิมพ์ใหญ่ในภาษาอังกฤษเท่านั้น) โดยสัญลักษณ์แต่ละอันนั้นจะหมายถึงคำซึ่งประกอบด้วยตัวพิมพ์เล็กเท่านั้น สมการแต่ละอันจะอยู่ในรูปแบบใดรูปแบบหนึ่งต่อไปนี้เท่านั้น
−	* A = สายอักขระตัวพิมพ์เล็ก
−	* A = B + C
−	~~โดยที่ A, B, C คือสัญลักษณ์พิเศษใด ๆ และ + หมายถึงการเอาสายอักขระมาต่อกัน~~
−	~~รับประกันว่าระบบสมการจะมีคุณสมบัติดังนี้~~
−	* Unambiguous กล่าวคือ สำหรับสัญลักษณ์พิเศษ A ใด ๆ จะมีไม่เกินหนึ่งสมการที่มี A อยู่ด้านซ้ายของเครื่องหมาย = เท่านั้น
−	* Acyclic กล่าวคือ ถ้าเราเริ่มจากสัญลักษณ์พิเศษ A ใด ๆ แล้วทำการแทนที่ค่าในสมการไปเรื่อย ๆ เราจะไม่เจอสมการที่มี A อยู่ภายในอีก
−	~~ตัวอย่างเช่น~~
−	* START = FIRST + SECND
−	* FIRST = D + E
−	* SECND = F + E
−	* D = good
−	* E = times
−	* F = bad
−	~~สัญลักษณ์ START นั้นจะหมายถึงคำว่า goodtimesbadtimes~~
−
−	กำหนดให้มีสายอักขระ P และสัญลักษณ์เริ่มต้น S จากระบบสมการ จงพิจารณาว่าเราสามารถสร้าง P จาก S ได้หรือไม่
−
−	~~=== ข้อมูลนำเข้า ===~~
−	บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
−	* บรรทัดแรกประกอบด้วยจำนวนเต็ม K (1 <= K <= 500) ซึ่งระบุถึงจำนวนของสมการทั้งหมดในระบบสมการ
−	* หลังจากนั้นอีก K บรรทัดเป็น ระบบสมการต่าง ๆ ตามรูปแบบที่กำหนดไว้ข้างต้น โดยจะมีช่องว่างหนึ่งตัวคั่นระหว่างเครื่องหมาย +, = และคำต่าง ๆ โดยที่คำต่าง ๆ นั้นมีความยาวอยู่ระหว่าง 1 ถึง 5 ตัวอักษร (รวมทั้งคำที่เป็นสัญลักษณ์พิเศษด้วย)
−	* บรรทัดถัดมาจะมีคำหนึ่งคำซึ่งหมายถึงสัษลักษณ์พิเศษ S
−	* บรรทัดสุดท้ายจะมีสายอักขระไม่ว่าง ที่ยาวไม่เกิน 2000 ตัวอักษร ซึ่งระบุถึงสายอักขระ P
−
−	~~=== ข้อมูลส่งออก ===~~
−	สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์คำว่า YES ถ้าเราสามารถสร้าง P จาก S ได้ และให้พิมพ์คำว่า NO ในกรณีอื่น ๆ
−	~~=== ตัวอย่าง ===~~
−	~~{\| class="wikitable"~~
−	\|-
−	~~\|ข้อมูลนำเข้า~~
−	~~\|ข้อมูลส่งออก~~
−	\|-
−	~~\| style="vertical-align:top;"\|~~
−	~~1<br />~~
−	~~6<br />~~
−	~~START = FIRST + SECND<br />~~
−	~~FIRST = D + E<br />~~
−	~~SECND = F + E<br />~~
−	~~D = good<br />~~
−	~~E = times<br />~~
−	~~F = bad<br />~~
−	~~START<br />~~
−	~~debate<br />~~
−	~~\| style="vertical-align:top;"\|~~
−	~~YES<br />~~
−	\|}
−
−	~~== Who Wants to Live Forever (Problem B) ==~~
−	ศาสตร์ Digital Physics เป็นวิชาที่มีแนวคิดว่าจักรวาลของเรานั้นเป็นคอมพิวเตอร์ขนาดใหญ่ โดยที่เราเป็นเพียงโปรแกรมที่รันอยู่ในเครื่องคอมพิวเตอร์นั้นเท่านั้น
−
−	เราอยากจะช่วยพัฒนาศาสตร์ทางด้าน Digital Physics ให้ดียิ่งขึ้น โดยเราจะพิจารณาแบบจำลองของจักรวาลแบบหนึ่งว่าแบบจำลองนี้มีจุดจบหรือไม่ หรือว่ามีการเปลี่ยนแปลงไปเรื่อย ๆ ตลอดเวลา
−
−	จักรวาลนี้ประกอบด้วยบิตสตริงขนาด n ตัวอักษร (ตัวอักษรประกอบด้วย 1 หรือ 0 เท่านั้น) จักรวาลนี้เกิดขึ้นมาเป็นสายอักขระแบบหนึ่งทันที และหลังจากนั้นจักรวาลนี้จะเปลี่ยนแปลงตัวเองไปเรื่อย ๆ เป็นขั้น ๆ ไป โดยกฎของการเปลี่ยนแปลงนั้นเป็นดังนี้ สถานะของบิต ณ ตำแหน่งที่ i ในขั้นถัดไปนั้นขึ้นอยู่กับ บิต ณ ตำแหน่ง i-1 และ i+1 (ในกรณีที่ไม่มีบิต i-1 หรือ i+1 ให้ถือว่าบิตที่ไม่มีนั้นมีค่าเป็น 0) โดย บิตที่ i จะมีค่าเป็น 1 ก็ต่อเมื่อมี 1 อยู่เพียงอันเดียวเท่านั้นในตำแหน่งที่ i-1 และ i+1 ค่าของบิตในขั้นถัดไปจะคำนวณพร้อมกัน กล่าวคือ ค่าในขั้นถัดไปจะขึ้นอยู่กับค่าในขั้นปัจจุบันเท่านั้น
−
−	~~เราจะถือว่าจักรวาลนั้นตาย ถ้าบิตสตริงของจักรวาลนั้นมีแต่เลข 0~~
−
−	กำหนดสถานะของจักรวาล ณ จุดเริ่มต้นให้ จงคำนวณว่าจักรวาลดังกล่าวตาย หรือว่ามีการเปลี่ยนแปลงไปเรื่อย ๆ ตลอดเวลา
−
−
−	บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบประกอบด้วยสายอักขระของตัวเลข 0 หรือ 1 โดยมีความยาวอย่างน้อย 1 และยาวไม่เกิน 200 000 อักขระ
−	~~=== ข้อมูลส่งออก ===~~
−	สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์คำว่า LIVES ถ้าจักรวาลนั้นไม่ตาย และให้พิมพ์คำว่า DIES ถ้าจักรวาลนั้นมีสถานะสุดท้ายเป็นตาย
−	~~=== ตัวอย่าง ===~~
−	~~{\| class="wikitable"~~
−	\|-
−	~~\|ข้อมูลนำเข้า~~
−	~~\|ข้อมูลส่งออก~~
−	\|-
−	~~\| style="vertical-align:top;"\|~~
−	~~3<br />~~
−	~~01<br />~~
−	~~0010100<br />~~
−	~~11011<br />~~
−	~~\| style="vertical-align:top;"\|~~
−	~~LIVES<br />~~
−	~~DIES<br />~~
−	~~LIVES<br />~~
−	\|}

	== Graphic Madness (Problem K) ==		== Graphic Madness (Problem K) ==

@@ แถว 83: / แถว 83: @@
 | style="vertical-align:top;"|
 YES<br />
 |}

@@ แถว 86: / แถว 86: @@
 == Graphic Madness  (Problem K) ==
 === ข้อมูลนำเข้า ===
 === ข้อมูลส่งออก ===
 === ตัวอย่าง ===