การดําเนินการซือกีตีกา (toi11_segitiga)


Time limit:
1000 ms
Memory limit:
512 MB

โหราศาสตร์ลึกลับแห่งบุหงาตันหยงนคร มีวิธีการทํานายภัยพิบัติที่จะเกิดขึ้นกับบ้านเมืองโดยการเสี่ยงทายด้วยการเขย่ากระบอกที่มีแท่งไม้จํานวนมากบรรจุอยู่ และแท่งไม้แต่ละแท่งมีตัวเลข 0, 1 หรือ 2 ตัวใดตัวหนึ่งสลักไว้ การเสี่ยงทายแต่ละรอบจะมีการเขย่ากระบอกทั้งหมด N ครั้ง เพื่อให้แท่งไม้หลุดออกมาครั้งละหนึ่งแท่ง แล้วบันทึกผลที่ได้จากการเสี่ยงทายแต่ละรอบไว้เป็นสตริงซือกีตีกา (Segi Tiga String) ซึ่งประกอบไปด้วยตัวเลขบนแท่งไม้ที่ได้จากการเขย่าแต่ละครั้ง แต่ละค่าตัวเลขจะถูกคั่นด้วยสัญลักษณ์ ∇ หนึ่งตัว

วิธีการทํานายสตริงซือกีตีกาถูกบันทึกไว้ในตําราเก่าแก่บูกูกุโน โดยใช้การดําเนินการทางคณิตศาสตร์ที่ประกอบไปด้วยตัวดําเนินการซือกีตีกา (Segi Tiga operator) ซึ่งแทนด้วยสัญลักษณ์ ∇ และตัวถูกดําเนินการซือกีตีกา (Segi Tiga operand) ซึ่งเป้นสมาชิกของเซต {0,1,2} เท่านั้น การดําเนินการของตัวดําเนินการซือกีตีกาหนึ่งตัวจะต้องมีตัวถูกดําเนินการซือกีตีกาสองตัวเสมอ และผลลัพธ์ที่ได้ก็เป้นสมาชิกของเซต {0,1,2} ด้วย โดยผลลัพธ์ของสตริงซือกีตีกาที่มีตัวดําเนินการหนึ่งตัวแสดงในตารางที่ 1

ตารางที่ 1 ผลลัพธ์ของสตริงซือกีตีกา ที่มีตัวดําเนินการ 1 ตัว

ผลที่ได้จากการเสี่ยงทายแต่ละรอบจะเป็นสตริงซือกีตีกา ประกอบไปด้วยตัวดําเนินการซือกีตีกาอย่างน้อยหนึ่งตัว และตัวถูกดําเนินการซือกีตีกาอย่างน้อยสองตัว เช่น หากผลที่ได้จากรอบการเสี่ยงทายที่มีการเขย่ากระบอกสี่ครั้งเป็น 0 ∇ 2 ∇ 2 ∇ 1 จะได้สตริงซือกีตีกา ที่มีตัวดําเนินการซือกีตีกาสามตัว และตัวถูกดําเนินการซือกีตีกาสี่ตัว

ผลลัพธ์ของสตริงซือกีตีกาขึ้นอยู่กับลําดับการทํางานของตัวดําเนินการ โดยสตริงซือกีตีกาที่อยู่ในวงเล็บในสุดต้องดําเนินการก่อน ตัวอย่างเช่น

  • ((0 ∇ 2) ∇ (2 ∇ 1)) ได้ผลลัพธ์เป็น 0
  • ((0 ∇ (2 ∇ 2)) ∇ 1) ได้ผลลัพธ์เป็น 1

โหรใหญ่ประจําบุหงาตันหยงนครเป็นผู้ศึกษาและใช้ตําราบูกูกุโนอย่างลึกซึ้งทําให้ทราบดีว่าการทํานายด้วยผลลัพธ์ของสตริงซือกีตีกาเป็นสิ่งที่แม่นยํา และทุกคนในนครต่างรอคอย หากผลลัพธ์ของสตริงซือกีตีกาที่ได้มาด้วยลําดับการทํางานลําดับใดลําดับหนึ่งเป็น 0 ทํานายได้ว่าจะมีภัยพิบัติเกิดขึ้น จําเป็นต้องมีการเตรียมป้องกันเมืองให้รอดพ้นจากหายนะที่จะตามมา

ขอให้นักเรียนเขียนโปรแกรมเพื่อช่วยตรวจสอบว่าผลลัพธ์ของสตริงซือกีตีกามีโอกาสเป็น 0 หรือไม่ 

Input

มีจํานวน 20 บรรทัด แต่ละบรรทัดประกอบด้วยจํานวนเต็ม ni และสตริง si ซึ่งถูกคั่นด้วยช่องว่างหนึ่งช่องว่าง โดย ni แสดงจํานวนครั้งที่เขย่าในแต่ละรอบของการเสี่ยงทายที่ i กําหนดให้ 1 ≤ i ≤ 20 และ 2 ≤ ni ≤ 255

สําหรับ si แสดงชุดของตัวถูกดําเนินการที่มีความยาว ni ประกอบด้วยจํานวนเต็ม 0, 1 หรือ 2 เท่านั้น เช่น si เท่ากับ 111102 แทนสตริงซือกีตีกา 1 ∇ 1 ∇ 1 ∇ 1 ∇ 0 ∇ 2

Output

มี 20 บรรทัด โดยที่บรรทัดที่ i (1 ≤ i ≤ 20) แสดงข้อความ “yes” ถ้ามีลําดับการทํางานของตัวดําเนินการที่ทําให้ผลลัพธ์ของสตริงซือกีตีกาที่แทนด้วยสตริง si มีค่าเป็น 0 หรือ ข้อความ “no” ถ้าไม่มีลําดับการทํางานของตัวดําเนินการใดๆ ทําให้ผลลัพธ์ของสตริงซือกีตีกาที่แทนด้วยสตริง si มีค่าเป็น 0

Constrains/Subtasks

อย่างน้อย 30% ของข้อมูลทดสอบ ni ≤ 10

Editor:

Source: Thailand Olympiad in Informatics 2015 (TOI11 / TOI 2015)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None