Codeforces Round 919 (Div. 2) |
---|
Закончено |
Алекс решает задачу. У него есть $$$n$$$ ограничений на то, каким может быть целое число $$$k$$$. Существует три типа ограничений:
Помогите Алексу найти количество целых чисел $$$k$$$, которые удовлетворяют всем $$$n$$$ ограничениям. Гарантируется, что ответ конечен (существует хотя бы одно ограничение типа $$$1$$$ и хотя бы одно ограничение типа $$$2$$$). Также гарантируется, что ни одно из ограничений не совпадает в точности с другим.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 100$$$) — количество ограничений.
Следующие $$$n$$$ строк описывают ограничения. Каждая строка содержит два целых числа $$$a$$$ и $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$). Число $$$a$$$ обозначает тип ограничения. Если $$$a=1$$$, то $$$k$$$ должно быть больше или равно $$$x$$$. Если $$$a=2$$$, то $$$k$$$ должно быть меньше или равно $$$x$$$. Если $$$a=3$$$, то $$$k$$$ должно быть не равно $$$x$$$.
Гарантируется, что существует конечное количество целых чисел, удовлетворяющих всем $$$n$$$ ограничениям (существует хотя бы одно ограничение типа $$$1$$$ и хотя бы одно ограничение типа $$$2$$$). Также гарантируется, что ни одно из ограничений не совпадает в точности с другим (другими словами, все пары $$$(a, x)$$$ различны).
Для каждого набора входных данных выведите одно целое число — количество целых чисел $$$k$$$, удовлетворяющих всем $$$n$$$ ограничениям.
641 32 103 13 521 52 4103 63 71 21 73 1003 442 1002 981 33 9961 52 101 92 23 23 951 12 23 13 23 361 100002 9000000003 5000000001 1000000003 100003 900000001
7 0 90 0 0 800000000
В первом наборе входных данных $$$k \geq 3$$$ и $$$k \leq 10$$$. Кроме того, $$$k \neq 1$$$ и $$$k \neq 5$$$. Возможные целые числа $$$k$$$, удовлетворяющие ограничениям: $$$3,4,6,7,8,9,10$$$. Поэтому ответ равен $$$7$$$.
Во втором наборе входных данных $$$k \ge 5$$$ и $$$k \le 4$$$, что невозможно. Поэтому ответ равен $$$0$$$.
Название |
---|