ЛШТН. 5 день

Сегодня подошел к концу первая часть первого модуля и ознаменовалась тем, что было много теории вероятности от Георгия Каспарьянца. Нас с каждой становилось все меньше и меньше. Было много теории, абстракций, а потом задачки на теорию вероятности. Ну главное, что наши участники поняли что такое вероятность и как оно вычисляется. Задач было 9, но мы справились только с 4. Надеюсь в конце школы мы сядем и разберем все нерешенные задачи.

А теперь перейдем, собственно, к решенным задачам.

Задача А. Бросок кубика. Ограничение по времени: 1 сек

Якко, Вакко и Дот, известные на весь мир анимашки, захотели отдохнуть от съёмок в мультфильмах и решили взять отпуск, чтобы немного попутешествовать. Якко мечтал поехать в Пенсильванию, свою родину и родину своих предков. Вакко склонялся к Тасмании, ее пляжам, солнцу и морю. Дот выбрала Трансильванию как самое таинственное и непредсказуемое место.

Но, к их большому сожалению, отпуск оказался таким коротким, что его хватит для посещения только одного места из трёх вышеперечисленных. Поэтому Якко, как самый умный, предложил поистине гениальную идею: пусть каждый бросит обычный шестигранный кубик, а у кого выпадет больше очков — тот и повезёт всех в место своей мечты.

Якко выбросил Y очков, Вакко — W очков. Осталась Дот. Но она не спешила. Дот хотела знать точно, с какой вероятностью ей удастся посетить Трансильванию.

Известно, что Якко и Вакко — настоящие джентльмены, поэтому, в случае равенства количества их очков и очков Дот, предпочтение отдаётся Дот.

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

В единственной строке входного файла даны два натуральных числа Y и W — результаты бросков Якко и Вакко.

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

Вывести искомую вероятность в виде несократимой дроби в формате «A/B», где A — числитель, а B — знаменатель. Если искомая вероятность равна нулю, выведите «0/1». Если искомая вероятность равна единице, выведите «1/1».

входные данные
4 2
выходные данные
1/2

Разбор:
Пусть максимум из очков Якко и Вакко — a. Тогда Дот выиграет, если выбросит не меньше a очков. Таких вариантов 6 – (а — 1). Всего различных вариантов выпадения очков -6. Тогда вероятность этого события равна (6 — (a-1)) / 6. Ответ нужно было дать в виде несократимой дроби —  это можно сделать двумя способами:

1. Так как знаменатель маленький, всего лишь 6, то можно было проверить все случаи, когда надо сокращать.
2. Можно было воспользоваться универсальным способом сокращения дробей, вычислив наибольший общий делитель (НОД) и поделив числитель и знаменатель на НОД

Тема: теория вероятности, математика

Время работы: О(1)

 

Задача B. Паша и палка. Ограничение по времени: 1 сек

У Паши есть прямая деревянная палка целой положительной длины n. Он хочет сделать ровно три распила и получить четыре куска палки целой положительной длины, суммарная длина которых, очевидно, будет равна n.

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

Перед вами стоит задача помочь Паше — посчитать количество таких способов. Два способа считаются различными, если отличаются наборы длин получившихся кусков, то есть для какой-то длины x количество палок длины x в одном способе не равно количеству палок такой же длины в другом способе.

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

В первой строке входных данных следует целое положительное число n (1 ≤ n ≤ 2·10⁹) — длина имеющейся палки.

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

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

входные данные
6
выходные данные
1
входные данные
20
выходные данные
4
Разбор:
Для начала отсечем случай, когда n нечетно. Так как периметр прямоугольника всегда четный, то ответ в таком случае 0.
Если n четно, то количество прямоугольников, которые можно составить, равно n  /  4. Если n кратно 4, то мы посчитаем и квадрат, который составлять нельзя, поэтому в таком случае из ответа нужно вычесть единицу.

Тема: математика

Время работы: О(1)

 

Задача C. Dreamoon и WiFi. Ограничение по времени: 1 сек

Dreamoon стоит на отметке 0 на числовой прямой. Drazil отправляет ему на смартфон список команд через Wi-Fi, а Dreamoon следует им.

Каждая команда относится к одному из двух типов:

1. Пройти на 1 единицу в положительном направлении, обозначается как «+»
2. Пройти на 1 единицу в отрицательном направлении, обозначается как «-»

Но так как уровень сигнала Wi-Fi очень слабый, смартфон Dreamoon’а сообщает, что некоторые команды не поддаются распознаванию. Более того, Dreamoon знает, что даже некоторые из рапознанных команд могут быть неверными. Dreamoon решил выполнять каждую распознанную команду, а для нераспознанных команд бросать монетку (это значит, что он пойдёт на 1 единицу в положительном или отрицательном направлении с одинаковой вероятностью 0.5).

Вам дан изначальный список команд, которые выслал Drazil, и список, который получил Dreamoon. Какова вероятность того, что Dreamoon окажется в том положении, к которому привели бы команды Drazil’а?

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

В первой строке записана строка s1 — команды, которые Drazil посылает Dreamoon’у, строка состоит только из символов из набора {«+», «-»}.

Во второй строке записана строка s2 — команды, которые распознал смартфон Dreamoon’а, эта строка состоит только из символов из набора: {«+», «-», «?»}. Символом «?» обозначается нераспознанная команда.

Обе строки одинаковой длины и не превышают 10.

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

Выведите требуемую вероятность. Ответ будет сраниваться с относительной или абсолютной погрешностью 10 ^-9.

входные данные
++-+-
+-+-+
выходные данные
1.000000000000
входные данные
+-+-
+-??
выходные данные
0.500000000000
входные данные
+++
??-
выходные данные
0.000000000000

Разбор:
Чтобы посчитать вероятность, нам нужно вычислить две величины: m – число благоприятных событий, n – число всевозможных событий.
Начнем с вычисления n. Так как нам надо вместо вопросов подставлять либо минус, либо плюс, то всевозможных случаев сформировать строку будет 2 в степени количество вопросов.
Чтобы вычислить m, то есть количество путей, которые приведут нас в ту же точку, что и первый путь, нам надо посчитать, сколько плюсов и сколько минусов надо поставить вместо вопросов. Заметим, что порядок того сначала мы назад пойдем, потом вперед и наоборот приведут к одной точке. Следовательно, посчитаем, сколько минусов и плюсов нам надо поставить вместо вопросов. Это можно сделать просто, посчитав в первой строке и во второй строке количество минусов и плюсов и от первого отнять второе. Если мы получили отрицательное количество минусов или плюсов, то ответ 0. Иначе считаем количество благоприятных путей. Пусть у нас n вопрос, a – плюсов, b – минусов. Тогда всевозможных перестановок в n местах равно n! , но среди них будут повторять и минусы и плюсы, чтобы убрать повтор, необходимо n!/ (a! * b!) .
Когда нашли обе величины, просто поделим одно на другое и выведем ответ.

Тема: теория вероятности, математика, комбинаторика

Время работы: О(n)

Задача D. Лучники. Ограничение по времени: 1 сек

SmallR — лучница. SmallR соревнуется с лучником Zanoes. Они оба будут стрелять в мишень по очереди, SmallR стреляет первой. Вероятность попасть в цель каждый раз равняется a / b для SmallR и  c / d для Zanoes. Тот, кто попадет в цель первым, будет победителем.
Выведите вероятность того, что SmallR выиграет.

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

Единственная строка содержит четыре целых числа a, b, c, d (1 <= a, b, c, d <= 1000, 0 < a / b < 1.0 < c / d < 1).

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

Выведите единственное вещественное число — вероятность того, что SmallR выиграет матч.

Ответ будет считаться правильным, если абсолютная или относительная погрешность не превышает 10 ^-6.

входные данные
1 2 1 2
выходные данные
0.666666666667

Разбор:
Опять воспользуемся формулой вероятности p = m / n.
m = a / b , так для нас благоприятно чтобы выиграл первый.
n = 1 – (1 – a / b) * (1 – c / d).
Поясним что есть что. (1 – a / b) – вероятность того, что первый не попал.
(1 – c / d) – вероятность того, что второй не попал.
1 – (1 – a / b) * (1 – c / d) – вероятность того, что хотя бы кто то попал, так как 1 – это вероятность достоверного события.

Тема: теория вероятности, математика
Время работы: О(n)