2002 : Zoo
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 16 megabyte(s)
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 16 megabyte(s)
สวนสัตว์วงกลม (Great Circular Zoo) เป็นความภาคภูมิใจล่าสุดของหมู่ชนภาคพื้นเอเชียแปซิฟิก สวนสัตว์แห่งนี้ตั้งอยู่บนเกาะเล็กๆแห่งหนึ่งในมหาสมุทรแปซิฟิก บนเกาะนี้ประกอบด้วยกรงสัตว์ต่างๆวางเป็นวงกลม โดยแต่ละกรงจะมีสัตว์หาดูได้ยากที่แตกต่างกัน ซึ่งแสดงดังภาพด้านล่าง
คุณได้รับมอบหมายให้เป็นประชาสัมพันธ์ของสวนสัตว์แห่งนี้ คุณจึงมีหน้าที่ทำให้ประชาชนที่มาชมสวนสัตว์มีความสุขมากที่สุดเท่าที่จะเป็นไปได้ เมื่อรถโรงเรียนที่บรรทุกเด็กเต็มรถมาถึง แน่นอนว่าคุณอยากที่จะทำให้เด็กเหล่านั้นพึงพอใจ อย่างไรก็ตาม งานนี้ไม่ง่ายอย่างที่คิด เพราะว่าพฤติกรรมของเด็กแต่ละคนในการชอบสัตว์และกลัวสัตว์ไม่เหมือนกัน ตัวอย่างเช่น อเล็กซ์ชอบลิงและโคอาล่าเพราะว่ามันน่ารักแต่กลัวสิงโตเพราะว่าเขี้ยวมันแหลม ในขณะที่ พอลลี่ ชอบสิงโตเพราะแผงคอสวยแต่กลัวโคอะล่าเพราะว่ามันกลิ่นเหม็น
คุณมีทางเลือกที่จะนำสัตว์บางตัวออกไปจากกรง เพื่อที่จะทำให้เด็กบางคนไม่ต้องกลัว อย่างไรก็ตามคุณไม่สามารถเอาสัตว์ออกได้ทุกตัวเพราะมิฉะนั้นก็คงไม่มีสัตว์หลงเหลือในสวนสัตว์ให้เด็กดูแม้แต่ตัวเดียว คุณจึงต้องเอาสัตว์ออกเพียงแค่บางตัวเพื่อทำให้จำนวนเด็กที่มีความสุขมากที่สุดเท่าที่จะเป็นไปได้
เด็กแต่ละคนจะยืนด้านนอกวงกลม ซึ่งในขณะใดขณะหนึ่งเด็กแต่ละคนจะมีมุมมองให้เห็นสัตว์ห้ากรงติดกัน คุณจะได้รับข้อมูลว่าเด็กคนใดกลัวและชอบสัตว์ชนิดใด คุณจะรู้ว่าเด็กมีความสุขถ้า
สมมติว่า คุณนำสัตว์จากกรงที่ ๔ และ ๑๒ ออก นั่นจะทำให้ อเล็กซ์และกาชูมีความสุข เพราะว่ามีสัตว์อย่างน้อยหนึ่งตัวที่เด็กทั้งสองคนกลัวได้ถูกนำออกไปจากกรง นอกจากนี้ ชัยธัญญาก็ยังมีความสุขเพราะว่ากรงที่ ๖ และ ๘ ก็ยังมีสัตว์ที่ตนชอบอยู่ อย่างไรก็ตาม ทั้งพอลลี่และหวานก็คงจะไม่มีความสุขเนื่องจากไม่เห็นชนิดสัตว์ที่ตัวเองชอบแล้วยังเห็นแต่ชนิดที่ทั้งสองคนกลัว สรุปก็คือการนำสัตว์ออกจากกรงตามตัวอย่างนี้ทำให้เด็กมีความสุข ๓ คน
ลองดูใหม่เอาสัตว์เข้าไปในกรงใหม่ แล้วสมมุติว่าคุณเอาสัตว์ออกจากกรงที่ ๔ และ ๖ แทน อเล็กซ์ และพอลลี่จะมีความสุขเพราะว่าสัตว์ที่กลัวในกรงที่ ๔ และ ๖ ได้ถูกเอาออกไปแล้ว ชัยธัญญาก็มีความสุขด้วยเนื่องจากแม้ว่าสัตว์ในกรงที่ ๖ ถูกเอาออกไป เขาก็ยังเห็นสัตว์ที่เขารักในกรงที่ ๘ ทำนองเดียวกัน หวานก็มีความสุขเพราะว่าเธอเห็นเฉพาะสัตว์ในกรงที่ ๑๒ ซึ่งเป็นสัตว์ที่เธอชอบ ในกรณีนี้คนที่ไม่มีความสุขมีคนเดียวคือ กาชู
สุดท้าย สมมติว่าคุณเอาสัตว์ทั้งหมดกลับเข้าไปในกรงอีกครั้งและเอาสัตว์ออกจากกรงที่ ๑๓ คราวนี้กาชูจะมีความสุขเพราะว่าสัตว์ที่เขาไม่กลัวหนึ่งตัวได้ถูกเอาออกไปจากกรง ส่วนอเล็กซ์ พอลลี่ ชัยธัญญา และ หวาน ก็มีความสุขเหมือนกันเนื่องจากว่าสามารถมองเห็นสัตว์ที่ตัวเองชอบได้อย่างน้อยหนึ่งตัว ดังนั้นวิธีการนี้เป็นวิธีที่ทำให้มีจำนวนเด็กมีความสุขมากที่สุดนั่นคือ ทั้งห้าคนมีความสุข
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัว N C โดยที่ N คือจำนวนของกรงสัตว์ (1 ≤ N ≤ 10 000) และ C เป็นจำนวนของนักเรียน (1≤C≤50 000) หมายเลขกรงจะนับตามเข็มนาฬิกาจาก 1,2,…, N
ต่อจากนั้น C บรรทัด จะเป็นรายละเอียดของเด็กแต่ละคน โดยมีรูปแบบคือ
E F L X1 X2 … XF Y1 Y2 … YL
โดยที่
ข้อมูลส่งออก
มีจำนวนเต็มหนึ่งตัว เป็นค่าที่เป็นจำนวนเด็กที่มีความสุขที่มากที่สุด
ที่มา: Asia-Pacific Informatics Olympiad
ความช่วยเหลือ: Hint[1]
คุณได้รับมอบหมายให้เป็นประชาสัมพันธ์ของสวนสัตว์แห่งนี้ คุณจึงมีหน้าที่ทำให้ประชาชนที่มาชมสวนสัตว์มีความสุขมากที่สุดเท่าที่จะเป็นไปได้ เมื่อรถโรงเรียนที่บรรทุกเด็กเต็มรถมาถึง แน่นอนว่าคุณอยากที่จะทำให้เด็กเหล่านั้นพึงพอใจ อย่างไรก็ตาม งานนี้ไม่ง่ายอย่างที่คิด เพราะว่าพฤติกรรมของเด็กแต่ละคนในการชอบสัตว์และกลัวสัตว์ไม่เหมือนกัน ตัวอย่างเช่น อเล็กซ์ชอบลิงและโคอาล่าเพราะว่ามันน่ารักแต่กลัวสิงโตเพราะว่าเขี้ยวมันแหลม ในขณะที่ พอลลี่ ชอบสิงโตเพราะแผงคอสวยแต่กลัวโคอะล่าเพราะว่ามันกลิ่นเหม็น
คุณมีทางเลือกที่จะนำสัตว์บางตัวออกไปจากกรง เพื่อที่จะทำให้เด็กบางคนไม่ต้องกลัว อย่างไรก็ตามคุณไม่สามารถเอาสัตว์ออกได้ทุกตัวเพราะมิฉะนั้นก็คงไม่มีสัตว์หลงเหลือในสวนสัตว์ให้เด็กดูแม้แต่ตัวเดียว คุณจึงต้องเอาสัตว์ออกเพียงแค่บางตัวเพื่อทำให้จำนวนเด็กที่มีความสุขมากที่สุดเท่าที่จะเป็นไปได้
เด็กแต่ละคนจะยืนด้านนอกวงกลม ซึ่งในขณะใดขณะหนึ่งเด็กแต่ละคนจะมีมุมมองให้เห็นสัตว์ห้ากรงติดกัน คุณจะได้รับข้อมูลว่าเด็กคนใดกลัวและชอบสัตว์ชนิดใด คุณจะรู้ว่าเด็กมีความสุขถ้า
- อย่างน้อยสัตว์ที่เด็กกลัวหนึ่งตัว ถูกเอาออกไปจากมุมที่เด็กมองเห็น หรือ
- อย่างน้อยสัตว์ที่เด็กชอบหนึ่งตัวไม่ถูกเอาออกไปจากมุมที่เด็กมองเห็น
| เด็ก |
กรงที่มองเห็นได้ | สัตว์ที่กลัว | สัตว์ที่ชอบ |
| อเล็กซ์ (Alex) | 2, 3, 4, 5, 6 | กรง 4 | กรง 2, 6 |
| พอลลี่ (Polly) | 3, 4, 5, 6, 7 | กรง 6 | กรง 4 |
| ชัยธัญญา (Chaitanya) | 6, 7, 8, 9, 10 | กรง 9 | กรง 6, 8 |
| หวาน (Hwan) | 8, 9, 10, 11, 12 | กรง 9 | กรง 12 |
| กาชู (Ka-Shu) | 12, 13, 14, 1, 2 | กรง 12, 13, 2 | - |
สมมติว่า คุณนำสัตว์จากกรงที่ ๔ และ ๑๒ ออก นั่นจะทำให้ อเล็กซ์และกาชูมีความสุข เพราะว่ามีสัตว์อย่างน้อยหนึ่งตัวที่เด็กทั้งสองคนกลัวได้ถูกนำออกไปจากกรง นอกจากนี้ ชัยธัญญาก็ยังมีความสุขเพราะว่ากรงที่ ๖ และ ๘ ก็ยังมีสัตว์ที่ตนชอบอยู่ อย่างไรก็ตาม ทั้งพอลลี่และหวานก็คงจะไม่มีความสุขเนื่องจากไม่เห็นชนิดสัตว์ที่ตัวเองชอบแล้วยังเห็นแต่ชนิดที่ทั้งสองคนกลัว สรุปก็คือการนำสัตว์ออกจากกรงตามตัวอย่างนี้ทำให้เด็กมีความสุข ๓ คน
ลองดูใหม่เอาสัตว์เข้าไปในกรงใหม่ แล้วสมมุติว่าคุณเอาสัตว์ออกจากกรงที่ ๔ และ ๖ แทน อเล็กซ์ และพอลลี่จะมีความสุขเพราะว่าสัตว์ที่กลัวในกรงที่ ๔ และ ๖ ได้ถูกเอาออกไปแล้ว ชัยธัญญาก็มีความสุขด้วยเนื่องจากแม้ว่าสัตว์ในกรงที่ ๖ ถูกเอาออกไป เขาก็ยังเห็นสัตว์ที่เขารักในกรงที่ ๘ ทำนองเดียวกัน หวานก็มีความสุขเพราะว่าเธอเห็นเฉพาะสัตว์ในกรงที่ ๑๒ ซึ่งเป็นสัตว์ที่เธอชอบ ในกรณีนี้คนที่ไม่มีความสุขมีคนเดียวคือ กาชู
สุดท้าย สมมติว่าคุณเอาสัตว์ทั้งหมดกลับเข้าไปในกรงอีกครั้งและเอาสัตว์ออกจากกรงที่ ๑๓ คราวนี้กาชูจะมีความสุขเพราะว่าสัตว์ที่เขาไม่กลัวหนึ่งตัวได้ถูกเอาออกไปจากกรง ส่วนอเล็กซ์ พอลลี่ ชัยธัญญา และ หวาน ก็มีความสุขเหมือนกันเนื่องจากว่าสามารถมองเห็นสัตว์ที่ตัวเองชอบได้อย่างน้อยหนึ่งตัว ดังนั้นวิธีการนี้เป็นวิธีที่ทำให้มีจำนวนเด็กมีความสุขมากที่สุดนั่นคือ ทั้งห้าคนมีความสุข
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัว N C โดยที่ N คือจำนวนของกรงสัตว์ (1 ≤ N ≤ 10 000) และ C เป็นจำนวนของนักเรียน (1≤C≤50 000) หมายเลขกรงจะนับตามเข็มนาฬิกาจาก 1,2,…, N
ต่อจากนั้น C บรรทัด จะเป็นรายละเอียดของเด็กแต่ละคน โดยมีรูปแบบคือ
E F L X1 X2 … XF Y1 Y2 … YL
โดยที่
- E คือ หมายเลขกรงแรกที่เด็กมองเห็น (1≤E≤N) หรืออาจกล่าวได้ว่า เด็กสามารถมองเห็นกรงหมายเลข E, E+1, E+2, E+3, และ E+4 สังเกตว่าหมายเลขของกรงที่มีค่ามากกว่า N จะถูกแปลงกลับให้เป็นหมายเลขของกรงตามวงกลม เช่น ถ้า N=14 และ E=13 เด็กจะเห็นกรงหมายเลข 13 14 1 2 และ 3
- F คือจำนวนของสัตว์ที่เด็กกลัว และ L คือจำนวนของสัตว์ที่เด็กชอบ
- X1… XF เก็บหมายเลขของสัตว์ที่เด็กกลัว (1 ≤ X1,…,XF ≤ N).
- Y1…YL เก็บหมายเลขสัตว์ที่เด็กชอบ (1 ≤ Y1,…,YL ≤ N)
- X1…XF, Y1…YL เป็นหมายเลขกรงที่เด็กจะมองเห็นได้ ซึ่งค่าเหล่านี้จะมีค่าที่ไม่ซ้ำกัน
ข้อมูลส่งออก
มีจำนวนเต็มหนึ่งตัว เป็นค่าที่เป็นจำนวนเด็กที่มีความสุขที่มากที่สุด
ที่มา: Asia-Pacific Informatics Olympiad
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 14 5 2 1 2 4 2 6 3 1 1 6 4 6 1 2 9 6 8 8 1 1 9 12 12 3 0 12 13 2 | 5 |
| 12 7 1 1 1 1 5 5 1 1 5 7 5 0 3 5 7 9 7 1 1 7 9 9 1 1 9 11 9 3 0 9 11 1 11 1 1 11 1 | 6 |
ความช่วยเหลือ: Hint[1]
กำลังออนไลน์: 6 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)