Всероссийская олимпиада по информатике 2010/2011 года (Новгородская область)
Для всех решенных задач в каталоге, указанном организаторами, должны быть сохранены исполняемый код и исходный текст программы с именем <шифр участника>Z<номер задачи>. Расширение имени для исходного текста программы выбирается в соответствии с используемым языком программирования. Входные данные поступают из файла, имя которого указано в условии задачи. Результат должен быть записан в файл с именем, указанным в условии задачи. Формат данных должен соответствовать описанному в условии задачи.
Задания первого тура муниципального этапа для 9-11 классов
Задача 1. Победитель олимпиады
Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
На муниципальном этапе олимпиады по информатике соревнования проводятся в два тура, на каждом туре участникам предлагаются для решения по три задачи. Максимальное количество баллов, которое можно получить за правильное решение любой задачи – 100. По условиям соревнований победителем признается участник, набравший максимальное количество баллов, при условии, что количество набранных им баллов превышает половину максимально возможных баллов. Если несколько участников набрали одинаковое наибольшее количество баллов, то все они признаются победителями.
Напишите программу, которая поможет жюри определить победителей олимпиады.
Формат входного файла
В первой строке входного файла находится одно число N (1 £ N £ 50) – количество участников олимпиады. Далее следуют N строк, каждая из которых содержит 6 целых чисел, разделенных пробелом, – оценки i-го участника за решение предложенных задач.
Формат выходного файла
В первой строке выходного файла содержится одно число – количество победителей
Во второй строке выводятся номера победителей олимпиады, разделенные пробелом.
Примеры
input. txt | output. txt | ||||||||||||||||||||||||
| 1 2 | ||||||||||||||||||||||||
| 0 |
Задача 2. Кодовый замок
Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
Кодовый замок состоит из N рычажков, каждый из которых может быть установлен в любое из K положений, обозначенных натуральными числами от 1 до K. Известно, что для того чтобы открыть замок, нужно, чтобы сумма положений любых трех последовательных рычажков была равна K. Рычажки пронумерованы числами от 1 до N.
Два рычажка уже установлены в некоторые положения, и их переключать нельзя. Рычажок с номером p1 установлен в положение v1, а рычажок p2 – в положение v2.
Напишите программу, которая определит, сколькими способами можно установить остальные рычажки, чтобы открыть замок.
Формат входного файла
Строка входного файла содержит 6 натуральных чисел N, K, p1, v1, p2, v2, разделенных пробелом. (3 ≤ N ≤ 10000, 3 ≤ K ≤ 6, p1≠p2, 1 ≤ p1 ≤ N, 1 ≤ p2 ≤ N, 1 ≤ v1 ≤ K, 1 ≤ v2 ≤ K).
Формат выходного файла
В выходной файл выводится число – количество искомых комбинаций или 0, если, соблюдая все условия, замок открыть невозможно.
Примеры
input. txt | output. txt |
1 | |
0 | |
2 |
Задача 3. Покупка грибов
Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
Мама послала сына Колю на рынок купить грибов. На рынке продаются подосиновики по цене А рублей за штуку и белые грибы по В рублей за штуку (А<В). У Коли есть С рублей. Он хочет купить максимальное количество грибов, и при этом потратить как можно больше денег из имеющихся у него..
Ваша задача – вычислить сколько денег Коля потратит на покупку грибов.
Формат входного файла
Входной файл содержит три целых числа А, В, С (1≤A<B≤100, 0≤C≤1000).
Формат выходного файла
В выходной файл выведите одно число – стоимость самого дорогого набора из максимального количества грибов.
Примеры
input. txt | output. txt |
2 3 11 | 11 |
2 5 10 | 9 |
В первом тесте искомый набор состоит из четырех подосиновиков и одного белого.
Во втором тесте – только из трех подосиновиков.
Всероссийская олимпиада по информатике 2010/2011 года (Новгородская область)
Основные идеи решения заданий первого тура муниципального этапа для 9-11 классов
Задача 1. Победитель олимпиады
Необходимо сформировать массив суммарных баллов участников олимпиады. Далее находится максимальное значение в этом массиве. Далее в соответствии с правилами находится количество победителей и, если они имеются, выводятся на отдельной строке их номера.
Задача 2. Кодовый замок
Автором данной задачи является Е. Андреева, разбора – В. Василевский.
Необходимо рассмотреть комбинацию положений рычагов, открывающую замок. Ключ к решению заключается в простом факте: положения рычажков, расположенных на расстоянии вида 3m, совпадают (m – натуральное). Доказать его достаточно для m = 1. Рассмотрим 4 последовательных положения рычажка, пусть номера их положений равны соответственно a1, a2, a3, a4. Тогда a1+a2+a3 =K = a2+a3+a4, то есть a1=a4.
Поэтому можно считать, что количество рычагов N равно 3. Рассмотрим два случая.
1. Пусть разность данных в условии позиций p1 и p2 не делится на 3. Это означает, что два из трех положений известны. Следовательно, последнее должно быть равно K-v1-v2. Если это число больше 0, то искомая конфигурация одна, иначе – ноль.
2. p1-p2 делится на 3. Если v1≠v2, то искомых комбинаций не существует. В противном случае если положения остальных двух ячеек равны b и с, то b+c=K-v1, b>0, c>0. Таких пар ровно K-v1-1, если это число положительно, и ноль иначе.
При заданном в условии задачи диапазоне значений для входных данных решение можно было найти перебором положений ячейки, соседней с p1, по этим данным полностью восстанавливается вся конфигурация. Остается только проверить корректность найденных положений (числа должны быть от 1 до K).
Задача 3. Покупка грибов
. Для решения задачи необходимо перебрать все варианты использования имеющейся суммы денег
