Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 235 236 237 238 239 240 241 >> Отображать по:
#3554
5E: культорги и скобки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дана скобочная последовательность. Необходимо определить количество циклических сдвигов, переводящих ее в правильную.

Встретились однажды три культорга ЛКШ...

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

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

Циклическим сдвигом строки называется перенос некоторого (возможно, нулевого) количества символов из конца строки в её начало без изменения их порядка.

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

В единственной строке дана скобочная последовательность, записанная первым культоргом. Длина последовательности не равна нулю и не превышает \(100\,000\) символов.

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

Выведите количество циклических сдвигов, превращающих записанную скобочную последовательность в правильную.

Примеры
Входные данные
)(()
Выходные данные
1
Входные данные
)()(
Выходные данные
2
Входные данные
()
Выходные данные
1
#3555
10E: Pink Floyd
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Найти самый длинный путь от одной вершины до другой в ориентрованном графе, либо определить, что существует сколь угодно длинный путь, либо определить, что пути не существует.

Группа Pink Floyd собирается отправиться в новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других — много ест и набирает вес.

Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным.

Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа \(n\), \(m\) и \(k\) — количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (\(n \le 100\), \(m \le 10\,000\), \(2 \le k \le 10\,000\)). Города пронумерованы числами от \(1\) до \(n\).

Следующие \(m\) строк содержат описание рейсов, по одному на строке. Рейс номер \(i\) описывается тремя числами \(b_i\), \(e_i\) и \(w_i\) — номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (\(1 \le b_i, e_i \le n\), \(-100\,000 \le w_i \le 100\,000\)).

Последняя строка содержит числа \(a_1, a_2, ..., a_k\) — номера городов, в которых проводятся концерты (\(a_i \neq a_{i+1}\)). В начале концертного тура группа находится в городе \(a_1\).

Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число \(l\) — количество рейсов, которые должна сделать группа. Вторая строка должна содержать \(l\) чисел — номера используемых рейсов.

Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку „infinitely kind“.

Примеры
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
Выходные данные
6
5 6 5 7 2 3
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
Выходные данные
infinitely kind
#3559
Алгоритм Краскала
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Первая строка входных данных содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них разные, в пределах от 0 до N–1 каждое, и обозначают концы соответствующего ребра, третье — в пределах от 1 до 1000000000 и обозначает длину этого ребра. Гарантировано, что все ребра имеют различные длины. Количество вершин графа не превышает 80000, количество рёбер — 100000.

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

Выведите на стандартный выход (экран) либо единственное число — сумму длин рёбер остовного дерева минимального веса (если граф связный), либо единственную фразу «NON-CONNECTED» (без кавычек, через дефис) если граф не связный.

Примечание

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

Указания.

Алгоритму Краскала, в отличие от предыдущих графовых задач, совершенно не нужно, чтобы граф был представлен списками смежности. Зато нужно сортировать ребра по длине. Разрешается самому написать сортировки (со сложностью O(N logN), иначе программа окажется не достаточно эффективной). Но рекомендуется заставить работать стандартный алгоритм sort. Для него нужно подключить заголовочный файл algorithm и указать, каким образом сравнивать структуры, представляющие ребра. Для этого можно перегрузить (overload) операцию сравнения operator < для типа, представляющего ребро (подробнее см. в книгах, help-е, а также в указаниях к задаче «Алгоритм Дейкстры за M logN»).

Примеры
Входные данные
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
Выходные данные
19
#3561
День рождения
  
Источники: [ Командные олимпиады, ВКОШП, 2010, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

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

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

В первой строке входного файлы содержится два целых числа: \(n\) и \(S\) (\(1 \le n \le 100\,000\), \(0 \le S \le 10^9\)) — количество друзей Коли и стоимость билета. В следующих \(n\) строках содержится по три целых числа: в \(i\)-й из этих строк находятся числа \(a_i\), \(b_i\) и \(f_i\) (\(0 \le a_i \le b_i \le S\), \(0 \le f_i \le 10^9\)). Они означают, что \(i\)-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между \(a_i\) и \(b_i\), и он произведет \(f_i\) веселья.

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

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

#3570
Деление пополам
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a.

Для решения используйте метод деления отрезка пополам.

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

Число a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после запятой. Число n – натуральное, не превосходящее 10.

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

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры
Входные данные
2
2
Выходные данные
1.41421356237
Страница: << 235 236 237 238 239 240 241 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест