4242 - perle

Graniţa nu se trece uşor. Asta pentru că Balaurul Arhirel (mare pasionat de informatică) nu lasă pe nimeni să treacă decât după ce răspunde la nişte întrebări. În acea ţară există trei tipuri de perle normale (le vom nota cu 1, 2 şi 3) şi trei tipuri de perle magice (le vom nota cu A, B şi C). Perlele magice sunt deosebite prin faptul că se pot transforma în alte perle (una sau mai multe, normale sau magice). Perla magică de tipul A se poate transforma în orice perlă normală (una singură). Perla magică de tipul B se poate transforma într-o perlă normală de tipul 2 şi una magică de tipul B, sau într-o perlă normală de tipul 1, una magică de tipul A, una normală de tipul 3, una magică de tipul A şi una magică de tipul C. Perla magică de tipul C se poate transforma într-o perlă normală de tipul 2 sau într-o perlă normală de tipul 3, una magică de tipul B şi una magică de tipul C sau într-o perlă normală de tipul 1, una normală de tipul 2 şi una magică de tipul A. Ca să rezumăm cele de mai sus putem scrie: A -> 1 | 2 | 3 B -> 2B | 1A3AC C -> 2 | 3BC | 12A Balaurul Arhirel ne lasă la început să ne alegem o perlă magică (una singură), iar apoi folosind numai transformările de mai sus trebuie să obţinem un anumit şir de perle normale. Când o perlă magică se transformă, perlele din stânga şi din dreapta ei rămân la fel (şi în aceeaşi ordine). De asemenea ordinea perlelor rezultate din transformare este chiar cea prezentată mai sus. De exemplu, dacă balaurul ne cere să facem şirul de perle 21132123, putem alege o perlă magică de tipul B şi următorul şir de transformări: B -> 2B -> 21A3AC -> 21A3A12A -> 21132123. Întrucât Balaurul nu are prea multă răbdare, el nu ne cere decât să spunem dacă se poate sau nu obţine şirul respectiv de perle.

Cerința

Să se determine pentru fiecare şir de intrare dacă se poate obţine prin transformările de mai sus sau nu (alegând orice primă perlă magică, la fiecare şir).

Date de intrare

Fișierul de intrare perlein.txt are următoarea structură: pe prima linie numărul N, reprezentând numărul de şiruri din fişierul de intrare urmează N linii; a i-a linie dintre cele N descrie şirul i, printr-o succesiune de numere naturale despărţite de câte un spaţiu. Primul număr reprezintă lungimea şirului L[i], iar următoarele L[i] numere sunt tipurile de perle normale, în ordine, de la stânga la dreapta.

Date de ieșire

Fișierul de ieșire perleout.txt va conţine N linii. Pe linia i se va scrie un singur număr 1 sau 0 (1 dacă se poate obţine şirul respectiv – al i-lea – şi 0 dacă nu se poate).

Restricții și precizări

• 0 < N < 11
• 0 < L[i] < 10001, pentru orice i

Exemplul 1

perlein.txt

3

8 2 1 1 3 2 1 2 3

2 2 2

1 3

perleout.txt

Datele introduse corespund restricțiilor impuse.

1

0

1

Exemplul 2

perlein.txt

4

8 2 1 1 3 2 1 2 3

2 2 2

1 3

12 1 2 3 4 5 6 7 8 9 10 11 12

perleout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 4242 - perle
def validare(op):           # functia de validare a datelor de intrare
    if len(op) > 11:
        raise ValueError
    for operatie in op:
        if operatie[0] < 1 or operatie[0] > 10001:
            raise ValueError
    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def perle(op):                     # functia de rezolvare
    for sir in op:
        if len(sir) % 2 == 0 or sir[0] != 1:
            fisier_iesire.write("0\n")
        else:
            fisier_iesire.write("1\n")


if __name__ == '__main__':
    fisier_intrare = open("perlein.txt", "r")         # declararea fisierelor
    fisier_iesire = open("perleout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        N = int(fisier_intrare.readline())
        operatii = [list(map(int, linie.split()))[1:] for linie in fisier_intrare.readlines()]

        validare(operatii)                 # apelul functiei de validare
        perle(operatii)               # apelul functiei de rezolvare

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")