Мережа Дюлока#12972

Мережа Дюлока

2 секунди
512 мегабайтів
Складна

Це інтерактивна задача (де ваша програма взаємодіє з програмою журі через ввід та вивід).

У королівстві Дюлок, Лорд Фаркуад розвиває мережу веж для моніторингу кожного куточка своєї землі. У нього є карта веж та доріг, що їх з’єднують, утворюючи неорієнтований простий граф G=(V,E), де кожна вежа — це вершина, а кожна дорога — це ребро між двома вежами. Однак Фаркуад хвилюється, що деякі частини Дюлока можуть бути ізольовані, що зробить неможливим доступ до кожної вежі з будь-якої іншої.

Щоб забезпечити повну зв’язність, він доручає вам перевірити, чи є його мережа з’єднаною. Проте є одна умова: вам дозволено обмежений доступ до інформації про граф.

Ви можете робити запити про мережу, щоб перевірити її зв’язність. Запит дозволяє вибрати підмножину веж і отримати кількість веж, що не належать і напряму з’єднані з хоча б однією вежею з . Тобто, query(S) = |N(S) \setminus S|, де S \subseteq V і N(S) = \{x \vert \exists y \in S \text{ such that } (x, y) \in E\}.

Ваше завдання — ефективно використовувати ці запити, щоб перевірити, чи мережа є зв’язною.

Чи можете ви допомогти Лорду Фаркуаду підтвердити безпеку його королівства, перевіривши, що кожна вежа досяжна з будь-якої іншої в мережі Дюлока?

Вхідні дані

У першому рядку задано одне ціле число — кількість веж в кололівстві Дюлок.

Після зчитування числа починається взаємодія. Ви можете робити запити вигляду: "? s" (без лапок), де — це бінарний рядок довжини , такий що символ s_i є 1 якщо i \in S і 0 в іншому випадку. Після запиту, зчитайте одне число — відповідь на ваш запит.

1 \leq |V| \leq 200.

Ви можете зробити не більше ніж 3500 запитів.

Вихідні дані

Коли ви визначите чи є зв’язним чи ні, виведіть відповідь у форматі: "! x" (без лапок), де це 1 якщо є зв’язним і 0 в іншому випадку.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі, |V| = 4, G = (V, E), V = \{1, 2, 3, 4\}, E = \{(1, 2), (2, 3), (3, 4), (2, 4)\}.

Input

Output

Description

4

Дано .

? 1100

Запит про підмножину .

2

Відповідь журі 2.

? 0010

Запит про підмножину .

2

Відповідь журі 2.

? 1001

Запит про підмножину .

2

Відповідь журі 2.

! 1

Алгоритм виявив, що G є зв’язним.

У другому прикладі, |V| = 2, G = (V, E), V = \{1, 2\}, E = \emptyset.

Input

Output

Description

2

Дано .

? 10

Запит про підмножину .

0

Відповідь журі 0.

? 11

Запит про підмножину .

0

Відповідь журі 0.

! 0

Алгоритм виявив, що G не є зв’язним.