Задачи с олимпиад

Здесь представлены задачи, которые подготовлены мною на олимпиады разного уровня. Некоторые были взяты из литературы по олимпиадам по программированию с несколько измененными условиями.

Муниципальный этап ВОШ по информатике 2017-2018 (ГКЛ г. Кемерово)
Школьный этап Всероссийской олимпиады школьников 2018 ГКЛ
Отборочный тур школьного этапа Всероссийской олимпиады школьников 2018

Задачи с командной олимпиады по программированию от 24.04.2015г.


Задачи с районной олимпиады от 12.11.2012г.

Эти задачи из вариантов ЕГЭ, немного изменив условие.
Задача № B. Увеличитель
У исполнителя Увеличитель две команды, которым присвоены номера:
1. прибавь a,
2. умножь на b,
где 1<=a<=10, 2<=b<=100.
Первая из них увеличивает число на экране на a, вторая - умножает на b.
Программа для Увеличителя - это последовательность команд, возможно пустая. Помогите написать программу, которая ответит на вопрос: сколько есть программ, которые число X преобразует в число Y?
На вход подаются: в первой строке два числа через пробел: a и b; во второй строке - еще два числа через пробел: X и Y (X<=Y, 1<=X,Y<=10000).
На выходе выводится одно число - количество программ.
Пример
Входные данные
Выходные данные
1 2
1 2
2


Задача № C. Олимпиада по информатике
На городской олимпиаде по информатике участникам было предложено выполнить 3 задания, каждое из которых оценивалось по 25-балльной шкале. Известно, что общее количество участников первого тура олимпиады не превосходит 250 человек.
Напишите программу, которая будет выводить на экран максимальный балл и фамилию и имя участника, набравшего это количество баллов. Если среди остальных участников есть ученики, набравшие такое же количество баллов, то их фамилии и имена также следует вывести. При этом имена и фамилии выводить в порядке их появления.
<Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов; <Баллы> – строка, содержащая три целых числа, разделенных пробелом, соответствующих баллам, полученным участником за каждое задание первого тура. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом.
На вход подаются сведения о результатах олимпиады. В первой строке вводится количество участников N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя> <Баллы>
На выходе в первой строчке вывести максимальный балл, а в следующих строчках Фамилию Имя участников, набравших его.
Пример
Входные данные
Выходные данные
2
Петрова Ольга 25 18 16
Калиниченко Иван 14 19 15
59
Петрова Ольга



Задачи с лицейской олимпиады от 15.10.2012г.

Задача А. Сортировка
Выполнить сортировку символов в строке по возрастанию «весов» символов, заданных таблицей ORD. Символы, не попавшие в таблицу, выводятся в конце таблицы по мере появления в тексте.
Ввод. В первой строке находится строка, задающая вес символов для сортировки (не более 200 символов), во второй строке – текст, который нужно отсортировать (не более 10000 сивмлов).
Вывод Вывести отсортированный по правилам текст.
Примеры 
Ввод
Вывод
АаБбВвГгДдЕе1234567890
Мама дала Гене 509 рублей.
аааабГдеее590Мм л н  рулй.
абвгдеёжзиклмнопрстуфхцчшщьыъэюя !:-)}{[].,?
С ДНЕМ РОЖДЕНИЯ, мама!
аамм   !,СДНЕМРОЖДЕНИЯ

Задача B. День рождения
Заданы день и месяц рождения, а также текущие день, месяц и год в формате дд.мм.гггг. Определить, сколько дней осталось до дня рождения.
Примечание. Високосный год делится на 400 или делится на 4, но не делится на 100.
Ограничения: год от 1920 до 3000, месяц - от 1 до 12, день - от 1 до числа дней в месяце, время 1 с.
Ввод. В первой строке находятся разделённые точками день и месяц рождения, во второй - разделённые точками текущие день, месяц и год.
Вывод. Вывести число дней, оставшихся до дня рождения.
Примеры
Ввод
Вывод
19.04
19.04.2002
0
05.05
19.04.2002
16
29.02
28.02.2001
1096

Задача C. Строка
В математике часто встречаются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей - очередное число в последовательности некоторым образом выражается через предыдущие. Примером такой последовательности являются числа Фибоначчи (в них очередное число равно сумме двух предыдущих). С помощью соотношений такого типа можно задавать не только последовательности чисел, но и последовательности строк. В этой задаче рассматривается последовательность строк s0, s1, . . . , задаваемая следующим образом. Строка s0 пуста, а каждая строка si (i >= 1) получается из si-1 по следующему правилу: если десятичная запись числа i входит как подстрока в si-1, то si = si-1, иначе si получается приписыванием к si-1 в конец десятичной записи числа i. Задано число n. Необходимо найти строку sn.
Ввод. Содержит целое число n (1 <= n < 1000).
Вывод. Выведите строку sn.
Примеры
Ввод
Вывод
1
1
3
123
13
123456789101113
Задача D. Химические реакции
Химическая реакция записана в виде уравнения, которое представлено строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделённых знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:
<формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
  • <последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
  • <элемент> ::= <химический элемент> | "(" <последовательность> ")"
  • <химический элемент> ::= <прописная буква> [<строчная буква>]
  • <прописная буква> ::= "A".."Z"
  • <строчная буква> ::= "a".."z"
  • <число> ::= "1".."9" {"0".."9"}

Будем говорить, что каждый отдельный химический элемент встречается в формуле всего X раз, если X - сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле C2H5OH+3O2+3(SiO2)

  • C встречается всего 2 раза;
  • H встречается всего 6 раз (5 + 1);
  • O встречается всего 13 раз; (1 + 3 * 2 + 3 * 2);
  • Si встречается всего 3 раза.

Все множители в формулах - целые числа не меньше 2, если заданы явно, или равны 1 - по умолчанию.

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

Ограничения: каждый отдельный химический элемент встречается всего не более 10 000 раз, время 1 с.

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

Примеры

Ввод
Вывод
C2H5OH+3O2+3(SiO2)
C2H6O13Si3

Примечание. Настоящие тесты могут содержать любые допустимые символы.

Задачи со студенческой олимпиады - апрель 2012 года


Задача 1.
Васе захотелось записать на диск песню в своем сопровождении и передать другу по Интернету. Сколько потребуется времени на передачу файла, если известны следующие данные: время записи в секундах, разрядность и частота звукового процессора, моно или стерео, а также скорость передачи по Интернету.

Формат входных данных
В строке через пробел передаются следующие данные: скорость передачи в бит/сек (от 100 до 109), время в секундах (от 1 до 109), разрядность в битах (8, 16, 32, 64) и частота в герцах (от 100 до 109), далее 1(моно) или 2 (стерео).

Формат выходных данных
Вывести время в формате: дд:чч:мм:сс - округлив секунды до целых.

Пример входных данных
100 10 16 1000 1

Пример выходных данных
00:00:26:40

Задача 2.
Ученые решили собрать компьютер и использовать в качестве разрядов системы счисления члены ряда Фибоначчи, которые вычисляются по правилу: F[0]=0, f[1]=1, f[i]=f[i-1]+f[i-2], где i=2,3,4,5,... Любое натуральное число можно представить в виде суммы этих чисел, например: 7=5+2, 33=21+8+3+1 и так далее. Помогите написать программу, которая по введенному натуральному числу будет выводить кодовое число в виде 0 и 1, где в соответствующей позиции n, начиная справа, ставится 1, если число с номером n присутствует в сумме, иначе 0. Так для 7 кодовое число будет выглядеть так: 10100, для 33 – 10101010.

Формат входных данных
Вводится натуральное число n (от 0 до 109).

Формат выходных данных
Вывести кодовое число.

Пример входных данных
33

Пример выходных данных
10101010

Задача 3.
Миша и Ваня играли в шахматы. Все ходы были записаны судьей Машей (она маленькая и могла записать ходы не всегда верно). Через некоторое время Маше надоело записывать, она перевернула доску и пошла гулять. Восстановите расстановку шахматных фигур по записям Маши, если это возможно.
 
Белые
Черные
Ходы
Король
Король
Король ходит в любое поле на 1 клетку
Ферзь
Ферзь
Ферзь ходит в любом направлении на любое поле
Ладья
Ладья
Ладья ходит по вертикали или по горизонтали
Слон
Слон
Слон ходит по диагональным направлениям
Конь
Конь
Конь ходит «углом»: 2 прямо/назад – 1 влево/вправо или 1 прямо/назад – 2 влево/вправо
Пешка
Пешка
Пешка ходит прямо, но рубит по диагонали на 1 клетку вперед
Формат входных данных
В каждой строке вводится ход одного из игроков в формате xn:ym, где x, y-символы от a до h; n, m – цифры от 1 до 8. Ходы типа рокировка, смена пешкой фигуры здесь не рассматриваются.

Формат выходных данных
Если входные данные ходов не верны, то в первой строке вывести “No solution”, если решение существует, то вывести таблицу расположения фигур, где для символов определены следующие фигуры:
k – белый король
q – белый ферзь
b - белый слон
r- белая ладья
p – белая пешка
n – белый конь
. – пустая клетка
K – черный король
Q – черный ферзь
B - черный слон
R- черная ладья
P – черная пешка
N – черный конь
Левый верхний угол шахматной доски при выводе начинается с позиции a8 и заканчивается позицией h1 – правый нижний угол.
Пример входных данных
Пример выходных данных
a2:a4
b7:b5
a4:b5
b8:c6
b5:c6
d7:c6
R.BQKBNR
P.P.PPPP
..P.....
........
........
........
.ppppppp
rnbqkbnr
a2:a4
b7:b8
c1:h1
No solution


Задачи со студенческих олимпиад прошлых лет

Задача G. Линия
Имя входного файла: G.in
Имя выходного файла: G.out
Максимальное время выполнения задачи – 10 секунд.

Дана последовательность k-линейных многочленов на отрезке [а,b] и их значения на концах отрезка. Выяснить, сколько линий пересекутся в заданной точке с координатами (х, у).
Формат входных данных
В первой строке число kколичество линейных многочленов, во второй – концы отрезка а и b, в третьей – координаты точки х ,у, последующие k строк – значения в точке а и в точке b для каждого многочлена.
Формат выходных данных
Одно число – количество линий, пересекающихся в заданной точке.
Пример
G.in
G.out
5
1.0 2.0
1.5 5.0
5.0 10.0
2.0 4.0
5.0 5.0
2.0 10.5
8.0 2.0
2

Задача H. Окужность
Имя входного файла: H.in
Имя выходного файла: H.out
Максимальное время выполнения задачи – 10 секунд.

Узор состоит из m (2..10) окружностей, заданных своими координатами центров (х, у) и радиусов r. Найти наибольшее количество окружностей, центры которых лежат на линиях первой окружности.
Формат входных данных
В первой строке число mколичество окружностей, в следующих m строках – центр х, у и радиус г каждой окружности/
Формат выходных данных
Одно число – количество таких окружностей.
Пример


H.in
H.out
5
2.0 3.0 2.0
4.0 1.0 1.0
4.0 4.0 3.0
7.0 4.0 2.0
2

Задача B. Геометрическая прогрессия
Имя входного файла: B.in
Имя выходного файла: B.out
Максимальное время выполнения задачи – 15 секунд.
Задана последовательность действительных чисел. Количество чисел в этой последовательности не превышает 10000. Необходимо определить, можно ли выстроить эти числа в отрезок геометрической прогрессии. Порядок может и не совпадать.
Формат входных данных
Во входном Файле, через пробел в одну или несколько строк записаны действительные числа.
Формат выходных данных:
Вывести "YES"- если такую последовательность можно построить, или "NO"- если это не так.
Пример


B.in
B.out
1 2 4 8 16 32 64 128
YES

Задача D. Точки на окружности
Имя входного файла: D.in
Имя выходного файла: D.out
Максимальное время выполнения задачи – 10 секунд
Заданы координаты N точек в декартовой системе координат. Определить наибольшее количество точек (K>1), лежащих на одной окружности, центром которой является координата (X0,Y0). Вывести наименьший радиус найденной окружности. Если таких точек нет, то вывести “No solution”.
Формат входных данных
В первой строке задается N (2<=N<=1000). Во второй строке координата центра окружности X0,Y0. Следующие N строк – координаты точек.
Формат выходных данных
В одной строке через пробел вывести количество точек и радиус окружности с тремя знаками после запятой или сообщение “No solution”.
Примеры


D.in
D.out
4
0.0 0.0
1.0 0.0
0.0 1.0
2.0 2.0
2.0 1.0
2 1.000
5
0.0 0.0
1.15 0.0
0.0 1.15
1.3 0.0
-1.15 0.0
0 -1.17
3 1.150
5
1.0 1.0
1.0 0.0
0.0 5.0
1.3 0.0
-1.15 0.0
0 -1.17
No solution

Задача B. Лист Мёбиуса
Технические требования:
Имя файла: b
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 2 сек.

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


input.txt
output.txt
абракадабра
бра
2 10
абрикос
коса
1 3

Задача C. Матрёшки

Технические требования:
Имя файла: с
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 2 сек.

Множество из N (N <= 1000) прямоугольных параллелепипедов задано измерениями этих параллелепипедов (длина и ширина основания, высота).
Нужно сделать так, чтобы параллелепипеды были вложены друг в друга как «матрешки». При вложении стороны параллелепипедов располагаются параллельно и перпендикулярно друг другу; параллелепипеды могут быть повёрнуты, чтобы разместиться в очередном.
Требуется написать программу, указывающую порядок вложения параллелепипедов или сообщающую об отсутствии решения задачи.
Примечание. Параллелепипеды ограничены каркасом ненулевой толщины. Это означает, что, например, параллелепипед размером 10 × 11 × 12 не может быть помещён в параллелепипед размером 10 × 11 × 13.
Формат входных данных
Первая строка — N; в каждой из следующих N строк — три действительных числа — измерения соответствующего параллелепипеда.
Формат выходных данных
Строка, содержащая N чисел, — номера параллелепипедов исходной последовательности в порядке вложения параллелепипедов друг в друга, начиная с большего, или сообщение «NO».
Примеры


input.txt
output.txt
3
1 2 3
10 30 20
5 6 8
2 3 1
3
1 2 40
10 30 20
5 6 8
NO

Задача A. Маленький принц
Технические требования:
Имя файла: а
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 1 мин.

В сказке-были Сент-Экзюпери маленький принц рассчитал свой путь от своей планеты до Земли и обратно, побывав на нескольких других планетах. Но если предположить, что планеты стоят на месте, а планет больше- то, как маленькому принцу найти наименьший путь от своей планеты и обратно, побывав на каждой из них один раз?
Формат входных данных
В первой строке задано число N (1<=N<=10)- количество планет, не считая планеты маленького принца. Во второй строке три действительных числа X, Y, Z координаты планеты маленького принца. В следующих N строках координаты планет, представленных тремя действительными числами Xi, Yi, Zi.
Формат выходных данных
В первой строке вывести наименьшее расстояние, пролетевшее маленьким принцем, в формате 6 знаков после десятичной запятой. Во второй строке вывести номера планет в порядке их обхода, не учитывая планету маленького принца.
Примеры


input.txt
output.txt
2
0 0 0
1 0 0
0 1 0
3.414214
1 2

Задача B. Новогодние хлопушки
Технические требования:
Имя файла: b
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 1 сек.
На Новый год гости, используя каждый по одной принесенной хлопушке, умудрились «захламить» весь дом. Каждая из хлопушек выстреливает N разноцветных шаблонов в виде кругов радиуса R. Определить количество гостей, если известно, что пол квартиры, площадью S=a*b, был покрыт этими кругами в один слой так плотно, как это возможно. Если и осталось какое-то свободное место на полу, то только из-за того, что было недостаточно кругов в последней хлопушке.
Формат входных данных
В первой строке задано число N (0<N<=1000) и радиус кругов R (действительное положительное число <=10). Во второй строке заданы стороны комнаты a и b (1<=a, b <=500).
Формат выходных данных
Вывести одно число – количество гостей.
Примеры


input.txt
output.txt
10 0.5
3 4
1
1 5
10 10
1
11 0.5
5 4
2

Задача F. Подарок
На Новый год каждый ребенок хочет, чтобы Дед Мороз принес им и своим друзьям подарки. Он просит об этом в своих открытках для Деда Мороза. Дед Мороз очень любит детей и он готов собрать новогодние подарки в один мешок и принести им и их друзьям. Для Деда Мороза не существует понятие стоимости или цены подарка. Количество детей, пославших открытку Деду Морозу, может быть меньше чем общее количество детей, для которых нужны подарки. Если Дед Мороз попросит, то ребенок может отказаться от своего подарка в пользу подарка друга, но сам дарит друзьям только выбранные им самим подарки. Ребенок так же может отказаться от подарка друга, если Дед Мороз принес ему подарок, который он попросил для себя в открытке.
Дед Мороз старый, поэтому ему тяжело донести все подарки детям. Поэтому он подбирает свой бесценный груз так, чтобы общий вес был не больше указанного и чтобы подарок получил каждый ребенок и только один. Помогите Деду Морозу собрать мешок. Если это сделать невозможно, то  сообщить ему: «Impossible, sorry!».
Формат входных данных
В первой строке задано число N (integer>0) – количество детей, и S – предельный вес новогодних подарков. В каждой последующей строке указан вес подарка и через пробел имена детей: первым в списке – имя отправившего открытку, затем список его друзей. Имена детей в списке не повторяются.
Формат выходных данных
Если вес мешка с подарками для детей не больше веса указанного предела, то вывести этот вес с точностью до 4 знака после запятой, иначе вывести «Impossible, sorry!»
Примеры


Входные данные
Выходные данные
50 50.5
10.5 Kat Sasha Olga Valentina
5.8 Sasha Kat
6.7 Mariya Sasha Olga
35.5000
1 1.9999
10 Viktor
Impossible, sorry!

Задача F. Снегурочка (1 сек.)
Под Новый год Дед Мороз должен найти свою внучку Снегуручку. Он решил отправить ей открытку с новогодними поздравлениями. Но он не знает, где она может быть. Так как Снегурочка все равно будет во всех городах Земли, то открытка когда-нибудь дойдет до нее. Ему хотелось бы, чтобы это произошло как можно быстрее. Для этого он должен знать хотя бы название города и его индекс. Тогда Дед Мороз решил воспользоваться случаем. Он открыл карту Земли и ткнул наугад «пальцем в небо». И так он проделал N раз (N – номер Нового года). По последнему выбранному городу он определил индекс этого города и отправил открытку Снегурочке в этот город.
Напишите программу действий Деда Мороза так, чтобы она по введенной переменной N выдавала индекс найденного города.
Формат входных данных (input.txt)
Задано целое число N (integer>0).
Формат выходных данных (output.txt)
Вывести число с шестью цифрами - индекс города.
Примеры
input.txt
output.txt
1
000000
40
020296
2003
169405
500
664007

День программиста
C 2009 года наша страна празднует день программиста 13 сентября.
Каким днем недели будет 13 сентября указанного года (начиная с 2009 до 10 000 года нашей эры)? Следует учитывать, что год високосный, если он кратен 4 и при этом не кратен 100, либо кратен 400, например, 2012 и 2400 - високосные года, а 2100 – не високосный. День недели вывести по-английски: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.
Пример входных данных:
2009
Пример выходных данных:
Sunday
Найди слово «программа»
Дан набор слов, в котором, удалив из него подряд идущие буквы и, может быть, знаки препинания и пробелы, можно найти слово «программа». Выведите те символы, которые нужно удалить, чтобы получить это слово.
Набор слов не превышает 255 символов русского и латинского алфавита, цифр, пробелов и знаков препинаний. Слово «программа» может быть как на русском, так и на английском языке (program), прописными или строчными буквами. Если слово найти не удалось, то ничего не выводить.
Например, в строке: «I am product Grandfather and my Mother. My name is Lena.» нужно удалить следующие символы: «I am duct ndfather and y Mother. My name is Lena.», чтобы получить слово «proGram».
Пример входных данных:
I am product Grandfather and my Mother. My name is Lena.
Пример выходных данных:
I am duct ndfather and y Mother. My name is Lena.
Правильный код
Новый программист написал программу для нахождения суммы первых N (от 1 до 10 000) натуральных чисел, но для некоторых значений ответ получил не верный.

Pascal
C++
var S: shortint;
I: byte;
N:Word;
begin
s:=0;
read(n);
for I:=1 to n do
begin
s:=s+I;
end;
writeln(s);
end.
#include
int main(){
short int S;
unsigned short int I;
unsigned int N;
cin>>N;
S=0;
for (I=1;I
cout<<S;
return 0;
}

Минимально исправьте код программы, чтобы выводился правильный результат.
Пример входных данных:
100
Пример выходных данных:
5050

Задача 5. Количество слов
Ограничение по времени: 1 с.
Будем считать, что слово – это набор символов, отделенных некоторым непустым количеством символов, обозначающих разделитель между словами. Задана непустая строка из таких символов-разделителей. Определить количество слов в тексте.
Входные данные
В первой строке задана строка символов-разделителей (от 1 до 10 символов). Во второй строке - заданный текст (от 0 до 10000 символов).
Выходные данные
Количество слов в строке.
Пример

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

Задача «Считалка»

Многие дети начинают играть со считалок. Играющий, на которого попадает последнее слово текста, выходит из круга. Предположим, что в кругу стоит N детей. Составить программу, которая выведет номера детей в том порядке, в каком они выходят из круга.
Входные данные: В первой строке задается количество детей (1<N<= 1000). Во второй строке вводится сама строка считалки (количество слов в строке от 2 до 1000, слова состоят не более 25 символов и разделены пробелом, в конце строки стоит точка).
Выходные данные: Вывести через пробел номера детей, которые выйдут из круга по порядку (последний пробел не выводится), а номер голящего (последнего оставшегося в кругу) во второй строке.
Пример входных данных:
10
Раз два три четыре пять вышел зайчик погулять.
Пример выходных данных:
8 6 5 7 10 3 2 9 4
1