Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 70 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
#1969
  
Темы: [Куча]
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Вам необходимо нанять работников для строительного проекта. Заявление о приёме на работу подали N кандидатов, пронумерованных от 1 до N включительно. Каждый кандидат с номером k требует, чтобы в случае приёма его на работу ему платили не менее чем Sk долларов. Также для каждого кандидата с номером k известен его уровень квалификации Qk. Положение о строительной деятельности требует, чтобы вы платили работникам пропорционально их уровню квалификации относительно друг друга. Например, если вы нанимаете двух работников A и B таких что QA = 3 * QB, то вы обязаны платить работнику A ровно в три раза больше, чем вы платите работнику B. Вам разрешается платить работникам нецелое число денег. Более того, разрешается даже платить количество денег, которое не может быть записано с помощью конечного числа десятичных цифр, такое как треть или шестую долю доллара.

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

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

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

Ограничения

1 ≤ N ≤ 500 000 Число кандидатов.

1 ≤ Sk ≤ 20  000 Минимальное требование к жалованию кандидата номер k.

1 ≤ Qk £ 20 000Уровень квалификации кандидата номер k.

1 ≤ W ≤ 10 000 000 000Сумма денег, доступная вам.

Важное замечание

Максимальное значение W не может быть представлено 32-битным типом данных. Вам необходимо использовать 64-битный тип данных, такой как long long в C/C++ или int64 в Pascal, чтобы значение W можно было сохранить в одной переменной. Дополнительные подробности представлены на страницах с технической информацией.

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

Ваша программа должна читать из стандартного потока ввода следующие данные:

  • Первая строка входного файла содержит два целых числа N и W, разделённые пробелом.
  • Следующие N строк описывают кандидатов, по одному кандидату на каждую строку. k-я строка из них описывает кандидата с номером k и содержит два целых числа Sk и Qk, разделённых пробелом.
Выходные данные

Ваша программа должна вывести в стандартный поток вывода следующие данные:

Первая строка должна содержать одно целое число H – количество работников, которых вы принимаете на работу.

Следующие H строк должны содержать список номеров кандидатов в произвольном порядке, которых вы выбрали для найма на работу (различные целые числа от 1 до N), по одному в каждой строке.

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

Для каждого из тестов, используемых для проверки решения этой задачи, вы получаете полный балл, если ваш выбор кандидатов помогает достигнуть всех ваших целей при удовлетворении всем заданным ограничениям. Если вы выведете корректно первую строку (то есть, корректное значение H), но при этом оставшаяся часть файла не будет соответствовать вышеописанным условиям, то вы получите 50% баллов за этот тест. Это правило также действует даже в случае, если оставшаяся часть файла отформатирована неправильно, но первая строка выведена правильно.

Для набора тестов общей стоимостью 50 баллов значение N не будет превосходить 5 000.

ПРИМЕРЫ

Пример ввода

Пример вывода

4 100

5 1000

10 100

8 10

20 1

2

2

3

 

 

Единственная комбинация, при которой вы можете позволить себе нанять двух рабочих и удовлетворить всем требованиям – это выбрать рабочих с номерами 2 и 3. Вы можете заплатить им 80 и 8 долларов, соответственно, таким образом, уложившись в бюджет 100 долларов.

 

Пример ввода

Пример вывода

3 4

1 2

1 3

1 3

3

1

2

3

 

 

В этом примере вы можете позволить себе нанять всех трёх рабочих. Вы платите 1 доллар рабочему с номером 1 и по 1.50 доллара рабочим с номерами 2 и 3, и таким образом, укладываетесь в ваш бюджет, равный 4 долларам.

 

Пример ввода

Пример вывода

3 40

10 1

10 2

10 3

2

2

3

 

В этом примере вы не можете позволить себе нанять всех трёх рабочих, так как это стоило бы вам 60 долларов, но вы можете позволить себе нанять любых двух из них. Вы выбираете рабочих с номерами 2 и 3, потому что в этом случае получается наименьшая сумма денег по сравнению с другими комбинациями из двух рабочих. Вы можете заплатить 10 долларов рабочему с номером 2 и 15 долларов рабочему с номером 3, общая сумма будет равна 25 долларам. Если бы вы наняли рабочих с номерами 1 и 2, то вам пришлось бы заплатить им хотя бы 10 и 20 долларов соответственно. Если бы вы выбрали рабочих с номерами 1 и 3, то вам пришлось бы заплатить им хотя бы 10 и 30 долларов соответственно.

#2532
Ханты-Мансийск — Париж
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

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

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

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.

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

В первой строке выходного файла выведите минимальную возможную стоимость передачи информации \(w\) и количество задействованных в цепочке телефонных номеров \(k\). Далее выведите \(k\) номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.

Система оценивания

  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 500, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 5 000, будут оцениваться из 60 баллов.

    • Примеры
    Входные данные
    2099013166
7043239909
1
0258442145
1
0000000000
1
0000000001
1
0000000002
1
0147571204
    Выходные данные
    22 5
2099013166
0000000000
0000000001
0000000002
7043239909
    Входные данные
    4261802325
7967612531
1
8176476745
1
3084033164
1
1737248630
1
9447552231
1
2848478213
    Выходные данные
    40 5
4261802325
3084033164
1737248630
9447552231
7967612531
    #2534
    Земледелие 2.0
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из \(n\) рядов по \(m\) участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.

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

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

    Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.

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

    В первой строке входного файла записаны натуральные числа \(n\) и \(m\) (\(2\le n\le2\,000\), \(2\le m\le2\,000\)), где \(n\) — количество рядов на поле, а \(m\) — количество участков в каждом ряду (количество столбцов). Далее в \(n\) строках содержится описание поля. Каждая из этих \(n\) строк содержит \(m\) символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.

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

    Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами \(a\), \(b\), \(c\), \(d\), где \(a\) и \(b\) — номер ряда и столбца самого северо-западного его участка, а \(c\) и \(d\) — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до \(n\), а столбцы — с запада на восток от 1 до \(m\).

    Вторая строка должна описывать фрагмент под посадку в том же формате.

    Третья строка должна содержать площадь фрагмента (количество участков) под посадку.

    Если решений несколько, выведите любое.

    Система оценивания

    Решения, корректно работающие при \(n\le40\) и \(m\le40\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le300\) и \(m\le300\), будут оцениваться из 60 баллов.

    Примеры
    Входные данные
    4 4
1110
1010
1110
0000
    Выходные данные
    2 2 2 2
1 1 3 3
9
    #3204
    Отрезки на прямой возвращаются
      

    На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

    • он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
    • среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

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

    Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

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

    Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

    Если существует несколько решений, выведите любое.

    Примечания

    Тесты состоят из четырёх групп.

    1. Тест 1, из условия, оценивается в 0 баллов.
    2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
    3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
    4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
    Примеры
    Входные данные
    4
2 3
0 4
1 6
0 5
    Выходные данные
    3 4 0 0
    #3205
    Отрезки на прямой возвращаются--2
      
    ограничение по времени на тест
    1.0 second;
    ограничение по памяти на тест
    64 megabytes

    При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

    Проверяющей программе доступно три блока информации:

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

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

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

    Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.

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

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

    Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

    Примечания

    Тесты состоят из четырёх групп.

    1. Тест 1, из условия, оценивается в 0 баллов.
    2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
    3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
    4. Тесты 28--35. Полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
    Примеры
    Входные данные
    4
2 3
0 4
1 6
0 5
2 2 1 0
3 4 0 0
    Выходные данные
    OK
WA
WA
OK
    Страница: << 3 4 5 6 7 8 9 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест