Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск
    Бинарный поиск в массиве(24 задач)
    Бинарный поиск по ответу(56 задач)
    Бинарный поиск значения функции(5 задач)
---> 32 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 >> Отображать по:
#715
Морской бой
  
Заданы начальные координаты и скорости кораблей на плоскости. Есть бомбы, уничтожающие корабли на расстоянии не превышающем R от центра взрыва. Взрывать бомбы можно только в целые моменты времени. Требуется уничтожить все корабли наименьшим количеством бомб.

N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше R). Взрывать бомбу можно только в целые моменты времени.

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

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

В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках  содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 105. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.

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

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

В первой строке выведите одно число – минимальное количество взрывов K. В следующих K строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени.

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

Комментарий. Решения, верно работающие при N ≤ 3, будут набирать не менее 50 баллов.

Примеры
Входные данные
3 3
-3 3 1 0
0 -6 0 2
-8 6 4 -1
Выходные данные
1
3 2.000 1.500
Входные данные
2 1
-4 -4 2 2
2 2 -2 -2
Выходные данные
2
0 -4.0000 -4.0000
0 2.0000 2.0000
#1227
Радио «Байтик»
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, при распространении радиоволн возникает интерференция, поэтому если рядом расположены две радиопередающие станции, вещающие на одной и той же частоте, то качество радиопередач резко снижается.

Радиостанция «Байтик» планирует транслировать свои программы в стране Флатландия. Министерство связи Флатландии выдало радиостанции лицензию на вещание на двух различных частотах.

Владельцы радиостанции имеют возможность транслировать свои радиопрограммы с использованием N радиовышек, расположенных в различных точках страны. Для осуществления трансляции на каждой радиовышке требуется установить специальный передатчик – трансмиттер. Каждый передатчик можно настроить на одну из двух частот, выделенных радиостанции. Кроме частоты вещания, передатчик характеризуется также своей мощностью. Чем мощнее передатчик, тем на большее расстояние он распространяет радиоволны. Для простоты, предположим, что передатчик мощности R распространяет радиоволны на расстояние, равное R километрам.

Все передатчики, установленные на вышках, должны, согласно инструкции министерства, иметь одну и ту же мощность. Чтобы программы радиостанции могли приниматься на как можно большей территории, мощность передатчиков должна быть как можно большей. С другой стороны, необходимо, чтобы прием передач был качественным на всей территории Флатландии. Прием передач считается качественным, если не существует такого участка ненулевой площади, на который радиоволны радиостанции «Байтик» приходят на одной частоте одновременно с двух вышек.

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

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

Первая строка содержит число N — количество вышек (3 ≤ N ≤ 1200). Последующие N строк содержат по два целых числа — координаты вышек. Координаты заданы в километрах и не превышают 104 по модулю. Все точки, в которых расположены вышки, различны. Все числа в строках разделены пробелом.

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

В первой строке выводится вещественное число — искомая мощность передатчиков. Во второй строке выводятся N чисел, где i-е число должно быть равно 1, если соответствующий передатчик должен вещать на первой частоте, и 2, если на второй. Ответ должен быть выведен с точностью, не меньшей 10–8.

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.707106781186548
1 2 2 1
#1282
Тапкодёр
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2k зарегистрировавшихся участников, которым присвоены номера от 1 до 2k.

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

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

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

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

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

В первой строке заданы три целых числа k (1 ≤ k ≤ 60), n (0 ≤ n ≤ 100 000) и m (1 ≤ m ≤ 100 000). В следующих n строках описаны n пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара x y, то пары y x быть не может, кроме того, x ≠ y. В последней строке перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.

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

Выходные данные должны содержать m целых чисел — максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до k.

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

1. У каждого из участников есть возможность выйти в финал, так как договорных матчей нет.

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

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

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

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

0. Тесты 1–10. k <= 5. Эта группа оценивается в 30 баллов.

1. Тесты 11–14. k <= 20. Эта группа оценивается в 20 баллов.

2. Тесты 15–18. k <= 30. Эта группа оценивается в 20 баллов.

3. Тесты 19–23. Дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов.

Примеры
Входные данные
2 0 3
1 3 4
Выходные данные
2 2 2
Входные данные
3 1 1
3 1
1
Выходные данные
3
Входные данные
3 3 4
1 2
1 3
4 1
1 2 3 4
Выходные данные
3 1 2 3
#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
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест