Задачи олимпиады "1й тур школьной олимпиады по Красноярскому краю"
Задача A. Хоккей
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В соревнованиях по хоккею участвует N команд. Сколько существует вариантов распределения комплектов золотых, серебряных и бронзовых медалей, если одно призовое место может занять только одна команда?
Входные данные
Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 104) – количество команд.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – искомое количество способов награждения участников.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3
6
2
20
6840
Задача B. Игра со спичками
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число — N (1 ≤ N ≤ 10000) начальное количество спичек в кучке.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
1
2
3
2
Задача C. Счастливые числа
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Все знают, что счастливые числа – это те числа, которые содержат только счастливые цифры 7 и 4. Вам нужно найти количество счастливых чисел не больших N.
Входные данные
В единственной строке входного файла INPUT.TXT записано натуральное число N, не превышающее 1032.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — ответ на задачу.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
56
4
Задача D. Перетягивание каната
(Время: 3 сек. Память: 16 Мб Баллы: 100)
Для участия в соревнованиях по перетягиванию каната зарегистрировалось N человек. Некоторые из участников могут быть знакомы друг с другом. Причем, если двое из них имеют общего знакомого, то это не означает, что они обязательно знакомы друг с другом.
Организаторы соревнований заинтересованы в их качественном проведении. Они хотят разделить всех участников на две команды так, чтобы в первой команде было K человек, а во второй – N-K человек. Из всех возможных вариантов формирования команд, организаторы хотят выбрать такой вариант, при котором сумма сплоченностей обеих команд максимальна. Сплоченностью команды называется количество пар участников этой команды, знакомых друг с другом. Ваша задача – помочь организаторам найти требуемое разделение участников на две команды.
Входные данные
В первой строке входного файла INPUT.TXT задаются три числа N, K, M, разделенные одиночными пробелами, где N – общее число зарегистрированных участников, K – требуемое количество человек в первой команде, M – количество пар участников, знакомых друг с другом.
Каждая из следующих M строк содержит два различных числа, разделенные пробелом – номера двух участников, знакомых друг с другом. Все участники нумеруются от 1 до N.
Ограничения: все числа целые, 0 < K < N < 25, 0 ≤ M ≤ N(N-1)/2
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одну строку, состоящую из K чисел, каждое из которых задает номер участника, попавшего в первую команду. Числа должны быть разделены пробелами. Если существует несколько решений данной задачи, то выведите любое из них.