Educational Codeforces Round 8 |
---|
Закончено |
Лимак — медведь гризли. Он большой и страшный. Прогуливаясь по лесу, вы случайно встретились с ним. Это не лучшее, что могло с вами произойти. Он съест все ваши печеньки, если вы не продемонстрируете ему свои математические навыки. Лимак решил дать вам головоломку, чтобы проверить вас.
Всем известно, что у Лимака, как и любого другого медведя, есть множество чисел. Вам известна некоторая информация об этом множестве:
Лимак загадочно улыбнулся вам и дал q подсказок об этом множестве. i-я подсказка выглядит следующим образом: "Количество элементов в множестве со значениями в промежутке от 1 до upToi включительно равно quantityi."
Вот-вот Лимак расскажет вам настоящую головоломку, но что-то явно не так... Эта улыбка была очень странной. Вы заподозрили причину этого. Может Лимак обманул вас? Или он всё-таки честный медведь гризли?
Вам заданы числа n, b, q и подсказки, определите мог ли Лимак быть честным с вами, то есть существует ли хотя бы одно множество с такими ограничениями. Если такое возможно выведите ''fair". В противном случае выведите ''unfair".
В первой строке находятся три целых числа n, b, q (5 ≤ n ≤ b ≤ 104, 1 ≤ q ≤ 104, n кратно 5) — количество элементов в множестве, верхняя граница для чисел множества и количество подсказок.
В следующих q строках находятся описания подсказок. i-я из них содержит пару целых чисел upToi и quantityi (1 ≤ upToi ≤ b, 0 ≤ quantityi ≤ n).
Выведите ''fair" если существует хотя бы одно множество, удовлетворяющее всем свойствам и подсказкам. В противном случае выведите ''unfair".
10 20 1
10 10
fair
10 20 3
15 10
5 0
10 5
fair
10 20 2
15 3
20 10
unfair
В первом примере всем условиям удовлетворяет только множество {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Во втором примере также существует только одно множество, удовлятворяющее всем условиям: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.
Легко видеть, что третий пример противоречив. Таким образом, Лимак вас обманул :-(
Название |
---|