НачалоПодразделы
Другие разделы
| 1471. As simple as it gets |
| 1472. Bit by bit |
| 1473. Concatenation |
| 1474. Deadlock detector |
| 1475. Быстрая помощь |
| 1476. Плотники |
| 1478. Ферзи на шахматной доске |
| 1479. Хоттабыч и векторы на плоскости |
Дата и время
20/12/2024 16:42:18
1477. Шалтай-Болтай
Шалтай-Болтай
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание (11G) |
| 16/07/2010 | Лето 2010 - 11 (G) |
| 07/07/2017 | Лето 2017 (командное) - 7 (H) |
Ограничения: время – 4s/8s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Шалтай-Болтай очень любит ходить по своей стене в разные стороны и кушать пирожки.
Сверху стена выглядит как длинная полоска из одинаковых клеток, пронумерованных по возрастанию слева направо.
Каждый день Шалтай-Болтай может выполнить одно из трёх действий:
- сдвинуться влево на `R_i` клеток;
- сдвинуться вправо на `R_i` клеток;
- скушать пирожок.
Число клеток `R_i` зависит от текущего дня недели. Шалтай-Болтай считает, что в неделе `M` дней.
В начальный момент времени Шалтай-Болтай находится на клетке с номером ноль, имеет `K` пирожков и считает, что
сейчас первый день недели.
Требуется найти минимальное количество дней `Q`, через которое он может оказаться в клетке с номером `D`, или определить,
что это невозможно.
Формат входного файла
Во входном файле содержатся числа `D\ K\ M`. Далее следует `M` целых чисел `R_i` – количество клеток, на которое
Шалтай может сдвинуться в `i`-й день недели.
Формат выходного файла
В выходном файле должно содержаться единственное число `Q`, либо `-1`, если добраться до клетки `D` невозможно.
Ограничения
`-2*10^4\ ≤\ D\ ≤\ 2*10^4`, `0\ ≤\ K\ ≤\ 10`, `1\ ≤\ M\ ≤\ 10`, `1\ ≤\ R_i\ ≤\ 2*10^4`
Пример ввода 1
4 1 2 2 10
Пример вывода 1
3
Пример ввода 2
1 5 1 3
Пример вывода 2
-1
