Contest.uni-smr.ac.ru :: Programming contests in Samara
Русская версия || English version
Login:
Password:
Forget password?
 example: Bill Gates
 






Задача С. Тринадцатый сектор.

Задачу добавил: DK

Успешно сдано решений: 20

В игре "Что?Где?Когда?" для определения вопроса используют волчок на круглом столе. Мы будем считать, что волчок абсолютно честный, так что вероятность того, что он укажет на некоторый сектор равна 1/13. Известно, что знатоки недолюбливают тринадцатый сектор. Требуется определить вероятности розыгрыша вопроса из 13-го сектора после 1-го, 2-го, ..., j-го, ... 13-го запуска волчка в текущей игре.

Примечание. Как выбирают вопрос в "Что?Где?Когда?".
Знатоки сидят за круглым столом, который поделен на 13 секторов, в каждом из которых первоначально лежит вопрос. Сыгравшие вопросы удаляются из секторов. Сектора занумерованы от 1 до 13 по часовой стрелке.
Волчок раскручивают и отпускают. Когда он останавливается и указывает на один из секторов, сектор считается выпавшим. Далее возможны следующие варианты:
1. В секторе есть (неразыгранный) вопрос. В этом случае разыгрывается именно этот вопрос.
2. В секторе нет вопроса. В этом случае по часовой стрелке, начиная со следующего за выпавшим, просматриваются подряд все сектора до тех пор, пока в каком-либо секторе не встретится неразыгранный вопрос. Этот вопрос и будет разыгран. Так, например, если в примере 1 волчок укажет на 5, будет разыгран 8-ой вопрос.

 

Входной файл.
Первая строка - целое неотрицательное число n <= 12.
Вторая строка содержит номера сыгранных вопросов - n различных целых чисел в диапазоне от 1 до 12.

 

Выходной файл.
Первая строка - числа p1, p2, ..., pj, ..., p13 через пробел - вероятности того, что 13 сектор будет разыгран в точности после j-го запуска волчка. Каждое из чисел pj (j = 1, 2, ..., 13) должно быть представлено в виде несократимой дроби в формате "числитель/знаменатель". Если соотвествующая вероятность равна нулю или запуска волчка не будет, следует вывести 0/1.

 

Пример 1.

input.txt:
10
1 2 4 5 6 7 9 10 11 12

output.txt:
5/13 5/13 3/13 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

 

Пример 2.

input.txt:
9
1 2 5 6 7 9 10 11 12

output.txt:
5/13 56/169 381/2197 243/2197 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

 

Пример 3.

input.txt:
0

output.txt:
1/13 1/13 1/13 1/13 1/13 1/13 1/13 1/13 1/13 1/13 1/13 1/13 1/13

 

Пример 4.

input.txt:
1
12

output.txt:
2/13 23/169 264/2197 3024/28561 34560/371293 393984/4826809 4478976/62748517 50761728/815730721 573308928/10604499373 6449725440/137858491849 72236924928/1792160394037 61917364224/1792160394037 0/1

 

Подсказка:
Разъясним пример 1.
С вероятностью 5/13 сразу выпадет 13-ый сектор (9,10,11,12 и 13 положения волчка)
С вероятностью 3/13*5/13 {если выпадут 1,2 или 3, а затем 9,10,11,12 или 13} + 5/13 * 10/13 {если выпадут 4,5,6,7 или 8, а затем от 4-го до 13} = 65/169=5/13 он выпадет на второе вращение
В оставшихся 3/13 случаях он выпадет на 3-е вращение, поскольку осталось всего 3 сектора.
По примеру 4. Неужели вы не поделили в уме предпоследнее число? Оно порядка 0,035 :). Надеемся, Вася сам напишет программу, которая будет приводить эти числа в удобоваримый формат :)

Submit

Задать вопрос жюри по этой задаче