Решение задачи "Диагноз Бори" с Codeforces

С пояснением   Просмотров: 13


Кажется, Боря серьезно заболел. Чтобы проверить это и узнать точный диагноз, ему нужно пройти обследование у n врачей. Каждому из врачей требуется вся информация обо всех предыдущих обследованиях, поэтому Боря должен посещать их в заданном порядке (т. е. сначала посетить доктора 1, затем доктора 2, затем доктора 3 и так далее). И только от последнего врача Боря получит информацию о своём здоровье.

График работы у врачей непростой. Врач под номером i выходит на работу в день s i и работает каждый d i-й день. Таким образом, он работает в дни s i, s i + d i, s i + 2d i, ....

Приём врача занимает довольно много времени, поэтому Боря не может посещать более чем одного врача за день. За какое наименьшее время он сможет обойти всех врачей?

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int n, s, d, ans;
 
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> s >> d;
 
		while (s <= ans)
			s += d;
		ans = s;
 
	}
	cout << ans << endl;
}

         

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


Заметим, что Боря может применять жадный алгоритм: посещать каждого врача настолько рано, насколько это возможно. Остаётся понять, как находить этот самый ранний день. Ограничения этой задачи позволяют делать это любым разумным образом.

Например, можно просто перебирать все дни, начиная от текущего, и проверять, работает ли в этот день нужный врач. На шаге i перебрать придётся не более чем max(s i, d i) дней.

Есть и более эффективный способ. Можно за O(1) найти такое минимальное x, большее номера текущего дня, что . Если x ≥ s i, то Боря пойдёт к врачу в день x, иначе — в день s i. Получается решение за O(n).

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

Комментарии

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