ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


Макс и крестики-нолики

Гость
• Вопросы к жюри (2)

Задачи раздела

• Макс и дегустация сыра
• Макс и дегустация сыра
• Макс и дедлайны
• Макс и дизайнерская плитка
• Макс и дни рождения великих
• Макс и канцелярские товары
• Макс и ключ
• Макс и командировочные документы
• Макс и крестики-нолики
• Макс и кубик Рубика 2x2x2
• Макс и ленточки
• Макс и маршрутка
• Макс и математические часы
• Макс и номера телефонов
• Макс и образовательный лагерь
• Макс и объединение результатов
• Макс и ожидание Нового Года

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/3000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и крестики-нолики
Макс и крестики-нолики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Макс и Владимир решили сыграть в крестики-нолики. Так как обычная игра на поле $$$3 \times 3$$$ кажется им слишком скучной, они решили играть на бесконечной доске. Побеждает, как и раньше, тот, кто первым составит вертикальный, горизонтальный или диагональный ряд из трёх своих фигур.

Увы, у Макса с Владимиром не оказалось под рукой бесконечного листа бумаги, поэтому играть пришлось в уме. Это привнесло свои трудности.

— Погоди-ка. Так я же вроде уже выиграл... на четыреста тридцать пятом ходу! — в какой то момент сказал Макс.

— Вроде того. Вот только я, похоже, построил ряд уже на четыреста двадцать четвёртом, — ответил Владимир.

Помогите Максу и Владимиру определить, кто же на самом деле оказался победителем. Гарантируется, что хотя бы один ряд из трёх одинаковых символов был собран.

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

Первая строка содержит целое число $$$N$$$ ($$$6 \le N \le 10^5$$$) — количество сделанных ходов.

Следующие $$$N$$$ строк описывают сделанные ходы. Каждая их них содержит целые числа $$$X_i$$$ и $$$Y_i$$$ ($$$-10^9 \le X_i, Y_i \le 10^9$$$) — координаты клетки, в которую был поставлен символ. Координаты всех ходов различны.

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

Выведите одно целое число — номер хода, после которого в игре определился победитель.

Примеры

Входные данные
6
1 1
0 0
1 2
0 2
1 3
0 1
Выходные данные
5
Входные данные
8
4 3
1 2
3 1
3 0
4 1
4 4
4 2
4 5
Выходные данные
7

Для отправки решений необходимо выполнить вход.

www.contester.ru