print1477. Шалтай-Болтай

printШалтай-Болтай

Ограничения: время – 4s/8s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Источник: http:/imcs.dvgu.ru/cats/, городская олимпиада, 2008
loading