codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

929A.md (5743B)


      1 Source: https://codeforces.com/problemset/problem/929/A
      2 
      3 A. Прокат велосипедов
      4 
      5 ограничение по времени на тест
      6 
      7 1 секунда
      8 
      9 ограничение по памяти на тест
     10 
     11 256 мегабайт
     12 
     13 ввод
     14 
     15 стандартный ввод
     16 
     17 вывод
     18 
     19 стандартный вывод
     20 
     21 Как известно, в теплую погоду многие жители крупных городов пользуются сервисами городского велопроката. Вот и Аркадий сегодня будет добираться от школы до дома, используя городские велосипеды.
     22 
     23 Школа и дом находятся на одной прямой улице, кроме того, на той же улице есть *n* точек, где можно взять велосипед в прокат или сдать его. Первый велопрокат находится в точке *x*1 километров вдоль улицы, второй — в точке *x*2 и так далее, *n*-й велопрокат находится в точке *x**n*. Школа Аркадия находится в точке *x*1 (то есть там же, где и первый велопрокат), а дом — в точке *x**n* (то есть там же, где и *n*-й велопрокат). Известно, что *x**i* < *x**i* + 1 для всех 1 ≤ *i* < *n*.
     24 
     25 Согласно правилам пользования велопроката, Аркадий может брать велосипед в прокат только на ограниченное время, после этого он должен обязательно вернуть его в одной из точек велопроката, однако, он тут же может взять новый велосипед, и отсчет времени пойдет заново. Аркадий может брать не более одного велосипеда в прокат одновременно. Если Аркадий решает взять велосипед в какой-то точке проката, то он сдаёт тот велосипед, на котором он до него доехал, берёт ровно один новый велосипед и продолжает на нём своё движение.
     26 
     27 За отведенное время, независимо от выбранного велосипеда, Аркадий успевает проехать не больше *k* километров вдоль улицы.
     28 
     29 Определите, сможет ли Аркадий доехать на велосипедах от школы до дома, и если да, то какое минимальное число раз ему необходимо будет взять велосипед в прокат, включая первый велосипед? Учтите, что Аркадий не намерен сегодня ходить пешком.
     30 
     31 Входные данные
     32 
     33 В первой строке следуют два целых числа *n* и *k* (2 ≤ *n* ≤ 1 000, 1 ≤ *k* ≤ 100 000) — количество велопрокатов и максимальное расстояние, которое Аркадий может проехать на одном велосипеде.
     34 
     35 В следующей строке следует последовательность целых чисел *x*1, *x*2, ..., *x**n* (0 ≤ *x*1 < *x*2 < ... < *x**n* ≤ 100 000) — координаты точек, в которых находятся велопрокаты. Гарантируется, что координаты велопрокатов заданы в порядке возрастания.
     36 
     37 Выходные данные
     38 
     39 Если Аркадий не сможет добраться от школы до дома только на велосипедах, выведите -1. В противном случае, выведите минимальное количество велосипедов, которые Аркадию нужно взять в точках проката.
     40 
     41 Примеры
     42 
     43 Входные данные
     44 
     45 ```
     46 4 4  
     47 3 6 8 10
     48 ```
     49 
     50 Выходные данные
     51 
     52 ```
     53 2
     54 ```
     55 
     56 Входные данные
     57 
     58 ```
     59 2 9  
     60 10 20
     61 ```
     62 
     63 Выходные данные
     64 
     65 ```
     66 -1
     67 ```
     68 
     69 Входные данные
     70 
     71 ```
     72 12 3  
     73 4 6 7 9 10 11 13 15 17 18 20 21
     74 ```
     75 
     76 Выходные данные
     77 
     78 ```
     79 6
     80 ```
     81 
     82 Примечание
     83 
     84 В первом примере Аркадий должен взять первый велосипед в первом велопрокате и доехать на нём до второго велопроката. Во втором велопрокате он должен взять новый велосипед, на котором он сможет добраться до четвертого велопроката, рядом с которым и находится его дом. Поэтому Аркадию нужно всего два велосипеда, чтобы добраться от школы до дома.
     85 
     86 Во втором примере всего два велопроката, расстояние между которыми 10. Но максимальное расстояние, которое можно проехать на одном велосипеде, равно 9. Поэтому Аркадий не сможет добраться от школы до дома только на велосипедах.