Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска
    Линейный поиск(29 задач)
    Бинарный поиск(101 задач)
    Порядковые статистики(3 задач)
    Поиск подстроки в строке(1 задач)
    Тернарный поиск(8 задач)
    "Два указателя"(18 задач)
---> 43 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1283
Сочи-2014
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

В строительстве объектов готовы участвовать K фирм. Фирмы имеют разные строительные мощности, выраженные в количестве денежных средств, которые фирма может осваивать в единицу времени.

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

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

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

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

Первая строка содержит целое число N — количество объектов (1 ≤ N ≤ 50). Во второй строке содержатся разделенные пробелами целочисленные значения S1, S2, S3, …, SN объемов денежных средств, выделяемых для строительства каждого из объектов. Числа Si выражены в тысячах рублей, положительные и не превышают 1000.

В третьей строке находится целое число K — количество строительных фирм (1 ≤ K ≤ 50). Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V1, V2, V3, …, VK в тыс.руб/час. Числа Vj положительные и не превышают 1000.

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

Первая строка содержит действительное число T — время в часах окончания всех работ, считая с начала строительства, выведенное не менее чем с тремя точными знаками после запятой. Далее в каждой строке содержатся разделенные пробелами три числа: t, i, j, где действительное число t — время от начала строительства в часах, в которое j-я фирма приступает к строительным работам на i-м объекте.

Значения времен необходимо выводить с максимально возможной точностью.

Строки должны быть отсортированы по неубыванию t.

Примеры
Входные данные
2
24 20
2
3 2
Выходные данные
8.800
0 1 1
0 2 2
6.4000000 1 2
6.4000000 2 1
Входные данные
3
100 100 100
4
5 5 10 10
Выходные данные
12.00000
0 1 3
0 2 4
0 3 1
4 2 2
4 3 4
8 1 1
8 3 4
8 2 3
#1341
Граффити на заборе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Плиты пронумерованы числами от 1 до N, граффити-художники имеют номера от 1 до M. Первоначально i-й граффити-художник находится около плиты с заданным номером pi. Каждому художнику требуется b минут на разрисовывание любой плиты. Каждую плиту должен разрисовать ровно один граффити-художник.

В начале работы, а также после разрисовывания любой плиты граффити-художник может перейти к любой неразрисованной плите. Время перемещения граффити-художника от любой плиты к соседней с ней одинаково и равно a минут. Таким образом, чтобы перейти от плиты с номером i к плите с номером j художнику требуется a×|i – j| минут.

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

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

В первой строке входного файла указаны числа N — количество плит в заборе и M — количество граффити-художников (1 ≤ N, M ≤ 100000). Во второй строке заданы два целых числа: a — количество минут, которое требуется для перехода от любой плиты к соседней, и b — количество минут, которое требуется граффити-художнику на разрисовывание одной плиты (1 ≤ a, b ≤ 106). В третьей строке заданы M чисел p1, p2, …, pM — начальные положения граффити-художников (1 ≤ pi ≤ N).

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

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

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

Примечание

Решения, корректно работающие при M ≤ 2, будут оцениваться из 40 баллов.

Примеры
Входные данные
10 2
19 56
9 2
Выходные данные
375
5 10 9 8 7 6 
5 1 2 3 4 5
#1387
Предпраздничная суета
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.

В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется Ai единиц времени на обработку одного товара и Bi единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет Ti единиц времени.

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

Напишите программу, которая определит это минимальное время.

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

В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).

Все числа во входном файле целые.

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

Выведите минимальное время выхода последнего школьника из магазина.

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

Здесь лучше всего встать в обе кассы и купить там по одному тортику.

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

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.

Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.

Примеры
Входные данные
2
100 10 40
10 100 50
2 2
Выходные данные
160
Входные данные
3 
1 2 0
5 2 1
2 10 1
3 5
Выходные данные
7
#1664
Суперсумма
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Дано \(N\) натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

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

В первой строке дано число \(N\) ( 1 ≤ \(N\) ≤ 10000). Далее заданы \(N\) натуральных чисел, не превосходящих \(10^9\). Для каждого числа количество разбиений меньше 231.

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

Вывести \(N\) чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры
Входные данные
5 
3
3
2
2
1
Выходные данные
2
2
0
0
0
#1923
Дипломы
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось \(n\) дипломов, причём, как оказалось, все они имели одинаковые размеры: \(w\) — в ширину и \(h\) — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером \(w\) на \(h\). Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

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

Входной файл содержит три целых числа: \(w\), \(h\), \(n\) (\(1\le w,h,n\le 10^9\)).

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Иллюстрация к примеру
Примеры
Входные данные
2 3 10
Выходные данные
9
Входные данные
1 1 1
Выходные данные
1
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест