Задачи олимпиады "II (районный) этап Всероссийской олимпиады школьников Красноярского края по информатике"

Задача A. Халява

Гриша очень любит газировку PupsiCola. Однажды он узнал, что, собрав несколько крышек со звездочками, можно получить футболку. Гриша нашел A крышек с одной звездочкой, B крышек с двумя звездочками и C крышек с тремя звездочками. На футболку можно обменять набор крышек, общее количество звездочек на которых не меньше K.

Помогите Грише узнать, сколько футболок он может получить.

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

Входной файл INPUT.TXT содержит целые числа A, B, C и K (0 ≤ A, B, C ≤ 100, 1 ≤ K ≤ 1000).

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

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

Примеры

Задача B. Номера автобусов

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

Основная часть государственного регистрационного номера состоит из 6 символов: трех букв и трех цифр. Сначала идет буква, затем 3 цифры и еще 2 буквы заканчивают запись. В качестве цифр могут использоваться любые цифры от 0 до 9, а в качестве букв только прописные буквы, обозначения которых присутствуют как в английском, так и в русском алфавите, т.е. только следующие символы: A, B, C, E, H, K, M, O, P, T, X, Y. Например, «P204BT» - правильный номер, а «X182YZ» и «ABC216» - нет.

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

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

Первая строка входного файла INPUT.TXT содержит единственное натуральное число N – количество записанных Васей номеров (N ≤ 50). Далее следует N строк с записями номеров автобусов. Длины строк от 1 до 300 и содержат только символы с кодами ASCII от 33 до 127 (не содержат пробелов, специальных и русских символов).

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

В выходной файл OUTPUT.TXT выведите N строк, в i-й строке должно содержаться «Yes», если соответствующая i-я запись номера верна и «No» в противном случае.

Пример

Задача C. Бинарные числа

Говорят, что плохой программист – это тот, кто считает, что в одном килобайте 1000 байт, а хороший программист – это тот, кто полагает, что в одном километре 1024 метра.

Многим эта шутка понятна, так как все знают, что в процессах, связанных с информатикой и компьютерной техникой, фигурирует множество значений, выражаемых степенью двойки, то есть чисел вида 2^K, где K – некоторое неотрицательное целое число. Назовем такие числа бинарными. Это такие числа как 2, 4, 8, 16, 32 и т.д. Действительно, когда речь идет о размере памяти или о разрешении экрана монитора, то мы часто наталкиваемся на бинарные числа. Все это связано с принципом хранения информации в памяти ЭВМ.

Задано целое число N. Требуется определить, является ли оно бинарным.

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

Входной файл INPUT.TXT содержит единственное целое число N, не превосходящее 10000 по абсолютной величине.

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

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

Примеры

Задача D. Конная прогулка

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

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

В первой строке входного файла INPUT.TXT содержится два натуральных числа N и M – размеры поля (6 ≤ N, M ≤ 100). Далее следует карта поля: N строк по M символов в каждой строке. Символом «.» (точка) обозначается пустое пространство, начальная позиция коня задаётся единственным в поле символом «K» (заглавная буква английского алфавита).

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

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

Пример

 1 16 27 22  3 18 47 54
26 23  2 17 46 55  4 19
15 28 25 50 21 48 53 56
24 35 30 45 58 51 20  5
29 14 59 34 49 44 57 52
36 31 38 41 60 63  6  9
13 40 33 62 11  8 43 64
32 37 12 39 42 61 10  7

Задача E. Неправильное сложение

Володя написал программу, которая складывает в столбик два числа. К сожалению, он не разобрался, как правильно переносить единицу из одного разряда в следующий. Поэтому программа стала выполняться следующим образом. Сначала она складывает последние цифры обоих чисел и записывает результат, как в случае, если он однозначный, так и в случае, если он двузначный. Затем программа складывает предпоследние цифры обоих чисел и результат сложения приписывает слева к результату предыдущего сложения. Далее процесс повторяется для всех разрядов. Если в одном числе цифр меньше, чем в другом, то программа размещает нули в соответствующих разрядах более короткого числа.

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

Требуется написать программу, которая поможет Феде и Володе определить, верно ли утверждение, что, складывая заданные три числа в разном порядке, можно получить разные суммы.

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

Входной файл INPUT.TXT содержит в одной строке три целых числа a, b и c (1 ≤ a, b, c ≤ 10⁶). Все числа в строке разделены пробелом.

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

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

В последующих строках необходимо вывести все возможные суммы, которые можно получить, складывая числа a, b и c. Суммы следует выводить по одной на строке и в порядке их возрастания.

Примеры