Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лимит времени 1000/2000/2000/2000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Фирма, в которой всё ещё работает ваш друг, решила установить в своих маршрутках автоматы по продаже чая и кофе, чтобы во время поездок и, особенно, во время ожидания в пробках, пассажиры могли с толком провести время.
Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100-рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам.
Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет. Сейчас на маршрутках фирмы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед выездом маршрутки в рейс. Вам дан протокол одного из таких испытаний: известен порядок, в котором пассажиры оплачивали свои покупки различными монетами и купюрами. Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем пассажирам хватило сдачи.
Формат входных данных
В первой строке входного файла находится одно натуральное число N -количество покупок в автомате, которые были совершены в ходе испытания (1 ≤ N ≤ 50 000). Во второй строке находятся N натуральных чисел, каждое из которых равно номиналу монеты или купюры, которую использовал очередной покупатель для оплаты; каждый номинал может принимать одно из четырёх значений: 5, 10, 50 или 100.
Формат выходных данных
В выходной файл выведите одно число - минимальное количество пятирублёвых монет, которые надо было загрузить в автомат изначально, чтобы всем покупателям хватило сдачи.
Пример
|
Ввод |
Вывод |
|
3 |
19 |
|
3 |
0 |
|
4 |
9 |
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
На поле, состоящем из M*N белых квадратных клеток единичного размера, некоторые клетки покрасили в чёрный цвет, в результате чего образовалось одна или несколько закрашенных фигур. Фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4 х соседних по стороне клеток. Несвязные фигуры считаются различными. Например, на данном рисунке приведены 3 фигуры. Периметр фигуры — это сумма длин ее внешних и внутренних (при наличии) сторон. Периметр фигур, изображенных на рисунке: 28, 6 и4. Суммарный периметр фигур равен 38.
Требуется написать программу, которая находит суммарный периметр фигур, получившихся на клетчатом поле.
Формат входных данных
Первая строка входного файла содержит два целых числа M и N (0 < M , N ≤ 100) — количество строк и столбцов, из которых состоит клетчатое поле. Во второй строке находится одно число K (0 ≤ K ≤ M*N) – количество клеток, закрашенных в черный цвет.
В последующих K строках содержатся координаты закрашенных клеток в формате:
<номер строки><пробел><номер столбца>.
Формат выходных данных
Выведите в выходной файл одно число — суммарный периметр всех фигур.
Пример
|
Ввод |
Вывод |
|
10 7 |
38 |
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Пусть нам дано натуральное число N. Рассмотрим множество различных целых чисел {a1, a2, …, ak}, где каждое число лежит в интервале от 0 до N - 1 включительно. Назовём такое множество свободным от сумм, если в этом множестве не найдётся таких трёх чисел, что сумма двух из них сравнима с третьим по модулю N. Строго говоря, назовём множество свободным от сумм, если для каждой тройки (не обязательно различных) индексов x, y и z (1 ≤ x, y, z ≤ k) выполняется неравенство (ax + ay) mod N ≠ az , где p mod q - остаток от деления p на q.
Например, при N = 6 множествами, свободными от сумм, не являются, например, {0} (т. к. (0 + 0) mod 6 = 0), {1, 2} ( т. к. (1 + 1) mod 6 = 2), {3, 4, 5} (т. к. (4 + 5) mod 6 = 3), но множество {1, 3, 5} является свободным от сумм.
По заданному N определите, сколько существует множеств, свободных от сумм.
Формат входных данных
Во входном файле находится одно целое число N. Гарантируется, что 1 ≤ N ≤ 35.
Формат выходных данных
В выходной файл выведите одно число - ответ на задачу.
Пример
|
Ввод |
Вывод |
|
2 |
2 |
|
6 |
14 |
Лимит времени 3000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Петя достаточно давно занимается в математическом кружке, поэтому он уже успел изучить не только правила выполнения простейших операций, но и такое достаточно сложное понятие как симметрия. Для того, чтобы получше изучить симметрию Петя решил начать с наиболее простых геометрических фигур – треугольников. Он скоро понял, что осевой симметрией обладают так называемые равнобедренные треугольники. Поэтому теперь Петя ищет везде такие треугольники.
Напомним, что треугольник называется равнобедренным, если его площадь положительна, и у него есть хотя бы две равные стороны.
Недавно Петя, зайдя в класс, увидел, что на доске нарисовано n точек. Разумеется, он сразу задумался, сколько существует троек из этих точек, которые являются вершинами равнобедренных треугольников.
Требуется написать программу, решающую указанную задачу.
Формат входных данных
Входной файл содержит целое число n (3 ≤ n ≤ 1500). Каждая из последующих строк содержит по два целых числа – xi и yi – координаты i-ой точки. Координаты точек не превосходят 109 по абсолютной величине. Среди заданных точек нет совпадающих.
Формат выходных данных
В выходной файл выведите ответ на задачу.
Примеры
|
Ввод |
Вывод |
|
3 |
1 |
|
4 |
4 |