W Monster City znajduje się duży park, który składa się z kilku atrakcji oraz łączących je jednokierunkowych dróg. W parku jest $v$ atrakcji o numerach $1, 2, \dots, v$. Wśród nich znajduje się $n$ wejść o numerach $1, 2, \dots, n$ oraz $1$ wyjście o numerze $v$. W parku znajduje się $e$ dróg, przy czym $i$-ta droga prowadzi z atrakcji $a_i$ do atrakcji $b_i$.
Każda atrakcja $i$ posiada znacznik $s_i$, który jest jednym ze znaków & lub |. Podobnie, każda droga $i$ posiada znacznik $t_i$, będący jednym ze znaków &, |, ~, <, >. Jeśli $t_i$ nie jest równe ~, droga $i$ posiada również wagę $l_i$.
Każdego dnia do parku wchodzi fala $n$ potworów. W $i$-tym dniu $n$ potworów o początkowych punktach życia $h_{i,1}, h_{i,2}, \dots, h_{i,n}$ wchodzi jednocześnie do $n$ wejść $1, 2, \dots, n$, a następnie przemierza park. W każdej minucie każdy potwór dzieli się na $k$ kopii (gdzie $k$ to liczba dróg wychodzących z atrakcji, w której znajduje się potwór), z których każda ma taką samą liczbę punktów życia jak przed podziałem i porusza się jedną z $k$ dróg wychodzących z danej atrakcji.
Pokonanie drogi zajmuje potworowi dokładnie $1$ minutę. Po przejściu drogi $i$ liczba punktów życia potwora $h$ zmienia się na $h'$. Poniższa tabela przedstawia relacje zmian:
| $t_i=$ | $h'=$ | Opis | |
|---|---|---|---|
& |
$h\ \mathrm{AND}\ l_i$ | Wynik operacji bitowej AND na $h$ oraz $l_i$ | |
| ` | ` | $h\ \mathrm{OR}\ l_i$ | Wynik operacji bitowej OR na $h$ oraz $l_i$ |
~ |
$\mathrm{NOT}\ h$ | Wynik bitowej negacji $h$ (zamiana $0$ na $1$ i $1$ na $0$) | |
< |
$h\ \mathrm{SHL}\ l_i$ | Przesunięcie bitowe $h$ w lewo o $l_i$ pozycji, uzupełnienie zerami | |
> |
$h\ \mathrm{SHR}\ l_i$ | Przesunięcie bitowe $h$ w prawo o $l_i$ pozycji, uzupełnienie zerami |
W tabeli $\mathrm{AND}, \mathrm{OR}, \mathrm{NOT}, \mathrm{SHL}, \mathrm{SHR}$ odpowiadają odpowiednio operacjom bitowym: AND, OR, NOT, przesunięciu w lewo i przesunięciu w prawo. $h, l_i$ oraz $h'$ są $32$-bitowymi liczbami całkowitymi bez znaku. Dla operacji $\mathrm{AND}, \mathrm{OR}$ zachodzi $0 \le l_i < 2^{32}$. Dla operacji $\mathrm{SHL}, \mathrm{SHR}$ zachodzi $0 \le l_i < 32$.
Gdy wiele potworów o punktach życia $h_1, h_2, \dots, h_c$ spotka się w tej samej atrakcji $i$, łączą się one w jednego potwora, którego punkty życia $h'$ są wynikiem operacji $s_i$ na wartościach $h_1, h_2, \dots, h_c$. Oznacza to: jeśli $s_i$ to &, to $h' = h_1\ \mathrm{AND}\ h_2\ \mathrm{AND}\ \dots\ \mathrm{AND}\ h_c$; jeśli $s_i$ to |, to $h' = h_1\ \mathrm{OR}\ h_2\ \mathrm{OR}\ \dots\ \mathrm{OR}\ h_c$. Następnie, jeśli potwór znajduje się przy wyjściu z parku, opuszcza on park. Pierwszy potwór, który opuści park w danej fali, nazywany jest Zwycięzcą (Winner). Rejestrowane są początkowe punkty życia wszystkich potworów oraz punkty życia Zwycięzcy w momencie opuszczenia parku.
Potwór ginie wtedy i tylko wtedy, gdy zajdzie jeden z poniższych przypadków (martwy potwór nigdy nie podejmuje działań ani nie bierze udziału w łączeniu):
- Z atrakcji, w której znajduje się potwór, nie wychodzi żadna droga, a potwór nie znajduje się przy wyjściu.
- Punkty życia potwora wynoszą $0$. Oznacza to, że potwór mógł zginąć na drodze lub natychmiast po połączeniu.
- Od momentu wejścia potworów do parku minęło więcej niż $k$ minut, gdzie $k$ to długość życia potwora.
Można przyjąć, że w dniu $i+1$ wszystkie potwory z dnia $i$ albo opuściły park, albo zginęły.
Jednak po $m$ dniach katastrofa naturalna poważnie zniszczyła park. Monster City chce odbudować park na podstawie zapisów z tych $m$ dni, ale jest to trudne zadanie. Twoim celem jest zaprojektowanie dowolnego schematu parku, który spełnia wszystkie zapisy z $m$ dni.
Wejście
Pierwsza linia zawiera $3$ liczby całkowite $n, m, k$, oznaczające odpowiednio liczbę potworów wchodzących każdego dnia, liczbę dni oraz długość życia potworów.
Kolejne $2m+1$ linii zawiera zapisy z $m$ dni. Wiersz $2i$ zawiera $n$ liczb całkowitych $h_{i,1}, h_{i,2}, \dots, h_{i,n}$, oznaczających początkowe punkty życia $n$ potworów wchodzących do parku w dniu $i$. Wiersz $2i+1$ zawiera $1$ liczbę całkowitą $w_i$, oznaczającą punkty życia Zwycięzcy w dniu $i$ w momencie opuszczenia parku. Gwarantuje się, że każdego dnia istnieje Zwycięzca.
Wyjście
Dla każdego z $10$ plików wejściowych rebuild1.in ~ rebuild10.in należy dostarczyć odpowiedni plik wyjściowy rebuild1.out ~ rebuild10.out.
Pierwsza linia wyjścia zawiera $2$ liczby całkowite $v$ oraz $e$, oznaczające liczbę atrakcji i liczbę dróg, gdzie $n < v \le 100$ oraz $0 \le e \le 500$.
Druga linia zawiera ciąg znaków $s$ o długości $v$, gdzie $i$-ty znak $s_i$ to & lub |, oznaczający znacznik atrakcji $i$.
Kolejne $e$ linii opisuje drogi. Wiersz $i+2$ zawiera cztery elementy (liczby lub znaki) $a_i, b_i, t_i, l_i$, oznaczające odpowiednio początek, koniec, znacznik i wagę $i$-tej drogi. $1 \le a_i, b_i \le v$, a znacznik jest jednym ze znaków &, |, ~, <, >. W szczególności, gdy $t_i$ to ~, wartość $l_i$ nie jest podawana. Dozwolone jest istnienie wielu dróg między dwiema atrakcjami oraz dróg, których początek i koniec są w tej samej atrakcji.
Możesz wypisać dowolny poprawny schemat. Gwarantuje się, że takie rozwiązanie istnieje.
Przykład
Wejście 1
2 4 2 11 1 20 11 2 18 11 3 16 18 12 12
Wyjście 1
4 4 ||&& 1 3 | 0 2 3 ~ 2 4 & 12 3 4 < 1
Uwagi
Przykładowe wyjście jest jednym z możliwych schematów odbudowy parku. Rozważmy potwory z pierwszego dnia:
Na początku są $2$ potwory w atrakcjach $1$ i $2$ o punktach życia odpowiednio $11$ i $1$.
W $1$. minucie potwór z atrakcji $1$ wchodzi drogą do atrakcji $3$, jego punkty życia zmieniają się na $11\ \mathrm{OR}\ 0 = 11$. Potwór z atrakcji $2$ dzieli się na $2$ kopie: jedna wchodzi drogą do atrakcji $3$ (punkty życia zmieniają się na $\mathrm{NOT}\ 1 = 4294967294$), a druga wchodzi drogą do atrakcji $4$ (punkty życia zmieniają się na $1\ \mathrm{AND}\ 12 = 0$, więc ginie przed wejściem do atrakcji). Następnie $2$ potwory w atrakcji $3$ łączą się w jednego o punktach życia $11\ \mathrm{AND}\ 4294967294 = 10$. W tym momencie tylko w atrakcji $3$ znajduje się $1$ potwór.
W $2$. minucie potwór z atrakcji $3$ wchodzi drogą do atrakcji $4$. Atrakcja $4$ jest wyjściem, więc potwór opuszcza park i staje się Zwycięzcą.
Zatem punkty życia Zwycięzcy wynoszą $20$.
Podzadania
Dostarczono $10$ plików oceniających rebuild1.ans ~ rebuild10.ans. Każdy plik zawiera $10$ linii, z których każda zawiera parametr oceny $a_i$.
Każdy zestaw danych jest oceniany osobno. Jeśli format wyjściowy jest nieprawidłowy, otrzymasz $0$ punktów. Jeśli wyjście jest poprawne, ale spełnia tylko część z $m$ zapisów, możesz otrzymać punkty częściowe.
Jeśli w Twoim rozwiązaniu liczba spełnionych zapisów wynosi $x_{user}$, punkty zostaną przyznane zgodnie z poniższą tabelą:
| Punkty | Warunek | Punkty | Warunek |
|---|---|---|---|
| $10$ | $x_{user} \ge a_{10}$ | $5$ | $x_{user} \le a_5$ |
| $9$ | $x_{user} \ge a_9$ | $4$ | $x_{user} \ge a_4$ |
| $8$ | $x_{user} \ge a_8$ | $3$ | $x_{user} \ge a_3$ |
| $7$ | $x_{user} \ge a_7$ | $2$ | $x_{user} \ge a_2$ |
| $6$ | $x_{user} \ge a_6$ | $1$ | $x_{user} \ge a_1$ |
Jeśli żaden z warunków nie jest spełniony, otrzymasz $0$ punktów. Jeśli spełnionych jest wiele warunków, otrzymasz najwyższą możliwą liczbę punktów.
Jak testować swoje rozwiązanie
W terminalu przejdź do katalogu z zadaniem (użytkownicy systemu Windows powinni użyć wiersza poleceń):
cd rebuild
Dostarczamy narzędzie checker do weryfikacji poprawności wyjścia. Aby go użyć, uruchom w terminalu:
./checker_linux64 <numer_zestawu>
Gdzie <numer_zestawu> to numer testu. Na przykład:
./checker_linux64 3
przetestuje plik rebuild3.out. (Użytkownicy systemu Windows powinni użyć checker_win32 3).
Dostępna jest również wersja dla systemów Linux 32-bit: checker_linux32. Jeśli program nie uruchamia się, spróbuj nadać uprawnienia do wykonywania poleceniem chmod +x checker_linux64 lub chmod +x checker_linux32.
Po uruchomieniu programu checker wyświetli wynik testu. Prosimy nie modyfikować plików wejściowych, aby uniknąć błędów w działaniu narzędzia.
Możesz również użyć polecenia:
./checker_linux64 –w <numer_zestawu>
aby wypisać proces przemieszczania się potworów i ich punkty życia do pliku report.log. Uwaga: plik report.log może być bardzo duży (nawet do $150\text{ MB}$).