Страница: << 2 3 4 5 6 7 8 >> Отображать по:

#112581

Футбол

Темы: [Теория вероятностей]

N = 2 ^K команд играют в турнире по футболу с выбыванием.

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

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

Аналогично играются третий, четвёртый и все раунды до K -ого.

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

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

Каждый тест состоит из нескольких наборов входных данных (в каждой тесте - не более пяти наборов). Число наборов указано в первой строке входного файла. Каждый набор начинается с числа команд N ( 2 ≤ N ≤ 1024, N - степень двойки). Потом идёт N строк длиной не более 10 - названия команд. Потом идёт матрица NxN , состоящая из целых чисел от 1 до 99 - j -ое число в i -ой строке это вероятность в процентах того, что i -ая команда выиграет j -ую. Вероятности будут дополненные ведущими нулями до двузначных чисел.

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

Примеры

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

2
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
4
Spartak
Lokomotiv
TCSKA
Anzhi
50 42 30 20
58 50 30 10
70 70 50 05
80 90 95 50

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

Test 1:
Brazil     8.54%
Chile      1.60%
Nigeria    8.06%
Denmark    2.79%
Holland    4.51%
Yugoslavia 7.50%
Argentina  8.38%
England    1.56%
Italy      9.05%
Norway     3.23%
France     13.72%
Paraguay   3.09%
Germany    13.79%
Mexico     3.11%
Romania    5.53%
Croatia    5.53%
Test 2:
Spartak   8.61%
Lokomotiv 6.38%
TCSKA     3.50%
Anzhi     81.51%

#112744

Выбор зала

Темы: [Формула]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2015, 1 день, Выбор зала ] [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2015, 1 день, Задача A ]

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом. Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от \(A\) до \(B\) квадратных метров, включительно.

Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от \(C\) до \(D\) метров, включительно. Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами \(Y\) × \(Z\) и \(Z\) × \(Y\) считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным \(A\), \(B\), \(C\) и \(D\) определяет количество различных залов, площадь которых находится в пределах от \(A\) до \(B\), а периметр — от \(C\) до \(D\), включительно.

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

Входной файл содержит четыре разделенных пробелами целых числа: \(A\), \(B\), \(C\) и \(D\) (1 ≤ \(A\) ≤ \(B\) ≤ \(10^9\) , 4 ≤ \(C\) ≤ \(D\) ≤ \(10^9\) )

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

Выходной файл должен содержать одно число — искомое количество залов.

Пояснения к примеру

В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

Система оценки и описание подзадач

Подзадача 1 (50 баллов)
1 ≤ \(A\) ≤ \(B\) ≤ 1000, 4 ≤ \(C\) ≤ \(D\) ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (50 баллов)
1 ≤ \(A\) ≤ \(B\) ≤ \(10^9\),
4 ≤ \(C\) ≤ \(D\) ≤ \(10^9\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Примеры

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

2 10 4 8

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

#112831

Строки

Темы: [Конструктив] [Строки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2014, Задача E ]

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.

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

Программа получает на вход три строки, состоящие из строчных букв латинского алфавита. Длина каждой строки не превышает 100 символов.

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

Если при помощи указанных операций возможно сделать все три строки равными, выведите такую строку S , что суммарное число операций, необходимых для преобразования всех трёх данных строк к строке S , будет минимальным. Если этого сделать нельзя, программа должна вывести одно слово IMPOSSIBLE (заглавными буквами).

Примечание

Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является слово IMPOSSIBLE, будет оцениваться в 0 баллов.

Примеры

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

aaaza
aazzaa
azzza

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

aazza

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

xy
xxyy
yx

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

IMPOSSIBLE

#113100

Три сына

Темы: [Остатки] [Конструктив]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 2 день, Три сына ] [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 2 день, Задача A ]

Во владениях короля Флатландии находится прямая дорога длиной \(n\) километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

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

каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры \(a \times a, b \times b\) и \(c \times c\);
стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна \(n\);
участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство \(a < b < c\);
суммарная площадь участков \(a^2 + b^2+ c^2\) должна быть минимальна.

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

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

Входной файл содержит одно целое число \(n\) (\(6 \le n \le 10^9\) ).

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

Выходной файл должен содержать три целых положительных числа, разделенных пробелами: \(a\), \(b\) и \(c\) – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Пояснение к примеру

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (25 баллов)

\(n \le 50\)

Подзадача 2 (25 баллов)

\(n \le 2000\)

Подзадача 3 (25 баллов)

\(n \le 40000\)

Подзадача 4 (25 баллов)

\(n \le 10^9\)

Примеры

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

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

1 2 3

#113299

Все слова

Темы: [Комбинаторика] [Целые числа]

Вася придумал свой собственный алфавит, в котором \(N\) символов. Теперь он хочет составить c с помощью этого алфавита все слова, состоящие ровно из \(K\) букв, причём ни одно слово не может начинаться с первой буквы алфавита и не может заканчиваться на последнюю букву алфавита. Помогите Васе определить, сколько он сможет составить таких слов.

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

Входная строка содержит два числа, разделённых пробелом: число символов в алфавите \(N\) и длину слов \(K\) (\(0\) < \(N, K\) <= \(10\)).

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

Программа должна вывести единственное число - количество слов длиной \(K\) в алфавите мощностью \(N\), таких что ни одно слово не начинается с первой буквы алфавита и не заканчивается на последнюю букву алфавита.

Примеры

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

4 1

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

Страница: << 2 3 4 5 6 7 8 >> Отображать по:

Выбрано

Отменить

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