Задача J. Логика В.О. Ключевского

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

"Когда дурак начинает считать себя остроумным, количество остроумных людей не увеличивается; когда умный человек признает себя остроумным, всегда становится одним умным меньше и иногда одним остроумным больше; когда остроумный начинает считать себя умным, всегда одним остроумным становится меньше и никогда не бывает одним умным больше."

(В.О. Ключевский "Афоризмы и мысли об истории")

Введём множество I = {О, У, Д}. Положим D ⊂ I × I равным D = {(Д, О), (У, О), (О, У)}. Определим на множестве D многозначные функции Ключевского KY(a, b), KO(a, b), значения которых равны множеству возможных приращений количеств умных и остроумных людей соответственно, если "a считает себя b".

Дано N пар (ai, bi) ∈ D. Определить нижнюю и верхнюю границы сумм Ni = 1KY(ai, bi) и Ni = 1KO(ai, bi).

Формат входного файла

Входной файл содержит целое число N. Далее следуют N пар целых чисел Ai Bi. Таблица соответствия: О — 0, У — 1, Д — 2.

Формат выходного файла

Выходной файл должен содержать 4 числа: mY MY mO MO.

Ограничения

1 ≤ N ≤ 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1 0
-1 -1   0 1
2
3
0 1
2 0
1 0
-1 -1   -1 0

Разбор

KY(Д, О) = 0, KO(Д, О) = 0
KY(У, О) =  − 1, KO(У, О) = {0, 1}
KY(О, У) = 0, KO(О, У) =  − 1

Пусть (a, b) ∈ D. Обозначим через C(a, b) количество индексов i, для которых (ai, bi) = (a, b). Тогда
KY(ai, bi) =  − C(У, О),
 − C(О, У) ≤ KO(ai, bi) ≤ C(У, О) − C(О, У).


0.089s 0.010s 13