Решение задачи Корова и друг с Codeforces

Без пояснения   Просмотров: 24

У Бесси действительно много друзей, потому что она — всеми любимая корова! Ее новый друг Кролик пытается допрыгать до Бесси, чтобы поиграть вместе!

Точнее, он хочет попасть из (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 в произвольном направлении. Одно и то же число он может выбирать любое количество раз.

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	do {
		int n, x;
		cin >> n >> x;
		int mx = 0, ans = INT_MAX;
		for(int i = 0; i < n; i++) {
			int a;
			cin >> a;
			if(a == x) ans = 1;
			mx = max(mx, a);
		}
		ans = min(ans, max(2, (x + mx - 1) / mx));
		cout << ans << '\n';
	} while(--t);
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта