Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 952 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 169 170 171 172 173 174 175 >> Отображать по:
#111707
Художник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом. Сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников с координатами углов (x1i;y1i), (x1i;y2i), (x2i;y2i), (x2i;y1i).

Помогите художнику определить площадь незакрашенной части холста.

Входные данные

Первая строка содержит два целых числа w и h (1 ≤ w;h ≤ 100) — ширину и высоту холста соответственно. Вторая строка входного файла содержит целое число n (0 ≤ n ≤ 5000) — количество прямоугольников. Следующие n строк содержат информацию о прямоугольниках. (i + 2)-ая строка содержит четыре целых числа x1i; y1i, x2i; y2i (0 ≤ x1i ≤ x2i ≤ w, 0 ≤ y1i ≤ y2i ≤ h).

Выходные данные

Выведите ответ на задачу.

Примеры
Входные данные
5 5
2
1 1 3 3
2 2 4 4
Выходные данные
18
Входные данные
6 7
3
0 0 5 5
1 1 4 4
2 2 3 3
Выходные данные
17
#111722
Задача о рюкзаке
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Одной из классических NP-полных задач является так называемая «Задача о рюкзаке». Формулируется она следующим образом. Дано n предметов, каждый из которых характеризуется весом wi и полезностью pi. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна. Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.

Входные данные

Первая строка входного файла содержит натуральные числа n(1 ≤ n ≤ 20) и W(1 ≤ W ≤ 109). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: wi — веса предмета и pi — его полезности (1 ≤ wi, pi ≤ 109).

Выходные данные

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

Примеры
Входные данные
2 10
10 100
9 80
Выходные данные
1 100
1
Входные данные
5 100
80 1000
50 550
50 550
50 550
50 550
Выходные данные
2 1100
2 3
Входные данные
6 100
80 1000
50 550
50 550
50 550
50 550
100 1100
Выходные данные
1 1100
6
#111787
Наибольший квадрат
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дан двумерный массив целых чисел n × m, все элементы которого — нули или единицы. Найти в нём наибольший по площади квадрат, состоящий только из единиц. Гарантируется, что в нём есть хотя бы одна единица.

Входные данные

Вводятся два целых числа n и m (1 ≤ n, m ≤ 1000), а потом n строк по m чисел 0 или 1 — элементы массива.

Выходные данные

Вывести три числа — длину стороны квадрата и координаты его левого верхнего угла.

Примеры
Входные данные
1 1
1
Выходные данные
1
1 1
Входные данные
3 5
1 1 0 0 0
1 1 1 1 1
0 0 0 1 1
Выходные данные
2
1 1
#111801
Гемоглобин
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.

Входные данные

Первой строкой входного файла задано число n ( 1 ≤ n ≤ 100000 )  — число обращений к базе данных. Запросы к базе выглядят следующим образом: + x ( 1 ≤ x ≤ 10 9 )  — добавить пациента с уровнем гемоглобина x в базу, - — удалить последнего пациента из базы, ? k ( 1 ≤ k ≤ 100000 )  — вывести суммарный гемоглобин последних k пациентов. Гарантируется, что k не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.

Выходные данные

Для каждого запроса " - " вывести уровень гемоглобина в крови пациента, а для каждого запроса " ? k " — суммарный гемоглобин у последних k поступивших пациентов. Ответы выводите в порядке поступления запросов.

Примеры
Входные данные
7
+1
+2
+3
?2
-
-
?1
Выходные данные
5
3
2
1
#111830
Количество вызовов функции Фибоначчи
  
Темы: [Рекурсия]
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, очередное число Фибоначчи равно сумме предыдущих двух. Первое и второе число Фибоначчи равны единице.

Программист Вася написал вычисление n-ого числа Фибоначчи с помощью рекурсивной функции. А сколько раз запустится эта функция прежде, чем будет получено значение?

Входные данные

Дано одно число n ( 1 ≤ n ≤ 50 )

Выходные данные

Выведите одно число — количество запусков функции.

Примеры
Входные данные
3
Выходные данные
3
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
1
Страница: << 169 170 171 172 173 174 175 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест