Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 194 195 196 197 198 199 200 >> Отображать по:
#2861
Тир
  
Темы: [Перебор]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Шесть стрелков решили повысить свою меткость и зашли в тир пострелять. В тире было установлено шесть мишеней, и каждый стрелок выстрелил во все мишени. После чего они собрались в баре, и каждый рассказал, сколько раз он попал в мишень. Бармен, запомнил, что сказал каждый из них, и на следующий день посчитал, сколько дырок в каждой мишени. Требуется помочь бармену определить: не ошибся ли кто-то из "снайперов", и сколько существует вариантов стрельбы (то есть, кто в какие мишень попадал), при которых получаются такие результаты. Считается, что две пули в одну дырку не попадают.

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

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

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

В первой строке - количество вариантов такой стрельбы. Если вариант всего один, то для каждого стрелка вывести строчку, в которой будет для каждой мишени проставлено 0 - не попал, 1 - попал.

Примеры
Входные данные
1 0 0 0 1 0

1 0 0 1 0 0
Выходные данные
2
Входные данные
5 5 5 5 5 0

5 5 5 5 5 0
Выходные данные
1
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
0 0 0 0 0 0
#2862
Последовательность
  
Сложная.

Последовательность чисел называется монотонно убывающей, если для любого номера \(i\) (кроме последнего) выполняется \(A_i > A_{i+1}\). Последовательность чисел называется монотонно возрастающей, если для любого номера \(i\) (кроме последнего) выполняется \(A_i < A_{i+1}\). Последовательность называется монотонной, если она или монотонно убывающая, или монотонно возрастающая. Дана последовательность \(A_i\) из \(N\) чисел. За одно действие каждый элемент последовательности можно либо увеличивать на 1, либо уменьшать на 1. Требуется изменить последовательность так, чтобы в ней содержалось ровно \(K\) монотонных непересекающихся последовательностей (один элемент тоже является последовательностью) за минимально возможное количество действий.

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

В первой строке входных данных содержатся числа \(N\) и \(K\) --- количество элементов в последовательности и сколько должно быть монотонный частей, соответственно (\(1 \leq N \leq 50, 1 \leq K \leq 25\)). В слеюущей строке содержатся \(N\) чисел --- элементы последовательности, каждое число по модулю не превосходит \(20\,000\,000\).

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

Одно число, ответ на задачу

Примеры
Входные данные
4 1 
1 1 1 1
Выходные данные
4
Входные данные
6 2
1 2 3 4 5 6
Выходные данные
0
#2863
План уничтожения
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Секретный бункер уходит на N этажей вниз. Под нижним этажом бункера находится сверхсекретная лаборатория. Злобный диверсант хочет вывести лабораторию из строя, залив её водой (даже очень небольшого количества воды хватит, чтобы запоганить сверхточные приборы). Для этого он использует лужицы воды, остающиеся от жизнедеятельности обитателей бункера. В лужицах i-го этажа находится Ei воды. Диверсанту известно, что если на нём скопится больше Сi воды, то перегородка не выдержит и вся вода сольется на этаж ниже. Он может проделать отверстия в некоторых перегородках, по которым вода также стечет вниз. Проделать отверстие в полу i-го этажа стоит Pi у.е. Помогите диверсанту уничтожить лабораторию с минимальными материальными затратами.

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

Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 500000) - количество этажей в бункере, в следующих N строках находятся тройки целых чисел Ci, Ei, Pi (0 < Ei ≤ Ci < 1000000; E1+E2+...+EN < 2000000000; Pi > 0; P1+P2+...+PN < 2000000000). Этажи нумеруются сверху вниз.

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

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

Примеры
Входные данные
4 
1 1 1 
1 1 3 
3 1 2 
3 1 10
Выходные данные
3
1
3
#2865
Просто матрица
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
+структуры данных

В этой задаче не будет идти речь о Бердяндии, о дорогах или авиарейсах. Здесь не будет надоевших монет. Речь пойдет о простой квадратной матрице.

В квадратную матрицу A порядка n были вписаны числа от 1 до n2, каждое по одному разу. Затем для каждого числа была записана пара чисел topi,j и lefti,j, где topi,j это количество чисел в столбце j стоящих выше числа Ai,j и одновременно больших него, а lefti,j это количество чисел в строке i стоящих левее числа Ai,j и одновременно больших него.

Вам заданы матрица top и left. Ваша задача состоит в нахождении возможной матрицы A, соответствующей входным данным.

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

В первой строке входного файла записано целое число n (1 ≤ n ≤ 600), где n это порядок искомой матрицы. Далее во входном файле записана пара матриц top и left, в виде n строк по n чисел в каждой строке. Матрицы разделены пустой строкой.

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

В выходной файл выведите матрицу A в формате, аналогичном входным данным. Если решений несколько, то выведите любое. Если решения не существует, выведите единственное число 0.

Примеры
Входные данные
3
0 0 0
0 0 0
0 0 2

0 0 0
0 1 0
0 1 2
Выходные данные
1 2 6
5 3 7
9 8 4
#2866
Волки и овцы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Пастбища Берляндии в опасности. Волки напали на пастбище овец. Пастух решил застрелить всех волков, при этом не убив ни одной овцы. Ружье заряжено бронебойными патронами, поэтому пули пролетают насквозь. Овцы и волки представлены отрезками. Пастух находится в точке (0, 0). Траектория полета пули — луч, выходящий из точки (0, 0). Если траектория пули имеет общуюточку с отрезком, характеризующим животное, то животное умирает. Найдите наименьшее количество выстрелов, необходимое для убийства всех волков. Овцы при этом должны остаться живы.

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

В первой строке записаны два целых числа N и M (0 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) — количество волков и овец соответственно. Далее следует N+M строк. В каждой строке записано четыре числа X1, Y1, X2, Y2 (−1000 ≤ X1, X2 ≤ 1000, 1 ≤ Y1, Y2 ≤ 1000), описывающие отрезки. Первые N отрезков описывают положение волков, следующие M строк положение овец.

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

Выведите наименьшее количество выстрелов, необходимое для убийства всех волков. Если невозможно убить всех волков, сохранив овец живыми, то выведите “No solution”.

Примеры
Входные данные
1 1
5 5 6 7
3 5 8 5
Выходные данные
No solution
Входные данные
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 999
Выходные данные
1
Страница: << 194 195 196 197 198 199 200 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест