Сохранен 115
https://2ch.hk/b/res/80002794.html
Изменился адрес Архивача в сети Tor — arhivachqqqvwqcotafhk4ks2he56seuwcshpayrm5myeq45vlff44yd.onion. Установите Tor Browser для беспрепятственного доступа!
Аноним 20/11/14 Чтв 01:58:14 #1 №80002794 
14164378946190.png
Есть тюрьма и 77 заключенных, каждый из которых сидит в отдельное камере и не имеет возможности общаться с другими. Есть одна камера, в которой на потолке висит лампочка и на стене установлен выключатель с положениями ВКЛ/ВЫКЛ для лампочки. Из других камер не видно, горит ли лампочка в этой отдельной камере.
Директор тюрьмы сказал, что каждый день один из заключенных будет ходить в эту камеру, где сможет включить свет, выключить свет или вообще ничего не делать. Причем заключенных могут приводить в камеру в произвольном порядке, некоторые могут попасть туда несколько раз, и даже много раз подряд каждый день.
Условие игры в том, что кто-то один может зайти в камеру, посмотреть на выключатель, и определить, побывали ли в камере 76 заключенных кроме него хотя бы по одному разу, или нет. И если он скажет, что в камеры уже побывали все, то все 77 человек выйдут на свободу, Если он ошибется, то всех расстреляют.
Перед стартом задания всем заключенным разрешили собраться вместе и выработать стратегию. Итак, какая должна быть стратегия?

PS: Оставлять какие-то знаки и пометки в камере заключенные не могут! Зарезать охранника и сбежать через вентиляцию тоже нельзя.
Loading...
Аноним 20/11/14 Чтв 01:59:05 #2 №80002825 
откуда сажа-то взялась?!
Аноним 20/11/14 Чтв 02:05:45 #3 №80003075 
бумп
Аноним 20/11/14 Чтв 02:06:20 #4 №80003105 
>>80002794
Что за хуйню я прочитал? В один бит нельзя засунуть так много информации :(
Аноним 20/11/14 Чтв 02:07:24 #5 №80003158 
>>80003105
ну да, нельзя.и?
Аноним 20/11/14 Чтв 02:09:58 #6 №80003262 
Назначить опа главпетухом и жить себе на казенных харчах.
Аноним 20/11/14 Чтв 02:09:59 #7 №80003264 
Сколько зэков требуется, чтобы поменять одну лампочку?
Аноним 20/11/14 Чтв 02:11:03 #8 №80003306 
>>80003158
Ну ты условие как-то по-человечески записал бы. Что это за
>каждый день один из заключенных будет ходить в эту камеру
>и даже много раз подряд за один день
Так один или не один? Если один, то к чему второе замечание? Пиздец какой-то. Нельзя сразу все нормально написать?
Аноним 20/11/14 Чтв 02:11:42 #9 №80003334 
>>80002794
Ответ есть, но они ёбане до сконания веком трахаться будут.
Выбирают одного счетовода, тот, кто попал в камер первым - включает свет и больше не трогает, все кто попадают позже так же не трогают включенный, когда в камеру попадает счетовод - он свет выключает - это +1, далее попадает новый зек и тоже включает свет, и больше не трогает, счетовод снова попадает в камеру, выключает свет - +2, далее смет включают зеки те, кто свет ещё не включал, а счетовод, каждый раз попадая в камеру свет вырубает и таким макаром считает до 76
Аноним 20/11/14 Чтв 02:12:50 #10 №80003387 
>>80003306
не "за один день", а "каждый день", но вообще я поленился сам печатать и просто нагуглил
Аноним 20/11/14 Чтв 02:13:08 #11 №80003403 
Условие непонятно, известно ли изначальное положение выключателя.
Аноним 20/11/14 Чтв 02:14:00 #12 №80003439 
>>80003334
винер. хотя я надеялся, что кто-то своих задач накидает. тред рип
Аноним 20/11/14 Чтв 02:14:28 #13 №80003458 
>>80003334
долго же
Аноним 20/11/14 Чтв 02:15:06 #14 №80003488 
>>80003334
Ну вот что это за хуйня? Почему блять из условия непонятно, что этого счетовода можно выбрать, а не каждый должен это понять. Пиздец, убить мало за такое условие, блять. Ебанаты, дегенераты.
Аноним 20/11/14 Чтв 02:15:52 #15 №80003518 
>>80003488
там ведь не сказано,что каждый должен понять. Ты сам поломался жи.
Аноним 20/11/14 Чтв 02:16:34 #16 №80003554 
>>80003488
>Почему блять из условия непонятно, что этого счетовода можно выбрать
>Перед стартом задания всем заключенным разрешили собраться вместе и выработать стратегию.
Аноним 20/11/14 Чтв 02:16:51 #17 №80003569 
>>80003439
Палю годноту:

Продавец продает шапку. Стоит 10 р. Подходит покупатель, меряет и согласен взять, но у него есть только 25 р. Продавец отсылает мальчика с этими 25 р. к соседке разменять. Мальчик прибегает и отдает 10+10+5. Продавец отдает шапку и сдачу в 15 руб. Через какое то время приходит соседка и и говорит, что 25 р. фальшивые, требует отдать ей деньги. Ну что делать. Продавец лезет в кассу и возвращает ей деньги.

ВОПРОС: на сколько обманули продавца?
Аноним 20/11/14 Чтв 02:17:40 #18 №80003599 
>>80003334
И тут такой прикол: прогнали 76 человек по одному разу, заводят счетовода. Свет включен, все 76 человек побывали по разу, у того в уме 1. Расстрел?
Аноним 20/11/14 Чтв 02:17:45 #19 №80003602 
>>80003569
не взлетит
Аноним 20/11/14 Чтв 02:18:26 #20 №80003630 
>>80003569
к сожалению, знаю. Хотя и тогда я её тоже решил. И на словах и на деле
Аноним 20/11/14 Чтв 02:21:02 #21 №80003727 
>>80003599
Ну давайте же кисоньки. Вроде как условию не противоречит.
Аноним 20/11/14 Чтв 02:21:24 #22 №80003742 
>>80003569
15 фальшивых рублей, 25 реальных отдал, 10 в шапке. Так? Если нет, то почему?
Аноним 20/11/14 Чтв 02:22:28 #23 №80003785 
>>80003599
А, я понял. Они еще и время могут варьировать на свое усмотрение, а не по первому требованию должны на вопрос ответить. Это уж совсем пиздец. Надеюсь ОП будет подальше от образования работать.
Аноним 20/11/14 Чтв 02:23:02 #24 №80003804 
>>80003599
Это ты ОП?
Аноним 20/11/14 Чтв 02:24:08 #25 №80003848 
>>80003599
>побывали ли в камере 76 заключенных кроме него хотя бы по одному разу, или нет

>хотя бы по одному разу

И ничего, прогонят еще раз. И еще 74 раза.
Аноним 20/11/14 Чтв 02:24:30 #26 №80003859 
>>80003727
Ноуп, пока ты не начал пиздеть игра продолжается же. Это если ты решил сказать "опа, бля буду все уже побывали", то тут за базар спросят. По идее счетовод может до конца жизни всех траллировать.
Аноним 20/11/14 Чтв 02:25:03 #27 №80003883 
>>80003569
На 40 и шапку.
Аноним 20/11/14 Чтв 02:25:18 #28 №80003891 
>>80003569
50
Аноним 20/11/14 Чтв 02:26:03 #29 №80003924 
>>80002794
Ладно, так и быть. Есть последовательность чисел очень большого размера. Все числа в ней встречаются два раза, и только одно -- один раз. Задача - найти это число за линейное время и с константной дополнительной памятью.
Аноним 20/11/14 Чтв 02:26:11 #30 №80003928 
>>80003602
Каждый раз взлетало, а тут не взлетит?
Аноним 20/11/14 Чтв 02:26:57 #31 №80003961 
>>80003569
15+закупочная цена шапки же.
Аноним 20/11/14 Чтв 02:27:30 #32 №80003984 
>>80003924
Числа совершенно случайные, целые.
Аноним 20/11/14 Чтв 02:27:43 #33 №80003995 
>>80003961
винар
Аноним 20/11/14 Чтв 02:29:09 #34 №80004048 
>>80003924
Все числа встречаются РОВНО два раза, и только одно - один раз.
Аноним 20/11/14 Чтв 02:31:32 #35 №80004145 
>>80003924
Объясните гумманитарию, что значит "константа дополнительной памяти"?
Аноним 20/11/14 Чтв 02:32:00 #36 №80004164 
>>80003924
Ну заебись. Тут никто не знает что значит слово "константный" что ли? Это значит не зависящий от количества чисел в последовательности.
Аноним 20/11/14 Чтв 02:34:05 #37 №80004252 
>>80003995
Лол, разве?
Я не подумав ответил, а теперь сомневаться стал. Просто навскидку 25 фальшивых рублей не могут нанести ущерб больше 25 рублей.
Аноним 20/11/14 Чтв 02:34:11 #38 №80004255 
>>80004145
Константная дополнительная память значит -- ты можешь использовать одно и то же количество бумаги для записей, когда перед тобой будут прогонять эту последовательность, независимо от того, сколько в ней чисел: сто, тысяча, или триллион. Линейное время - это для этой задачи даже чересчур. Можно сказать, что нужно это понять за один проход.
 Аноним 20/11/14 Чтв 02:35:03 #39 №80004291 
Заключенным надо выработать стратегию поведения: заключенные выбирают из себя того кто будет считать (счетовод) а теперь алгоритм 1. тот кто первый раз заходит в камеру и видит что свет не горит зажигает его. 2. Если счетовод попадает в камеру и видит что свет горит он его выключает и делает +1 3. если кто то заходит в камеру второй раз он свет не трогает 4. если кто то заходит первый раз и видит что свет горит он его не трогает 5 если счетовод попадает в камеру и видит что свет не горит он его не трогает 6 выключать лампочку может только счетовод когда счетовод досчитает до 77 все зеки были в камере
Аноним 20/11/14 Чтв 02:35:07 #40 №80004297 
>>80004255
За один проход значит: тебе покажут эту последовательность только один раз.
Аноним 20/11/14 Чтв 02:36:06 #41 №80004335 
>>80004291
А теперь давай ответ для этой >>80003924
Аноним 20/11/14 Чтв 02:37:27 #42 №80004386 
>>80004252
все правильно
Аноним 20/11/14 Чтв 02:39:38 #43 №80004469 
>>80004386
>>80004252
неправильно, не забывайте упущенную прибыль, поэтому не себестоимость шапки+15 р, а 25 р.
Аноним 20/11/14 Чтв 02:39:56 #44 №80004482 
>>80004255
выписываешь новые номера,когда встречается второй раз-зачеркиваешь, незачеркнутое-искомое
Аноним 20/11/14 Чтв 02:41:04 #45 №80004520 
>>80004469
если считать упущеную прибыль убытком
Аноним 20/11/14 Чтв 02:42:22 #46 №80004573 
>>80004482
Это значит, что количество бумаги зависит от размера последовательности: для 10 чисел тебе хватит тетрадного листочка, а для триллиона нужно ебаный лес на бумагу пустить.
Аноним 20/11/14 Чтв 02:44:05 #47 №80004644 
>>80003924
Эта задача видимо слишком сложна для подобного треда, без знания дискретки ее на вряд ли решишь.
Аноним 20/11/14 Чтв 02:44:20 #48 №80004650 
>>80003773
А почему он дает сдачу в 15 рублей, когда мальчик разменял деньги. Следовательно, он дал ему десятку.
Аноним 20/11/14 Чтв 02:44:38 #49 №80004662 
>>80004520
Вопрос на сколько обманули продавца, а не какой его убыток. Если из магазина крадут товар стоимостью 10 р, то и в деле будет фигурировать 10 р, неважно, что закупочная цена 5 р.
Аноним 20/11/14 Чтв 02:45:44 #50 №80004708 
>>80004662
да знаю, невнимательно читал условие и попытался выкрутиться=3
Аноним 20/11/14 Чтв 02:47:04 #51 №80004758 
>>80004573
Снова и по-быдлокоредски, пожалуйста. Грубо говоря, без разницы, какой размер у массива, мы можем использовать только фиксированный объём памяти (можно меньше, но не в коем случае не больше) для записи элементов, так?
>Можно сказать, что нужно это понять за один проход.
Это тоже непонятно. Т.е передо мной, скажем, тем же циклом прокрутили последовательность и всё? Запомнить я её не могу, исходя из первого условия?
Аноним 20/11/14 Чтв 02:47:19 #52 №80004768 
>>80004644
Это связано с XOR'ом?
Аноним 20/11/14 Чтв 02:49:27 #53 №80004856 
>>80004662
Азаза, сумму ущерба определяет госоценщик и срать он хотел на магазинный ценник.
Аноним 20/11/14 Чтв 02:49:31 #54 №80004860 
>>80004758
Ты в обоих пунктах совершенно прав.
Аноним 20/11/14 Чтв 02:52:07 #55 №80004958 
помойму вы нихуя не отгадали загадку
- если одно тело, допустим, не зашло туда ни разу, а уже 25человек прошел, то как он узнает, когда зайдёт в камеру, что пришла его очередь зажигать свет?
sageАноним 20/11/14 Чтв 02:52:07 #56 №80004959 
>>80003334
счетовода перестанут приводить в камеру до достижения 76 и все соснут. нигде не написано что приводят случайно.

дибильная задача оп.
Аноним 20/11/14 Чтв 02:52:31 #57 №80004974 
>>80004768
Да, это может быть связано с ним.
Аноним 20/11/14 Чтв 02:54:04 #58 №80005032 
>>80004959
А что если приводят случайно, но выбирая всех, кроме счетовода? Тогда считай, они себе пожизненное устроили своей выигрышной стратегией.
Аноним 20/11/14 Чтв 02:55:04 #59 №80005071 
>>80004856
Какой госоценщик? Кто будет платить за оценку? Нет, сумма ущерба определяется именно ценником. Но если адвокат обвиняемого будет с ценой, он, конечно, имеет право ходатайствовать и за деньги клиента пытаться проводить любые экспертизы и оценки, только в путь.
Аноним 20/11/14 Чтв 02:55:23 #60 №80005082 
>>80004958
Элементарно, Ватсон, свет должен быть выключен. если свет выключен - включай, но только один раз.
>>80004959
Ну тогда кум пидр в натуре, перо ему под ребро.
Аноним 20/11/14 Чтв 02:55:38 #61 №80005097 
>>80004958
Соблюдай неписаное правило зека: "Включай за всеми, выключай за собой"
Аноним 20/11/14 Чтв 02:56:21 #62 №80005122 
>>80005071
будет с ценой несогласен
selffx
sageАноним 20/11/14 Чтв 02:56:56 #63 №80005140 
>>80003924
xor всех последовательно.

проебал эту задач на собеседовании нивала.
Аноним 20/11/14 Чтв 02:57:53 #64 №80005180 
>>80005140
Что такое Нивала? Ты откуда?
Аноним 20/11/14 Чтв 02:58:11 #65 №80005191 
>>80005097
да похуй же, когда счетовод узнает, что уже прошли все?
всегда есть вероятность, что даже через 1000 лет кто-то ещ не заходил.
Аноним 20/11/14 Чтв 02:58:28 #66 №80005199 
>>80005180
http://ru.nival.com/
Мимо-геймер
Аноним 20/11/14 Чтв 02:58:45 #67 №80005210 
>>80004860
Блин, тут не хватает моих 11 классов образования. Я бы тупо решил циклом внутри цикла, а с такими выкрутасами хз.
Аноним 20/11/14 Чтв 02:58:58 #68 №80005220 
>>80005071
Какая блджад экспертиза, три рубля которая? Кто думаешь определяет ценность всех этих спизженных с дачных участков трехколёсных велосипедов и газовых баллонов?
Аноним 20/11/14 Чтв 03:00:15 #69 №80005266 
>>80005191
Надо просто посчитать матожидание хождения по равномерному распределению и всем зекам сказать его, чтобы успокоились. А кума попросить, что датчик случайных чисел равномерный взял.
Аноним 20/11/14 Чтв 03:00:54 #70 №80005284 
>>80003924
пять
Аноним 20/11/14 Чтв 03:02:04 #71 №80005325 
>>80005210
Гугли XOR. В вузе учи дискретку, лол, наверное будет интересно.
Аноним 20/11/14 Чтв 03:02:16 #72 №80005335 
>>80005140
Я так и думал.
[CODE]
#include <stdio.h>

int main()
{
int a[] = {5, 8, 2, 1, 8, 2671, 5, 2, 1};
int res = 0;
for (int i = 0; i < 9; i++)
res ^= a;
printf("%d", res);
return 0;
}
[/CODE]
мимо-быдлокодер->>80004768
sageАноним 20/11/14 Чтв 03:03:01 #73 №80005368 
>>80005082
вообще наверное лучшей стратегии и правда нет. если он пидр, то он пидр.
Аноним 20/11/14 Чтв 03:03:36 #74 №80005393 
>>80005335
Ты че, охуел указатель ксорить? :3
Аноним 20/11/14 Чтв 03:04:39 #75 №80005426 
>>80005335
Что значит эта строчка?
>res ^= a;
Аноним 20/11/14 Чтв 03:05:21 #76 №80005450 
>>80003569
>дали фальшивку номиналом 25 рублей
>НА СКОЛЬКО ЖИ ПОПАЛ ПРОДАВЕЦ??????
Блядь, на 25 рублей.
Аноним 20/11/14 Чтв 03:05:29 #77 №80005456 
>>80005335
>>80005393
[i.] без точки скушала макаба. Когда уже макак [CODE] починит?
Аноним 20/11/14 Чтв 03:05:45 #78 №80005467 
>>80005426
Респа каждые а секунд. Настройки сервера же, стыдно не знать.
Аноним 20/11/14 Чтв 03:05:48 #79 №80005470 
>>80005426
Там должно быть
res ^= a;
Аноним 20/11/14 Чтв 03:06:29 #80 №80005498 
>>80005470
Fuck
Аноним 20/11/14 Чтв 03:07:01 #81 №80005517 
>>80005335
>i++

ньюфаг же :3 ну и a же
Аноним 20/11/14 Чтв 03:07:24 #82 №80005527 
>>80005426
Это типа xor от всех чисел.
Аноним 20/11/14 Чтв 03:08:15 #83 №80005546 
>>80005517
Пиздец, сэкономил 9 наносекунд.
Аноним 20/11/14 Чтв 03:08:23 #84 №80005556 
Объясните задачу с числами
Аноним 20/11/14 Чтв 03:08:45 #85 №80005569 
>>80005220
Ценность заявляет потерпевший. А все дальнейшие товароведческие экспертизы в полномочиях следствия (оно назначать их не будет) либо по ходатайству защиты (а там как сложится)
Аноним 20/11/14 Чтв 03:10:56 #86 №80005626 
>>80005556
Посмотри там раздел свойства, первые две штуки тут работают. http://ru.wikipedia.org/wiki/Сложение_по_модулю_2
Аноним 20/11/14 Чтв 03:12:44 #87 №80005667 
>>80005517
ньюфаг же, не может в асимптотику
Аноним 20/11/14 Чтв 03:15:13 #88 №80005729 
>>80005517
http://www.viva64.com/ru/b/0093/
Знаю, да. Набросал это дело за минуту, ибо уже практически засыпаю, так что не бейте, лучше обоссыте судите строго.
>>80005546
Здесь - 9 наносекунд, если не меньше, а в больших проектах, где используются шаблоны и прочие прелести STL, счет может идти уже и на секунды.
Аноним 20/11/14 Чтв 03:16:38 #89 №80005761 
>>80005467
Валидация персистентности же, стыдно не знать комбинаторов полиморфной инкапсуляции.
Аноним 20/11/14 Чтв 03:17:45 #90 №80005792 
>>80005761
Папа, а с кем это ты сейчас разговаривал?
Аноним 20/11/14 Чтв 03:18:05 #91 №80005799 
>>80005729
В больших проектах, скомпилированных с ключом -O это также не будет играть никакой роли.
Аноним 20/11/14 Чтв 03:26:11 #92 №80006017 
>>80003334
Непонимат. Считовод значит приходит выключает это +1. Потом зек заходит включает, за ним еще 1 выключает, потом включает, потом выключает, потом все взрывается.
Аноним 20/11/14 Чтв 03:26:18 #93 №80006019 
Аноним 20/11/14 Чтв 03:26:46 #94 №80006027 
Mevg
Аноним 20/11/14 Чтв 03:28:39 #95 №80006076 
>>80006017
>потом зек заходит включает, за ним еще 1 счетовод выключает

Поправил, не благодари
sageАноним 20/11/14 Чтв 03:32:03 #96 №80006154 
>>80003264
3. Один ебет петуха - другой петух вкручивает лампочку за возможность оставить зубы.
Аноним 20/11/14 Чтв 03:38:49 #97 №80006326 
>>80005450
Схуяли? Допустим, решил купить я у тебя айфон, расплатившись фальшивыми купюрами. Итог: ты остался без айфона, да еще и с фальшивыми купюрами.
sageАноним 20/11/14 Чтв 03:39:06 #98 №80006335 
>>80002794
Можно определить, было ли там четное количество зеков или нечетное.

Тогда каждый должен просто менять положение выключателя, если он в камере в первый раз, а если не в первый - не менять.

Большей информации передать нельзя. Но это уже что-то, четность искомого числа ведь известна.
Аноним 20/11/14 Чтв 03:43:04 #99 №80006430 
>>80006335
А если у тебя завтра дембель, то дергать выключатель?
Аноним 20/11/14 Чтв 03:51:07 #100 №80006647 
>>80006430
Анус себе дерни, дембель
Аноним 20/11/14 Чтв 04:20:13 #101 №80007301 
>>80006326
не было никаких, а остался с фальшивыми. убыток
Аноним 20/11/14 Чтв 04:24:29 #102 №80007366 
>>80002794
Заключенные по умолчанию проиграли. Чтобы сработал 1 бит им надо все проделать за 77 - 5929 дней.бесконечности А тюряги тролльнут на 2 день.
sageАноним 20/11/14 Чтв 05:48:29 #103 №80008891 
не спится вам, суки
Аноним 20/11/14 Чтв 07:12:57 #104 №80010188 
test
Аноним 20/11/14 Чтв 08:02:43 #105 №80011054 
тест2
sageАноним 20/11/14 Чтв 08:08:50 #106 №80011172 
>>80002794
Есть два стула...
Аноним 20/11/14 Чтв 08:17:57 #107 №80011341 
>>80011172
и?
Аноним 20/11/14 Чтв 08:28:57 #108 №80011588 
123
Аноним 20/11/14 Чтв 08:36:56 #109 №80011801 
bmp
Аноним 20/11/14 Чтв 09:02:02 #110 №80012520 
bump
Аноним 20/11/14 Чтв 09:13:18 #111 №80012859 
comment
Аноним 20/11/14 Чтв 09:21:54 #112 №80013148 
>>80011341
И твое очко отправляется к телезрителям
Аноним 20/11/14 Чтв 09:23:34 #113 №80013203 
>>80007301
Здравый человек
Аноним 20/11/14 Чтв 09:27:40 #114 №80013323 
>>80003924

Районая олимпиада младшие классы. Памяти n+1 ячеек, обрабатывается за n операций с помощью xor. От куда там большие числа не ясно. Если они в long long не влезут то быстро с помощью xor обработать не получится и задача становится не решаемой.
Аноним 20/11/14 Чтв 09:30:16 #115 №80013401 
>>80013323
this
comments powered by Disqus

Отзывы и предложения