Задача 00A. Hello, world!

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)


Задача 00B. Сложение чисел

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:200 Мб

Условие

Даны два целых числа A и B. Вычислить их сумму A + B.

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

Во входном файле содержатся числа A B, разделённые пробелами.

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

В выходном файле должно содержаться единственное число — сумма A + B.

Ограничения

 − 10000 ≤ A, B ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 5
8

Задача 01A. Олины торты

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Сегодня к Оле в гости придет N одногруппников, из-за чего она решила приготовить N тортов. В ее распоряжении есть M грамм сахара. Поскольку Оля не хочет никого обидеть, в каждом торте должно быть одинаковое количество сахара. Какое максимальное количество сахара может содержать каждый торт?

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

Входные данные содержат числа M и N, каждое на новой строке.

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

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

Примеры тестов

Стандартный вход Стандартный выход
1
10
2
5
2
6
4
1.5

Задача 01B. Программист и квартплата

Автор:Д. Глушкова, В. Глушков   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Молодой программист Иннокентий решил переехать на новую квартиру и начать жить самостоятельно. Внимательно изучив коммунальные платежи, Иннокентий выяснил, что 1 киловатт электричества стоит K бурлей. Бюджет на электричество у Кеши равен M бурлям. Помогите ему понять, на какое количество полных дней бюджета Кеши хватит для оплаты электричества, если известно, что:

с 16:00 до 18:00 всегда горит свет, поглощающий Р киловатт в час;

с 9:00 до 18:00 всегда работает ноутбук, поглощающий Z киловатт в час;

круглые сутки работает роутер, поглощающий F киловатт в час.

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

Входные данные содержат целые числа M — бюджет, K — стоимость 1 киловатта, Р — количество киловатт, поглощающихся светом, Z — ноутбуком, F — роутером.

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

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

Ограничения

1 ≤ M, K, P, Z, F ≤ 105

Примеры тестов

Стандартный вход Стандартный выход
1
20000 20 10 6 1
10
2
15000 100 3 40 500
0

Задача 01C. Установить бит в числе

Автор:Заборцева Д. В.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:2 Мб
Выходной файл:Стандартный выход  

Условие

Требуется написать программу, которая устанавливает i-й бит в целом числе n с помощью битовых операций.

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

Входные данные содержат целое число n и номер бита i. Нумерация битов начинается с нуля от младшего к старшему.

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

Выходные данные должны содержать целое число n с установленным битом под номером i.

Ограничения

 − 231 ≤ n ≤ 231 − 1

0 ≤ i ≤ 31

Примеры тестов

Стандартный вход Стандартный выход
1
2 0
3
2
-2 0
-1

Задача 01D. Битовый диктатор

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Возьми число a, подели нацело его на 4 (22), далее умножь на 16 (24), после этого сделай побитовое "ИСКЛЮЧАЮЩЕ ИЛИ" с числом b, получившийся результат умножь на 2 (21), и сделай побитовое "ИЛИ" с числом c. Ответом будет побитовое "И" уже получившегося результата и числа 1073741823.

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

Первая строка входного файла содержит три числа a, b и c.

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

Входной файл должен содержать одно число — значение результат формулы.

Ограничения

0 ≤ a, b, c ≤ 2 ⋅ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
0 10 25
29
2
123 123 123
895

Задача 01E. K-й бит в числе

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дано целое неотрицательное число x, требуется вернуть значение k-го бита числа x, то есть k-й разряд двоичного представления числа x. Разряды нумеруются с 0 начиная с младшего. Считается что число содержит неограниченное количество лидирующих нулей.

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

Первая строка входного файла содержит два числа x, k.

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

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 109

0 ≤ k ≤ 300

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
0 10
0
2
123 0
1
3
12345 100
0

Задача 01F. Заплыв

Автор:Н. Чистякова   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

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

Первая строка входного файла содержит четыре натуральных числа: N M K L.

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

Выходной файл должен содержать единственное целое число — количество проплытых метров.

Ограничения

1 ≤ N, M, K, L ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
25 76 2 45
865
2
50 50 1 60
3530

Задача 01G. Котенок Гав и сосиски

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В распоряжение котенка Гава и щенка Шарика поступила лента из N сосисок. Они договорились есть ее с разных концов до тех пор, пока не встретятся. Гав съедает VGav сосисок в секунду, а Шарик — VSharik сосисок в секунду.

Напишите программу, которая вычислит количество сосисок, целиком съеденных каждым зверем.

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

Входной файл содержит три целых числа: N — количество сосисок, VGav — скорость Гава, VSharik — скорость Шарика.

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

Выходной файл должен содержать два числа: сначала количество сосисок, целиком съеденных Гавом, а затем количество сосисок, целиком съеденных Шариком.

Ограничения

1 ≤ N ≤ 108; 1 ≤ VGav, VSharik ≤ 10

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 1 2
3 6
2
2 5 3
1 0
3
2 5 5
1 1

Задача 02A. Светофор

Автор:О. Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Входной файл состоит из одной строки, задающей цвет светофора — RED, YELLOW, GREEN.

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

В выходном файле должна быть одна строка - YES или NO.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
RED
NO

Задача 02B. Вынутый разворот

Автор:Владивостокская городская олимпиада школьников по информатике 2002/2003   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Брошюра составлена из листов. На каждой стороне листа напечатано по две страницы. Страницы пронумерованы начиная с первой. Из брошюры был вынут один лист. Требуется по двум номерам страниц, напечатанным на одной из сторон этого листа, определить общее количество страниц в брошюре.

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

Во входном файле содержатся два целых числа A и B — номера страниц на стороне листа, в произвольном порядке

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

В выходном файле должно содержаться единственное число:

Ограничения

1 ≤ A, B ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 14
16
2
9 1
0

Задача 02C. Строки в книге

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:1 сек
Входной файл:a.in   Ограничение памяти:64 Мб
Выходной файл:a.out  

Условие

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй - с (K + 1)-й по (2 × K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

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

Входной файл содержит число K — количество строк, которое печатается на странице, и число N — номер строки

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

В выходной файл выведите два числа — номер страницы, на которой будет напечатана эта строка и номер строки на странице

Ограничения

1 ≤ K ≤ 200, 1 ≤ N ≤ 20000

Примеры тестов

Входной файл (a.in) Выходной файл (a.out)
1
50 1
1 1
2
20 25
2 5
3
15 43
3 13

Задача 02D. FizzBuzz

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

Примеры тестов

Стандартный вход Стандартный выход
1
23
2
25
Buzz
3
30
FizzBuzz

Задача 02E. Дворец в квадрате

Автор:Н. Малявин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Вы работаете программистом в строительной компании. Царь выдал компании заказ на постройку в Лесу фей дворца. Дворец должен иметь форму квадрата со стороной a и быть окружён квадратным садом. Прораб сообщил вам, что самый большой квадратный участок в Лесу имеет площадь S.

Команде садовников-аналитиков для разработки оптимального сада требуется знать, какой площадью для сада они располагают. Площадь для сада — это площадь на участке, не занятая дворцом.

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

Входной файл содержит целые числа a и S.

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

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

Ограничения

1 ≤ a ≤ 1000

1 ≤ S ≤ 108

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
0
2
2 10
6
3
2 2
-1

Задача 02F. Единственный канал у пикселя

Автор:mesenev   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Витя, Петя и Олег — программисты. Они решили написать свой графический редактор на библиотеке Qt!

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

Петя и Олег знают, что цвет пикселя обычно кодируется тремя значениями — red, green, blue. Каждый в диапазоне от 0 до 255. Но модуль Вити возвращает цвет пикселя в виде единственного числа. В битах с 0 по 7 включительно отражена интенсивность синего канала. С 8 по 15 зелёного, а с 16 по 23 интенсивность красного.

Разработчикам нужно не много — оставить только один цветовой канал и вернуть полученный цвет в том же формате. К сожалению, Петя и Олег проспали лекцию по битовому представлению чисел в памяти компьютера, и теперь им нужна ваша помощь.

На вход подаётся число, и буква r\g\b — канал, который нужно оставить. Ваша задача получить итоговый цвет в том же формате.

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

Входные данные содержат число n и символ m — значение цвета и необходимый канал.

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

Выходные данные должны содержать единственное число — цвет в числовом представлении.

Ограничения

0 ≤ n ≤ 16777215

m ∈ {′r′, ′g′, ′b′}

Примеры тестов

Стандартный вход Стандартный выход
1
6579300 g
25600

Задача 02G. Варфоломей и вафли

Автор:В. Глушков, Д. Глушкова   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

Какой максимальной высоты можно построить башню, если на каждом этаже нужно установить K вафель?

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

Входные данные содержат 3 числа: A — количество вафель первого вида, B — количество вафель второго вида, K — количество вафель на этаже.

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

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

Ограничения

1 ≤ A, B, K ≤ 104

Примеры тестов

Стандартный вход Стандартный выход
1
4 8 2
5
2
5 7 3
3

Задача 02H. В ожидании Нового года

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

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

Входной файл содержит текущее время — часы и минуты.

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

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
12 0
12 0
2
23 59
0 1
3
22 25
1 35

Задача 02I. Точка в углу

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x1, y1) и (x2, y2).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

Напишите программу, которая по данному прямоугольнику и точке определяет, находится ли точка в углу.

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

Входной файл содержит целые числа x1 y1 x2 y2 x y — координаты вершин прямоугольника и точки.

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

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

Ограничения

 − 104 ≤ x1,y1,x2,y2 ≤ 104

min(x1, x2) ≤ x ≤ max(x1, x2)

min(y1, y2) ≤ y ≤ max(y1, y2)

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
100 200 300 400 290 210
CORNER
2
100 200 300 400 200 300
CENTER

Задача 03A. Сложение массива чисел

Автор:unknown   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана последовательность целых чисел A1, …, AN. Вычислить их сумму.

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

Во входном файле содержится число N, за которым следуют числа A1… AN.

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

В выходном файле должно содержаться единственное число — сумма всех чисел входного файла.

Ограничения

0 ≤ Ai ≤ 10000, 1 ≤ N ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
6

Задача 03B. Количество битов в числе

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дано целое неотрицательное число x, требуется посчитать количество не нулевых битов в числе.

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

Первая строка входного файла содержит число x.

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

Входной файл должен содержать одно число  — количество не нулевых битов в числе x.

Ограничения

0 ≤ x ≤ 2 ⋅ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
2
15
4

Задача 03D. Слишком вложенные скобки

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана правильная последовательность из круглых скобок. Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более. Например, в последовательности (()((()(())())))(((()))) выделены скобки, вложенные на 3 и более уровней.

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

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

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

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

Ограничения

1 ≤ N ≤ 5000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
()(())
()(())
2
3
(()((()(())())))(((())))
(()(()))((()))

Задача 03G. Подсчёт баллов за задачу

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в ai баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

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

В первой строке файла содержится единственное число N.

Во второй строке файла содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

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

Выходной файл должен содержать единственное число — количество баллов за задачу.

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 5 10 
+-++-
9
2
6
1 1 3 5 10 25
+-+--+
29

Задача 03H. Ладья на шахматной доске

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Ладья — шахматная фигура, которая может двигаться на любое число клеток по горизонтали или по вертикали.

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится ладья. Требуется вывести шахматную доску с изображением ладьи и всех клеток, в которые она может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка с ладьёй обозначается символом 'X' (ASCII 88), клетка, в которую может походить ладья обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

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

Входной файл содержит целые числа N X Y.

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

Выходной файл должен содержать N строчек из N символов каждая — изображение шахматной доски.

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8
3 5
#.*.#.#.
.#*#.#.#
#.*.#.#.
.#*#.#.#
**X*****
.#*#.#.#
#.*.#.#.
.#*#.#.#
2
3 1 2
*.#
X**
*.#

Задача 03I. Слон на шахматной доске

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Слон — шахматная фигура, которая может двигаться на любое число клеток по диагонали.

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится слон. Требуется вывести шахматную доску с изображением слона и всех клеток, в которые он может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка со слоном обозначается символом 'X' (ASCII 88), клетка, в которую может походить слон обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

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

Входной файл содержит целые числа N X Y.

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

Выходной файл должен содержать N строчек из N символов каждая — изображение шахматной доски.

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8
3 5
#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#
2
3 1 2
#*#
X#.
#*#

Задача 04A. Максимум в массиве

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Вводится массив, состоящий из целых чисел. Найти наибольшее среди них

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

Сначала задано число N — количество элементов в массиве (1 ≤ N ≤ 35). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел в диапазоне от  − 231 до 231 − 1.

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

Необходимо вывести значение наибольшего элемента в массиве.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
3

Задача 04B. Гирлянда

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Ваша программа должна вывести в выходной файл изображение гирлянды. Гирлянда состоит из N звеньев, каждое из которых имеет вид ромба, состоящего из символов '#' (ASCII 35) для нечётных звеньев, либо '*' (ASCII 42) — для чётных звеньев. Размер i-го звена задаётся целым числом Ai. Каждая сторона ромба размером Ai состоит из Ai + 1 символа.

Гирлянда должна быть изображена на фоне прямоугольника, заполненного символами '.' (ASCII 46).

Каждое звено, начиная со второго, расположено вертикально под предыдущим и "сцеплено" с ним, как изображено в примере.

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

Во входном файле находится целое число N, за которым следует N чисел A1 AN — размеры звеньев.

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

Выходной файл должен содержать изображение гирлянды.

Ограничения

1 ≤ N ≤ 100, 1 ≤ Ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
.#.
#.#
.#.
2
2 3 2
...#...
..#.#..
.#...#.
#.....#
.#...#.
..#*#..
..*#*..
.*...*.
..*.*..
...*...
3
3 1 1 2
..#..
.#*#.
.*#*.
.#*#.
#...#
.#.#.
..#..

Задача 04C. Яблоки поровну

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В школьной столовой на завтрак раздавали яблоки. Каждому школьнику должно было достаться по одному яблоку, но трём из них удалось незаметно набрать в карманы a1, a2 и a3 яблок соответственно.

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

Например, если у первого школьника 2 яблока, у второго — 3, а у третьего — 4, то третий школьник может передать первому одно яблоко, и тогда у каждого из них будет по 3 яблока.

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

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

Входной файл содержит целые числа a1 a2 a3.

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

Выходной файл должен содержать целые положительные числа x y z — номер школьника, который отдаёт яблоки, номер школьника, которому отдаёт яблоки школьник x, и количество яблок.

Если у школьников уже одинаковое количество яблок, выведите единственное число 0.

Если решения не существует, выведите единственное число  − 1.

Ограничения

1 ≤ ai ≤ 1000; 1 ≤ x, y ≤ 3

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 3
0
2
1 3 5
3 1 2
3
1 3 6
-1

Задача 04D. Стремление к нулю

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Дано число N и массив из S целых чисел Ai.

За одну операцию можно заменять число N на любое из чисел N + Ai, N − Ai, N × Ai, N / Ai.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

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

Первая строка входных данных содержит целое число N.

Вторая — целое число S.

Третья — S целых чисел, массив A.

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

Выходные данные должны содержать одно целое число — минимальное количество операций.

Ограничения

0 ≤ N, Ai ≤ 2 * 109

1 ≤ S ≤ 100

Пояснения к примеру

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

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

Примеры тестов

Стандартный вход Стандартный выход
1
100
6
4 7 10 5 25 11
2

Задача 04E. Шифр Юлия Цезаря

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:4 Мб

Условие

Дана строка, состоящая из маленьких букв латинского алфавита. Требуется закодировать строку при помощи шифра Юлия Цезаря. Суть этого шифра такова: каждая буква сдвигается на три позиции по алфавиту, т.е. a заменяется на d, b — на e, p — на s, w — на z, x — на a, y — на b, z — на c.

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

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

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

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

Ограничения

Длина строки от 1 до 202 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
hello
khoor
2
z
c

Задача 04F. Энтое слово

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

Примеры тестов

Стандартный вход Стандартный выход
1
FEFU was established in 1899 as the Eastern Institute
5
1899
2
FEFU was established
5
established

Задача 04G. Идеальное стихотворение

Автор:А. Валявка, Д. Глушкова, В. Глушков   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Лев хочет написать стихотворение для своей девушки. У него есть K строк, которые он бы хотел использовать. Строки ставятся друг за другом так, чтобы между ними была рифма. Считается, что между двумя строками есть рифма, если последние Т символов этих строк совпадают. Лев считает, что чем больше рифмы в поэзии, тем лучше. Поэтому он решил составить стихотворение так, чтобы все строки в нем рифмовались друг с другом.

Определите максимальное количество строк с одинаковыми T буквами на конце. Гарантируется, что как минимум две такие строки существуют.

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

Первая строка входных данных содержит 2 целых числа: K  — количество строк, которые имеются у Льва и T  — требуемое количество совпадающих символов. Далее следует K строк, из которых нужно выбрать строки для стихотворения.

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

Выходные данные должны содержать единственное число — максимально возможное количество строк стихотворения.

Ограничения

1 ≤ K, T ≤ 1000

Примеры тестов

Стандартный вход Стандартный выход
1
8 2
If I ever were to lose you
I'd surely lose myself
Everything I have found dear
I've not found by myself
Try and sometimes you'll succeed
To make this man of me
All my stolen missing parts
I've no need for anymore
2
2
5 2
And both that morning equally lay
In leaves no step had trodden black
Oh I kept the first for another day
Yet knowing how way leads on to way
I doubted if I should ever come back
3

Задача 04H. Фонари

Автор:А. Кленин, И. Бураго   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

Рекомендуется рассмотреть частичные решения:

  1. N ≤ 2

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

Во входном файле содержится число N, за которым следует N пар целых чисел x1 y1 x2 y2… xN yN.

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

Выходной файл должен содержать единственное число — максимальное количество фонарей.

Ограничения

1 ≤ N, yi ≤ 100, 0 ≤ xi ≤ 100.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 50 10 51 10
2

Задача 04I. Миша и негатив

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:negative.in   Ограничение памяти:64 Мб
Выходной файл:negative.out  

Условие

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

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

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

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

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

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

Первая строка входного файла содержит целые числа n и m — высоту и ширину исходного изображения (в пикселях).

Последующие n строк содержат описание исходного изображения. Каждая строка состоит из m символов B и W. Символ B соответствует черному пикселю, а символ W — белому.

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

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

В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.

Ограничения

1 ≤ n, m ≤ 100

Примеры тестов

Входной файл (negative.in) Выходной файл (negative.out)
1
3 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB
2
2
2 2
BW
BB

WW
BW
2

Задача 04J. Максимальная тройка

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

Входной файл содержит число N, за которым следует N2 чисел
a1,1 a1,2a1,N
a2,1 a2,2a2,N
&nbsp;&nbsp;
aN,1 aN,2aN,N
 — элементы массива.

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

Выходной файл должен содержать единственное число — максимальную сумму. При N = 1 следует вывести единственный элемент матрицы.

Ограничения

1 ≤ N ≤ 2000, 0 ≤ ai,j ≤ 109,

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
3 4
9

Задача 04K. Калейдоскоп

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Назовём калейдоскопом размера N ASCII-изображение, состоящее из 2 × N + 3 строк по 2 × N + 3 символа. Центральная горизонталь, центральная вертикаль, обе большие диагонали калейдоскопа должны состоять из символов '#' (ASCII 35). Восемь сегментов, на которые калейдоскоп разбивается этими четырьмя осями, должны быть заполнены латинскими буквами таким образом, чтобы изображение было симметрично относительно осей.

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

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

Первая строка входного файла содержит число N. Следующие N строк содержат 1, 2, …, N латинских букв — заданный сегмент калейдоскопа.

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

Выходной файл должен содержать 2 × N + 3 строки по 2 × N + 3 символа — получившийся калейдоскоп.

Ограничения

1 ≤ N ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
a
bc
def
ghij
klmno
#abdgk#kgdba#
a#cehl#lhec#a
bc#fim#mif#cb
def#jn#nj#fed
ghij#o#o#jihg
klmno###onmlk
#############
klmno###onmlk
ghij#o#o#jihg
def#jn#nj#fed
bc#fim#mif#cb
a#cehl#lhec#a
#abdgk#kgdba#

Задача 04L. Максимальный перепад

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

Условие

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

Карта региона представляет собой матрицу размером N x N клеток, в каждой клетке которой содержится средняя высота определённого района над уровнем моря. Максимальным перепадом высот называется максимальная величина, на которую отличаются средние высоты двух районов, соседних на карте по горизонтали или по вертикали. Требуется по карте региона определить максимальный перепад высот в нем.

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

Входной файл содержит число N, за которым следуют N2 целых чисел — описание карты региона.

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

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

Ограничения

1 &le; N &le; 100. Все высоты — целые числа от 0 до 231&minus;1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 1
1 2 1
1 2 3
2

Задача 04M. Элемент N-мерного масcива

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется написать программу, которая по количеству измерений массива — N, размерностям измерений — ai и индексы элемента в массиве — ki, напечатает позицию элемента в памяти относительно начала массива. Размер элемента массива составляет один байт.

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

В первой строке входные данные содержат число N — количество измерений массива.

В следующих двух строках содержатся по N чисел ai и ki соответственно.

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

Выходные данные должны содержать одно целое число — позицию элемента в памяти.

Ограничения

1 ≤ N ≤ 32

1 ≤ ai ≤ 232

0 ≤ ki < ai

Примеры тестов

Стандартный вход Стандартный выход
1
1
10
8
8
2
2
2 5
1 3
8
3
2
5 5
2 1
11

Задача 05A. Сеть Фейстеля

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Необходимо реализовать шифрование Сетью Фейстеля

Псевдокод шифрования:

    
      for i in range(blocks):
          for r in range(rounds):
              TEMP = L[i]
              L[i] = R[i]
              R[i] = TEMP XOR F(K[r], R[i])
      
  

L[i] - первая половина i-го блока

R[i] - вторая половина i-го блока

K[r] - ключ шифрования на r-ом раунде, в данной задаче размер ключа равен размеру половины блока

F - функция шифрования, в данной задаче используется XOR

В случае если длина строки не кратна размеру блока, строка дополняется символами '\0'

Половины блока имеют одинаковую длину

Длина блока всегда четная

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

Первая строка входного файла содержит количество тестов N

Первая строка теста: 2 целых числа - количество раундов, размер блока в байтах

Вторая строка теста: раундовые ключи шифрования одной HEX строкой

Третья строка теста: целевая ASCII строка, которую необходимо зашифровать

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

Выходной файл должен содержать N строк - шифротекстов HEX-ом для каждой целевой строки

Ограничения

Длина строки <= 65536

Размер блока <= 64

Кол-во раундов <= 32

Кол-во тестов <= 335

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2 4
90A314CE
Phad1d2Ref
A1AFD4059395B509F5C5E10B

Задача 05B. Максимум в скользящем окне

Автор:Известная   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел ai - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2n − 2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL
4 4 4 4 5 8 8 8 8 8 8 6

Задача 05C. Болезнь

Автор:Анна Малова (Жюри XXI командной олимпиады школьников Санкт-Петербурга по информатике и программированию)   Ограничение времени:2 сек
Входной файл:disease.in   Ограничение памяти:256 Мб
Выходной файл:disease.out  

Условие

В Байтландии вспыхнула эпидемия опасной болезни. Известно, что возбудителями болезни являются n различных болезнетворных бактерий.

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

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

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

В первой строке входного файла заданы два числа n (1 ≤ n ≤ 100) — число различных возбудителей болезни и m — число анализов. Следующие m (1 ≤ m ≤ 10 000) строк содержат по n + 1 числу. Первые n чисел описывают, какие возбудители обнаруживаются этим анализом, i-е число равно 1, если анализ проверяет наличие i-го возбудителя и 0 — в противном случае.

Последнее число в строке равно 1, если анализ дал положительный результат, и 0 — в противном случае.

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

Если входные данные противоречивы, выведите в выходной файл единственную строку Incorrect. В противном случае выведите в выходной файл три строки. Каждая строка задается в формате: число бактерий, далее их номера.

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

Примеры тестов

Входной файл (disease.in) Выходной файл (disease.out)
1
3 3
1 0 0 0
1 1 1 1
0 1 0 0
2 1 2
1 3
0
2
2 2
1 1 0
1 0 1
Incorrect
3
2 1
1 1 1
0
0
2 1 2

Задача 05D. Библиотека для динамических массивов

Автор:Известная   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Необходимо написать реализацию динамических массивов согласно описанию в прикрепленном файле.

Прикрепленный файл представляет собой хедер "linear_sequence.h".


Задача 06B. Библиотека для списков

Автор:Известная   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:6 Мб
Выходной файл:output.txt  

Условие

Необходимо написать реализацию связных списков согласно описанию в прикрепленном файле.

Прикрепленный файл представляет собой хедер "linear_sequence.h".


Задача 07A. Двоичный порядок float

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб

Условие

Требуется написать программу, которая считывает вещественное число в переменную типа float и выводит его двоичный порядок по стандарту IEEE-754.

Для поиска порядка необходимо использовать битовые операции.

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

Входные данные содержат единственное вещественное число.

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

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

Примеры тестов

Стандартный вход Стандартный выход
1
2.0
1
2
0.5
-1

Задача 07B. Поворот отрезка

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

Требуется найти координаты вершин отрезка A *  B *  (X * a; Y * a) и (X * b; Y * b), полученного путём поворота отрезка AB вокруг точки O (Xo; Yo) на β градусов.

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

Выходной файл должен содержать четыре вещественных числа X * a, Y * a, X * b, Y * b с точностью 10 − 3.

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

Задача 07C. Быстрее к границе!

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Входной файл содержит два целых числа xA yA — координаты точки A, за которыми следуют четыре целых числа x1 y1 x2 y2 — координаты двух противоположных углов прямоугольника.

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

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

Ограничения

 − 1000 ≤ x, y, x1, y1, x2, y2 ≤ 1000; x1 ≤ x2, y1 ≤ y2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
-1 0
1 1 4 3
2.236
2
2 2
1 1 4 3
1

Задача 07D. Endless expression

Автор:N. Grebenyuk   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

«Бесконечность — не предел»

Вы попали в царство Бесконечности, где ничто не имеет конца.

Для того, чтобы выбраться обратно, в мир смертных, Вам нужно найти значение бесконечного выражения 3n + 3n + 3n + ... с некоторой точностью (как и всё в царстве Бесконечности, значение выражения вполне может быть бесконечным в десятичном представлении).

Ваш ответ будет считаться правильным, если его абсолютная погрешность не превосходит 10 − 5. А именно: пусть ваш ответ равен a, а ответ жюри — b. Тогда ваш ответ будет считаться правильным, если |a − b| ≤ 10 − 5.

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

Первая строка ввода содержит целое число n.

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

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

Ограничения

 − 1018 ≤ n ≤ 1018

Примеры тестов

Стандартный вход Стандартный выход
1
1
1.32471796
2
67738
40.77223943
3
-2184
-13.00000000

Задача 07E. Вероятность

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

В корзине лежат w белых, b черных и y желтых шаров. Из корзины вынули K шаров.

Требуется определить вероятность того, что среди K вынутых шаров хотя бы L — белые.

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

Первая строка входных данных содержит 5 целых чисел w, b, y, K и L.

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

Выходные данные должны содержать одно вещественное число — искомую вероятность с точность не менее чем 3 знака после десятичной точки.

Ограничения

0 ≤ w, b, y ≤ 100

0 ≤ K, L ≤ w + b + y

Примеры тестов

Стандартный вход Стандартный выход
1
1 1 1 0 0
1
2
3 4 5 10 2
0.95454545454545447480
3
10 0 0 3 4
0.00000000000000000000

Задача 07F. Поиск планктона

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб

Условие

Исследователи Арктики исследуют изменение количества тонн планктона на некотором участке океана вдоль траектории движения от точки x0 до xn для прогнозирования объема биомассы в целом. Исследователи поняли, что в точке x на траектории движения количество тонн планктона определяется формулой f(x;a,b) =  − 0.0001 ⋅ x4 + a ⋅ x3 − 0.05 ⋅ x2 + b ⋅ x + 50, где a – коэффициент, который соответствует глубине замера, b - коэффициент, зависящий от температуры воздуха у поверхности воды.

Исследователей интересует вопрос, каково минимальное количество тонн планктона на траектории движения. Они просят Вас написать программу, находящую глобальный (наименьший из всех) минимум на заданном участке [x0, xn], даже если этот минимум отрицателен. При нахождении результата Исследователи просят Вас при вычислении использовать шаг изменения координаты x:

xi − xi − 1 = 1.

Напишите программу для решения этой задачи.

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

В первой строке вводится два целых числа x0, xn — начальная и конечная координаты точек измерений вдоль траектории движения.

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

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

В единственной строке выведите одно вещественное число y = f(x) — минимальное количество тонн планктона на рассматриваемом участке с точностью два десятичных знака после запятой (x ∈ [x0, xn]).

Ограничения

 − 104 ≤ x0 < xn ≤ 104

 − 10 ≤ a,b ≤ 10

Примеры тестов

Стандартный вход Стандартный выход
1
0 20
0.001000 1.000000
42.000
2
4 30
0.010000 -1.000000
43.510

Задача 07G. Производная

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Дана функция f(x) = sin( − 10 ⋅ x2 + 5 ⋅ x + 10).

Для указанной точки x требуется определить значение производной f′(x), а также является ли точка x экстремумом функции f(x).

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

Входные данные содержат вещественное число x.

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

Первая строка выходных данных должна содержать значение производной в точке x, с точностью не менее 5 десятичных цифр после запятой.

Вторая строка должна содержать YES, если точка x отстоит от точки экстремума не более чем на 10 − 5, и NO в противном случае.

Ограничения

 − 50000 ≤ x ≤ 50000

Примеры тестов

Стандартный вход Стандартный выход
1
0
-4.195357645
NO
2
0.7764046320109196
0
YES

Задача 07H. Марфа Геннадьевна в поезде

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Однажды Марфа Геннадьевна ехала вместе с Аполлинарием Матвеевичем на поезде. К ним подошёл проводник и предложил кипяток. Пассажиры переглянулись: никто не хотел пить слишком горячий чай. Проводник сказал, что у него есть холодная вода в отдельной ёмкости, но холодной и горячей воды не очень много.

Теперь перед Марфой Геннадьевной и Аполлинарием Матвеевичем стоит непростая задача. У проводника имеется 2 сосуда с холодной и горячей водой. В первом сосуде есть A л холодной воды при температуре T1 градусов. Во втором сосуде есть B л горячей воды при температуре T2 градусов. Требуется перелить определённое количество воды из первого и второго сосуда в третий сосуд так, чтобы в третьем сосуде вода была при температуре от m до M градусов и её было как можно больше.

Если из 1-го сосуда налить x л, а из 2-го — y л, то температура воды в 3-м сосуде будет усреднена и равна T1 x + T2 yx + y.

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

Входной файл содержит целые числа A B T1 T2 m M.

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

Требуется вывести в выходной файл вещественное число — максимальное количество воды в литрах, которое можно получить в 3-м сосуде при температуре от m до M градусов, с точностью до 4-х знаков после запятой.

Ограничения

1 ≤ A, B ≤ 20

0 ≤ T1 ≤ m ≤ M ≤ T2 ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 10 25 100 50 60
9.3750

Задача 07I. Треугольник Максима

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:triangle.in   Ограничение памяти:256 Мб
Выходной файл:triangle.out  

Условие

С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент — треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.

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

Вам Максим показал запись, в которой приведена последовательность частот, выставляемых им на тюнере, и про каждую ноту, начиная со второй, записано — ближе или дальше она к звуку треугольника, чем предыдущая нота. Заранее известно, что частота звучания треугольника Максима составляет не менее 30 герц и не более 4000 герц.

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

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

Первая строка входного файла содержит целое число n — количество нот, которые воспроизводил Максим с помощью тюнера. Последующие n строк содержат записи Максима, причем каждая строка содержит две компоненты: вещественное число fi — частоту, выставленную на тюнере, в герцах, и слово closer или слово further для каждой частоты, кроме первой.

Слово closer означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |fi − fтреуг.| < |fi − 1 − fтреуг.|.

Слово further означает, что частота данной ноты дальше, чем предыдущая.

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

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

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

В выходной файл необходимо вывести через пробел два вещественных числа с точностью не менее 10 − 8 — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом.

Ограничения

2 ≤ n ≤ 1000, 30 ≤ fi ≤ 4000

Примеры тестов

Входной файл (triangle.in) Выходной файл (triangle.out)
1
3
440
220 closer
300 further
30.0 260.0
2
4
554
880 further
440 closer
622 closer
	
531.0 660.0

Задача 08A. Дипломы

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:diploma.in   Ограничение памяти:64 Мб
Выходной файл:diploma.out  

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 109

Примеры тестов

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

Задача 08B. Гаджет в кредит

Автор:М. Спорышев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Студент Вася решил приобрести себе новый гаджет. Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.

В магазине Васе объяснили правила предоставления кредита.

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

Рекомендуется рассмотреть частичные решения

  1. P = 0
  2. C, P ≤ 103

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

Входной файла содержит целые числа N P C.

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

Выходной файл должен содержать единственное целое число — подходящий Васе ежемесячный платеж.

Ограничения

1 ≤ C ≤ 109; 0 ≤ P ≤ 109; 1 ≤ N ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0 1
1
2
1 124 12
8
3
1 1 12
2

Задача 08C. Вырубка леса

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:1 сек
Входной файл:forest.in   Ограничение памяти:256 Мб
Выходной файл:forest.out  

Условие

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3.

Система оценивания и описание подзадач

Подзадача 1 (32 баллов)

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

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

Подзадача 2 (10 баллов)

1 ≤ X ≤ 1018; X < K; X < M.

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

Подзадача 3 (10 баллов)

1 ≤ X ≤ 1018.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 1018, 1 ≤ A, B ≤ 109, 2 ≤ K, M ≤ 1018.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

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

Выходной файл должен содержать одно целое число — искомое количество дней.

Ограничения

1 ≤ A, B ≤ 109, 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018

Примеры тестов

Входной файл (forest.in) Выходной файл (forest.out)
1
2 4 3 3 25
7

Задача 09A. Быки и коровы

Автор:Д. Глушкова, В. Глушков   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Необходимо реализовать игру "Быки и коровы". Правила игры:

1. Программа загадывает случайное число в пределах от 1000 до 9999.

2. Пользователь пытается отгадать это число, вводя его с консоли.

3. Программа выдает подсказку. Например: "быков: N, коров: K", где коровы — количество совпавших цифр числа, не стоящих на своих местах, быки  — количество цифр числа, которые стоят на своих позициях.

4. Шаги 2-3 повторяются до тех пор, пока пользователь не отгадает число.

5. По завершению игры пользователю выводится поздравительное сообщение.

Если цифра введенного пользователем числа встречается в загаданном числе несколько раз и попадает в несколько групп сразу, следует учитывать в подсказке их все. Например, когда пользователь ввел число 1000, а было загадано 1001, программа должна вывести "быков: 3, коров: 1".

Если цифра введенного пользователем числа встречается в загаданном числе несколько раз и стоит не на своем месте, то в количестве коров нужно учитывать все. Например, если будет загадано 6612, а введено 7776, то программа должна вывести "быков: 0, коров: 2".

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

Отправьте код для решения этой задачи в окно ниже. Задача будет проверяться только вручную. Дедлайн для отправки этой задачи — последняя неделя перед зачетной.

В качестве среды разработки укажите Answer text.

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

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


Задача 09B. BMP

Автор:Д. Глушкова, В. Глушков   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

В этой задаче вам надо: 1) Посчитать количество пикселей заданного цвета. 2) Перевернуть изображение на 90 градусов. 3) Увеличить изображение в 2 раза. Цвет задается в формате RGB.

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

Отправьте код для решения этой задачи в окно ниже. Задача будет проверяться только вручную. Дедлайн для отправки этой задачи — последняя неделя перед зачетной.

В качестве среды разработки укажите Answer text.

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

Изображение в формате BMP


Задача 09C. Крестики-нолики

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Задание №1

Реализовать игру крестики-нолики на поле 3х3. В качестве противника должен выступать другой человек. Игроки ходят по очереди. Ход осуществляется через ввод координат на поле, в которых игрок хочет расположить свой крестик/нолик.

Задание №2

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

Задание №3

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

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

В качестве «крестика» выступает заглавная латинская буква X, в качестве «нолика» выступает заглавная латинская буква O, если клетка поля пустая, то на ней располагается символ точки «.». Поле должно выглядеть следующим образом:


.│.│.
─┼─┼─
.│.│.
─┼─┼─
.│.│.

4.105s 0.020s 131