Задача
Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.
Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.
Выходные данные:
Для каждого теста вывести в отдельной строке
"YES" если возможно встретить всех преподавателей за один день, или
"NO", если это невозможно.
Тесты
| Входные данные | Вывод программы |
| 2 1 1 2 2 1 2 3 4 |
YES NO |
| 1 1 5 6 |
YES |
| 2 2 1 4 7 9 3 1 30 2 5 5 10 |
NO YES |
Решение
Если представить график каждого преподавателя отрезком, то задача сводится к вопросу об общем пересечении всех отрезков. Если такое пересечение существует, то ответ положительный, иначе отрицательный.
Для нахождения пересечения двух отрезков нужно посчитать максимум из левых концов: $l$ и минимум из правых: $r$, тогда если $l > r$, то пересечения нет, иначе $[l; r]$ — искомое пересечение.
Теперь нам надо последовательно находить пересечение текущего пересечения и нового отрезка, для этого просто посчитаем l — максимальный из левых концов отрезков и r — минимальный из правых. Если $l > r$ то ответ "YES", иначе "NO".
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> using namespace std; int main() { int t; cin >> t; while(t--){ int n, l = 0, r = 32; cin >> n; for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; l = max(l, a); r = min(r, b); } cout << (l > r ? "NO" : "YES") << endl; } return 0; } |
Ссылки
Задача на E-Olymp
Код на IdeOne
Засчитанное решение на E-Olymp