tag:blogger.com,1999:blog-6846929136376245264.post6929368541065338163..comments2024-01-03T12:54:39.457+03:00Comments on Привычка не думать: Аукцион с камнямиИлья Весеннийhttp://www.blogger.com/profile/12075968879288943233noreply@blogger.comBlogger89125tag:blogger.com,1999:blog-6846929136376245264.post-65642517762606592382012-04-03T13:07:02.536+04:002012-04-03T13:07:02.536+04:00А как влияет число камней у какого-то из игроков н...А как влияет число камней у какого-то из игроков на количество слагаемых, которые они выбирают для представления числа 13?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-87634431341849051282012-02-22T09:45:34.035+04:002012-02-22T09:45:34.035+04:00crem,
спасибо за такое подробное описание!
Здорово...<b>crem</b>,<br />спасибо за такое подробное описание!<br />Здорово, что Вы пояснили, каким образом думали. Ведь многим часто хочется не столько узнать ответ, сколько понять, как дойти до ответа. Поэтому Ваш текст обладает повышенной ценностью :)Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-56562652860612388922012-02-21T22:35:27.683+04:002012-02-21T22:35:27.683+04:00http://crem.dyndns-home.com/files/sponges.html
Пе...http://crem.dyndns-home.com/files/sponges.html<br /><br />Перенёс ссылку в место позаметнее, чтоб те которые любят играться но не любят читать скучные тексты её не пропустили. :)cremhttps://www.blogger.com/profile/02020005361431778903noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-54920069856601031212012-02-21T22:33:52.846+04:002012-02-21T22:33:52.846+04:00Надеюсь я не очень отстал от остальных решающих эт...Надеюсь я не очень отстал от остальных решающих эту задачу. :-)<br /><br />Сам по себе я ленивый, и поэтому ждал когда же кто-нибудь понятно разжуёт решение для ответа 2535, вникать в код не очень-то хотелось. Не дождавшись, решил порешать сам. Получились всё те же 2535, но теперь я хоть понимаю откуда.<br /><br />Да, кстати выше предлагали дать возможность одному из шпионов выбрать кто будет ходить первым. Я считаю что этот дополнительный канал информации условию не соответствует.<br /><br />Решал так, можно сказать по индукции:<br /><br />Если осталось 0 камней:<br />Тот, чья очередь кидать, может передать второму 1 различных чисел.<br />Втотой первому - тоже 1 различных чисел.<br />Обозначу это 1:1<br /><br />Если остался 1 камень:<br />У первого только один вариант выкинуть этот камень, поэтому никакой дополнительной информации он передать не может.<br />1:1<br /><br />Если осталось 2 камня:<br />У игрока 2 варианта:<br />1) кинуть один камень, тогда второй остаётся с одним камнем (и возможностями 1:1)<br />2) кинуть два камня, тогда второй остаётся с нулём камней (1:1)<br />Таким образом у игрока есть 1+1=2 способа оставить второго игрока с 1 вариантом, поэтому это ситуация 2:1<br /><br />Если осталось 3 камня:<br />1) можно кинуть один камень, оставив второго в ситуации 2:1<br />2) кинув 2 камня, можно оставить второго в ситуации 1:1<br />2) кинув 3 камня, можно оставить второго в ситуации 1:1<br />Находясь перед кучей из трёх камней игрок может либо предоставить второму возможность выбрать число из двух выкинув один камень и не передав никакой информации, это ситуация 1:2,<br />Либо передать информацию кинув 1, 2 или 3 камня, но не получив ничего взамен, 3:1.<br />Обращаю внимание, что хотя в последней ситуации может так оказаться что передавая информацию первый кидает 1 камень и вроде бы у второго появляется возможность тоже что-то передать, это не ситуаций 3:2, потому что мы не можем гарантировать что при любом из 3х вариантов для первого, у второго будет 2 варианта.<br />Таким образом, с тремя камнями ситуации может быть две: 1:2 и 3:1.<br /><br />Ситуация с 4 камнями:<br />С 4 камнями я надеюсь что всё будет понятнее.<br />1) кидаем один, оставляем коллегу в ситуации 1:2 или 3:1 на выбор<br />2) кидаем два, оставляем в 2:1<br />3) кидаем три, оставляем в 1:1<br />4) кидаем четыре, оставляем в 1:1<br />Если мы хотим предоставить коллеге возможность передать одно из 3х чисел, мы кидаем один камень, это 1:3<br />У нас есть два способа дать ему возможность передать один из 2х чисел (кинув два камня, и кинув один, в последнем случае у него даже избыток возможности), получается 2:2<br />И самое интересное: если мы не хотим от второго игрока никакой информации, у нас есть 4 способа кинуть камень сейчас, но если мы кинем 1 камень, то позже мы можем воспользоваться ситуацией 1:2, и передать ещё один из двух вариантов. Таким образом, это 5:1.<br />То есть с четырьмя камнями ситуации 5:1 2:2 1:3.<br /><br />Напоминаю, что это значит, что по предварительной договорённости с 4 камнями шпионы могут:<br />* первый второму может передать число от 1 до 5, не получив информации взамен<br />* каждый каждому может передать число от 1 до 2<br />* первый может информацию не передавать, но принять от второго число от 1 до 3<br /><br />Допустим мы просчитали возможности для всех ситуаций с количеством камней от 0 до N:<br />(пример для N=4)<br />S[0] = {1:1}<br />S[1] = {1:1}<br />S[2] = {2:1}<br />S[3] = {1:2, 3:1}<br />S[4] = {1:3, 2:2, 5:1}<br /><br />Для того, чтобы посчитать возможности для N+1, мы<br />для каждого d (из множества натуральных чисел :-) ) {<br /> sum := 0<br /> для каждого n из 0..N {<br /> ищем в S[0] пару a:b, с максимальной b, при условии что a>=d;<br /> sum := sum + b<br /> }<br /> добавляем в S[N+1] пару sum:d<br /> }<br /><br />S[5] = {1:5, 2:3, 4:2, 8:1}<br />И т д.<br />Из S[26] выбираем пару a:b с наибольшим min(a,b) и это оказывается 2535:2536, это и есть наш ответ.<br />Для того чтобы из полученных данных построить алгоритм выбора количества камней, надо идти по нему в обратном порядке.<br />Написал на джаваскрипте обратный ход алгоритма, можете поиграться:<br />http://crem.dyndns-home.com/files/sponges.html (только я решал в терминах мочалок а не камней)cremhttps://www.blogger.com/profile/02020005361431778903noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-28712271161730722222012-02-01T12:15:41.340+04:002012-02-01T12:15:41.340+04:00Спасибо, теперь всё работает.Спасибо, теперь всё работает.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-90672670239570982312012-02-01T11:12:48.401+04:002012-02-01T11:12:48.401+04:0040? Понятно. Это я невнятно изложил. Файл pebbles....40? Понятно. Это я невнятно изложил. Файл pebbles.js начинается с предыдущего сообщения, т.е. с<br /><br />var N = 32; // максимальный ключ<br />var pebblesLimit = 12; // не считать больше, чем интересует<br />...<br /><br />А в следующем сообщении, начиная с<br /><br />var viewportOrig = 0, viewportSize = 34;<br />...<br /><br />- это его продолжениеДмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-5192097757562218492012-02-01T10:37:24.004+04:002012-02-01T10:37:24.004+04:00Дмитрий К,
да, ошибка в 40 строке файла pebbles.js...<b>Дмитрий К</b>,<br />да, ошибка в 40 строке файла pebbles.js (не определены N и K, речь о строке «td.innerHTML = (r < N) && (c < N) ? (K[r][c] ? K[r][c] : " ") : " ";»). И я глазами тоже не вижу их объявления.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-67988997253540261032012-02-01T10:07:38.548+04:002012-02-01T10:07:38.548+04:00Илья,
Я запускал в IE и FF. Проблем не наблюдал. ...<b>Илья,</b><br /><br />Я запускал в IE и FF. Проблем не наблюдал. Раз выводит шапку и на этом останавливается, вероятен какой-то exception в функции showK, т.к. она должна выводить квадратную таблицу размером viewportSize. Эти границы для нее определены безусловным образом. А FF что-нибудь пишет в консоль ошибок?Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-80517208077357320432012-02-01T09:44:59.130+04:002012-02-01T09:44:59.130+04:00Дмитрий К., каким браузером пользуетесь?
nik_vic, ...<b>Дмитрий К.</b>, каким браузером пользуетесь?<br /><b>nik_vic</b>, смогли разобраться?<br /><br />У меня ни в FF, ни в Chrome не заработало (т.е. выводит только шапку таблицы, а данные не отображаются). Есть идеи, как поправить?Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-43291176758787246392012-01-31T21:28:42.932+04:002012-01-31T21:28:42.932+04:00K(1,1)=0 - это да, это самая базовая база. Но если...K(1,1)=0 - это да, это самая базовая база. Но если в качестве базы служит целый столбец таблицы - это весьма существенное подспорье. В результате целый внутренний цикл заменяется разностью двух значений. Таблица заполняется слоями - вот этими вот дугами, которые образуют семейства одинаковых значений. Поэтому я не вычисляю h1 - оно на единицу больше предыдущего.Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-49354191919503774342012-01-31T21:12:07.406+04:002012-01-31T21:12:07.406+04:00==Но при этом где-то же должна быть и база==
Дык ...==Но при этом где-то же должна быть и база==<br /><br />Дык куда ж без неё: K(1,1)=0. И хватает ;)<br /><br />Насчёт 2535 - верно.<br />Настоящие комбинаторщики, небось, могут и производящую функцию сварганить...<br /><br />nik_vic ЖЖAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-12733582895872443832012-01-31T20:33:27.659+04:002012-01-31T20:33:27.659+04:00Пардон, наоборот. K(2535,2535)=26.Пардон, наоборот. K(2535,2535)=26.Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-88696301111237099672012-01-31T20:31:27.104+04:002012-01-31T20:31:27.104+04:00Вижу, что отдельно считается К(1,в) - фибоначчи. З...<i>Вижу, что отдельно считается К(1,в) - фибоначчи. Зачем?</i><br /><br />Вернее, так считается K(a,1). Затем, что каждый последующий шаг использует результат предыдущего. Но при этом где-то же должна быть и база.<br /><br /><i>Не вижу варианта типа моего...</i><br /><br />Ну да, у меня нет пристрелки.<br /><br /><i>И есть сильно ускоряющее<br />If s > NN Then s = NN<br />For i = a To s: K(i, b) = h1: Next i</i><br /><br />А вот этому и у меня есть аналог:<br /><br />while ((count-- > 0) && (r < N)) { K[r][c] = currPebbles; ++rFilling[r]; ++rFilled[r++]; }<br /><br /><i>До какого числа камней Вам удалось добраться?</i><br /><br />Так можно задавать разные значения N и pebblesLimit. Ну я подставил N=2540, pebblesLimit=27. Получил K(26,26)=2535.Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-87225765162494615002012-01-31T20:03:14.363+04:002012-01-31T20:03:14.363+04:00nik_vic ЖЖ
Вижу, что отдельно считается К(1,в) - ...nik_vic ЖЖ<br /><br />Вижу, что отдельно считается К(1,в) - фибоначчи. Зачем?<br />Не вижу варианта типа моего<br />For x = a - 1 To 1 Step -1<br />If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)<br />Next x<br /><br />Повторного захода нет и у меня. <br />И есть сильно ускоряющее (используется монотонность) - <br />If s > NN Then s = NN<br />For i = a To s: K(i, b) = h1: Next i<br /><br />До какого числа камней Вам удалось добраться?<br /><br />Там возможна ещё и экономия памяти - за счёт времени, разумеется.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-40251034026317446252012-01-31T19:11:47.614+04:002012-01-31T19:11:47.614+04:00Ну не знаю... Я вот только что прямо отсюда на дру...Ну не знаю... Я вот только что прямо отсюда на другой компьютер скопировал. И прекрасно сразу все пошло. Жаль только, что при вставке сюда программного кода форматирование пропало, это пришлось вручную восстанавливать, а то некрасиво. Надо в одну директорию поместить файлы pebbles.html и pebbles.js (здесь приведен в двух фрагментах).<br /><br />А оптимизация в том, что вся таблица заполняется одной тупой арифметикой, практически без логики - вся логика только в том, чтобы за границы не выйти. Ну и обход таблицы без повторного захода в просчитанные клетки.Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-48976518508201288832012-01-31T18:45:51.015+04:002012-01-31T18:45:51.015+04:00nik_vic ЖЖ
Дмитрий К.==А вот немножко оптимизиров...nik_vic ЖЖ<br /><br />Дмитрий К.==А вот немножко оптимизированный вариант.==<br />А в чём оптимизация? <br />Ваш pebbles.html не пошёл, пытаюсь разобраться...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-47187032712519562142012-01-31T15:32:17.543+04:002012-01-31T15:32:17.543+04:00Для визуализации создал pebbles.html:
<!DOCTYP...Для визуализации создал pebbles.html:<br /><br /><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><br /><br /><html xmlns="http://www.w3.org/1999/xhtml"><br /><head><br /> <title>pebbles</title><br /> <style type="text/css"><br /> table { margin-top: 2mm; border-collapse: collapse; }<br /> td { border: solid 1px black; text-align: center; }<br /> td.key { font-weight: bold; background-color: #cccccc; padding-left: 0.5ex; padding-right: 0.5ex; }<br /> td.diag { color: #aa0000; font-weight: bold; }<br /> td.count { width: 3ex; }<br /> td.portion { width: 6ex; border: none; }<br /> </style> <br /></head><br /><br /><script type="text/javascript" src="pebbles.js"></script><br /><br /><body onload="showK(); showP();"><br /><br /></body><br /></html><br /><br /><br />Функции showK и showP включил в pebbles.js:<br /><br />var viewportOrig = 0, viewportSize = 34;<br /><br />function showK()<br />{<br /> var tbl = document.createElement("table");<br /> tbl.cellSpacing = 0;<br /> document.getElementsByTagName("body")[0].appendChild(tbl);<br /> var tbd = document.createElement("tbody");<br /> tbl.appendChild(tbd);<br /> <br /> var tr = document.createElement("tr");<br /> tbd.appendChild(tr);<br /> for (var i = 0; i <= viewportSize; i++)<br /> {<br /> var td = document.createElement("td");<br /> tr.appendChild(td);<br /> td.className = "key";<br /> td.innerHTML = i == 0 ? " " : viewportOrig + i;<br /> }<br /> <br /> for (var i = 0; i < viewportSize; i++)<br /> {<br /> var r = viewportOrig + i; <br /> <br /> tr = document.createElement("tr");<br /> tbd.appendChild(tr);<br /> <br /> var td = document.createElement("td");<br /> td.className = "key";<br /> tr.appendChild(td);<br /> td.innerHTML = r+1;<br /> <br /> for (var j = 0; j < viewportSize; j++)<br /> {<br /> td = document.createElement("td");<br /> td.className = "count";<br /> if (j == i) td.className += " diag";<br /> tr.appendChild(td);<br /> var c = viewportOrig + j;<br /> td.innerHTML = (r < N) && (c < N) ? (K[r][c] ? K[r][c] : " ") : " ";<br /> }<br /> }<br />}<br /><br />function showP()<br />{<br /> var tbl = document.createElement("table");<br /> tbl.cellSpacing = 0;<br /> document.getElementsByTagName("body")[0].appendChild(tbl);<br /> var tbd = document.createElement("tbody");<br /> tbl.appendChild(tbd);<br /> <br /> for (var i = 0; i < viewportSize; i++)<br /> {<br /> var r = viewportOrig + i;<br /> if (r >= N) break;<br /> <br /> tr = document.createElement("tr");<br /> tbd.appendChild(tr);<br /> <br /> var td = document.createElement("td");<br /> td.className = "key";<br /> tr.appendChild(td);<br /> td.innerHTML = r+1;<br /> <br /> for (var j = 0; j < P[r].length; j++)<br /> {<br /> td = document.createElement("td");<br /> td.className = "portion";<br /> tr.appendChild(td);<br /> td.innerHTML = P[r][j];<br /> }<br /> }<br />}Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-39598826084532193012012-01-31T14:20:40.898+04:002012-01-31T14:20:40.898+04:00А вот немножко оптимизированный вариант. И заодно ...А вот немножко оптимизированный вариант. И заодно уж, наряду с таблицей K, заполняется и таблица P, содержащая правила разбиения для каждого ключа. При практическом применении такой таблицей пользоваться удобнее.<br /><br />var N = 32; // максимальный ключ<br />var pebblesLimit = 12; // не считать больше, чем интересует<br /><br />var fibCount;<br />var fib = new Array();<br />calcFib();<br /><br />function calcFib()<br />{<br /> fib[1] = fib[0] = 1; fibCount = 2;<br /> do fib[fibCount] = fib[fibCount-2] + fib[fibCount-1]; while (fib[fibCount++] < N);<br />}<br /><br />var K = new Array(); for (var i = 0; i < N; i++) { K[i] = new Array(); }<br />var rFilled = new Array(), rFilling = new Array(), cFilled = new Array();<br />rFilled[0] = cFilled[0] = 1;<br />for (var i = 1; i < N; i++) rFilled[i] = cFilled[i] = 0;<br /><br />var P = new Array(); for (var i = 0; i < N; i++) { P[i] = new Array(); }<br />var pFilled = new Array();<br />P[0][0] = 1; pFilled[0] = 1;<br />for (var i = 1; i < N; i++) pFilled[i] = 0;<br /><br />var cCompleted = 0;<br /><br />calcPebbles();<br /><br />function calcPebbles()<br />{<br /> var currPebbles = 2;<br /><br /> while ((currPebbles <= pebblesLimit) && (cCompleted < N))<br /> {<br /> var n = currPebbles < fibCount ? fib[currPebbles-1] : N;<br /> for (var c = cCompleted; c < n; c++) rFilling[c] = 0;<br /> for (var c = cCompleted; c < n; c++)<br /> {<br /> var r = cFilled[c];<br /> <br /> var count = c == 0 ? fib[currPebbles-2] : rFilled[c]-rFilling[c];<br /> <br /> var x = r+count;<br /> if (x <= N) P[c][pFilled[c]++] = count;<br /> if (x >= N) cCompleted++;<br /> <br /> cFilled[c] += count;<br /> while ((count-- > 0) && (r < N)) { K[r][c] = currPebbles; ++rFilling[r]; ++rFilled[r++]; }<br /> }<br /> currPebbles++;<br /> }<br />}Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-85107585413572584222012-01-25T11:36:43.355+04:002012-01-25T11:36:43.355+04:00nik_vic ЖЖ
Дмитрий К.==А вот 23х23 для 12 камней ...nik_vic ЖЖ<br /><br />Дмитрий К.==А вот 23х23 для 12 камней - это, на мой взгляд, многовато.==<br /><br />12 камней хватает даже для 24х23 - смотрите мою таблицу, строка 23.<br /> Первое разбиение - 24=13+7+3+1, бросается 1, 2, 3 либо 4 камня.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-77783258570148266362012-01-25T08:13:56.399+04:002012-01-25T08:13:56.399+04:00В самом деле, многовато получилось. Нашел-таки у с...В самом деле, многовато получилось. Нашел-таки у себя ошибку. Не всегда корректен такой способ пересчета массива D. Надо найти какой-то более корректный вариант. Соответственно, результат окажется поскромнее. Но вроде бы, не должно быть намного.<br /><br />А вот 23х23 для 12 камней - это, на мой взгляд, многовато. Поэтому и спрашиваю, получилось ли это у Вас. Не рассчитать количество (в чем можно и ошибиться), а именно указать, как каждый из участников зашифрует свое значение и как расшифрует значение партнера.Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-40844110032535030632012-01-23T21:49:13.849+04:002012-01-23T21:49:13.849+04:00nik_vic ЖЖ
Красные - на диагонали, в максимальном ...nik_vic ЖЖ<br />Красные - на диагонали, в максимальном положении для данного количества камней.<br />Вот главная часть программы - <br />=====<br />h1 = K(a - 1, b) 'pristrelka<br />AAA: h = h1: s = 0<br />For x = a - 1 To 1 Step -1<br />If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)<br />Next x<br />If s < a Then h1 = h1 + 1: GoTo AAA<br />If s > NN Then s = NN<br />For i = a To s: K(i, b) = h1: Next i<br />=====Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-63756793687259116582012-01-23T21:37:41.223+04:002012-01-23T21:37:41.223+04:00Ну конечно, я мог где-то и ошибиться. В процессе р...Ну конечно, я мог где-то и ошибиться. В процессе размышлений не раз ловил себя на ошибках. Если заметите ошибку - сообщите, пожалуйста.<br /><br />А что в Вашей таблице означают красные числа?<br /><br />Попробую. А скажите сразу, у Вас это получилось?Дмитрий К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-67860240755644317262012-01-23T20:28:42.551+04:002012-01-23T20:28:42.551+04:00nik_vic ЖЖ
Дмитрий К ==Выходит 2577==
Многовато......nik_vic ЖЖ<br />Дмитрий К ==Выходит 2577==<br />Многовато...<br />Попробуйте с Вашими идеями получить 23х23 для 12 камней или 31х31 для 13 камней.<br />http://www.ljplus.ru/img4/n/i/nik_vic/Shifr13-13.GIFAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-59662157638320551002012-01-23T10:52:04.089+04:002012-01-23T10:52:04.089+04:00Дмитрий К,
спасибо за такое подробное описание!
Я ...<b>Дмитрий К</b>,<br />спасибо за такое подробное описание!<br />Я уверен, многим будет интересно его прочитать.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-22990566371384790592012-01-23T08:38:33.276+04:002012-01-23T08:38:33.276+04:00А пожалуй, что от второй подзадачи (с k1+k2 камням...А пожалуй, что от второй подзадачи (с k1+k2 камнями) можно и вовсе отказаться. Решение станет красивее. Если один из игроков делает максимальный ход, то второй применяет алгоритм односторонней передачи. В противном случае, по результатам пары ходов (А+Б) каждый пересчитывает свой массив D.Дмитрий К.noreply@blogger.com