Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2396. Арифмантика
Сокращение перебора с помощью идеиПредрасчеты, кэширование вычислений
Олимпиадные задачи на русском языке
| 04/09/2018 | Отборочный тур личных соревнований (C) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
При изучении арифмантики Гермиона обнаружила уникальную самоописывающую
неубывающую последовательность натуральных чисел `G`, в которой число `n` входит `G(n)` раз.
| `n` | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | … |
| `G(n)` | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 | 5 | 5 | 5 | 6 | 6 | 6 | 6 | 7 | … |
`G(1)=1`, так как при `G(1)>1` получаем противоречие в количестве 1 с `G(1)`.
`G(2)=2`, так как при `G(2)=1` получим противоречие с `G(1)=1`,
а при `G(2)>2` число 2 отсутствует в `G`, а должно входить ровно `G(2)` раз.
Последующие элементы последоватетальности определяются по её предыдущим элементам.
Напишите программу, которая найдет значения `G(n)` для некоторых заданных `n`.
Первая строка входного файла содержит одно целое число `Q` – количество запросов.
Последующие `Q` строк содержат одно целое число `n`.
Для каждого запроса вывести на отдельной строке значение `G(n)`.
Пример ввода
6 1 2 3 4 5 10
Пример вывода
1 2 2 3 3 5
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых
подзадач успешно пройдены.
Подзадача 1 (20 баллов)
`1\ ≤\ Q\ ≤\ 1000`, `1 ≤ n ≤ 10^6`
Подзадача 2 (20 баллов)
`1\ ≤\ Q\ ≤\ 10`, `1 ≤ n ≤ 10^9`
Подзадача 3 (20 баллов)
`1\ ≤\ Q\ ≤\ 10`, `1 ≤ n ≤ 10^18`
Необходимые подзадачи: 2.
Подзадача 4 (40 баллов)
`1\ ≤\ Q\ ≤\ 50\ 000`, `1 ≤ n ≤ 10^18`
Необходимые подзадачи: 1,2,3.
