2000 : Mobiles
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
คุณถูกขอร้องให้ซื้อของขวัญให้กับลูกของพี่ชายชื่อ ไอค์ อย่างไรก็ตามคุณสังเกตเห็นว่า ไอค์มีรสนิยมเฉพาะในเรื่องของขวัญกล่าวคือไอค์ชอบเฉพาะทุกๆอย่างที่ไอค์สามารถจัดเรียงลำดับได้
คุณพบร้านขายของแห่งหนึ่งซึ่งขายโมบาย ซึ่งเป็นการตกแต่งคล้ายกับปลาตะเพียนแขวนของไทยที่เป็นชั้นๆ แขวนจากเพดานลงมา โมบายแต่ละชุดประกอบด้วยแกนแนวนอนหลายๆแกนโดยที่ปลายทั้งสองด้านของแกนมีเส้นลวดผูกแนวดิ่งอยู่ติดกับแกนหรือติดกับของเล่น ตัวอย่างของโมบายแสดงไว้ดังรูปด้านล่างนี้
เพื่อให้พี่ชายของคุณพอใจ คุณจำเป็นที่ต้องหาโมบาย ที่สามารถปรับเปลี่ยนรูปแบบได้เพื่อที่จะให้
ในขณะที่คุณกำลังฝึกฝนสำหรับการแข่งขันคอมพิวเตอร์โอลิมปิก คุณตัดสินใจที่จะฝึกทักษะโดยออกแบบ ขั้นตอนวิธี ในการทดสอบว่าจากโมบาย ที่ให้ไปนั้นสามารถปรับเปลี่ยนเป็นของขวัญที่ไอค์ ชอบได้
ในตัวอย่างรูปด้านบน ไอค์ ไม่ชอบ โมบายแบบนี้ แม้ว่ามันจะสอดคล้องเงื่อนไขที่ 1 แต่ไม่เข้าเงื่อนไขข้อที่ 2 เนื่องจากของเล่นที่ปลายด้านซ้ายสุดอยู่สูงกว่าของเล่นที่อยู่ทางด้านขวามือ
อย่างไรก็ตาม โมบายนี้สามารถปรับเปลี่ยนให้เป็นแบบที่ ไอค์ ชอบได้ โดยการสลับที่เป็นไปตาม
รูปที่ ๓ อาจมองได้ว่าเป็นรูปแบบ โมบายที่เป็นไปตามความต้องการของไอค์ ของเล่นที่ติดอยู่ทุกชิ้นต้องมีความแตกต่างของชั้นไม่เกินหนึ่งระดับ ของเล่นที่อยู่ในระดับที่ต่ำกว่าจะอยู่ไปทางซ้ายของของเล่นที่อยู่ระดับที่สูงกว่า
งานของคุณคือจากข้อมูลของ โมบายที่ได้ให้หาจำนวนครั้งที่น้อยที่สุดในการสลับที่กันของแกนที่ทำให้ได้รูปแบบที่ ไอค์ พึงพอใจ (ถ้ามีรูปแบบนั้นอยู่) คุณยังมั่นใจได้ด้วยว่าของเล่นสองข้างของแกนจะไม่มีการสลับที่กันเอง
ข้อมูลนำเข้า
บรรทัดแรก เป็นตัวเลขจำนวนเต็ม n มีค่าอยู่ระหว่าง (1 ≤ n ≤ 100 000) ซึ่งแสดงถึงจำนวนแกนใน โมบายแกนจะถูกกำหนดตัวเลขตั้งแต่ 1,2,…,n
บรรทัดต่อมาอีก n บรรทัด เป็นการบรรยายถึงการเชื่อมต่อกันของแกนแต่ละอัน เช่น บรรทัดที่ i ของกลุ่มบรรทัดในส่วนนี้แสดงถึงแกนหมายเลข i แต่ละบรรทัดจะมีตัวเลขจำนวนเต็ม 2 ตัว l และ r แยกกันด้วยช่องว่างหนึ่งช่อง ซึ่งจะเป็นตัวที่บอกว่ามีอะไรแขวนอยู่ทางด้านซ้ายและด้านขวาของแกนนั้น ถ้ามีของเล่นแขวนอยู่ภายใต้แกนนี้ค่าของ l และ r จะมีค่าเป็น -1 ถ้าไม่เช่นนั้นค่าตัวเลข l และ r จะหมายถึงแกนที่แขวนอยู่ภายใต้แกนนั้น
ถ้ามีแกนใดที่อยู่ใต้แกน i, แกนเหล่านั้นจะต้องมีหมายเลขแกนมากกว่า i เสมอ และแกนหมายเลข 1 เป็นแกนเดียวที่อยู่บนสุดของโมบาย
ข้อมูลส่งออก
ข้อมูลส่งออกประกอบด้วยตัวเลขจำนวนเต็มหนึ่งตัวในบรรทัดเดียวที่ให้จำนวนครั้งที่น้อยที่สุดในการสลับที่กันของแกนที่ปรับเปลี่ยน โมบายให้ได้รูปแบบตามเงื่อนไขของไอค์ ถ้าไม่มีรูปแบบดังกล่าวข้อมูลส่งออกจะมีค่าเป็นจำนวนเต็ม -1
ที่มา: Asia-Pacific Informatics Olympiad 2007
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
คุณพบร้านขายของแห่งหนึ่งซึ่งขายโมบาย ซึ่งเป็นการตกแต่งคล้ายกับปลาตะเพียนแขวนของไทยที่เป็นชั้นๆ แขวนจากเพดานลงมา โมบายแต่ละชุดประกอบด้วยแกนแนวนอนหลายๆแกนโดยที่ปลายทั้งสองด้านของแกนมีเส้นลวดผูกแนวดิ่งอยู่ติดกับแกนหรือติดกับของเล่น ตัวอย่างของโมบายแสดงไว้ดังรูปด้านล่างนี้
เพื่อให้พี่ชายของคุณพอใจ คุณจำเป็นที่ต้องหาโมบาย ที่สามารถปรับเปลี่ยนรูปแบบได้เพื่อที่จะให้
- ของเล่นสองชิ้นใดๆ จะอยู่ที่ระดับเดียวกัน (เชื่อมจากเพดานที่จำนวนของแกนเท่ากัน) หรือต่างกันได้ไม่เกินหนึ่งระดับ
- สำหรับของเล่นที่ต่างกันหนึ่งระดับนี้ของเล่นที่อยู่ทางด้านซ้ายจะอยู่ต่ำกว่าของเล่นที่อยู่ทางด้านขวา
ในขณะที่คุณกำลังฝึกฝนสำหรับการแข่งขันคอมพิวเตอร์โอลิมปิก คุณตัดสินใจที่จะฝึกทักษะโดยออกแบบ ขั้นตอนวิธี ในการทดสอบว่าจากโมบาย ที่ให้ไปนั้นสามารถปรับเปลี่ยนเป็นของขวัญที่ไอค์ ชอบได้
ในตัวอย่างรูปด้านบน ไอค์ ไม่ชอบ โมบายแบบนี้ แม้ว่ามันจะสอดคล้องเงื่อนไขที่ 1 แต่ไม่เข้าเงื่อนไขข้อที่ 2 เนื่องจากของเล่นที่ปลายด้านซ้ายสุดอยู่สูงกว่าของเล่นที่อยู่ทางด้านขวามือ
อย่างไรก็ตาม โมบายนี้สามารถปรับเปลี่ยนให้เป็นแบบที่ ไอค์ ชอบได้ โดยการสลับที่เป็นไปตาม
- ขั้นแรก ปลายทางด้านซ้ายและขวาของแกนสลับที่กันซึ่งเป็นผลให้แกนหมายเลข 2 และแกนหมายเลข 3 เปลี่ยนที่กันดังแสดงไว้ในรูปที่ ๒
- ขั้นที่สองและเป็นขั้นสุดท้ายปลายทางซ้ายและขวาของแกนที่ 2 สลับที่กันและของเล่นจะอยู่ที่ปลายด้านขวาของแกนที่ 2 ดังแสดงไว้ในรูปที่ ๓
รูปที่ ๓ อาจมองได้ว่าเป็นรูปแบบ โมบายที่เป็นไปตามความต้องการของไอค์ ของเล่นที่ติดอยู่ทุกชิ้นต้องมีความแตกต่างของชั้นไม่เกินหนึ่งระดับ ของเล่นที่อยู่ในระดับที่ต่ำกว่าจะอยู่ไปทางซ้ายของของเล่นที่อยู่ระดับที่สูงกว่า
งานของคุณคือจากข้อมูลของ โมบายที่ได้ให้หาจำนวนครั้งที่น้อยที่สุดในการสลับที่กันของแกนที่ทำให้ได้รูปแบบที่ ไอค์ พึงพอใจ (ถ้ามีรูปแบบนั้นอยู่) คุณยังมั่นใจได้ด้วยว่าของเล่นสองข้างของแกนจะไม่มีการสลับที่กันเอง
ข้อมูลนำเข้า
บรรทัดแรก เป็นตัวเลขจำนวนเต็ม n มีค่าอยู่ระหว่าง (1 ≤ n ≤ 100 000) ซึ่งแสดงถึงจำนวนแกนใน โมบายแกนจะถูกกำหนดตัวเลขตั้งแต่ 1,2,…,n
บรรทัดต่อมาอีก n บรรทัด เป็นการบรรยายถึงการเชื่อมต่อกันของแกนแต่ละอัน เช่น บรรทัดที่ i ของกลุ่มบรรทัดในส่วนนี้แสดงถึงแกนหมายเลข i แต่ละบรรทัดจะมีตัวเลขจำนวนเต็ม 2 ตัว l และ r แยกกันด้วยช่องว่างหนึ่งช่อง ซึ่งจะเป็นตัวที่บอกว่ามีอะไรแขวนอยู่ทางด้านซ้ายและด้านขวาของแกนนั้น ถ้ามีของเล่นแขวนอยู่ภายใต้แกนนี้ค่าของ l และ r จะมีค่าเป็น -1 ถ้าไม่เช่นนั้นค่าตัวเลข l และ r จะหมายถึงแกนที่แขวนอยู่ภายใต้แกนนั้น
ถ้ามีแกนใดที่อยู่ใต้แกน i, แกนเหล่านั้นจะต้องมีหมายเลขแกนมากกว่า i เสมอ และแกนหมายเลข 1 เป็นแกนเดียวที่อยู่บนสุดของโมบาย
ข้อมูลส่งออก
ข้อมูลส่งออกประกอบด้วยตัวเลขจำนวนเต็มหนึ่งตัวในบรรทัดเดียวที่ให้จำนวนครั้งที่น้อยที่สุดในการสลับที่กันของแกนที่ปรับเปลี่ยน โมบายให้ได้รูปแบบตามเงื่อนไขของไอค์ ถ้าไม่มีรูปแบบดังกล่าวข้อมูลส่งออกจะมีค่าเป็นจำนวนเต็ม -1
ที่มา: Asia-Pacific Informatics Olympiad 2007
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 6 2 3 -1 4 5 6 -1 -1 -1 -1 -1 -1 | 2 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)