Сегодня подошел к концу первая часть первого модуля и ознаменовалась тем, что было много теории вероятности от Георгия Каспарьянца. Нас с каждой становилось все меньше и меньше. Было много теории, абстракций, а потом задачки на теорию вероятности. Ну главное, что наши участники поняли что такое вероятность и как оно вычисляется. Задач было 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. Ответ нужно было дать в виде несократимой дроби — это можно сделать двумя способами:
- Так как знаменатель маленький, всего лишь 6, то можно было проверить все случаи, когда надо сокращать.
- Можно было воспользоваться универсальным способом сокращения дробей, вычислив наибольший общий делитель (НОД) и поделив числитель и знаменатель на НОД
Тема: теория вероятности, математика
Время работы: О(1)
Задача B. Паша и палка. Ограничение по времени: 1 сек
У Паши есть прямая деревянная палка целой положительной длины n. Он хочет сделать ровно три распила и получить четыре куска палки целой положительной длины, суммарная длина которых, очевидно, будет равна n.
Паша любит прямоугольники, но в то же время очень не любит квадраты, поэтому хочет знать, сколько существует способов разрезать палку на четыре части таким образом, чтобы из получившихся кусков палки можно было сложить какой-нибудь прямоугольник, но нельзя было сложить квадрат.
Перед вами стоит задача помочь Паше — посчитать количество таких способов. Два способа считаются различными, если отличаются наборы длин получившихся кусков, то есть для какой-то длины x количество палок длины x в одном способе не равно количеству палок такой же длины в другом способе.
Входные данные
В первой строке входных данных следует целое положительное число n (1 ≤ n ≤ 2·109) — длина имеющейся палки.
Выходные данные
Выведите в первую строку выходных данных единственное целое число — количество способов разделить Пашину палку на четыре части ненулевой длины таким образом, чтобы можно было соединить концы получившихся частей и получить прямоугольник, но не квадрат.
входные данные
6
выходные данные
1
входные данные
20
выходные данные
4
Разбор:
Для начала отсечем случай, когда n нечетно. Так как периметр прямоугольника всегда четный, то ответ в таком случае 0.
Если n четно, то количество прямоугольников, которые можно составить, равно n / 4. Если n кратно 4, то мы посчитаем и квадрат, который составлять нельзя, поэтому в таком случае из ответа нужно вычесть единицу.
Тема: математика
Время работы: О(1)
Задача C. Dreamoon и WiFi. Ограничение по времени: 1 сек
Dreamoon стоит на отметке 0 на числовой прямой. Drazil отправляет ему на смартфон список команд через Wi-Fi, а Dreamoon следует им.
Каждая команда относится к одному из двух типов:
- Пройти на 1 единицу в положительном направлении, обозначается как «+»
- Пройти на 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)
Arthurfep
https://clck.ru/EtfqU — футболки самбо
Интернет магазин уникальных футболок. Мы предлагаем Вам только качественные и уникальные товары. На Ваш выбор толстовки, футболки, головные уборы, чехлы, посуда, аксессуары и вещи для интерьера.
Вы с легкостью сможете подобрать рисунок, который Вам нравится или же сделать свой уникальный с помощью конструктора.
Приобретя товр Вы можете воспользоваться услугами доставки на очень выгодных условиях.
Заходи и заказывай:
http://supermayki-ok.ru — Шапка
Arthurfep
https://clck.ru/EtfqU — женская футболка супермен
Интернет магазин уникальных футболок. Мы предлагаем Вам только качественные и уникальные товары. На Ваш выбор толстовки, футболки, головные уборы, чехлы, посуда, аксессуары и вещи для интерьера.
Вы с легкостью сможете подобрать рисунок, который Вам нравится или же сделать свой уникальный с помощью конструктора.
Приобретя товр Вы можете воспользоваться услугами доставки на очень выгодных условиях.
Заходи и заказывай:
http://supermayki-ok.ru — Шорты и брюки
Charleswab
http://bit.do/eJvLZ — пояс для похудения и коррекции фигуры
Единственный аксессуар, который может уменьшить размер талии на двенадцать сантиметров
всего за две секунды. А если носить Xtreme Power Belt регулярно,
то можно легко избаваться от лишнег жира на животе!
Charleswab
http://bit.do/eJvLZ — Extreme Power Belt — пояс для похудения и коррекции фигуры
Единственный аксессуар, который может уменьшить размер талии на двенадцать сантиметров
всего за две секунды. А если носить Xtreme Power Belt регулярно,
то можно легко избаваться от лишнег жира на животе!
Charleswab
http://bit.do/eJvLZ — Extreme Power Belt
Единственный аксессуар, который может уменьшить размер талии на двенадцать сантиметров
всего за две секунды. А если носить Xtreme Power Belt регулярно,
то можно легко избаваться от лишнег жира на животе!
JeremyPom
https://clck.ru/F7nBP — Держатель для смартфона с функцией беспроводной зарядки
Уникальный автомобильный держатель для смартфона с беспроводной зарядкой.
Устройство надежно крепится в салоне авто благодаря двойной фиксации.
Автоматически заряжает смартфон, когда вы в пути.