Решение задачи Корова и друг с Codeforces
Без пояснения   Просмотров: 63
У Бесси действительно много друзей, потому что она — всеми любимая корова! Ее новый друг Кролик пытается допрыгать до Бесси, чтобы поиграть вместе!
Точнее, он хочет попасть из (0,0) в (x,0), сделав несколько прыжков. Он готов прыгнуть из одной точки в другую на плоскости только если евклидово расстояние между этими точками равно одному из n его любимых чисел: a1,a2,…,an. За какое минимальное количество прыжков Кролик сможет добраться из (0,0) в (x,0)? Кролик может приземляться, в том числе, и в точки с нецелочисленными координатами. Можно доказать, что Кролик всегда может достигнуть точки назначения.
Напомним, что евклидово расстояние между точками (xi,yi) и (xj,yj) равно (xi−xj)2+(yi−yj)2−−−−−−−−−−−−−−−−−−√.
Например, если любимые числа Кролика — это 1 и 3, то он может добраться из (0,0) в (4,0) за два прыжка (как показано ниже). Заметим, что существуют и другие способы добраться до (4,0) за 2 прыжка (например, (0,0) → (2,−5–√) → (4,0)).
Изображение соответствует первому набору входных данных из примера. Длина обоих прыжков равна 3, одному из любимых чисел Кролика.
Таким образом, перед каждым прыжком Кролик выбирает одно из чисел ai и прыгает из текущей точки на расстояние ровно ai в произвольном направлении. Одно и то же число он может выбирать любое количество раз.
Точнее, он хочет попасть из (0,0) в (x,0), сделав несколько прыжков. Он готов прыгнуть из одной точки в другую на плоскости только если евклидово расстояние между этими точками равно одному из n его любимых чисел: a1,a2,…,an. За какое минимальное количество прыжков Кролик сможет добраться из (0,0) в (x,0)? Кролик может приземляться, в том числе, и в точки с нецелочисленными координатами. Можно доказать, что Кролик всегда может достигнуть точки назначения.
Напомним, что евклидово расстояние между точками (xi,yi) и (xj,yj) равно (xi−xj)2+(yi−yj)2−−−−−−−−−−−−−−−−−−√.
Например, если любимые числа Кролика — это 1 и 3, то он может добраться из (0,0) в (4,0) за два прыжка (как показано ниже). Заметим, что существуют и другие способы добраться до (4,0) за 2 прыжка (например, (0,0) → (2,−5–√) → (4,0)).
Изображение соответствует первому набору входных данных из примера. Длина обоих прыжков равна 3, одному из любимых чисел Кролика.
Таким образом, перед каждым прыжком Кролик выбирает одно из чисел ai и прыгает из текущей точки на расстояние ровно ai в произвольном направлении. Одно и то же число он может выбирать любое количество раз.