Темы
Информатика(2656 задач)
--->
61 задач
<---
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На циферблате записана последовательность чисел в двоичной системе счисления. Линии разбиения могут проходить как между числами, так и между цифрами одного числа, разбивая его на два или больше чисел. Для каждого сектора можно посчитать сумму чисел, которые в нем расположены. 
Каждое число в последовательности не равно 0, и его запись начинается с единицы. Количество цифр в двоичной записи числа не превышает 25. Общее количество цифр на циферблате не больше чем 100.
Циферблат может быть разбит на сектора. На рисунке изображен привычный нам циферблат с числами от 1 до 12 (в немного непривычном виде). Он разбит на 4 сектора. Суммы в секторах будут 1, 15, 18 и 36.
Напишите программу, которая по заданной последовательности определяет количество разных разбиений циферблата на сектора, таких что сумма чисел во всех секторах одинакова.
Входные данные
В единственной строке входного файла задана последовательность чисел. Числа последовательности разделены пробелом.
Выходные данные
В единственной строке выходного файла должно находиться натуральное число — количество искомых разбиений циферблата на сектора.
Примеры
Входные данные
10 11 10
Выходные данные
9
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Трехмерная фигура состоит из единичных кубиков. По фигуре можно построить ее фронтальную и правую проекции. Очевидно, что по этим двум проекциям не всегда можно восстановить фигуру.
Напишите программу, которая получает на вход фронтальную и правую проекции фигуры и определяет минимальное и максимальное количество кубиков, которое можно было бы использовать для построения фигуры с заданными проекциями.
Входные данные
В первой строке входного файла находятся три числа N, M и К, которые задают размеры проекций (1≤N, M, K≤100). Дальше задаются две проекции: сначала фронтальная, а затем правая. Проекция задается N строками, каждая из которых состоит из чисел 0 и 1, разделенных пробелами. Для фронтальной проекции таких чисел будет M, а для правой — K. 0 означает свободную клетку проекции, 1 — заполненную.
Выходные данные
В единственной строке выходного файла должно находиться два числа: минимальное и максимальное число кубиков, которые можно было бы использовать для построения фигуры с заданными проекциями.
Примеры
Входные данные
2 2 3 1 0 1 1 0 0 1 1 1 1
Выходные данные
4 7
#1344
Темы:
[Быстрая сортировка]
[Элементарная геометрия]
ограничение по времени на тест
0.1 second;
ограничение по памяти на тест
64 megabytes
На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:
- никакие два многоугольника не имеют общих точек;
- для каждого i –го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0 ≤Pi≤N-1.
Напишите программу, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.
Входные данные
Первая строка входного файла содержит целое число N — количество многоугольников, 3≤N≤100000. Следующие N строк файла описывают N многоугольников. (i+1)–ая строка файла описывает i–ый многоугольник. Первое целое число Ci — количество вершин многоугольника, 3≤Ci≤20. Последующие Ci пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.
Выходные данные
Единственная строка выходного файла должна содержать N чисел: i–ое число строки должно быть Pi — количество многоугольников, внутри которых находится i–ый многоугольник.
Примеры
Входные данные
3 3 -2 1 8 9 12 1 3 7 5 6 3 7 4 4 4 3 7 7 9 3 1 2
Выходные данные
0 2 1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Прямоугольное поле состоит из N строк и M столбцов. Игровая фишка за один ход может переместиться с клетки одного столбца на одну из клеток следующего столбца. Для каждой клетки поля известны номера строк клеток следующего столбца на которые фишка может сделать ход. Фишка не может пойти на клетку, которую она уже посещала раньше.
В начале игры фишку устанавливают на произвольную клетку первого столбца. После этого фишка начинает двигаться в сторону последнего столбца. Когда фишка достигает последнего столбца, ее снова устанавливают на любую клетку первого столбца, которая не была посещена раньше, и возобновляют ее движение.
Игра завершается когда фишка не может сделать ход.
Напишите программу, которая по числам N, M (1≤N≤50, 2≤M≤10), и таблице переходов между клетками определяет какое наибольшее количество раз можно провести фишку от первого до последнего столбца игрового поля.
Входные данные
В первой строке входного файла находятся числа N иM. Далее следует M-1 блок по N строк в каждом — описание возможных переходов для каждой клетки поля. Каждая i–ая строка j–го блока описывает возможные переходы из клетки в i–ой строке и j–ом столбце игрового поля. Первое число в строке задает количество возможных переходов из клетки, после чего следуют номера строк следующего столбца по возрастанию и без повторений.
Выходные данные
В единственной строке выходного файла должно находиться целое число, которое соответствует искомому количеству путей. (Ответ может быть 0, если ни из одной клетки первого столбца нельзя достичь ни одной клетки последнего). Для приведенного примера входных данных фишку можно провести 3 раза, например, по таким маршрутам: (133), (244) и (422).
Примеры
Входные данные
4 3 2 1 3 3 1 2 4 0 2 2 3 1 2 1 2 1 3 2 2 4
Выходные данные
3
#1346
Темы:
[НОД и алгоритм Евклида]
[Элементарная геометрия]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Территория Великой Треугольной Области (ВТО) представляет собой прямоугольный треугольник. Длины его катетов равны M и N государственных единиц длины (ГЕД). Правительство ВТО решило покрыть как можно большую часть территории области квадратными плитами размером 11 ГЕД. Плиты должны плотно прилегать друг к другу и к катетам ВТО. Разрезать плиты нельзя.
Согласно межгосударственным соглашениям, правительство ВТО не имеет права покрыть частью своей плиты чужую территорию. Производитель поставляет плиты только контейнерными партиями — по P плит. Правительство заказывает столько контейнеров, сколько необходимо для реализации проекта.
Заведующий центральным складом, узнав про проект, решил, что его интересует количество плит, которые останутся на складе из последнего контейнера после покрытия территории ВТО.
Напишите программу, которая по длинам катетов ВТО и вместимости контейнера находит количество плит, которые останутся на складе после осуществления проекта.
Входные данные
Единственная строка входного файла содержит три целых числа: M, N (2≤M, N≤2 000 000 000) и P (100≤P≤10 000).
Выходные данные
Единственная строка выходного файла должна содержать целое число — количество неиспользованных плит из последнего контейнера.
Примеры
Входные данные
4 3 100
Выходные данные
97
Выбрано
:
|