#1952

Фотография города

Темы: [Одномерные массивы]

Некоторый город построен на квадратном участке земли. Более того, территория города поделена на одинаковые квадратные участки, на каждом из которых построено какое-то здание. Здания пронумерованы числами от 1 до N², сначала нумеруются подряд здания одной "улицы", затем другой и так далее. Здания могут быть разной высоты.

Пример карты города для N=3 приведен на рисунке. В скобках сначала указан номер здания, затем его высота.

(1; 10)

(2; 6)

(3; 2)

(4; 5)

(5; 4)

(6; 7)

(7; 3)

(8; 8)

(9; 1)

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

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

Cначала вводится число N – длина стороны города (натуральное, не превышает 20). Затем вводится N² чисел – высоты зданий; число номер i показывает высоту i-го здания; высоты – натуральные числа, не превосходят 20.

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

Выведите панораму города, снятую со стороны, указанной на рисунке стрелкой, в следующем формате: N столбцов чисел (по количеству рядов зданий). Каждый столбец состоит из 20 чисел, которые описывают фотографию ряда зданий сверху вниз. Число равно номеру того здания, которое видно на панораме на данной высоте. Если на данной высоте нет здания, то выводится 0.

Для примера, показанного на рисунке вывод будет выглядеть так:

0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
1	0	0
1	0	0
1	8	0
1	8	6
1	8	6
4	8	6
4	8	6
7	8	6
7	8	6
7	8	9

Пояснения: при съемке первого ряда зданий высота самого высокого из них равна 10. Поэтому над ним ничего нет (десять нулей вверху первого столбца). Затем, здание номер 4 перекрывает нижнюю часть здания номер 1, поэтому у здания 1 видно только верхние 5 этажей (следующие пять единиц). Затем здание 7 перекрывает вид на нижние 3 этажа здания 4. Поэтому от здания 4 видны только два верхних этажа.

Второй столбец: при съемке с указанной точки здание 8 перекроет вид на все остальные здания этого ряда (потому что оно выше их), таким образом видно только это здание, а над ним ничего нет (12 нулей).

Третий столбец: самое высокое здание в этом ряду – здание 6, его высота равна 7. Поэтому вверху столбца идет 13 нулей. Здание 6 полностью загораживает собой здание 3. Вид на нижний этаж здания 6 загораживает здание 9, которое расположено ближе к точке съемки.

Комментарий к примеру тестов

Нумерация зданий будет такой:
1 2
3 4

Примеры

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

2
15 8
4 18

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

#1967

Транспортировка

Темы: [Бинарный поиск по ответу] [Алгоритм Дейкстры]

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

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

Примеры

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

3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099

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

#1969

Темы: [Куча]

Источники: [ Личные олимпиады, Международные олимпиады, 2009, 1 тур, Задача B ]

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

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

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

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

Ограничения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕРЫ

Пример ввода

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

4 100

5 1000

10 100

8 10

20 1

2

3

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

Пример ввода

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

3 4

1 2

1 3

3

1

2

3

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

Пример ввода

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

3 40

10 1

10 2

10 3

2

3

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

#1972

Первый ход

Темы: [Игры и выигрышные стратегии]

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

Пример таблицы для N=4 показан на рисунке: в первом столбце перечислены возможные ходы Димы, в первой строке – возможные ходы Кати. На пересечении строки и столба записана сумма выигрыша Димы (если число положительное) или сумма его проигрыша (если число отрицательное).

	1	2	3	4
1	5	0	1	-9
2	-2	-4	8	-6
3	9	-10	6	3
4	5	1	-1	-3

Определите оптимальный первый ход для Димы (указание: используйте маскиминный критерий).

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

Сначала вводится число N (натуральное, не превосходит 20), затем вводится N строк по N чисел в каждой – таблица сумм выигрышей. Числа в таблице целые, по модулю не превосходят 1000.

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

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

Примеры

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

2
4 -8
-1 2

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

#1973

k-й ход

Темы: [Игры и выигрышные стратегии]

Дима и Катя продолжают играть в игру, описанную в задаче A (задача №1972) . В данный момент каждый из них уже сделал (k-1) ходов. При этом Катя, с ее феноменальной памятью, прекрасно помнит, какие карточки использовал Дима (и, конечно же, Катя знает какие карточки использовала она сама).

Определите оптимальный k-й ход для Кати (указание: используйте маскиминный критерий).

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

Cначала вводится число N (натуральное, не менее 2 не превосходит 20), затем вводится N строк по N чисел в каждой – таблица сумм выигрышей для Кати. Числа в таблице целые, по модулю не превосходят 1000. Затем вводится число k – номер текущего хода (натуральное, не менее двух, не превосходит N). После этого следуют две строки по (k-1) числу в каждой: первая строка – карточки, которые уже использовал Дима, вторая строка – карточки, которые использовала Катя. Гарантируется, что описания использованных карточек корректны (натуральные числа, не превосходят N, никакое число в строке не повторяется).

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

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

Примеры

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

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

0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
1	0	0
1	0	0
1	8	0
1	8	6
1	8	6
4	8	6
4	8	6
7	8	6
7	8	6
7	8	9

0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
1	0	0
1	0	0
1	8	0
1	8	6
1	8	6
4	8	6
4	8	6
7	8	6
7	8	6
7	8	9

0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
0	0	0
1	0	0
1	0	0
1	8	0
1	8	6
1	8	6
4	8	6
4	8	6
7	8	6
7	8	6
7	8	9