Anna i Bruno są archeologami. Badają ruiny w Iranie.

Ich zadania są następujące: Anna odwiedza ruiny i odkrywa artefakty, a Bruno analizuje wyniki w obozie bazowym.

Badania zaplanowano na $Q\;(=1\,000)$ dni. Każdego dnia Anna przesyła wyniki Brunowi za pomocą urządzenia komunikacyjnego. Wyniki z każdego dnia są wyrażone jako liczba całkowita $X$.

Anna może użyć urządzenia komunikacyjnego tylko raz dziennie. Może ono przesłać ciąg długości $N\;(=150)$ złożony z zer i jedynek.

Jednak urządzenie jest uszkodzone. W ciągu długości $N$ jest kilka uszkodzonych pozycji. Na uszkodzonej pozycji urządzenie zawsze przesyła wartość $0$, niezależnie od faktycznie ustawionej wartości. Gdy Anna wysyła ciąg, zna położenia uszkodzonych pozycji. Bruno jednak ich nie zna. Położenia i liczba uszkodzonych pozycji mogą zmieniać się każdego dnia.

Istnieje ryzyko opóźnienia badań. Ponieważ jesteś kandydatem na uczestnika międzynarodowych zawodów programistycznych w Iranie, Anna i Bruno proszą cię o napisanie programu przesyłającego wyniki ich badań.

Zadanie

Napisz dwa programy umożliwiające komunikację między Anną i Brunem.

• Na podstawie długości ciągu $N$, przesyłanej liczby całkowitej $X$, liczby uszkodzonych pozycji $K$ i ich położeń $P$ pierwszy program ustawia ciąg $S$ wysyłany przez Annę.
• Na podstawie ciągu $A$ odebranego przez Bruna drugi program odtwarza liczbę całkowitą $X$.

Na pozycji, na której urządzenie działa, ciągi $S$ i $A$ mają tę samą wartość. Na uszkodzonej pozycji ciąg $A$ zawsze ma wartość $0$, niezależnie od wartości ciągu $S$.

Szczegóły implementacji

Należy przesłać dwa pliki napisane w tym samym języku programowania.

Pierwszy plik to Anna.c albo Anna.cpp. Ustawia on ciąg wysyłany przez Annę i implementuje poniższą funkcję. Program powinien dołączać plik Annalib.h.

• void Anna( int N, long long X, int K, int P[] )

  Dla każdego przypadku testowego funkcja ta jest wywoływana $Q=1\,000$ razy.

  • Parametr N jest długością wysyłanego ciągu.
  • Parametr X jest przesyłaną liczbą całkowitą.
  • Parametr K jest liczbą uszkodzonych pozycji.
  • Parametr P[] jest ciągiem długości $K$ opisującym położenia uszkodzonych pozycji.

  W funkcji Anna należy wywoływać poniższą funkcję.

  • void Set( int pos, int bit )

    Funkcja ta ustawia bit w ciągu $S$, który ma zostać wysłany przez urządzenie komunikacyjne.

    • Parametr pos jest pozycją, którą należy ustawić. pos musi być liczbą całkowitą od $0$ do $N-1$ włącznie. Uwaga: pozycje są numerowane od $0$. Jeśli funkcja zostanie wywołana z parametrem spoza tego zakresu, program otrzyma werdykt Wrong Answer[1]. Nie wolno wywołać tej funkcji więcej niż raz z tą samą wartością parametru pos. W przeciwnym razie program otrzyma werdykt Wrong Answer[2].
    • Parametr bit jest wartością ustawianą na pozycji pos ciągu. Wartość bit musi wynosić $0$ albo $1$. Jeśli funkcja zostanie wywołana z inną wartością, program otrzyma werdykt Wrong Answer[3].

  Funkcja Set musi zostać wywołana dokładnie $N$ razy w funkcji Anna. Jeśli po zakończeniu funkcji Anna liczba wywołań funkcji Set jest różna od $N$, program otrzyma werdykt Wrong Answer[4].

  Program zostanie zakończony, jeśli wywołanie funkcji przez Anna zostanie uznane za nieprawidłowe.

Drugi plik to Bruno.c albo Bruno.cpp. Odtwarza on liczbę całkowitą wyrażającą wyniki badań i implementuje poniższą funkcję. Program powinien dołączać plik Brunolib.h.

• long long Bruno( int N, int A[] )

  Dla każdego przypadku testowego funkcja ta jest wywoływana $Q=1\,000$ razy.

  • Parametr N jest długością ciągu odebranego przez Bruna.
  • Parametr A jest ciągiem liczb całkowitych długości $N$. Jest to ciąg odebrany przez Bruna.
  • Funkcja Bruno musi odtworzyć wartość $X$ i ją zwrócić.

Procedura oceniania

Ocenianie przebiega następująco. Jeśli program otrzyma werdykt Wrong Answer, zostaje natychmiast zakończony.

1. Ustaw $\mathrm{cnt}=0$.
2. Wywołaj funkcję Anna jeden raz.
3. Niech $S$ będzie ciągiem ustawionym przez funkcję Anna. Ustaw w nim wartość $0$ na pozycjach z $P$, otrzymując ciąg $A$. Wywołaj funkcję Bruno jeden raz z parametrem $A$.
4. Ustaw $\mathrm{cnt}=\mathrm{cnt}+1$. Jeśli $\mathrm{cnt}<Q$, przejdź do (2). Jeśli $\mathrm{cnt}=Q$, przejdź do (5).
5. Program otrzyma punkty.

Ważne uwagi

• Czas działania i zużycie pamięci oblicza się dla kroków (1), (2), (3), (4) procedury oceniania.
• Program nie może otrzymać werdyktu Wrong Answer podczas wywołania funkcji Anna w (2) ani Bruno w (3). Program musi działać bez błędów wykonania.
• Program może implementować inne funkcje do użytku wewnętrznego lub korzystać ze zmiennych globalnych. Przesłane programy zostaną skompilowane z programem oceniającym do jednego pliku wykonywalnego. Wszystkie zmienne globalne i funkcje wewnętrzne powinny być zadeklarowane jako static, aby uniknąć konfliktów z innymi plikami. Podczas oceniania programy Anny i Bruna będą uruchamiane jako 2 oddzielne procesy, więc nie mogą współdzielić zmiennych globalnych.
• W trakcie działania każda z funkcji Anna i Bruno jest wywoływana $Q=1\,000$ razy. Zmienne używane przez programy należy odpowiednio inicjalizować.
• Program nie powinien używać standardowego wejścia ani standardowego wyjścia. Nie powinien w żaden sposób komunikować się z innymi plikami.

Kompilacja i uruchamianie testów

Ze strony zawodów można pobrać archiwum zawierające przykładowy program oceniający do testowania rozwiązania. Archiwum zawiera również przykładowy plik źródłowy twojego programu.

Przykładowy program oceniający składa się z jednego pliku źródłowego, grader.c albo grader.cpp. Na przykład, jeśli twoje programy to Anna.c i Bruno.c albo Anna.cpp i Bruno.cpp, skompiluj je następującymi poleceniami.

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Po pomyślnej kompilacji powstaje plik wykonywalny grader.

Rzeczywisty program oceniający różni się od przykładowego. Przykładowy program oceniający jest uruchamiany jako jeden proces, który czyta dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający czyta poniższe dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczbę całkowitą $Q$.
• Następnie podane są informacje o $Q$ zapytaniach.

• Informacje o każdym zapytaniu składają się z dwóch wierszy:

  • Pierwszy wiersz zawiera trzy liczby całkowite $N$, $X$, $K$, oddzielone spacjami. Oznacza to, że długość wysyłanego ciągu wynosi $N$, Anna ma przesłać liczbę całkowitą $X$, a liczba uszkodzonych pozycji wynosi $K$.
  • Drugi wiersz zawiera $K$ liczb całkowitych $P_0,P_1,\ldots,P_{K-1}$, oddzielonych spacjami. Oznacza to, że dla każdego $i$ ($0 \le i \le K-1$) pozycja $P_i$ w ciągu jest uszkodzona.

Wyjście przykładowego programu oceniającego

Gdy program zakończy się pomyślnie, przykładowy program oceniający wypisuje na standardowe wyjście poniższe informacje. (Cudzysłowy nie są w rzeczywistości wypisywane.)

• Jeśli program otrzyma werdykt Wrong Answer, przykładowy program oceniający wypisuje jego typ w postaci Wrong Answer [1], po czym twój program zostaje zakończony.
• Jeśli żadne wywołanie funkcji Anna nie otrzyma werdyktu Wrong Answer, przykładowy program oceniający wypisuje Accepted i wartość $L^*$. Opis wartości $L^*$ znajduje się w sekcji „Podzadania”.

Jeśli program otrzyma kilka typów werdyktu Wrong Answer, przykładowy program oceniający zgłasza tylko jeden z nich.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $Q=1000$.
• $N=150$.
• $0 \le X \le 1\,000\,000\,000\,000\,000\,000$.
• $1 \le K \le 40$.
• $0 \le P_i \le N-1$ ($0 \le i \le K-1$).
• $P_i<P_{i+1}$ ($0 \le i \le K-2$).

Podzadania

• Niech $L^*$ będzie minimum poniższej wartości po wszystkich przypadkach testowych tego zadania.

  • Największa liczba całkowita $L \le 40$ taka, że dla każdego zapytania z $K \le L$ Bruno odpowiada poprawną wartością $X$.

• Punkty za zadanie oblicza się następująco:

  • Jeśli $L^*=0$, wynik wynosi $0$ punktów.
  • Jeśli $1 \le L^* \le 14$, wynik wynosi $8$ punktów.
  • Jeśli $15 \le L^* \le 37$, wynik wynosi $(L^*-15)\times2+41$ punktów.
  • Jeśli $38 \le L^* \le 40$, wynik wynosi $(L^*-38)\times5+90$ punktów.

Przykładowa komunikacja

Poniżej podano przykładowe wejście programu oceniającego i odpowiadające mu wywołania funkcji. Przykład nie spełnia ograniczeń zadania, ponieważ $Q=2$, $N=3$.

Wejście 1

2
3 14 1
2
3 9 2
0 1

Przykładowe wywołania

Wywołanie    Zwracana wartość    Wywołanie    Zwracana wartość
Anna(...)
                                Set(0,0)
                                            (brak)
                                Set(1,0)
                                            (brak)
                                Set(2,1)
                                            (brak)
             (brak)
Bruno(...)
             14
Anna(...)
                                Set(0,0)
                                            (brak)
                                Set(1,1)
                                            (brak)
                                Set(2,1)
                                            (brak)
Bruno(...)
             9

Parametry kolejnych wywołań Anna(...), Bruno(...), Anna(...), Bruno(...) są następujące.