Конспект занятия «Программирование. Профильный уровень»

Конспект занятия «Программирование. Профильный уровень»

Задачи по программированию

ЗАДАЧИ УРОВНЯ А

(За каждую правильно решенную задачу участник получает 2 балла)

Задача 1-А. Однажды Петя Васечкин сдал сессию только на пятерки. И все потому, что перед сдачей очередного экзамена он с удовольствием съедал счастливый автобусный билет.

С тех пор он озабочен приобретением при каждой поездке счастливого билета.

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

Формат входных данных:

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

Формат выходных данных:

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

Пример входного файла: Пример выходного файла:

123122 5

Задача 2-А. Имеется список, состоящий из английских слов, записанных строчными буквами, и натуральных чисел, расположенных вперемешку. Слова и числа разделяются одним пробелом.

Требуется выполнить сортировку слов в алфавитном порядке, а чисел – по возрастанию, причем, если i-й элемент списка является словом, то и после преобразований он должен остаться словом, если i-й элемент списка – число, то он должен остаться числом и после преобразований.

Требуется написать программу, которая произведет нужную сортировку.

Формат входных данных:

Входной файл содержит слова и натуральные числа. Количество элементов списка не превосходит 3000.

Формат выходных данных:

Выходной файл должен содержать одну отсортированную строку, элементы которой разделены одним пробелом.

Пример входного файла: Пример выходного файла:

orange 123 end begin 2 then 5 begin 2 end orange 5 then 123

Задача 3-А. C 2009 года наша страна празднует день программиста 13 сентября.

Каким днем недели будет 13 сентября указанного года (начиная с 2009 до 10 000 года нашей эры)? Следует учитывать, что год високосный, если он кратен 4 и при этом не кратен 100, либо кратен 400, например, 2012 и 2400 — високосные года, а 2100 – не високосный. День недели вывести по—английски: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.

Пример входного файла: Пример выходного файла:

2009 Sunday

Задача 4-А. Программа должна по данному n, 0≤n≤10⁹

вычислить последнюю цифру числа Фибоначчи F_n.

Пример входного файла: Пример выходного файла:

10 9

Задача 5-А. Многие дети начинают играть со считалок. Играющий, на которого попадает последнее слово текста, выходит из круга. Предположим, что в кругу стоит N детей. Составить программу, которая выведет номера детей в том порядке, в каком они выходят из круга.

Входные данные: В первой строке задается количество детей (1<N<= 1000). Во второй строке вводится сама строка считалки (количество слов в строке от 2 до 1000, слова состоят не более 25 символов и разделены пробелом, в конце строки стоит точка).

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

Пример входного файла: Пример выходного файла:

10 8 6 5 7 10 3 2 9 4

Раз два три четыре пять вышел зайчик погулять. 1

Задача 6-А. Дано N целых чисел. Найдите наибольшее число, являющееся произведением трех из данных чисел.

Формат входных данных

Первая строка входных данных содержит натуральное число N, не превосходящее 10⁶. Далее идет N целых чисел, не превосходящих по модулю 1000, по одному числу на строке.

Формат выходных данных

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

Пример входного файла: Пример выходного файла:

5 72

2 -3 -4 5 6

Комментарий. 72=(-3)×(-4)×6.

Задача 7-А. Программа получает на вход две строки, содержащие даты, записанные в формате dd.mm.yyyy, где dd – день месяца от 01 до 31, mm – номер месяца от 01 до 12, yyyy – номер года от 0001 до 2999. Программа должна вычислить разность между этими датами (количество дней между ними) и вывести ответ в виде натурального числа. Обе даты корректные, вторая позже первой.

Учтите, что года, чьи номера делятся на 4 и не делятся на 100, а также все года, чьи номера делятся на 400 являются високосными.

Пример входного файла: Пример выходного файла:

01.01.0001 1

02.01.0001

29.02.2004 366

01.03.2005

ЗАДАЧИ УРОВНЯ В

(За каждую правильно решенную задачу участник получает 15 баллов)

Задача 1-В. При составлении волшебных зелий Северус Снегг заставляет учеников заучивать все рецепты. Но однажды Рон Уизли не приготовил домашнее задание и не может приготовить смесь. Верная Гермиона передала Гарри Поттеру шпаргалку, на которой записаны названия элементов, входящих в рецепт. Но необходимо знать, в каком порядке их следует смешивать. И вот теперь Гарри пытается перебрать различные варианты смешивания, чтобы выручить Рона.

Помогите Гарри получить все возможные варианты приготовления зелья.

Формат входных данных:

В первой строке входного файла записано целое число: N – количество составных элементов требуемой смеси. В следующих N строках записаны названия элементов. (0<N<=100)

Формат выходных данных:

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

Пример:

вход

выход
3 сера пепел растертый зуб вампира	1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

Задача 2-В. В школе Хогварц ученики, помимо других предметов, изучают алхимию. Известно, что химические вещества состоят из отдельных элементов. Однажды на уроке алхимии Северус Снегг выдал ученика набор из N химических веществ и для каждого вещества выписал список составляющих его элементов. Элемент задается своим номером в таблице Менделеева (маги тоже ею пользуются!). Известно, что существует элемент, входящий в состав всех веществ. Помогите магам-ученикам найти его. Для простоты считаем, что все вещества состоят из одинакового числа элементов. Всего в таблице Менделеева 250 элементов (по крайней мере, у магов).

Формат входных данных:

В первой строке входного файла записаны через пробел два целых числа: N – количество веществ, M – число элементов в веществе. В следующих N строках записаны через пробел по M целых чисел – номера составляющих элементов. Всего задано не более 30000 веществ.

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

Формат выходных данных:

В выходной файл вывести номер найденного элемента.

Лимит времени: 1 секунда на тест.

Пример:

вход

выход
3 4 1 2 5 64 2 3 4 5 1 5 57 85	5

Задача 3-В. Археологи нашли в раскопках длинный лист Мёбиуса с набранными на нем буквами (лист Мёбиуса не имеет начала и конца, т.е. нет верха и низа и все символы располагаются как будто на одной стороне). Если отметить начало, то можно найти одно и то же слово несколько раз. Так как лист Мёбиуса не имеет начала и конца, то символы могут быть как в начале строки, так и в конце. Поэтому, при поиске строки  необходимо все символы циклически сдвигать влево, забирая символ с конца и переставляя его на первое место, так чтобы их можно было прочитать с начала строки. Определите, сколько раз встречается на этом листе заданный набор символов и сколько раз при поиске потребуется сделать циклический сдвиг символа влево.

Формат входных данных

В первой строке записаны символы, найденные на листе Мёбиуса в заданном порядке (их может быть от 2 до 10 000), во второй – набор символов для поиска.

Формат выходных данных

В одну строку через пробел вывести количество повторений и наименьшее количество циклических сдвигов влево при поиске заданного набора символов. Считать прописные и строчные буквы разными.

Примеры

вход

Задача 4-В. По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит «Мы с радостью продадим Вам метр ткани за P_i бурлей, однако если Вы купите не менее R_i метров, то получите прекрасную скидку – каждый купленный метр обойдется Вам всего в Q_i бурлей». Чтобы воплотить в жизнь лозунг «экономика страны должна быть экономной», правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более F_i метров ткани.

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

Формат входных данных

В первой строке входного файла записаны два целых числа N и L (1≤N≤100, 0≤L≤100). В каждой из последующих N строк находится описание магазина номер i – 4 целых числа P_i, R_i, Q_i, F_i

(1≤Q_i≤P_i≤1000, 1≤R_i≤100, 1≤F_i≤100).

Формат выходных данных

Первая строка выходного файла должна содержать единственное число – минимальное необходимое количество бурлей. Во второй строке выведите N чисел, разделенных пробелами, где i-ое число определяет количество метров ткани, которое нужно купить в i-ом магазине. Если в i-ом магазине ткань покупаться не будет, то на i-ом месте должно стоять число 0. Если вариантов покупки несколько, выведите любой из них. Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1.

Примеры

Вход

Задача 5-В. Юный хакер Костя случайно набрал команду rm -f c еще одним дополнительным параметром – маской. Маска содержит в себе буквы, а также символы ? (обозначает ровно один произвольный символ) и * (обозначает любую последовательность символов, возможно, пустую). Выясните, сколько файлов осталось в каталоге после исполнения этой команды.

Формат входных данных

Первая строка входных данных содержит маску , указанную Костей в качестве параметра. Вторая строка входных данных содержит целое число N (0≤N≤1000) – количество файлов, которое было в каталоге. Далее идет N различных строк с именами файлов, каждая строка состоит из строчных латинских букв и по длине не превосходит 32 символов. Исходная маска также не превосходит по длине 32 символов и может содержать строчные латинские буквы и символы ? и *.

Формат выходных данных

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

Вход

Задача 6-В. Петя является администратором нескольких локальных сетей. Его клиентам выделены различные IP-адреса, и он решил сгруппировать все их IP-адреса в наименьшую возможную IP-сеть.

Каждый IP-адрес является 4-байтовым числом, записываемого в виде отдельных байт, разделенных точками: «byte0.byte1.byte2.byte3″ (кавычки добавлены для понятности). Каждый байт записывается в виде десятичного числа от 0 до 255 (включительно), без лидирующих нулей.

IP-сеть задается двумя 4-байтовыми числами: сетевым адресом и маской сети. Сетевой адрес и маска сети записываются в таком же виде, как и IP-адреса.

Для того чтобы понять назначение сетевого адреса и маски сети необходимо рассмотреть их двоичное представление. Двоичное представление IP-адреса, сетевого адреса и маски сети состоит из 32 бит: 8 бит для byte0 (записываемых от старшего к младшему), затем 8 бит для byte1, 8 бит для byte2 и 8 бит для byte3. Например, для адреса 212.65.71.73 двоичное представление имеет вид 11010100010000010100011101001001.

IP-сеть содержит диапазон из 2ⁿ адресов, где 0≤n≤32. Маска сети для данной сети всегда содержит 32-n старших бит (идущих в начале маски), равных 1 и n бит, равных 0, следующих в конце. IP-сеть содержит все IP-адреса, чьи первые 32-n бит совпадают с первыми 32-n битами сетевого адреса, а следующие n бит принимают произвольные значения. Будем считать одну IP-сеть меньше другой, если она содержит меньше IP-адресов.

Например, IP-сеть с сетевым адресом 212.65.71.72 и маской сети 255.255.255.248 содержит 8 IP-адресов от 212.65.71.72 до 212.65.71.79 (включительно).

Формат входных данных

Первая строка входных данных содержит натуральное число m, не превосходящее 1000. Затем идет m строк, содержащих IP-адреса, по одному IP-адресу в строке. IP-адреса могут повторяться.

Формат выходных данных

Программа должна вывести две строки, описывающие наименьшую IP-сеть, содержащую все заданные адреса. Выведите сетевой адрес в первой строке и маску сети во второй строке.

Вход

Задача 7-В. Ане, как будущей чемпионке мира по программированию, поручили очень ответственное задание. Правительство Н-ской области вручает ей план постройки дорог между городами. По плану все дороги односторонние, но между двумя городами может быть больше одной дороги, возможно, в разных направлениях. Ане необходимо вычислить минимальное такое k, что данный ей план является слабо k-связным.

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

Формат входного файла

В первой строке входного файла даны два числа 2≤n≤300 и 1≤m≤10⁵ – количество городов и дорог в плане. В последующих m строках даны по два числа  номера городов, в которых начинается и заканчивается соответствующая дорога.

Формат выходного файла

Выведите минимальное k, такое, что данный во входном файле план является слабо k-связным.

Вход

Задача 8-В. Входная строка содержит арифметическое выражение, которое может содержать целочисленные константы, скобки, бинарные операторы +, —, *, /, унарные операторы + и —. Вычислите значение этого выражения.

Формат входных данных

Во входных данных содержится единственная строка, содержащая цифры, знаки арифметических операций, круглые скобки. Строка не содержит пробелов. Все целочисленные константы не превосходят по модулю 10⁹. Арифметическое выражение корректно, никакие два знака арифметической операции не идут подряд (то есть унарный оператор не следует после бинарного), числа не содержат лидирующих нулей. Гарантируется, что результат работы, а также результаты всех промежуточных вычислений, не превосходят 10⁹. Длина строки не превосходит 1000 символов.

Все действия выполняются слева направо. Сначала выполняются умножения и деления, затем – сложения и вычитания. Деление выполняется нацело по правилам компилятора g++.

Формат выходных данных

Программа должна вывести значение данного выражения. При возникновении деления на ноль, программа должна вывести слово Error.

Вход