Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 30 31 32 33 34 35 36 >> Отображать по:
#3701
Посадка в поезд
  

Цифровой поезд нового поколения состоит из вагонов, содержащих по \(N\) мест для пассажиров. Все места расположены вдоль вагона и пронумерованы от \(1\) до \(N\). Вход в вагон расположен левее места \(1\), а места \(1, 2, \ldots, N\) расположены правее от входа в соответствующем порядке. \(N\) пассажиров готовятся сесть в поезд. Каждый заходящий в вагон характеризуется номером места \(A_i\) и своей массой \(B_i\). Когда пассажир идет по вагону от входа до своего места, некоторые пассажиры, которые сели ранее, мешают ему пройти. Пассажир испытывает неудобство, каждый раз проходя мимо человека массы большей, чем у него самого. Суммарным неудобством пассажира при посадке называется количество раз, когда он испытывал неудобство при движении к своему месту от входа в вагон. Ваша задача — по заданному порядку посадки пассажиров найти суммарное неудобство каждого.

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

Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается с целого числа \(N\; (1 \leq N \leq 100\,000)\) — количества мест (пассажиров). Далее набор входных данных содержит пары целых чисел \(A_i, B_i\; (1 \leq A_i \leq N, 1 \leq B_i \leq 10^9)\). Все числа \(A_i\) и \(B_i\) различны между собой. То есть номера мест пассажиров образуют перестановку. Пассажиры садятся в поезд именно в том порядке, в котором они заданы во входном файле. Количество наборов входных данных не превосходит \(5\).

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

Выведите ответ на каждый набор входных данных. Каждый ответ должен состоять из последовательности \(N\) целых чисел \(P_1, P_2, \ldots, P_N\), где \(P_i\) — суммарное неудобство \(i\)-го пассажира.

Пример
Ввод
3
1 2
2 3
3 1
2
1 1
2 2
Вывод
0 0 2
0 0
#3711
Большой, белый, очень прямоугольный
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.

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

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

Примеры
Входные данные
5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
Выходные данные
9
#3767
Англо-латинский словарь
  

Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.

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

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

Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.

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

В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на латинский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.

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

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

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

Примеры
Входные данные
3
apple - malum, pomum, popula
fruit - baca, bacca, popum
punishment - malum, multa
Выходные данные
7
baca - fruit
bacca - fruit
malum - apple, punishment
multa - punishment
pomum - apple
popula - apple
popum - fruit
#3769
Продажи
  

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

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

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

Вводятся сведения о покупках в указанном формате. Количество не превосходит 10^9

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

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

Примеры
Входные данные
Ivanov paper 10
Petrov pens 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5
Выходные данные
Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pens 5
#3770
Выборы в США - 2
  

Как известно, в США президент выбирается не прямым голосованием, а путем двухуровневого голосования. Сначала проводятся выборы в каждом штате и определяется победитель выборов в данном штате. Затем проводятся государственные выборы: на этих выборах каждый штат имеет определенное число голосов — число выборщиков от этого штата. На практике, все выборщики от штата голосуют в соответствии с результами голосования внутри штата, то есть на заключительной стадии выборов в голосовании участвуют штаты, имеющие различное число голосов.

На этот раз вам известно число выборщиков от каждого штата США и результаты голосования каждого гражданина США (а также в каком штате проживает данный гражданин).

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

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

Первая строка входных данных содержит количество штатов в США N. Далее идет N строк, описывающих штаты США, каждая строка состоит из названия штата и числа выборщиков от этого штата. Далее до конца файла идут записи результатов голосования по каждому из участников голосования. Одна строка соответствует одному избирателю. Записи имеют вид: название штата, имя кандидата, за которого проголосовал данный избиратель. Названия штатов и имена кандидатов не содержат пробелов.

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

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

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

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

Примечание к примерам тестов

1. В Florida 2 избирателя голосует за Gore и три избирателя за Bush, поэтому 25 голосов выборщиков от Floria получает Bush. В Pennsylvania побеждает Gore (5 голосов против 1), поэтому Gore получает 23 голоса выборщиков от Pennsylvania.

2. В Florida побеждает Gore (5 голосов выборщиков), в Alaska — Bush (2 голоса выборщика). В Pennsylvania два кандидата набрали наибольшее число голосов (по 1), поэтому 4 голоса выборщиков от этого штата получает Clinton, т.к. он идет раньше в лексикографическом порядке.

Примеры
Входные данные
2
Florida 25
Pennsylvania 23
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Pennsylvania Bush
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Выходные данные
Bush 25
Gore 23
Входные данные
3
Florida 5
Pennsylvania 4
Alaska 3
Florida Gore
Pennsylvania Obama
Pennsylvania Clinton
Alaska Bush
Выходные данные
Gore 5
Clinton 4
Bush 3
Obama 0
Страница: << 30 31 32 33 34 35 36 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест