Страница: << 16 17 18 19 20 21 22 >> Отображать по:

#1282

Тапкодёр

Темы: [Двоичная система счисления] [Бинарный поиск в массиве] [Сортировка слиянием]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2008, 2 день, Задача B ]

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

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

Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме 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 1 2 3

#1297

Одинаковые шары

Темы: [Арифметические алгоритмы]

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

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

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

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

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

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

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

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

Пример

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

6
10
256

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

0.62500000
0.72656250
0.94998552

#1303

Произведение матриц

Темы: [Арифметические алгоритмы]

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

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

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

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

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

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

Пример

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

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

YES
NO

#1306

Чемпионат мира

Темы: [Арифметические алгоритмы]

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%

#1339

Цифры и числа

Темы: [Двоичная система счисления] [Простые задачи на перебор]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2009, Задача C ]

Как много открытий можно сделать, исследуя числа и составляющие их цифры!

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

Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 1110₂ (в десятичной системе — 14) можно получить из числа 1100₂ (в десятичной системе — 12), прибавив к последнему сумму его цифр:

1100₂ + 10₂ = 1110₂.

Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 1₂, 4 = 100₂, 6 = 110₂, 13 = 1101₂, 15 = 1111₂. Продолжить работу он собирается с помощью компьютера.

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

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

В первой строке входного файла содержится число n, записанное в десятичной системе счисления (1 ≤ n ≤ 10¹⁸).

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

В единственной строке выходного файла должно содержаться единственное число — количество двоичных некрасивых чисел, не превосходящих n.

Примечание

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

Примеры

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

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

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

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

Страница: << 16 17 18 19 20 21 22 >> Отображать по:

Выбрано

Отменить

Добавить в контест