C. Success Rate - Codeforces

Question

Witam,
Próbuje to rozwiązać: https://codeforces.com/problemset/problem/807/C

Ale nie przychodzi mi nic do głowy co wpasowywałoby się w wymagania co do złożoności, konkretnie logarytmicznej.

Namachałem funkcję do sprawdzenia czy konkretna liczba może rozwiązuje problem, wygląda tak:

long long GCD(long long a, long long b) {
	if (b == 0)
		return a;

	return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return (a * b) / GCD(a, b);
}

bool check(int x, int y, int p, int q, int k) {
	int left = 0;
	int right = k;

	while (left <= right) {
		long long wins = (1LL * left + right) / 2;

		long long x2 = x + wins;
		long long y2 = y + k;

		long long lcm = LCM(y2, q);
		x2 = x2 * (lcm / y2);
		y2 = lcm;

		long long p2 = p;
		long long q2 = q;

		p2 = p2 * (lcm / q2);
		q2 = lcm;

		if (x2 == p2 && y2 == q2)
			return true;
		else if (x2 > p2)
			right = wins - 1;
		else
			left = wins + 1;
	}

	return false;
}

Czyli sprowadzam liczby do wspólnego mianownika dodając konkretną ilość wygranych do ogółu, używając binary searcha. Potem używam tej funkcji check w pętli O(y) i pokolei sprawdzam każdą możliwą liczbę. Nie dość, że to nie zawsze działa, to jeszcze jest za wolne. Jakieś pomysły?
 

Comments

Jakby co do prawie wszystkich zadań na codeforces są rozwiązania w zakładce "Tutorials". To zadanie akurat idzie z bin searcha, ale trochę innego.

---

O dzięki, nie wiedziałem. Schowali to całkiem na dole :D  Takie proste zadanie, ale jak zwykle trzeba było sobie utrudnić :/ Dzięki!