Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 133 134 135 136 137 138 139 >> Отображать по:
#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
#1297
Одинаковые шары
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

prb1316Корабельная роща. 1898. При сравнении колорита «Корабельной рощи», позднего произведения Шишкина, с колоритом ранних его работ, ясно видно, что художник-пейзажист, подобно своим современникам-жанристам, перешел от локального понимания цвета к скупой, но целостной цветовой гамме. В основе этой гаммы лежит передача объединяющей изображение светотени.

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

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

В непрозрачной закрытой урне с небольшим отверстием в крышке находится n шаров (n четно), ровно половина из которых черные, остальные – белые. У Вас есть симметрическая монета, которую Вы начинаете подбрасывать. Если выпадет орел, то Вы извлекаете белый шар, если решка – то черный. Когда в урне остается в точности два шара, то они оказываются одинакового цвета и смысла дальше бросать монету нет (до этого момента в урне обязательно присутствуют хотя бы один белый и хотя бы один черный шар). Какая вероятность того, что произойдет описанная ситуация?

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

Каждая строка является отдельным тестом и содержит количество шаров в урне n (0 < n ≤ 100000, n четно).

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

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


Пример

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

6
10
256

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

0.62500000
0.72656250
0.94998552
#1303
Произведение матриц
  
ограничение по времени на тест
0.75 second;
ограничение по памяти на тест
64 megabytes

prb1322В лесу графини Мордвиновой. Петергоф. 1891. С годами у художника развилось обостренное цветовое видение. Теперь он видит и может передать кистью изменчивость цветов в зависимости от освещения и от рефлексов соседних предметов. Живописец выписывает мягкие переходы зеленых, желтоватых и сероватых оттенков стволов елей, хвои и мха. Но тонкие колористические изменения не самоцель для художника: ими он стремится донести до зрителя реальную жизнь природы. Картина вызывает у зрителя впечатление, что он находится внутри лесного пространства, дает прочувствовать окружающую атмосферу сосновой чащобы.

   Даны три квадратные матрицы A, B, C, каждая из которых имеет размер n х n. Необходимо проверить равенство: A х B = C.

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

Каждый тест начинается значением n (n ≤ 500). Далее следуют три матрицы A, B, C, каждая из которых представляется n строками, содержащих в точности n чисел. Элементы матриц А и В по модулю не превышают 1000. Последний тест содержит n = 0 и не обрабатывается. Например, в первом тесте следует проверить равенство

prb1322-1

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

Для каждого теста в отдельной строке вывести "YES" или "NO" в зависимости от того, имеет ли место равенство A х B = C или нет.


Пример

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

2
1 2
3 4
1 3
2 3
5 9
11 21
2
1 2
3 4
1 3
2 3
5 9
10 21
0

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

YES
NO
#1306
Чемпионат мира
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

В финале чемпионата мира по футболу во Франции принимали участие 16 команд. Победитель определялся по олимпийской системе:

   prb1324-1

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

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

Состоит из нескольких тестов. Первая строка каждого теста содержит количество команд в чемпионате n (4 ≤ n ≤ 64, n является степенью двойки). Следующие n строк описывают названия команд, каждая из которых содержит не более 10 символов. Далее следует матрица вероятностей p размера n×n. Ячейка p[i][j] содержит неотрицательное целочисленное значение вероятности в процентах, с которой i-ая команда выиграет у j-ой. Очевидно, что p[i][j] + p[j][i] = 100%.

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

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

Пример входных данных Пример выходных данных
16
Brazil
Chile
Nigeria
Denmark
Holland
Yugoslavia
Argentina
England
Italy
Norway
France
Paraguay
Germany
Mexico
Romania
Croatia
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50		 Test 1:
Brazil     p=8.54%
Chile      p=1.60%
Nigeria    p=8.06%
Denmark    p=2.79%
Holland    p=4.51%
Yugoslavia p=7.50%
Argentina  p=8.38%
England    p=1.56%
Italy      p=9.05%
Norway     p=3.23%
France     p=13.72%
Paraguay   p=3.09%
Germany    p=13.79%
Mexico     p=3.11%
Romania    p=5.53%
Croatia    p=5.53%

 

 

 

 

 

 

 

 

 
Страница: << 133 134 135 136 137 138 139 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест