Omówienie zadania Zera i jedynki (III etap XXIX OI)

W zadaniu mamy zgadnąć \(n\)-elementowy ciąg złożony z liczb \(0\) i \(1\) przy pomocy co najwyżej \(n\) pytań o sumę dwóch różnych elementów.

Analiza zadania

Przeanalizujmy prosty przykład: jeśli biblioteka odpowiedziała, że suma elementów \(a_1\) i \(a_2\) wynosi \(1\), to wiemy, że mamy dwie możliwości: albo \(a_1=0\) i \(a_2=1\), albo \(a_1=1\) i \(a_2=0\). Musimy więc zadać jakieś inne pytanie, na przykład o sumę elementów \(a_2\) i \(a_3\). Jeżeli znowu dostaniemy \(1\), to wiemy, że w pierwszym przypadku \(a_3=0\), a w drugim \(a_3=1\). Powiedzmy, że w kolejnym pytaniu o sumę elementów \(a_3\) i \(a_4\) uzyskaliśmy \(2\). Wtedy możemy już być pewni, że zarówno \(a_3=a_4=1\), a zatem \(a_2=1\) i \(a_1=0\).

Widać, że pożyteczna będzie sytuacja, gdy odpowiedź na jakieś nasze pytanie o sumę dwóch elementów \(a_i\) i \(a_j\) będzie równa \(0\) lub \(2\). Wartość każdego innego elementu będziemy mogli wyznaczyć za pomocą jednego pytania o sumę elementu \(a_i\) i tego innego elementu.

Może się jednak tak nieszczęśliwie złożyć, że wszystkie sumy, które będziemy uzyskiwali, będą równe \(1\). Co więcej, ponieważ sprawdzaczka może być adaptatywna, to znaczy może w trakcie naszej interakcji zmieniać elementy ciągu, o ile nowe elementy będą nadal spójne z wynikami zwróconymi przez dotychczasowe wywołania, to nie należy zakładać, że będziemy mieli szczęście, a raczej, że sprawdzaczka będzie starała się jak najdłużej zwracać nam odpowiedzi równe \(1\). I nasz program musi sobie z tym poradzić.

Rozwiązanie wzorcowe

Jednym z rozwiązań jest zadanie najpierw \(n - 1\) pytań o każdą parę kolejnych elementów \(a_i\) oraz \(a_{i+1}\). Jeżeli odpowiedź na któreś z tych pytań będzie równa \(0\) lub \(2\), to na podstawie uzyskanych odpowiedzi będziemy w stanie odzyskać cały ciąg. Jeżeli nie, to nadal będziemy mieli dwie możliwości: kolejne elementy będą na przemian równe \(0\) i \(1\), z tym, że nie wiemy, czy zaczynamy od \(0\), czy od \(1\). Ale aby się o tym przekonać, wystarczy zadać pytanie o sumę elementów \(a_1\) i \(a_3\). Odpowiedź na nie już nie może być równa \(1\), będzie albo \(0\), albo \(2\), co ustali, z którym przypadkiem mamy do czynienia.

To daje nam strategię, która w pesymistycznym przypadku zada co najwyżej \(n\) pytań.