Страница: 1 Отображать по:
#111985
Информатическая сила
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В одной школе издавна велись соревнования в информатической силе между классами одной параллели. По введённой учителями шкале информатическая сила класса — это суммарное количество задач, решённых всеми школьниками этого класса на последней районной олимпиаде. Соревновательный дух школы весьма высок, а значит, каждый участник решил хотя бы одну задачу.

В школьной летописи сохранились информатические силы двух классов, \(A\) и \(B\), а также количество задач на олимпиаде \(N\). Завучу, нашедшему летопись, очень хочется узнать, могло ли быть в первом классе больше учеников, чем во втором.

Напишите программу, которая определит, могло ли быть учеников в классе с информатической силой \(A\) больше, чем учеников в классе с информатической силой \(B\).

Входные данные

Вводятся три целых числа, каждое в своей строке — \(A\), \(B\), \(N\) (\(0 \le A, B \le 10 000, 1 \le N \le 10 000\)).

Выходные данные

Выведите «Yes», если в первом классе могло быть больше учеников, чем во втором, и «No», в противном случае.

Примечания

Тесты к этой задаче состоят из трех групп.

  • Тесты 1 – 3. Тесты из условия, оцениваются в ноль баллов.
  • Тесты 4 – 17. В тестах этой группы \(0 \le A, B \le 10, 1 \le N \le 10\). Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы.
  • Тесты 18 – 30. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 70 баллов, баллы ставятся только при прохождении всех тестов группы.

Примеры
Входные данные
60
30
4
Выходные данные
Yes
Входные данные
30
30
1
Выходные данные
No
Входные данные
30
150
4
Выходные данные
No
#111988
Хоровод
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Настал декабрь, и вместе с ним пришло время готовиться к Новому Году. На острове рыцарей и лжецов этот праздник традиционно отмечается очень масштабно. Праздничный стол, новогодняя ёлка, конфетти и бенгальские огни — все готово к началу торжества.

Как вы знаете, на острове рыцарей и лжецов живут только два вида жителей — рыцари и лжецы. Рыцари никогда не лгут, так как этого им не позволяют их высокие моральные принципы. Лжецы же, наоборот, всегда говорят только неправду.

Важнейшей частью празднования Нового года является хоровод вокруг елки. Все приглашенные жители острова берутся за руки и движутся по кругу под музыку. Поскольку население острова весьма консервативно, то в этом году жители хотят выстроиться в круг в том же порядке, что и в прошлом. Однако данных о том, как был устроен хоровод, не сохранилось. Известно только, что каждый житель острова запомнил, кем были его соседи по хороводу (рыцарями или лжецами).

Опросив каждого человека, приглашенного на празднование, вы узнали, кем были их соседи по их словам (при этом лжецы говорят неправду про каждого соседа). Осталось только придумать какое-нибудь расположение жителей острова в круг так, чтобы их показания не противоречили друг другу.

Напишите программу, которая по списку жителей и их показаний определит, существует ли такое расположение или же выстроиться в хоровод как в прошлом году не получится.

Входные данные

В первой строке входных данных дано целое число n (2 ≤ n ≤ 105) — количество жителей на острове лжецов.

В следующих n строках даны целые числа li и ri (0 ≤ li, ri ≤ 1) — данные о соседях i-го человека. Если li = 0, то i-й житель утверждает, что его сосед по хороводу в направлении против часовой стрелки был лжецом, а если li = 1, то рыцарем. Аналогично, число ri содержит информацию о соседе по часовой стрелке.

Выходные данные

Требуется вывести «Yes», если существует способ выстроить людей по указанным правилам, или «No», если нет.

Примеры тестов

Входные данные
5
1 1
0 1
1 1
0 0
1 0
Выходные данные
Yes
Входные данные
2
0 0
1 1
Выходные данные
No

Примечание

Тесты к этой задаче состоят из четырёх групп.

  • Тесты 1 – 2. Тесты из условия, оцениваются в ноль баллов.
  • Тесты 3 – 10. На тесты этой группы накладывается ограничение n ≤ 10. Группа тестов оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов группы.
  • Тесты 11 – 26. На тесты этой группы накладывается ограничение n ≤ 20. Группа тестов оценивается в 25 баллов, баллы ставятся только при прохождении всех тестов группы.
  • Тесты 27 – 38. В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 55 баллов, баллы ставятся только при прохождении всех тестов группы.

В первом примере, можно выстроить жителей в порядке (2, 1, 3, 5, 4) по часовой стрелке. Показания всех людей будут сходиться в этом случае, например, когда четвертый житель будет рыцарем, а все остальные четыре человека — лжецами.

Во втором примере, очевидно, нельзя получить никакого решения, так как выстроить двух человек в хоровод можно лишь одним способом. Рассмотрим два случая: если первый человек — рыцарь, то, по его словам, второй человек — лжец, однако, из лживости его слов следует, что первый человек не рыцарь. С другой стороны, если первый человек — лжец, то из его показаний следует, что второй человек — рыцарь, но второй человек говорит, что первый — тоже рыцарь. Таким образом, поскольку в обоих случаях мы получили противоречие, не существует способа построить хоровод из имеющегося набора жителей.

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест