Comments on Алёна C++: Пост Get that job at Google

Читал, читал, устал, у каждого свое мнение, не зна...

2009-06-10T23:50:05.402+04:00

Читал, читал, устал, у каждого свое мнение, не знаю дал кто то правильный ответ или нет. Но насчет ответа по поводу 240 бочек. Возьмем первые 24 часа. Пусть вне зависимости от того когда кто выпьет, умрет раб на 24 часу. На каждого раба по 48 бочек(группа1). пусть в какой то группе есть бочка с ядом. По идеи кто то должен умереть. остальные откидываем. в первые же 24 часа, в той группе где приблизительно есть яд - 48 бочек( группа 2) остаются на оставшихся 4 рабов. на каждого по 12 бочек. Кто то из этой группы умирает, остальные откидываем, остается 3 раба на 12 бочек. А они все пьют и пьют, откуда такое здоровье. Из этих же 12 бочек в первый день выпивает каждый оставшийся (осталось 3 раба) по 4 бочки. Остается 2 раба. которые ждут следующего дня. по истечение первых суток у нас есть 4 бочки. вот эти 4 бочки распределяются между рабами в следующем порядке. 1 бочку выпивает 1 раб, 2 бочку выпивает 2 раб, 3 бочку выпивает 1 и 2 раб. 4 бочку никто. После окончания второго дня и узнаем остался кто то жить или нет.
Меня лично к этому ответу привели мысли всех вас. У каждого свое мнение, объединивши их месте получился результат. Спасибо за совместный разум.

Общее количество бочек 240

Первые 24 часа выпивает каждый раб из каждой подгруппы

1 группа 48 48 48 48 48 48 240/5
2 группа 12 12 12 12 12 12 48/4
3 группа 4 4 4 4 4 4 12/3

Получается каждый раб выпьет из 64 бочек и умрет максимум 3 раба,

Остало четыре

1 раб – 1 бочка
2 раб – 2 бочка
1,2 рабы – 3 бочка
Не тронутая 4 бочка

Зависит кто то умрет или нет вот и узнаем кто будет жить а кто не будет

Не читал верхние комменты, честно :) Всего за перв...

2009-01-08T16:45:00.000+03:00

Не читал верхние комменты, честно :) Всего за первую проверку количество бочек можно разбить на 2^5 = 32 группы. Осталось определить, сколько бочек находится в каждой группе. 1 группа с 0 рабами - максимум 2^5 = 32, 5 групп с 1 рабом - 2^4 = 16, 10 групп с 2 рабами - 2^3 = 8, 10 групп с 3 рабами - 2^2 = 4, 5 групп с 4 рабами - 2^1 = 2, 1 группа с 5 рабами - 2^0 = 1. Итого выходит возможное количество проверяемых бочек = 243 > 240. Если не задействовать группы по 4 и 5 рабов - получается 240.

букву е не надо я описалсяА Б В Г Д Ж З И

2008-09-05T15:50:00.000+04:00

букву е не надо я описался
А Б В Г Д Ж З И

Ответ! Тк в условии сказано что смерть настает в т...

2008-09-05T15:49:00.001+04:00

Ответ! Тк в условии сказано что смерть настает в течении 24 часов и то что через 48 часов бал,
а всего 5 рабочих чтоб проверить бочки,нужно понять и двигаться от обратного.
Те кароль узнал что смерть приходит в течении 24 часов от одного из рабов,
те 72 часа до бала у него после поимки вора было 6 рабов,за 48 часов осталось 5 рабов и всего 40 бочек,за 24 часа осталось 4 раба и 8 бочек.
далее идет лог формула,допустим,назавер рабов цифрами 1,2,3,4 бочки назавем буквами а б в г д е ж з и,:

Далее формула-

1а 2в 3д 4з
2б 3г 4ж 1и
3а 4в 1д 2з
4б 1г 2ж 3и

Итог остаеться бочка с ядом и всего 2 рабочих!!!

Кратко но с решением!!!

Если утверждение, что рабы могут сдохнуть в течени...

2008-07-03T09:18:00.000+04:00

Если утверждение, что рабы могут сдохнуть в течение 24 часов после пробы вина, причем время, прошедшее от пробы до смерти, индивидуально (т.е. разное) для каждого раба, верно, то задача решения, как мне кажется, не имеет. В самом деле, исходя из этого предположения, максимум у нас есть 2 пробы: сначала и через 24 часа. Пробы, осуществляемые по ходу первых (к примеру) 24 часов смысла не имеют, т.к. не понятно как определить результат. Напр. сдохли 2 раба, кто знает от какой бочки? Может два раба пили из отравленной бочки, один сдох на месте, другой через 24 часа, а решение нужно принимать сейчас.

На 2 пробы тут не хватает рабов, т.к. тут 3чная система не катит (нету 3го состояния -- надо определять на месте умер раб или нет, и думать, что делать дальше), максимум, что можно отсюда выжать, так это 2 раза применить 2чную систему, но это только 64 бочки.

Да задачка в пять секунд - пусть каждый раб пьет ч...

2008-06-19T08:15:00.000+04:00

Да задачка в пять секунд - пусть каждый раб пьет через пол чяса из разных бочек 240/5, который помрет - отматать процесс на 24 и в бочку =)
По больше бы таких задачек - очень нра! спасибо =)

_1 день каждому рабу по 48+8+8+8+8 бочек._Первый у...

2008-06-06T18:26:00.000+04:00

_1 день каждому рабу по 48+8+8+8+8 бочек._

Первый угостил второго своими 8-ю бочками, второй угостил первого своими 8-ю бочками. Если умерли оба - у них всего 16 общих бочек, а не 8. Решение не годится.

И опять я, по шнурам...=)Кладем паралельно оба шну...

2008-06-01T09:04:00.000+04:00

И опять я, по шнурам...=)
Кладем паралельно оба шнура. Поджигаем их одновременно так, что-бы когда они прогорят до совмещения, т.е. до такого момента, что если сложить длины остатков, то получится целый шнур. Время которое пройдет будет равно 45минутам.

Вот такое решение про бочки с рабами...Делим бочки...

2008-06-01T08:59:00.000+04:00

Вот такое решение про бочки с рабами...
Делим бочки для рабов на массивы по 48 + по 8 из каждого чужого, только что-бы не повторялись.
1 день каждому рабу по 48+8+8+8+8 бочек.
2 день если умер 1 то это только его собственные бочки из которых пил толко он, если умерло 2, то смотря каких( но это не важно, просто берем ту партию 8ми бочек), каждому оставшимуся по 2+1(т.е. тут едлим на кажого по 2 бочки своих + одана соседа, при этом они не должны пить из этих бочек больше 2х раз, т.е. каждый пьет только 1 раз).

Если в 1 день умерло 2, то одну из 8ми бочек оставляем, а из других 7ми пьют оставшиеся 3 раба так, что каждый пьет из 2х своих и 1 чужой, при этом опять без повторов(т.е. каждый раб пьет 3 раза из 3х бочек).

В итоге получаем если из этих 3х умрут 2, то пили из одной бочки, если один, то ипл из своей, а если ни одного, то отравлена оставшаяся бочка.

При этом потери рабов составляют от 1 до 4ех=)

Вместо 62 должно быть 52. Да, позор, окончательн...

2008-05-30T20:02:00.000+04:00

Вместо 6*2 должно быть 5*2.
Да, позор, окончательно убедился, что устный счет не моя сильная сторона. Значит работа в гугле мне не светит.

Но задачу надо переформулировать, ибо непонятно, почему вино настолько ценно, что приближенное решение (пожертвовать 5% бочек) тут не катит.

Сорри за мусор в комментах…

2Stas Fomin:Т.е. только пять лишних бочек, по отно...

2008-05-30T15:43:00.000+04:00

2Stas Fomin:
Т.е. только пять лишних бочек, по отношению к условию, можно впихнуть.

На самом деле не пять, а три.
Вместо 6*2 должно быть 5*2.

Нет, извините, я идиот. У меня «Сдвиг на разряд» (...

2008-05-30T01:52:00.000+04:00

Нет, извините, я идиот. У меня «Сдвиг на разряд» (5 рабов-разрядов это 32 бочки). Соотвественно, при даже если перебирать все комбинации рабов, получится (биномиальный коэфф. C^k_n):
32+С^1_5*16+С^2_5*8+С^3_5*4+С^4_5*2+C^5*5*1=
32+5*16+10*8+10*4+6*2+1=245

Т.е. только пять лишних бочек, по отношению к условию, можно впихнуть.
Сорри за беспокойство.

Хм. Ошибся. Можно взять и 304 бочки.64+564-516=3...

2008-05-30T01:14:00.000+04:00

Хм. Ошибся. Можно взять и 304 бочки.
64+5*64-5*16=304.
(включения/исключения — пересечений пять, а не шесть, как я подумал сдуру).

Случайно наткнулся на эту задачу. Подумал (не загл...

2008-05-30T01:10:00.000+04:00

Случайно наткнулся на эту задачу.
Подумал (не заглядывая в ответы)
У меня получилось, что можно пятью рабами взять 288 бочек.
Второй тур, где нужно вычислить конкретную точку — «бинарный пробник» (рабы=разряды), для множеств размером
16 (тремя рабами), 32 (четыремя рабами), 64 (пятью рабами).
Первый тур — покрыть исходное множество бочек пересекающимся по рабам множеством распробованных бочек так, чтобы после первого тура было вычислено множество, которое можно оставшимся числом рабов обработать как указано выше.
Для этого делам следующее разбиение:
64 бочки не пьет никто.
Каждый раб пьет по 64 бочки,
причем 32 бочки у каждого раба свои, а 16 бочками раб «пересекается» с соседним (1 со вторым, второй с третьим, пятый с первым).
Таким образом покрывается множество размером 64+5*64-6*16=288.
Три возможных исхода:
1. Никто не умер — 5 рабов атакуют множество размером 64.
2. Один умер — 4 раба атакуют множество размером 32.
3. Двое умерло — 3 раба атакуют множество размером 16.

Так что у задачи есть потенциал для закручивания гаек (возможно ли еще больше бочек «распознать» — я не в курсе…).
Ну либо найдите у меня ошибку, время позднее, мог и ошибится.

Я бы немножко поменял решение с состояниями, чтобы...

2008-05-06T22:33:00.000+04:00

Я бы немножко поменял решение с состояниями, чтобы не было путаницы.
0 - не умер
1 - умер после первого захода
2 - после второго
Тогда номер захода, когда нужно пить бочку, находится в соответствующем разряде числа. Тогда нет сопоставлений 0 - в первом разряде, 1 - во втором... Правда, мы можем считать с нуля :)

С таблетками аналогично. Берём одну таблетку из первой упаковки, две из второй, три из третьей. Число сотых в весе является номером бракованной упаковки.

Спасибо за задачку :)

P. S. За соседним столом на работе сидит к.т.н., так он сразу начал думать в правильном направлении :)

А вы ведь говорили аська пустая трата времени.... ...

2008-05-01T23:42:00.000+04:00

А вы ведь говорили аська пустая трата времени.... Ето я к добавлению от 23 апреля....

Одно дело несколько близких друзей, а совсем другое - непрерывный поток сознания от людей, которых я совсем не знаю..

А вы ведь говорили аська пустая трата времени.... ...

2008-05-01T10:30:00.000+04:00

А вы ведь говорили аська пустая трата времени.... Ето я к добавлению от 23 апреля....

2rocker:Да - действительно, в моем методе определя...

2008-04-30T21:55:00.000+04:00

2rocker:
Да - действительно, в моем методе определяющим является последовательность смертей. Например, если первым умер раб 1 - значит отравленная бочка в первых 48. Если Последовательность смертей 1 2 3 4 - значит это бочка №1 если 1 2 3 4 5 - значит №2, 1 2 3 5 - бочка №3 итд.
Т.е. интервал от принятия яда до смерти может быть любой до 24 часов, но одинаковый у всех.

2Alexey:возможно множество случаев, когда все(!) р...

2008-04-30T19:10:00.000+04:00

2Alexey:
возможно множество случаев, когда все(!) рабы умрут. И тогда никак не определить, в какой бочке яд.

если конкретнее, то есть 120 шансов умереть всем. 120 - умереть четверым. как же найти отравленную бочку?

Хотя люди уже призывают закрыть тему.Рискну предло...

2008-04-30T16:04:00.000+04:00

Хотя люди уже призывают закрыть тему.
Рискну предложить свое оригинальное решение,
кстати имеющее еще одно преимущество, оно позволяет
решить задачу за 28 часов.
Итак, разбиваем 240 бочек на 5 частей по 48 бочек
соответственно каждый из рабов пьет из своей части.
Через час (выбрано как минимальная временная разница)
каждая из 5 частей делиться на 4 по 12 бочек в каждой,
из которых пробуют вино все рабы, кроме того кто пил
из всех 48 бочек этой группы, далее каждую группу из 12 бочек
делим на 3 по 4 бочки, каждую из групп по 4 бочки на 2 группы
по 2 бочек. Все. Поскольку расписать здесь все разбиение трудно,
приведу разбиение только начиная с 1 группы по 48
промежуток между дегустациями 1 час (0 - никто не пробует)
+0ч - 111111111111111111111111111111111111111111111111
+1ч - 222222222222333333333333444444444444555555555555
+2ч - 333344445555222244445555222233335555222233334444
+3ч - 445533553344445522552244335522552233334422442233
+4ч - 050405030403050405020402050305020302040304020302
Максимальный промежуток между началом теста и последней смертью
24+число подходов(5)-1=28 часов
Замечу, что в отличии от других решений число бочек точно соответствует
числу рабов необходимых для решения. Также решение не зависит от конкретных
физиологических свойств реципиентов т.е. смерть может наступить в любой промежуток
времени от 0 до 24 часов.

Смущает то, что бочек 240, а не 243... Может автор...

2008-04-30T10:05:00.000+04:00

Смущает то, что бочек 240, а не 243... Может автор задачи сам не знал правильного решения? Есть один неверный путь в рзмышлениях, который приводит нас к 240-ка. Может автор его и имел ввиду?

Уже не меньше 4 раз правильное решение писали. Хва...

2008-04-29T14:54:00.000+04:00

Уже не меньше 4 раз правильное решение писали. Хватит, пора закрывать тему. А то откровенные глупости люди писать начинают.

Или можно переформулировать условие: доказать, что задача решена оптимально, т.е. что нельзя вычислить отравленную бочку из более, чем 243.

простое решение:делим 240 бочек на 6 групп по 40 б...

2008-04-29T13:02:00.000+04:00

простое решение:

делим 240 бочек на 6 групп по 40 бочек, 1 раб распробует вино из всех бочек первой группы, 2 - из второй и тд. Если через 24 рабы остались живы - отравленная бочка в 6 группе, иначе имеем 4 раба и группу из 40 бочек.

далее делим 40 бочек на 5 групп по 8 бочек и 4 раба дегустируют вино каждый в своей группе. Через 24 часа либо они остаются живы и отравленая бочка находится в 5 группе, либо в той группе - которую дегустировал умерший раб.

таким образом получаем 240-8 НЕотравлееных бочек, которых оправляются на пьянку, а так как у нас осталось 3(в худшем случае) раба - они будут определять в какой бочке отравленное вино:

8 делится на 4 группы по 2, 3 раба пробуют из трех групп - если через 24 часа все живы- отравленная в 4 группе. Теперь у нас две бочки - даем ее одному (из 2 выживших) рабу - если он выживает - отравлена другая бочка.

Похоже, в общем случае (N рабов и k дней) рекуррен...

2008-04-29T04:40:00.000+04:00

Похоже, в общем случае (N рабов и k дней) рекуррентная формула будет такой:

M(k, N) = Sum(i = 0, N) { C(i,N) * M(k-1, N-i) }

M(1, N) = 2^N

Да… задачка доставила удовольствие. Первая мысль –...

2008-04-29T02:55:00.000+04:00

Да… задачка доставила удовольствие.

Первая мысль – 5 рабов за один заход могут дать 32 комбинации. Но нужно оставить несколько рабов на второй заход.

Выберем те комбинации из 32, при которых остаётся некоторое количество рабов на другой ход.

Предположим, два идут на первый (С2/5 = С3/5 = 10, больше брать смысла не имеет), три на последний.
Тогда за первый заход можем проверить десять групп бочек, остаётся 24 на трёх человек. Много.

Так! Но можно же брать не только комбинации, в которых два бита равны единице.

Можно брать те, в которых число единиц меньше либо равно двум. Это 16 из 32.
240/16 = 15. Такой мизер тремя рабами не ловится… Скверно.

Мысль: в некоторых случаях на второй ход остаётся больше трёх рабов. Нельзя ли использовать это преймущество?

Мы можем проверить 16 групп бочек, используя те пятибитовые комбинации, в которых не более трёх единиц.
! Но не обязательно количество бочек в этих группах должно быть одинаковым.

Для комбинаций, после которых остаётся больше рабов, можно использовать группу с бОльшим количеством точек.

Будем учитывать то количество
бочек, которое мы сможем исследовать остатком рабов.

Если после первого эксперимента у нас остаётся 5 рабов, мы можем исследовать с помощью них 32 бочки. Если 4 – 16 бочек. Если 3 – 8 бочек.
Комбинаций с нулём единиц у нас одна, с одной – 5, с двумя – 10.
Выделяем группу бочек числом 32 (из которых никто не будет пить), под 00000, пять групп бочек числом 16 для одноединичных комбинаций и 10 груп числом 8 под двухъединичные комбинации.
1*32 + 5*16 + 10*8 = 192. Мало. Но близко.

Блин, а кто сказал, что за первый заход мы можем сгнобить только двух рабов?
Если мы сгнобим трёх, после этого мы сможем исследовать 4 бочки (но комбинаций из трёх рабов 10, на каждую мы можем выделить по 4 бочки), если у нас останется один раб – с его помощью можно будет проверить две бочки. Ну а если все умрут – на это событие 11111 можно поставить группу в одну бочку.

Продолжим ряд:
1*32 + 5*16 + 10*8 + 10*4 + 5*2 + 1 = 243.

Comments on Алёна C++: Пост Get that job at Google

Читал, читал, устал, у каждого свое мнение, не зна...

Не читал верхние комменты, честно :) Всего за перв...

букву е не надо я описалсяА Б В Г Д Ж З И

Ответ! Тк в условии сказано что смерть настает в т...

Если утверждение, что рабы могут сдохнуть в течени...

Да задачка в пять секунд - пусть каждый раб пьет ч...

_1 день каждому рабу по 48+8+8+8+8 бочек._Первый у...

И опять я, по шнурам...=)Кладем паралельно оба шну...

Вот такое решение про бочки с рабами...Делим бочки...

Вместо 6*2 должно быть 5*2. Да, позор, окончательн...

2Stas Fomin:Т.е. только пять лишних бочек, по отно...

Нет, извините, я идиот. У меня «Сдвиг на разряд» (...

Хм. Ошибся. Можно взять и 304 бочки.64+5*64-5*16=3...

Случайно наткнулся на эту задачу. Подумал (не загл...

Я бы немножко поменял решение с состояниями, чтобы...

А вы ведь говорили аська пустая трата времени.... ...

А вы ведь говорили аська пустая трата времени.... ...

2rocker:Да - действительно, в моем методе определя...

2Alexey:возможно множество случаев, когда все(!) р...

Хотя люди уже призывают закрыть тему.Рискну предло...

Смущает то, что бочек 240, а не 243... Может автор...

Уже не меньше 4 раз правильное решение писали. Хва...

простое решение:делим 240 бочек на 6 групп по 40 б...

Похоже, в общем случае (N рабов и k дней) рекуррен...

Да… задачка доставила удовольствие. Первая мысль –...

Вместо 62 должно быть 52. Да, позор, окончательн...

Хм. Ошибся. Можно взять и 304 бочки.64+564-516=3...