B-თამაში

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, შესარჩევი


ანდრო იდაძეს დაებადა ახალი თამაშის იდეა ორი მოთამაშისათვის. თამაშისათვის საკმარისია ცარცი და დაფა. დაფაზე წერენ N (2≤N≤20) ცალ მთელ დადებით რიცხვს. თითოეული რიცხვის მნიშვნელობა არ აღემატება 1,000,000-ს. მოთამაშეები რიგ-რიგობით აკეთებენ სვლებს და ყოველ სვლაზე უფლება აქვთ, დაფიდან წაშალონ მხოლოდ ერთი რიცხვი და მის ადგილას ჩაწერონ დაფაზე დარჩენილი რიცხვებიდან ერთ-ერთი, რომელიც აუცილებლად ნაკლები უნდა იყოს წაშლილ რიცხვზე. მაგალითად, ვთქვათ დაფაზე წერია სამი რიცხვები – 1, 3 და 5. ამ სიტუაციაში შესაძლებელია 3 განსხვავებული სვლა:
 
    1) 3-იანი შევცვალოთ 1-ით. მიიღება 1, 1 და 5;
    2) 5-იანი შევცვალოთ 3-ით. მიიღება 1, 3 და 3;
    3) 5-იანი შევცვალოთ 1-ით. მიიღება 1, 3 და 1.
 
    მოთამაშე, რომელიც სვლის გაკეთებას ვეღარ მოახერხებს, დამარცხებულად ითვლება.
    ანდროს აინტერესებს, ყოველთვის მოიგებს თუ არა პირველი სვლის გაკეთების შემთხვევაში. დაწერეთ პროგრამა, რომელიც მოცემული რიცხვებისათვის დაადგენს არსებობს თუ არა მომგებიანი სტრატეგია იმ მოთამაშისათვის, რომელიც იწყებს თამაშს.
 
    შემავალი მონაცემები: შემავალი ფაილის პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი N – დაფაზე დაწერილი რიცხვების რაოდენობა. მეორე სტრიქონში მოცემულია ჰარით გაყოფილი N ცალი მთელი დადებითი რიცხვი 1-დან მილიარდამდე.
 
    გამომავალი მონაცემები: გამომავალი ფაილის ერთადერთი სტრიქონი უნდა შეიცავდეს ერთ მთელ რიცხვს: 1-ს ან 0-ს. 1 უნდა გამოიტანოთ იმ შემთხვევაში, თუკი არსებობს მომგებიანი სტრატეგია პირველი სვლის გამკეთებელი მოთამაშისათვის, ხოლო თუკი ასეთი სტრატეგია არ არსებობს – გამოიტანეთ 0.



მაგალითები

შესატანი მონაცემები
4 1 2 3 4 დაკოპირება
გამოსატანი მონაცემები
0 დაკოპირება
შესატანი მონაცემები
5 1 1 1 2 3 დაკოპირება
გამოსატანი მონაცემები
1 დაკოპირება