Podczas implementacji obwodu dla robota zauważyłeś pewne anomalie. Istnieje $N = 128$ programów, ponumerowanych od $0$ do $N-1$, które robot może uruchomić. Zazwyczaj w każdej chwili powinien działać tylko jeden program (spośród $N$ dostępnych). Jednak z nieznanych przyczyn czasami dokładnie trzy programy działają jednocześnie. Na szczęście, jako doświadczony programista, wiesz jak poradzić sobie z tą sytuacją i decydujesz się zaimplementować obwód, który wykryje takie anomalie.
Najpierw tworzysz $N$ wejść. $i$-te wejście wynosi $0$, jeśli $i$-ty program nie działa, i $1$ w przeciwnym razie. Następnie dodajesz bramki, które mają indeksy ponumerowane kolejno, zaczynając od $N$. Każda bramka może przyjmować określoną liczbę wejść i generować pojedyncze wyjście, $0$ lub $1$. Wejściami $i$-tej bramki może być wyjście dowolnej bramki o indeksie mniejszym niż $i$ lub dowolne z początkowych $N$ wejść.
Istnieją trzy rodzaje bramek:
NOT: przyjmuje dokładnie jedno wejście. Wyjście wynosi $1$, jeśli wejście wynosi $0$, i $0$ w przeciwnym razie.OR: przyjmuje dokładnie dwa wejścia. Wyjście wynosi $0$, jeśli oba wejścia wynoszą $0$, i $1$ w przeciwnym razie.AND: przyjmuje dokładnie dwa wejścia. Wyjście wynosi $1$, jeśli oba wejścia wynoszą $1$, i $0$ w przeciwnym razie.
Wyjście ostatniej bramki powinno wynosić $1$, jeśli wykryto anomalię — to znaczy, jeśli dokładnie trzy z pierwszych $N$ wejść mają wartość $1$ — oraz $0$, jeśli dokładnie jedno z pierwszych $N$ wejść ma wartość $1$.
Gwarantuje się, że liczba jedynek wśród pierwszych $N$ wejść wynosi dokładnie jeden lub dokładnie trzy.
Szczegóły implementacji
Musisz zapisać do pliku wyjściowego opis poprawnego obwodu dla $\color{red}{N = 128}$.
Pierwsza linia wyjścia powinna zawierać liczbę całkowitą reprezentującą liczbę użytych bramek.
Każda kolejna linia wyjścia powinna mieć jeden z następujących trzech formatów:
NOT in_1 OR in_1 in_2 AND in_1 in_2
Każda z nich dodaje odpowiednio bramkę NOT, OR lub AND. W przypadku NOT, in_1 jest indeksem wejścia bramki. W przypadku OR oraz AND, in_1 i in_2 są indeksami wejść bramki. Indeks bramki dodanej w $i$-tej linii po pierwszej linii wynosi $N-1 + i$.
Całkowita liczba bramek nie powinna przekraczać $1024$. Innymi słowy, całkowita liczba linii w pliku wyjściowym nie powinna przekraczać $1025$.
Podzadania
- (100 punktów) Brak dodatkowych ograniczeń.
Punktacja
Dla każdego podzadania, jeśli istnieje przypadek, którego obwód nie przechodzi, otrzymasz $0$ punktów.
W przeciwnym razie, niech $K$ oznacza liczbę bramek użytych w obwodzie. Twój wynik wyniesie $f(K) \times$ [wynik podzadania], gdzie:
$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$
Rysunek 1: Wynik za zadanie dla każdej wartości K
Musisz zapisać swoje rozwiązanie w pliku wyjściowym 1.out, a następnie skompresować pliki wyjściowe do pojedynczego pliku .zip i przesłać go.
Przykład
Rozważmy uproszczoną wersję zadania z $N = 4$ (Zauważ, że musisz dostarczyć rozwiązanie tylko dla $N = 128$). Możliwym rozwiązaniem jest zbudowanie następującego obwodu:
Wejście 1
3 OR 0 1 OR 2 3 AND 4 5
Wyjście 1
(brak danych wyjściowych w przykładzie)
Uwagi
Obwód posiada: - bramkę $4$, która zwraca $1$, jeśli przynajmniej jedno z wejść $0$ lub $1$ wynosi $1$; - bramkę $5$, która zwraca $1$, jeśli przynajmniej jedno z wejść $2$ lub $3$ wynosi $1$; oraz - bramkę $6$, która zwraca $1$, jeśli oba wyjścia bramki $4$ i bramki $5$ wynoszą $1$.
Można sprawdzić, że dla wszystkich możliwych wejść obwód daje poprawną odpowiedź.