Comments 62
Про пиратов: 61.
2 * 3 * 4 * 5 * 6 + 1.
Сокращаем лишние простые множители, остаются 3 * 4 * 5 + 1
2 * 3 * 4 * 5 * 6 + 1.
Сокращаем лишние простые множители, остаются 3 * 4 * 5 + 1
Про монеты — 75%
Про пиратов — 7*7 = 49 (нам нужен множитель к семёрке, но не ниже 7-ки же, т.к. мы знаем, что результат не делился на [2..6]).
Про монеты — 50/50. По сути у нас спросили является ли монета поддельной.
Про монеты — 50/50. По сути у нас спросили является ли монета поддельной.
Остаток от деления 49 на 5 — 4, а у нас по условию всегда остаётся лишней только 1 монета
1. Не подходит, так как когда их было 5 у них остался 1! камень, а при 49 осталось бы 4.
49 не соответствует условию 5n+1
С вероятностью 0,5 согласен, но считаю что надо смотреть с точки зрения условной вероятности.
Р(2-я решка)= P(фальшивая монета)*Р(решка на фальшивой монете) = 0.5*1=0.5
С вероятностью 0,5 согласен, но считаю что надо смотреть с точки зрения условной вероятности.
Р(2-я решка)= P(фальшивая монета)*Р(решка на фальшивой монете) = 0.5*1=0.5
А какова, по вашему, будет вероятность того, что внизу решка, если сверху орёл? Тоже 50%? Ведь по сути это вопрос о том, является ли монета настоящей…
Про монеты: был неправ. Ответ: 2/3. jsfiddle.net/shdqse5z/6
Если target = 14 и k = 3, тогда выход должен быть “4 20”.
Разве не 12 и 20?
Разве не 7 камней у пиратов?)
Про пиратов — 2/3.
Вопрос 1
Поскольку для 2, 3, 4, 5 и 6 пиратов оставался один камень, то значит необходимо найти число вида НОК(2, 3, 4, 5, 6)*n+1 = 60*n+1, нацело делящееся на 7.
Признак делимости на 7 — число без последней цифры минус удвоенная последняя цифра делится на 7. Последняя цифра всегда 1, получаем что 6*n-2 должно делиться на 7. Ближайшее n = 5, значит число камней 60*5+1 = 301.
Признак делимости на 7 — число без последней цифры минус удвоенная последняя цифра делится на 7. Последняя цифра всегда 1, получаем что 6*n-2 должно делиться на 7. Ближайшее n = 5, значит число камней 60*5+1 = 301.
Вопрос 2
Всего у нас есть 4 варианта развития событий:
1 — взята фальшивая монета, выложена первой решкой вверх;
2 — взята фальшивая монета, выложена второй решкой вверх;
3 — взята настоящая монета, выложена решкой вверх;
4 — взята настоящая монета, выложена орлом вверх;
Поскольку мы видим, что наверху решка, то остаются только варианты 1, 2 и 3. Из этих вариантов решка внизу в двух, то есть с вероятностью 2/3.
1 — взята фальшивая монета, выложена первой решкой вверх;
2 — взята фальшивая монета, выложена второй решкой вверх;
3 — взята настоящая монета, выложена решкой вверх;
4 — взята настоящая монета, выложена орлом вверх;
Поскольку мы видим, что наверху решка, то остаются только варианты 1, 2 и 3. Из этих вариантов решка внизу в двух, то есть с вероятностью 2/3.
про камни и пиратов у меня получилось 189 хз почему =)
про монеты 50% шанс )
про монеты 50% шанс )
От задач по терверу нужно отказаться, как когда-то отказались от логических задач, потому что ответ может меняться значительно от положения фразы "какова вероятность, что" в постановке задачи. В данном случае ответ 50%, потому что монеты всего две, выбираются они равновероятно, а значит две решки появятся только в половине случаев. Но вот если спросить иначе: какова вероятность, что после случайного выбора и подбрасывания будет решка с обоих сторон, от ответ уже получится другой.
В последнем предложении написал ерунду, но мысль должна быть понятна — переформулировав задачу, можно получить правильный ответ, отличный от "50%".
Всё зависит от того, из чего формируется множество элементарных исходов. Допустим, мы равновероятно выбираем монету. Если после подбрасывания выпал орёл, то такой исход мы не считаем, а во всех остальных — считаем. Тогда у "неправильной" монеты больше шансов попасть в выборку, а значит и шанс получить решку после переворота не 50%. Но если нам ничего не известно про возможные выпадения орла, то всё таки шанс остаётся 50%.
Здесь в задаче два выбора — равновероятный выбор одной из двух монет и равновероятный выбор положения монеты. Они дают нам четыре равновероятных исхода. Один из этих исходов (настоящая монета орлом вверх) отсеивается условием. Остаётся три, из них только два с решкой внизу. 2/3.
Пираты —
Ещё Евклид считал очевидным, что с помощью умножения только простых чисел можно получить все натуральные числа, причем каждое натуральное число представимо в виде произведения простых чисел единственным образом. Поэтому искомое число камней состоит из числа 7(НОД) и ещё какого-то числа Dimonds_X
При этом Dimonds_X не делится ни на 2 ни на 3 ни 5. То есть оно состоит из простых чисел >= 7. Фактически поиск таких чисел это задача факторизации, т.е. требуется пробовать и проверять. Поскольку нужно минимальное, предположим что оно состоит из 1 простого сомножителя. И оно будет минимально до тех пор, пока искомый простой сомножитель не превысит 47 ( максимальное простое число меньшее чем 7*7 = 49, а это в свою очередь минимальное число состоящее их 2х простых чисел, которые оба >=7, напомню, что числа с 2 по 5 не подходят)
Перебираем простые числа от 7 до 47 и проверяем на калькуляторе.
Суть проверки, поскольку у тех ребят всё время оставался один камень, то 7*Dimonds_X — 1 должно делиться на 2(дважды) 3 и 5. Поскольку числа кратные 5 будут встречаться реже(их просто меньше) пусть это будет первый маркер.
7*7 -> 48 fail
7*11-1 -> 76 fail
7*13-1 -> 90 win? нет fail потому что не делится на 4.
Перебирая подобным незамысловатым способом остальне простые числа в диапазоне 7 до 47
неожиданно наткнулся насундук с пиастрами на число 43. 43*7-1 -> 300 то есть общее число камней которое полностью удовлетворяет условию задачи 301
Ещё Евклид считал очевидным, что с помощью умножения только простых чисел можно получить все натуральные числа, причем каждое натуральное число представимо в виде произведения простых чисел единственным образом. Поэтому искомое число камней состоит из числа 7(НОД) и ещё какого-то числа Dimonds_X
При этом Dimonds_X не делится ни на 2 ни на 3 ни 5. То есть оно состоит из простых чисел >= 7. Фактически поиск таких чисел это задача факторизации, т.е. требуется пробовать и проверять. Поскольку нужно минимальное, предположим что оно состоит из 1 простого сомножителя. И оно будет минимально до тех пор, пока искомый простой сомножитель не превысит 47 ( максимальное простое число меньшее чем 7*7 = 49, а это в свою очередь минимальное число состоящее их 2х простых чисел, которые оба >=7, напомню, что числа с 2 по 5 не подходят)
Перебираем простые числа от 7 до 47 и проверяем на калькуляторе.
Суть проверки, поскольку у тех ребят всё время оставался один камень, то 7*Dimonds_X — 1 должно делиться на 2(дважды) 3 и 5. Поскольку числа кратные 5 будут встречаться реже(их просто меньше) пусть это будет первый маркер.
7*7 -> 48 fail
7*11-1 -> 76 fail
7*13-1 -> 90 win? нет fail потому что не делится на 4.
Перебирая подобным незамысловатым способом остальне простые числа в диапазоне 7 до 47
неожиданно наткнулся на
перебор можно было упростить, если заметить, что остаток от деления на 5 дает 1, а значит число должно заканчиваться на 1 (6-ку естественно отбрасываем), а значит число, на которое нужно умножить 7 должно оканчиваться на 3, тогда в перебор войдут только числа 13, 23 и 43
Можно проще: чтобы выполнить первое условие, необходимо
Х % НОК(2,3,4,5,6) == 1 (%-остаток от деления, НОК(2,3,4,5,6)==60)
итого Х = 60n +1.
Заметив, что 60 % 7 = 4, ищем число вида
4+4+...+4+1 = 7n
А найдя, заменяем все 4+4+… на 60+60+..., и получаем 301
Х % НОК(2,3,4,5,6) == 1 (%-остаток от деления, НОК(2,3,4,5,6)==60)
итого Х = 60n +1.
Заметив, что 60 % 7 = 4, ищем число вида
4+4+...+4+1 = 7n
А найдя, заменяем все 4+4+… на 60+60+..., и получаем 301
Монета — ответ 50% неверный.
Такой вариант не учитывает того, что мы уже произвели одно испытание и имеем некоторую информацию на этот счёт и в то же время наши знания на этот счёт ограничены. О чём я?
Всего у нас имеется 4 стороны монет(2 одной и 2 другой), для ясности проименуем их
a b c d/ из них a орёл, а остальные решки.
после испытания мы видим одну из b c d но не знаем которая из них. И нет никаких запретов на то, чтобы на противоположной стороне оказалась a либо две любые из b c d
иными словами, образно выражаясь, в мешке есть один орёл и две решки с равной вероятностью. Следовательно, вероятность того что на той стороне тоже решка — 2/3
Такой вариант не учитывает того, что мы уже произвели одно испытание и имеем некоторую информацию на этот счёт и в то же время наши знания на этот счёт ограничены. О чём я?
Всего у нас имеется 4 стороны монет(2 одной и 2 другой), для ясности проименуем их
a b c d/ из них a орёл, а остальные решки.
после испытания мы видим одну из b c d но не знаем которая из них. И нет никаких запретов на то, чтобы на противоположной стороне оказалась a либо две любые из b c d
иными словами, образно выражаясь, в мешке есть один орёл и две решки с равной вероятностью. Следовательно, вероятность того что на той стороне тоже решка — 2/3
Как раз-таки 50% — верный ответ.
Раз уж мы уже видим решку, то варианта возможно только 2 (и вероятность у них одинаковая): выбранная монета или «настоящая» или фальшивая. И этим определяется содержимое обратной стороны (т.е. 50/50). Если бы речь шла о нескольких случаях бросания монет и вероятностях тех или иных событий, то определенно вероятности могли бы быть иными. Но для отдельного определенного случая с фактическим раскладом «решка» вверху — есть только два (равнозначных) варианта.
Раз уж мы уже видим решку, то варианта возможно только 2 (и вероятность у них одинаковая): выбранная монета или «настоящая» или фальшивая. И этим определяется содержимое обратной стороны (т.е. 50/50). Если бы речь шла о нескольких случаях бросания монет и вероятностях тех или иных событий, то определенно вероятности могли бы быть иными. Но для отдельного определенного случая с фактическим раскладом «решка» вверху — есть только два (равнозначных) варианта.
Нет, мы видим либо первую решку фальшивой монеты, либо вторую её решку, либо решку настоящей монеты.
Всего вариантов может быть 2, т.к. монет только 2. Либо окажется что это правильная монета, либо фальшивая. Если вариантов исхода 2 то и ответ 1/2.
Вы забыли, что кроме выбора монет было и второе действие — выбор стороны.
Выбора монет не было. Мы не подкидываем монеты 2 раза. Мы не считаем количество разных подбросов чтобы получить текущую ситуацию. По условию мы имеем уже подброшенную монету и уже видим решку и от этого отталкиваемся. Нам осталось лишь перевернуть и увидеть что на обратной стороне.
Чтобы посчитать вероятность нужно знать количество возможных исходов, а исходов у нас может быть только 2, потому что мы уже подбросили какую-то монету и мы уже знаем что выпала решка, и когда мы перевернем монету там будет либо решка либо орел.
Чтобы посчитать вероятность нужно знать количество возможных исходов, а исходов у нас может быть только 2, потому что мы уже подбросили какую-то монету и мы уже знаем что выпала решка, и когда мы перевернем монету там будет либо решка либо орел.
Первый выбор — выбор монеты. Мы можем выбрать либо фальшивую (Ф), либо настоящую (Н). Выбор равновероятен.
Второй выбор — выбор стороны, он тоже равновероятен. В случае Ф мы можем выбрать либо одну решку (ФР1), либо вторую (ФР2). В случае Н — либо решку (НР), либо орла (НО).
Таким образом до получения информации имеем четыре равновероятных исхода — ФР1, ФР2, НР, НО. Открыв глаза видим, что сверху решка, значит исход НО не выпал. Остаются три варианта, в двух из которых снизу вторая решка.
Второй выбор — выбор стороны, он тоже равновероятен. В случае Ф мы можем выбрать либо одну решку (ФР1), либо вторую (ФР2). В случае Н — либо решку (НР), либо орла (НО).
Таким образом до получения информации имеем четыре равновероятных исхода — ФР1, ФР2, НР, НО. Открыв глаза видим, что сверху решка, значит исход НО не выпал. Остаются три варианта, в двух из которых снизу вторая решка.
Я понял Вашу мысль :)
Но мне все-таки кажется, что независимо от того какая именно сторона выпала в случае с фальшивой монетой, это не влияет на исход, т.е. не важно для нас.
Давайте подождем ответы от автора статьи. Думаю кто-то из нас сильно удивиться :)
Но мне все-таки кажется, что независимо от того какая именно сторона выпала в случае с фальшивой монетой, это не влияет на исход, т.е. не важно для нас.
Давайте подождем ответы от автора статьи. Думаю кто-то из нас сильно удивиться :)
Думаю я оказался не прав)
Я решил практическим путем проверить и накидал код: cpp.sh/8ibyj
У меня получается 1/3 в ответе. Я где-то допустил ошибку?
Я решил практическим путем проверить и накидал код: cpp.sh/8ibyj
У меня получается 1/3 в ответе. Я где-то допустил ошибку?
Вторая задача = 2/3. Классическая задача на теорему Байеса.
Байес вас бы в угол поставил.
Выбирается монета. Одна из двух. Решка вверху по условию задачи. Всё, выбора больше нет.
Выбирается монета. Одна из двух. Решка вверху по условию задачи. Всё, выбора больше нет.
События H1 и H2 — соответственно выбор первой и второй монеты. Их вероятности(априорные) P(H1) и P(Н2) по условию равны 0,5. Событие A — появление решка. Условные вероятности события A равны P(A/Н1) = 1(если выбрана первая монета) и P(A/Н2) = 0,5(если выбрана вторая монета). Событие А произошло, необходимо пересчитать априорную вероятность выбора первой монеты. По формуле Байеса находим = 0,5 * 1 / (0,5 * 1 + 0,5 * 0,5) = 0,67 (или 2/3)
Байес в чистом виде)) в одно действие
Байес в чистом виде)) в одно действие
Даже не близко. Решка вверху — это условие задачи, заданное ещё до того, как я выбрал монету. Если я выбрал качественную монету, то обратная сторона гарантированно не решка. Если выбрал бракованную — обратная сторона гарантированно тоже решка.
Неправильно. Задача не в том, чтобы найти вероятность выпадение решки. А именно найти вероятность, что выбранная монета неправильная!!! При условии что мы видим решку. Повторюсь, это чисто Байесовская схема и постановка задачи. Т.е. сначала выбор монеты(гипотезы), потом результат(событие) и по результату пересчитать вероятность гипотезы.
Уточню. Задача не в том, чтобы найти вероятность выпадение первой решки.
Чтобы понять суть вышесказанного, попробуйте решить немного усложненный вариант этой задачи. У вас на столе N правильных монет и M неправильных монет. Наугад, с закрытыми глазами выбираете одну. Подбрасываете ее K раз, и ровно K раз выпадает решка. Найти вероятность, что и в K+1 раз тоже выпадет решка.
Задача не в том, чтобы найти вероятность выпадение решки. А именно найти вероятность, что выбранная монета неправильная!!!
Вероятность, что выбранная монета неправильная, равна 1/2 независимо от того, какую сторону мы видим.
В том то и дело, что нет. Это понятно даже интуитивно. Изначально вероятность правильной и неправильной монеты одинакова и равна 0.5. Но по мере того, как мы выбрасываем решки наша убежденность(вероятность) в том что у нас в руках именно неправильная монета растет с каждой решкой. Представьте что вы выбросили 100 решек подряд, неужели вы будете по прежнему думать что вероятности правильной и неправильной монеты равны 0.5 ???? В этом и состоит суть Байеса. После поступившей новой информации(произошедшего события, в данном случае выпадения решки) мы пересчитываем исходную вероятность гипотезы(выбор неправильной монеты). После первой выпавшей решки изначальная вероятность неправильной монеты увеличивается с 0.5 до 0.67. и дальше по мере выпадения решек она будет стремится к 1. Я поэтому и предложил немного другой вариант задачи, чтобы понять суть этого метода. Исходная задача достаточно простая и ее можно решить в лоб, не прибегая к Байесу. Но если обобщить, то надо уже с Б.
Про камни — условие делится на пять с остатком 1 соотв. только числа с окончанием на 6 (не подходит т.к. четное и 1), смотрим числа с 1 которые делятся на 7 = 21 + 7*10*nб если еще учесть остаток о деления на 3, то = 91 + 7*3*10*n, первое число такое 301
Про монеты вероятность выкинуть правильную монету решкой вверх = 25%, для неправильной 50%, т.о. вероятность при перевороте получить решку = 2/3
Про монеты вероятность выкинуть правильную монету решкой вверх = 25%, для неправильной 50%, т.о. вероятность при перевороте получить решку = 2/3
Задача 1
for (int i = 0; i<1000; i++)
{
if (i%2==1&&i%3==1&&i%4==1&&i%5==1&&i%6==1&&i%7==0&&)
{
cout<<«Значение i»<<i;
}
}
ответ 301
{
if (i%2==1&&i%3==1&&i%4==1&&i%5==1&&i%6==1&&i%7==0&&)
{
cout<<«Значение i»<<i;
}
}
ответ 301
Задача 2
Всего три решки и один орел, при выпадении решки на другой стороне остается две решки и орел, следовательно вероятность 2/3
Монеты
Мы имеем всего два варианта на старте:
1) Выпала монета орел-решка.
2) Выпала монета решка-решка.
Верхнюю решку можно не считать — это уже данность.
Таким образом, вероятность того что это монета решка-решка 50%.
Если добавить в условия еще одну монету решка-решка:
1) Выпала монета орел-решка.
2) Выпала монета1 решка-решка.
3) Выпала монета2 решка-решка.
Вот так уже вероятность обнаружения решки будет 2/3.
В двух случаях из трех мы найдем под решкой еще одну решку.
Иными словами, условие что мы на старте уже видим решку исключает ее из нашего расчета вероятности. Это уже свершившийся факт и нужно считать только те варианты, которые могут быть на скрытой стороне монеты.
Мы имеем всего два варианта на старте:
1) Выпала монета орел-решка.
2) Выпала монета решка-решка.
Верхнюю решку можно не считать — это уже данность.
Таким образом, вероятность того что это монета решка-решка 50%.
Если добавить в условия еще одну монету решка-решка:
1) Выпала монета орел-решка.
2) Выпала монета1 решка-решка.
3) Выпала монета2 решка-решка.
Вот так уже вероятность обнаружения решки будет 2/3.
В двух случаях из трех мы найдем под решкой еще одну решку.
Иными словами, условие что мы на старте уже видим решку исключает ее из нашего расчета вероятности. Это уже свершившийся факт и нужно считать только те варианты, которые могут быть на скрытой стороне монеты.
В условиях задачи 1 указано неверное бинарное дерево
10 > 8, но при этом находится слева от узла 8.
20
/ \
8 22
/ \
4 12
/ \
10 14
10 > 8, но при этом находится слева от узла 8.
Спасибо, принято.
Зря. В задаче написано binary tree, а CakeOfChaos говорит о binary search tree.
Первое: берем условно-рандомное число, чтобы понять, что к чему.
Выбираем 49 из логики, что множитель больше 6. При переборе получаем, что не подходит 5. Наводит на мысль, что это число имеет форму или *6 или *1, чтобы удовлетворить 5. Отсекаем вариант с *6, потому что оно будет кратно 2.
Имеем, что число должно быть в формате *1. В силу того, что при умножении 7 на числа [0..9] только один вариант дает на конце единицу (7*3=21). Перебираем множители: n*10+3.
7*13 = 91 [91 % 4 = 3]
7*23 = 161 [161 % 3 = 2]
7*33 = 231 [число 33 само по себе делится на 3]
7*43 = 301 — бинго.
Ответ: 301.
Выбираем 49 из логики, что множитель больше 6. При переборе получаем, что не подходит 5. Наводит на мысль, что это число имеет форму или *6 или *1, чтобы удовлетворить 5. Отсекаем вариант с *6, потому что оно будет кратно 2.
Имеем, что число должно быть в формате *1. В силу того, что при умножении 7 на числа [0..9] только один вариант дает на конце единицу (7*3=21). Перебираем множители: n*10+3.
7*13 = 91 [91 % 4 = 3]
7*23 = 161 [161 % 3 = 2]
7*33 = 231 [число 33 само по себе делится на 3]
7*43 = 301 — бинго.
Ответ: 301.
1
Могло быть 301, а могло бы быть 721. Число делящееся на 2-6 это сразу 60 (даже считать не надо, т.к. количество минут в часах — все знают что на эти числа можно разделить) Далее подойдёт любое число вида 60*n+1, если делится на 7. Последняя цифра всегда один, потому ищем по признаку делимости такое 6*n-2, которое делится на 7. Проще всего перебором 14*n+2, которые делятся на 6 (14, потому что 6*n-2 гарантировано чётное). Сходу 301, 721, 1981
2
2/3 же…
1 Задача
Поиск в ширину. Всё, больше ничего не надо.
2 задача
Поразмыслив, я решил что дифференциально узнать выгоду невозможно. Понятно, что если t_i,j + S_(i+1),(j+1) + t_(i+1),(j+1) < S_i,(j+1), то S_i,(j+1) следует исключить из графа прохождения. Точно также для любой последовательности где SUM_(j_0<j<j_0+k) (S_(i+1),j) + t_i,(j_0) + t_(i+1),(j_0+n+1) < SUM_(j_0<j<j_0+k) ((S_i,j))
Если исключить такие последовательности, то для оставшихся нод нужно ввести перебор с конца линии к началу.
Если исключить такие последовательности, то для оставшихся нод нужно ввести перебор с конца линии к началу.
3
Отвечу картинкой с диаграммой прохождения по числам
зелёная — движение курсора от начала таблицы,
красная — линия, на которой курсор понимает что число больше искомого,
голубая — линия, на которой курсор понимает что число меньше искомого,
оранжевая точка — искомое число.
зелёная — движение курсора от начала таблицы,
красная — линия, на которой курсор понимает что число больше искомого,
голубая — линия, на которой курсор понимает что число меньше искомого,
оранжевая точка — искомое число.
что то не понял вторую задачу, если
то выгоднее пустить по обоим сборочным линиям две ( 2 * n ?) машин делая паралельно одно и то же?
Параллельные станции на обеих сборочных линиях выполняют одинаковую задачу.
то выгоднее пустить по обоим сборочным линиям две ( 2 * n ?) машин делая паралельно одно и то же?
Sign up to leave a comment.
Выпуск#18: ITренировка — актуальные вопросы и задачи от ведущих компаний