Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 319 320 321 322 323 324 325 >> Отображать по:
#113866
Бюрократия
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, пронумерованных от 1 до N , Мирко имеет номер 1 . У всех кроме Мирко есть начальник. Начальник может иметь несколько подчинённых, но не более одного своего начальника.

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

Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 и так далее. Потом тот, кто на самом деле сделал работу, осознаёт, насколько эта капиталистическая система несправедлива и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации. Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.

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

Первая строка содержит одно натуральное число N ( 1 ≤ N ≤ 2·10 5 ) — число сотрудников компании. Следующая строка содержит N - 1 чисел a 2 , a 3 , ... a n ( 1 ≤ a i < i ), a i — номер начальника i -го сотрудника.

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

Выведите N чисел, i -е число должно означать, сколько монет получил i -й сотрудник

Система оценки

Программы, верно работающие при 2 ≤ N ≤ 5000 оцениваются в 50 баллов.

Примечание

Пояснения к первому примеру:

Пояснения ко второму примеру:
Примеры
Входные данные
3
1 1
Выходные данные
5 1 1
Входные данные
5
1 2 2 4
Выходные данные
13 8 1 3 1
#113887
Чемпионат Юпитера
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

На Юпитере выпускают футбольную форму m цветов. Каждая команда привезёт с собой два комплекта формы различных цветов. Разумеется, во время матча все игроки одной команды должны быть одеты в форму одного цвета, отличного от цвета формы другой команды.

Для судейства всех матчей этого чемпионата был приглашён глава Фантастической Инопланетной Футбольной Ассоциации Йозеф. Перед началом матча Йозеф назначает каждой из команд цвет футболок, в которых игроки выйдут на поле. Разумеется, выбирать можно только из тех двух цветов футболок, которые привезла с собой команда. После этого Йозеф выбирает себе футболку какого-то цвета, отличного от обоих цветов, в которых будут играть команды. Таким образом, обе команды и судья будут находиться на поле в футболках разного цвета. Любую футболку и команды, и Йозеф могут использовать в неограниченном количестве игр чемпионата.

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

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

В первой строке входных данных записаны два числа n и m ( 2 ≤ n ≤ 100 000, 2 ≤ m ≤ 10 9 ) — количество команд, участвующих в чемпионате, и количество возможных цветов футболок.

В i -й из следующих n строк записаны два различных целых числа от 1 до m — цвета футболок, которые привезла с собой команда с номером i .

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

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

В следующей строке выведите цвета этих футболок.

Если оптимальных решений несколько, разрешается вывести любое из них.

Система оценки

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

Примеры
Входные данные
3 4
1 2
2 3
1 4
Выходные данные
1
1
Входные данные
5 3
1 2
2 3
2 3
3 1
1 2
Выходные данные
2
3 1
#113889
Злая Лига Зла
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Злой Конь объявляет набор в Злую Лигу Зла! Он начертил своим копытом на бумаге длинную строку s , состоящую только из символов « ( », « ) » и « ? » и послал всем потенциальным кандидатам. Желающий подать заявку в злодеи должен для каждого символа « ? » выбрать: заменить его на открывающую скобку или на закрывающую. В Злую Лигу Зла попадёт тот из них, у кого в получившейся строке можно будет выделить самую длинную подпоследовательность , являющуюся правильной скобочной последовательностью.

Подпоследовательностью строки называется строка, получающаяся из данной удалением какого-то (возможно нулевого) количества символов. Например, строки « abc », « ac », « bcc » и « abbcc » являются подпоследовательностями строки « abbcc », а строки « cb » и « ba » не являются. Обратите внимание, пустая строка является подпоследовательностью любой строки.

Последовательность круглых скобок называется правильной в следующих случаях:

  1. Если она пустая.
  2. Если она состоит из правильной скобочной последовательности, заключённой в скобки.
  3. Если она состоит из двух правильных скобочных последовательностей, записанных одна за другой.

Например, последовательности круглых скобок « ()() » и « ((()))() » являются правильными, а « )(() », « ((((( » и « ()) » — нет.

Доктор Хоррибл уже давно мечтает попасть в Злую Лигу Зла, но из-за его пацифизма у него не очень-то хорошо выходит совершать злые поступки. Решает задачи Доктор Хоррибл тоже неважно, поэтому попросил вас помочь ему справиться с головоломкой от Злого Коня.

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

В единственной строке входных данных содержится строка s ( 1 ≤ | s | ≤ 10 000 000 ). Гарантируется, что строка s состоит только из символов « ( », « ) » и « ? ».

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

Выведите решение задачи Злого Коня, благодаря которому Доктор Хоррибл точно попадёт в Злую Лигу Зла. То есть замените « ? » на « ( » или « ) » таким образом, чтобы длина самой длинной правильной скобочной подпоследовательности, которую можно выделить в этой строке, была максимальной. Если оптимальных ответов несколько, разрешается вывести любой.

Система оценки

Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

Примечание

В первом тесте из результирующей строки можно после замены вопросов выделить правильную скобочную подпоследовательность длины 4 : « ()() ».

Во втором тесте из результирующей строки можно выделить правильную скобочную подпоследовательность длины 4 : « (()) ». Обратите внимание, возможны и другие варианты ответа.

Примеры
Входные данные
?)))?)
Выходные данные
()))()
Входные данные
)(???)(
Выходные данные
)((())(
#113890
Фото от пилота
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Дима архитектор. А ещё Дима фотограф. Он часто носится по свету и фотографирует местные Биг Бены и прочие крутые сооружения.

На этот раз Дима приехал в Берляндию, знаменитую своим метрополитеном. Он состоит из n линий, каждая из которых представлена прямой на карте города. На пересечении каждых двух линий метрополитена расположены станции, наземные павильоны которых признаны национальными памятниками архитектуры. Как только Дима увидел их с экрана своего смартфона, он мгновенно загорелся желанием их сфотографировать.

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

Вам даны n прямых, задающих линии метро, и t прямых, задающих доступные вертолётные маршруты. Дима просит для каждого маршрута найти расстояние до ближайшей к нему станции.

Гарантируется, что никакие две линии метрополитена не совпадают и что любые две линии пересекаются, а также, что любые два маршрута пересекаются и что любой маршрут пересекается с любой линией.

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

В первой строке входного файла находятся два числа n и t ( 2 ≤ n ≤ 100 000 , 1 ≤ t ≤ 20 ) — количество линий метро и количество возможных маршрутов, соответственно.

В следующих n строках содержатся по три целых числа a i , b i и c i ( | a i |, | b i | ≤ 10 000 , a i 2 + b i 2 > 0 , | c i | ≤ 10 8 ), описывающие линии метро. Каждая линия представляет собой прямую a i · x + b i · y + c i = 0 .

Затем следуют t строк с описанием возможных вертолётных маршрутов, каждая из них содержит три целых числа u i , v i , w i ( | u i |, | v i | ≤ 10 000 , u i 2 + v i 2 > 0 , | w i | ≤ 10 8 ). Аналогично, каждый маршрут представляет собой прямую u i · x + v i · y + w i = 0 .

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

Для каждого маршрута выведите единственное вещественное число — расстояние между i -м вертолётным маршрутом и наиболее близкой к нему станцией. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность относительно ответа жюри не будет превосходить 10 - 9 , то есть, , где p — ответ участника, а j — ответ жюри.

Система оценки

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

Примечание

Изображения к тестами из условия приведены ниже.

Примеры
Входные данные
3 1
1 -1 0
1 1 -4
4 -6 -4
0 1 0
Выходные данные
1.20000000000000000000
Входные данные
3 3
1 3 -6
-1 1 0
-5 2 15
3 -2 -3
-1 -1 4
1 0 -5
Выходные данные
0.41602514716892186000
0.16637806616154061000
0.00000000000000000000
#113892
Хранители
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Хранители в опасности, и Доктор Манхэттен со своим другом Дэниелом Драйбергом должны срочно их предупредить. Всего в команде хранителей n человек, i -й из которых находится в точке плоскости с координатами ( x i , y i ) .

Как всем известно, доктор Манхэттен вычисляет расстояние между двумя хранителями i и j по формуле | x i - x j | + | y i - y j | . Дэниел, как обычный человек, считает, что расстояние равно .

Сейчас успех операции зависит от того, сколько существует пар ( i , j ) ( 1 ≤ i < j ≤ n ), таких что расстояние между хранителем i и хранителем j , вычисленное Доктором Манхэттеном, равняется расстоянию между ними, вычисленному Дэниелом. Вычислить эту величину попросили именно вас.

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

В первой строке входных данных записано число n ( 1 ≤ n ≤ 200 000 ) — количество хранителей.

В каждой из следующих n строк записаны два целых числа x i и y i ( | x i |, | y i | ≤ 10 9 ).

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

Выведите количество пар хранителей, таких что расстояние между ними, вычисленное доктором Манхэттеном, равно расстоянию, вычисленному Дэниелом.

Система оценки

Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

Примечание

В первом примере расстояние между хранителем 1 и хранителем 2 равняется |1 - 7| + |1 - 5| = 10 в понимании Доктора Манхэттена и в понимании Дэниела. Для пар (1, 1) , (1, 5) и (7, 5) , (1, 5) расстояния, вычисленные Доктором Манхэттеном и Дэниелом, совпадают.

Примеры
Входные данные
3
1 1
7 5
1 5
Выходные данные
2
Входные данные
6
0 0
0 1
0 2
-1 1
0 1
1 1
Выходные данные
11
Страница: << 319 320 321 322 323 324 325 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест