Задачи олимпиады "Школьная олимпиада по Красноярскому краю, 9-11 классы"
Задача A. От перестановки что-то меняется ...
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Всем известно, что «от перестановки слагаемых сумма не изменяется». Однако, случается и так, что перестановка двух чисел приводит к более интересным последствиям.
Пусть, например, заданы три числа: a1, a2, a3. Рассмотрим равенство a1+ a2= a3. Оно может быть неверным (например, если a1= 1, a2= 4, a3= 3), однако может стать верным, если поменять некоторые числа местами (например, если поменять местами a2 и a3, оно обратится в равенство 1 + 3 = 4).
Ваша задача – по заданным трем числам определить: можно ли их переставить так, чтобы сумма первых двух равнялась третьему.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа через пробел: a1, a2, a3 (−108 ≤ a1, a2, a3 ≤ 108).
Выходные данные
В выходной файл OUTPUT.TXT выведите слово «YES», если заданные числа можно переставить так, чтобы сумма первых двух равнялась третьему. В противном случае выведите в выходной файл слово «NO».
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 5 2
YES
2
2 2 5
NO
3
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, 1 ≤ Y ≤ 9999).
Выходные данные
В выходной файл OUTPUT.TXT выведите одну строку – дату в формате D/M/Y в системе счисления с основанием D+1.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
1/10/2000
1/1010/11111010000
Задача C. Звездные прямоугольники
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Астроном Костя очень любит разглядывать звездное небо в телескоп. Однажды, глядя на звезды, он задумался: а сколько различных звездных прямоугольников видно на небе? Звездный прямоугольник – это четыре различных звезды, которые при соединении четырьмя прямыми линиями образуют прямоугольник.
Два звездных прямоугольника считаются различными, если хотя бы одна звезда из набора звезд, их формирующих отличается.
Помогите Косте сосчитать количество различных звездных прямоугольников.
Входные данные
Входной файл INPUT.TXT содержит число N (1 ≤ N ≤ 100) – количество звезд. Следующие N строк содержат координаты звезд (X, Y), разделенные пробелом. Координаты представлены целыми числами (0 ≤ X, Y ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите количество различных прямоугольников, образующихся звездами.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
4 1 1 10 10 1 10 10 1
1
2
4 1 1 2 10 9 10 10 1
0
Задача 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
1
3 3
1 2
2 3
3 1
2 3 1 2
2
5 4
1 2
1 3
1 4
1 5
1 1 1
Пояснение
В первом примере существует три способа захватить две станции так, чтобы контролировать все каналы связи: {1, 2}, {1, 3}, {2, 3}.
