Расшифровка ДНК

시간 제한5초메모리 제한512 MB

요약

구간에 포함된 서로 다른 뉴클레오티드 수를 돌려주는 스캔을 최대 q번 사용해 DNA를 같은 뉴클레오티드끼리 1부터 k까지의 번호로 복원한다.

난이도: 보통10점 중 5점
유형: 구현, 완전 탐색, 구간
정답자: 아직 제출이 없습니다

문제

Это интерактивная задача.

При проведении раскопок на территории Республики Татарстан были обнаружены останки неизвестного древнего животного, обитавшего в окрестностях современной Казани миллионы лет назад. Как и у всех живых организмов, молекула его ДНК представляет собой последовательность из n нуклеотидов, однако число встречающихся в ней различных нуклеотидов может отличаться от современных организмов.

Для изучения находки был создан специальный прибор, который может просканировать последовательный участок нуклеотидов в ДНК и вычислить, сколько различных видов нуклеотидов содержится на нём. К сожалению, молекула ДНК может выдержать не более q операций сканирования, после чего разрушается.

Исследователи хотят с помощью этого прибора найти k — количество различных нуклеотидов в ДНК, и определить позиции, в которых в ДНК находятся одинаковые нуклеотиды. Ученые хотят закодировать последовательность нуклеотидов в молекуле последовательностью целых положительных чисел a1, a2, . . . , an (1 ⩽ ai ⩽ k), таких что одинаковые числа кодируют одинаковые нуклеотиды, а различные числа — различные нуклеотиды.

Требуется написать программу, которая, взаимодействуя с программой жюри, определит количество различных нуклеотидов в последовательности, а также числовую последовательность, кодирующую последовательность нуклеотидов в молекуле ДНК.

힌트

В первом примере n = 2, за один запрос можно определить, равны ли первый и второй нуклеотид друг другу.

В втором примере n = 3, результат первого запроса показывает, что первые два нуклеотида одинаковые, результат второго запроса позволяет сделать вывод о том, что третий нуклеотид от них отличается. В этом случае допустимы два варианта ответа: 1 1 2 и 2 2 1.

В точности соблюдайте формат выходных данных. После каждого вывода обязательно выводите один перевод строки и сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

예제2

예제 1
입력
```
2
2
```
예상 출력
```
? 1 2
Ready!
2
1 2
```
예제 2
입력
```
3
1
2
```
예상 출력
```
? 1 2
? 1 3
Ready!
2
1 1 2
```