Всероссийская олимпиада школьников 2015-2016 УЧ. Г

ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ 2015-2016 УЧ. Г.

ШКОЛЬНЫЙ ЭТАП (ИНФОРМАТИКА И ИКТ)

КЛАССЫ (ПРОДОЛЖИТЕЛЬНОСТЬ 210 МИНУТ)

 

Задача A. От перестановки что-то меняется...

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Всем известно, что «от перестановки слагаемых сумма не изменяется». Однако, случается и так, что перестановка двух чисел приводит к более интересным последствиям.

Пусть, например, заданы три числа: a₁, a₂, a₃. Рассмотрим равенство a₁+ a₂= a₃. Оно может быть неверным (например, если a₁= 1, a₂= 4, a₃= 3), однако может стать верным, если поменять некоторые числа местами (например, если поменять местами a₂ и a₃, оно обратится в равенство 1 + 3 = 4).

Ваша задача – по заданным трем числам определить: можно ли их переставить так, чтобы сумма первых двух равнялась третьему.

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

Входной файл INPUT.TXT содержит три целых числа: a₁, a₂, a₃ (−10⁸ ≤ a₁, a₂, a₃ ≤ 10⁸).

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

В выходной файл OUTPUT.TXT выведите слово «YES», если заданные числа можно переставить так, чтобы сумма первых двух равнялась третьему. В противном случае выведите в выходной файл слово «NO».

Примеры

№	INPUT.TXT	OUTPUT.TXT
	3 5 2	YES
	2 2 5	NO
	2 2 4	YES

 

Задача B. Развлечения гномов

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Гномы свободно владеют системами счисления с разными основаниями и достигли они этого ежедневными тренировками. Именно поэтому каждое утро у гномов начинается с того, что они текущую календарную дату переводят в другую систему счисления. Ваше задание такое же: перевести заданную дату D/M/Y в систему счисления с основанием D+1.

Для обозначения цифр больших 9 используются большие латинские буквы в алфавитном порядке.

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

Входной файл INPUT.TXT содержит строку, содержащую дату в формате D/M/Y в десятичной системе счисления (1 ≤ D ≤ 31, 1 ≤ M ≤ 12, 0 ≤ Y ≤ 9999).

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

В выходной файл OUTPUT.TXT выведите одну строку – дату в формате D/M/Y в системе счисления с основанием D+1.

Пример

№	INPUT.TXT	OUTPUT.TXT
	1/10/2000	1/1010/11111010000

Задача C. Звездные прямоугольники

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Астроном Костя очень любит разглядывать звездное небо в телескоп. Однажды, глядя на звезды, он задумался: а сколько различных звездных прямоугольников видно на небе? Звездный прямоугольник – это четыре различных звезды, которые при соединении четырьмя прямыми линиями образуют прямоугольник.

Два звездных прямоугольника считаются различными, если хотя бы одна звезда из набора звезд, их формирующих отличается.

Помогите Косте сосчитать количество различных звездных прямоугольников.

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

Входной файл INPUT.TXT содержит число N (1 <= N <= 100) – количество звезд. Следующие N строк содержат координаты звезд (X, Y), разделенные пробелом. Координаты представлены целыми числами (0 <= X, Y <= 10⁵).

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

В выходной файл OUTPUT.TXT выведите количество различных прямоугольников, образующихся звездами.

Примеры

№	INPUT.TXT	OUTPUT.TXT
	4 1 1 10 10 1 10 10 1
	4 1 1 2 10 9 10 10 1

 

Задача D. Мафия в городе

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Об этом еще никто не знает, но многие догадываются – мафия уже в городе. Поговаривают, что в планах главы мафиозного клана захват контроля над всем городом, однако поначалу он решил ограничиться захватом основных линий связи города.

В городе находятся n базовых телефонных станций, некоторые пары которых соединены двусторонними каналами связи. Для удобства, занумеруем базовые станции целыми числами от 1 до n, канал связи в этом случае задается парой чисел (u, v) – номерами станций, которые он соединяет.

Будем говорить, что канал связи (u, v) – контролируется мафией, если захвачена, либо станция u, либо станция v (либо обе).

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: n и m (2 ≤ n ≤ 18, 0 ≤ m). Каждая из последующих m строк описывает один канал связи и содержит по два целых числа: u и v (1 ≤ u, v ≤ n, u ≠ v) – номера базовых станций, соединенных этим каналом связи. Любая пара станций соединена не более, чем одним каналом.

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

В первой строке выходного файла OUTPUT.TXT выведите два числа: k и c – соответственно, минимальное количество базовых станций, которые необходимо захватить для того, чтобы контролировать все каналы связи, и число способов захватить такое количество станций так, чтобы контролировать все каналы связи.

Во второй строке выведите k чисел – номера базовых станций, соответствующих одному из способов захвата.

Примеры

№	INPUT.TXT	OUTPUT.TXT
	3 3 1 2 2 3 3 1	2 3 1 2
	5 4 1 2 1 3 1 4 1 5	1 1 1

Пояснение

В первом примере существует три способа захватить две станции так, чтобы контролировать все каналы связи: {1, 2}, {1, 3}, {2, 3}.

 

ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ 2015-2016 УЧ. Г.