Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 155 156 157 158 159 160 161 >> Отображать по:
#1664
Суперсумма
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Дано \(N\) натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

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

В первой строке дано число \(N\) ( 1 ≤ \(N\) ≤ 10000). Далее заданы \(N\) натуральных чисел, не превосходящих \(10^9\). Для каждого числа количество разбиений меньше 231.

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

Вывести \(N\) чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры
Входные данные
5 
3
3
2
2
1
Выходные данные
2
2
0
0
0
#1666
Супермногоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

  1. Oтрезок соединяет только пару супермногоугольников.

  2. Суммарная длина отрезков была минимальна.

  3. Между любыми двумя супермногоугольниками должен существовать путь (последовательность некоторых отрезков и частей границ супермногоугольников).

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

В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.

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

В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.

Примеры

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

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

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000
#1668
Блохи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Блохи сидят на клетках шахматного поля и ходят конем. Должны собраться в одной из клеток. Определить сумму длин кратчайших путей.

На клеточном поле, размером \(N\)x\(M\) (2 ≤ \(N\), \(M\) ≤ 250) сидит \(Q\) (0 ≤ \(Q\) ≤ 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

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

В первой строке входного файла находится 5 чисел, разделенных пробелом: \(N\), \(M\), \(S\), \(T\), \(Q\). \(N\), \(M\) - размеры доски (отсчет начинается с 1); \(S\), \(T\) - координаты клетки - кормушки (номер строки и столбца соответственно), \(Q\) - количество блох на доске. И далее \(Q\) строк по два числа - координаты каждой блохи.

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

Содержит одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.

Примеры
Входные данные
2 2 1 1 1
2 2
Выходные данные
-1
#1669
Отчет
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы две последовательности чисел: объем продукции и процент брака. Требуется найти наибольшую подпоследовательность, в которой объем продукции растет, а процент брака падает.

Один из цехов завода производит продукцию в течение \(N\) месяцев. Начальнику цеха было поручено составить отчет о росте производительности данного цеха и об уменьшении доли некачественной продукции в процентном соотношении (точность доли процента до одного знака после запятой, например, 2/7=0.(285714) ≈ 28.6%). При этом в отчет должна войти информация как можно за большее число месяцев \(K\) (\(K\) ≤ \(N\)) работы цеха. Начальник цеха решил, что он включит в отчет данные только по тем месяцам (не обязательно взятым подряд, но обязательно в хронологическом порядке), по которым наблюдается строгий рост количества производимой продукции и строгий спад доли бракованных товаров по сравнению с данными предыдущего месяца, вошедшего в отчет. Определить, какое максимальное количество месяцев удовлетворяет этим условиям и сколько есть возможных вариантов составления отчета.

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

Первая строка файла содержит число \(N\) (1 ≤ \(N\) ≤ 40) - количество месяцев работы цеха. Далее следует N строк, содержащих целые числа \(v_i\) (1 ≤ \(v_i\) ≤ 10000) и \(b_i\) (1 ≤ \(b_i\) ≤ \(v_i\)); \(v_i\) - объем продукции, произведенной цехом за \(i\)-ый месяц; \(b_i\) - количество бракованной продукции в \(i\)-ом месяце.

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

Первая строка файла содержит число \(K\) - количество месяцев, по которым будет включена в отчет информация о работе цеха. Вторая строка содержит число \(P\) - количество возможных вариантов составления отчета с максимальным содержанием.

Примеры
Входные данные
10
313 100
313 106
442 106
442 104
475 104
475 102
539 102
539 109
682 109
682 111
Выходные данные
5
32
#1678
Номера для секретной службы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В королевстве Его Величества Короля Бубея Второго приняты шестизначные автомобильные номера, состоящие только из цифр. Руководство Королевской Секретной Службы пожелало придумать особенные номера для своих сотрудников, чтобы они могли узнать «своих» среди обычных граждан. Было предложено, чтобы номер машины сотрудника Секретной Службы содержал только цифры от 1 до 6. При этом цифры номера должны подчиняться такой закономерности:

1) первые три цифры номера могут быть какими угодно (при условии, что это не цифры 0, 7, 8, или 9);

2) четвертая цифра в сумме с третьей должна давать 7;

3) пятая цифра в сумме со второй должна давать 7;

4) шестая цифра в сумме с первой должна давать 7.

Однако, у руководства Дорожной Службы возникла проблема: они уже успели отпечатать и раздать гражданам первые \(N\) номеров. Определите, у скольких граждан необходимо изъять номера в пользу Секретной Службы, а им самим выдать новые?

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

вводится единственное число \(N\) (положительное, не превышает \(10^6\)) – количество номеров, которые уже розданы гражданам страны. Обратите внимание: номера начинаются с «000000», затем «000001», затем «000002» и т.д.

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

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

Примеры
Входные данные
620775
Выходные данные
186
Входные данные
580447
Выходные данные
180
Страница: << 155 156 157 158 159 160 161 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест