Автор: | Бадерик П.М. | Ограничение времени: | 1 сек | |
Ввод / вывод: | интерактивный | Ограничение памяти: | 256 Мб |
Farpost — самый популярный классифайд Дальнего Востока, где ежедневно публикуются миллионы объявлений.
Быть в топе на Фарпосте — задача со звёздочкой. Один из факторов, который на это влияет — рейтинг продавца (по оценкам покупателей).
Представим, что вы берёте проект на практике в Фарпосте и хотите помочь продавцам скорректировать их поведение на сайте для достижения высокого рейтинга.
Вам нужно проанализировать рейтинг продавца за последние N дней.
Конечно самое интересное в рейтинге — это что такого может сделать продавец, чтобы изменить тренд своего рейтинга (убывающий тренд превратить в возрастающий и наоборот). Для начала найдите, когда происходит правильное изменение тренда.
Кажется не очень сложным, да?)
Но из-за защиты персональных данных пользователей (в том числе и продавцов) вы не можете напрямую получить рейтинг продавца. Такие данные есть только у наших сотрудников.
Зато у вас есть возможность отправить небольшое количество запросов в систему.
Запросы могут быть только 2 видов:
Чтобы вас не забанили как бота, вы можете отправить не более 90 запросов.
В первой строке входных данных идет целое число N.
В запросе с ответом, позиции экстремумов должны идти по возрастания. Так же обращаю внимание, что номера дней: 0≤ij<N.
Каждый вопрос и вывод ответа должны заканчиваться символом перевода строки, а также необходимо выполнять сброс буфера flush()
i позиция называется правильным разворотом, если hi−1>hi<hi+1 или hi−1<hi>hi+1.
Напоминаем, что биты нумеруются справа налево.
1≤n≤31
−1017≤hi≤1017
|hi−hi−1|≤1, где hi - целое число, значение в i день на графике.
Запрос | Ответ | Биты |
---|---|---|
? 97 | 127 | 1111111 |
? 99 | 11 | 0001011 |
? 101 | 0 | 0000000 |
Первый запрос: во все дни рейтинг больше или равен 97.
Второй запрос: только в первый, второй и четвёртый дни рейтинг больше или равен 99.
Третий запрос: во все дни рейтинг меньше чем 101.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|