Задача A. Брокер

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

Условие

Брокер Лёша решил подзаработать, для чего собирается совершить N звонков в разные банки. Стратегия Лёши проста: он просит у очередного банка деньги и иногда их получает. Банк под номером i может выдать брокеру ровно mi денег и делает это только в том случае, если у брокера на момент звонка уже есть ri денег на счету. С самого начала на счету брокера содержится A денег.

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

Если счет брокера удовлетворяет условию банка, и если самому брокеру выгодно продолжать разговор, он тратит дополнительно ti секунд на совершение сделки и вежливое завершение разговора, после чего ему на счет поступает mi денег. В ином случае Лёша мгновенно отменяет сделку, бросает трубку и получает от банка 0 денег.

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

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

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

В первой строке входные данные содержат три целых числа N, A и C — количество звонков, исходное количество денег на счету и стоимость одной секунды разговора.

В следующих N строках содержится по три числа ti, ri и mi — количество секунд, затрачиваемых на получение информации от i-го банка, требование i-го банка к количеству денег на счету брокера и количество денег, которое i-й банк готов заплатить.

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

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

Ограничения

0 ≤ N ≤ 102

0 ≤ A, C, ri, mi ≤ 104

1 ≤ ti ≤ 103

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1000 10
10 500 1000
1000 0 20
5 2000 8400
100

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

Автор:А. Кленин   Ограничение времени: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

Задача C. Бада развешивает зоков

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

Условие

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

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

В первом примере, приведённом ниже, двоих зоков можно повесить рядом. Для этого хватит 3 прищепок.

Во втором примере в ряд можно повесить троих зоков (на это уйдёт 4 прищепки), а четвёртого зока повесить на другую верёвку, использовав ещё 2 прищепки. Можно также повесить зоков на двух верёвках по два зока на каждой, также использовав в сумме 6 прищепок.

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

Во входном файле содержатся целые числа N и M.

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

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

Ограничения

1 ≤ N, M ≤ 106

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

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

Задача D. Редактор уровней с грибами

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

Условие

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

Уровень для игры кодируется прямоугольной таблицей символов из N строк и M столбцов. Свободные ячейки таблицы обозначаются символом '.' (ASCII 46). Ячейки, занятые платформами — символом '#' (ASCII 35). Каждый гриб занимает одну ячейку и обозначается символом '*' (ASCII 42).

Платформа — это набор последовательных ячеек из одной строки, который содержит лишь символы '#', и ограничен слева и справа границами уровня либо символами '.' или '*'.

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

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

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

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

Первая строка входного файла содержит числа N M. Далее следует N строк по M символов в каждой — описание уровня.

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

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

Ограничения

1 ≤ N, M ≤ 20

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

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

Задача E. Забор по фен-шую

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

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту ai сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a1 < a2 > a3 < a4 > …, либо условие a1 > a2 < a3 > a4 < ….

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

Напишите программу, которая по указанным длинам досок ai определяет новый набор длин bi, в котором:

  1. ai ≤ bi,
  2. либо b1 < b2 > b3 < b4 > …, либо b1 > b2 < b3 > b4 < …
  3. сумма bi минимальна.

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

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

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

Входной файл должен содержать N целых чисел bi — новые длины досок. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ ai ≤ 100

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

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

Задача F. В поисках Васи

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

Условие

Данная история основана на реальных событиях.

Мальчик Влад идёт в гости к своему другу Васе, который живёт в доме с N подъездами и M этажами. На каждом этаже каждого подъезда расположено одинаковое количество квартир. Влад помнит номер Васиной квартиры X (квартиры нумеруются с 1), но не помнит ни номер подъезда, ни этаж.

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

У Влада есть K предположений насчет того, какое количество квартир может быть на одном этаже одного подъезда. Влад собирается вычислить для каждого из K предположений номер подъезда и номер этажа, зайти в соответствующий подъезд, подняться на этаж и позвонить в домофон, чтобы проверить, живёт ли здесь Вася. Перейти из одного подъезда в другой можно только через улицу (0 этаж). Влад может проверять свои предположения в любом порядке.

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

В примере 2 для 1-го и 2-го предположения Вася живёт на 10 этаже 1 подъезда, в то время как для 3-го предположения Вася будет жить на 7 этаже 1 подъезда. Влад может сначала подняться на 7 этаж 1 подъезда для проверки 3-го предположения, а потом подняться на 10 этаж этого же подъезда для проверки предположений 1 и 2.

В примере 3 для 1-го предположения количество квартир в доме будет равно 40, а для 2-го предположения — 60. Ни в том, ни в другом случае в доме не найдётся квартиры с номером 100.

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

Входной файл содержит целые числа N M X K — количество подъездов и этажей в доме Васи, номер его квартиры, количество предположений Влада. Далее следуют K различных целых чисел ai — предположения Влада о количестве квартир на одном этаже одного подъезда дома Васи.

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

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

Если ни одно предположение Влада не позволяет определить, где живёт Вася, то выведите  − 1.

Ограничения

1 ≤ N, M ≤ 104; 1 ≤ X ≤ 106; 1 ≤ K ≤ 105; 1 ≤ ai ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 10 100
2
1 10
20
2
10 10 100
3
10 11 15
10
3
2 10 100
2
2 3
-1

Задача G. Вася и мысли

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

Условие

Юный программист Вася любит прогуливаться по тропинке длиной D метров, проходящей неподалёку от его школы, и размышлять о том о сём.

В начале прогулки Вася размышляет о Важных Вещах, и ноги несут его с постоянной скоростью, равной либо v1, либо v2 м/c. Затем Вася отвлекается и начинает думать о Всякой Ерунде. В этот момент его скорость становится равной либо w1, либо w2 м/c.

Если Вася затратил на прогулку T секунд, каково максимальное возможное расстояние, пройденное им с Важными Вещами в голове?

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

Первая строка входного файла содержит числа D T. Во второй строке записаны числа v1 v2. В третьей строке записаны числа w1 w2. Каждое число имеет не более трёх знаков после десятичной точки.

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

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

Входные данные таковы, что решение всегда существует.

Ограничения

1 ≤ D, T ≤ 1000

10 − 3 ≤ v1 < v2 ≤ 102

10 − 3 ≤ w1 < w2 ≤ 102

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10.0 5.0
1.0 3.0
0.5 1.0
9.0
2
15.0 3.0
1.0 2.5
4.25 6.1
2.291
3
25.0 5.0
1.0 3.0
4.0 5.0
0.0

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

Автор:А. Кленин, И. Бураго   Ограничение времени: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

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

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

Условие

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

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


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

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

Условие

Смотри задание

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

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

Ограничения


Problem K. Lin-log sort 2

Author:StdAlg   Time limit:2 sec
Input file:input.txt   Memory limit:512 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Задача O. Быки и коровы 2

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

Условие

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

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

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

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

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

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

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

Ограничения

1 ≤ N < 105, 1 ≤ h ≤ N

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

Стандартный вход Стандартный выход
1
15 5
XX...XXYYYXX.YY
6 10

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

Автор:А. Жуплев   Ограничение времени: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

Задача R. Аквалангист

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

Условие

Аквалангист Джонс находится в море в координате xj, yj на глубине hj метров. Джонс заметил акулу, которая находится в координате xs, ys на глубине hs метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью vs м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

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

Входные данные содержат в двух строках целые числа xj, yj, hj и xs, ys, hs, vs.

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

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |xj|, |yj|, hj, |xs|, |ys|, hs ≤ 105

1 ≤ vs ≤ 100

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

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

Problem S. Alice and numbers

Author:М. Спорышев   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Young programmer Alice does not like integers number K.

Alice wants to know number of integers in range from 1 to N (inclusive) not divisible by K.

Input format

Input contains two integer numbers N and K.

Output format

Output a single integer — number of integers not divisible by K.

Constraints

2 ≤ N ≤ 109

1 ≤ K ≤ 100

Sample tests

No. Standard input Standard output
1
5 2
3
2
4 2
2

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100. Все высоты — целые числа от 0 до 231−1

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

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

1.704s 0.041s 45