Задача С. Тринадцатый сектор.
Задачу добавил: 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 :). Надеемся, Вася сам напишет программу, которая будет приводить эти числа в удобоваримый формат :)