Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 284 285 286 287 288 289 290 >> Отображать по:
#111789
Различные подстроки
  
ограничение по времени на тест
1.6 second;
ограничение по памяти на тест
64 megabytes

Дана строка S. Назовем ее подстрокой строку с i-го по j-й символ (i ≤ j). Ваша задача — посчитать количество различных подстрок данной строки.

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

Во входном файле находится одна строка S, состоящая не более, чем из 200000 символов. Все символы в строке — маленькие латинские буквы.

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

В выходной файл выведите единственное число — количество различных подстрок заданной строки. Гарантируется, что в данных тестах ответ не более 1018.

Примеры
Входные данные
aaba
Выходные данные
8
#111790
Экзамен
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла содержится два целых числа N, D (1 ≤ N ≤ 10000; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ..., XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента

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

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

Примеры
Входные данные
4 1
11 1 12 2
Выходные данные
2
1 1 2 2
Входные данные
4 0
11 1 12 2
Выходные данные
1
1 1 1 1
#111791
День рождения
  
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
256 megabytes

У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за S рублей!

Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.

Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше bi (больше денег у него просто с собой нет) и не меньше ai (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).

Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число fi — количество веселья, который тот произведет, если его позвать.

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

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

В первой строке входного файлы содержится два целых числа: n и S (1 ≤ n ≤ 100000, 0 ≤ S ≤ 109) — количество друзей Коли и стоимость билета. В следующих n строках содержится по три целых числа: в i-й из этих строк находятся числа ai, bi и fi (0 ≤ ai ≤ bi ≤ S, 0 ≤ fi ≤ 109). Они означают, что i-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между ai и bi, и он произведет fi веселья.

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

В первой строке выходного файла выведите два числа: k (количество приглашенных на вечеринку друзей) и F (максимальное суммарное веселье, которое можно получить). Во второй строке выведите k чисел — номера друзей, которых нужно пригласить

Примеры
Входные данные
4 10
4 5 40
2 4 30
2 6 10
3 5 20
Выходные данные
2 50
2 4
#111792
Головоломка умножения
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
16 megabytes

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

Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки 10·1·50 + 50·20·5 + 10·50·5 = 500 + 5000 + 2500 = 8000. Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким: 1·50·20 + 1·20·5 + 10·1·5 = 1000 + 100 + 50 = 1150.

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

В первой строке файла находится число карт N, во второй — разделённые пробелами N чисел на картах. Ограничения: 3 ≤ N ≤ 100, числа на картах целые от 1 до 100.

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

Вывести одно целое число — минимально возможное число очков.

Примеры
Входные данные
6
10 1 50 50 20 5
Выходные данные
3650
#111795
Сложности ремонта
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

До наступления летнего сезона ремонта теплотрасс по улицам города можно было проехать от любой площади до любой другой. При ремонте теплотрассы под какой-либо площадью движение по ней полностью перекрывается. Требуется определить, под какими из площадей ремонт теплотрассы нарушает возможность проезда из любого конца города, не затронутого ремонтом, в любой другой. Учесть, что в один и тот же момент времени ремонтная бригада работает только на одной из площадей.

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

В первой строке входного файла находятся числа N — количество площадей в городе и М — количество улиц их соединяющих (1 ≤ N ≤ 2000, 1 ≤ M ≤ 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

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

На первой строке выведите число C — количество площадей, ремонт на которых недопустим. На следующей строке выведите C целых чисел — номера этих площадей в возрастающем порядке.

Примеры
Входные данные
5 6
1 2
2 3
1 3
3 4
3 5
4 5
Выходные данные
1
3
Страница: << 284 285 286 287 288 289 290 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест