Много раз пытался сдать 198B - прыжки по стенам. Вроде бы вполне осмысленное решение -
- код ниже — получает RE на 12 тесте. Но это не самое интересное — я поглядел 12 тест и
обнаружил, что на том же тесте с длиной прыжка 56465 все нормально, а при длине 56466 — уже RE. Но и это не все. Мистика (для меня) состоит в том, что при чистке кода я обнаружил, что при удалении ненужных (нигде не используемых) переменных это самое число 56465 изменяется на несколько сотен. Я, естественно, понимаю, что один дурак может задать столько вопросов, что тысяча мудрецов не ответит, но все же, может кто что подскажет... (Для меня это — третья по счету задача с использованием рекурсии, а может и не в рекурсии дело). Заранее благодарен за подсказку.
program pr1;
{$APPTYPE CONSOLE} var n,k,i,j:longint; t:array[0..1,0..1000000] of int64; flag:boolean; marked: array [0..1,0..1000000] of boolean; sss:array[0..1] of string;
procedure dfs(num,pl,shag:longint); var i,p:longint;
begin if shag<pl then begin marked[num,pl]:=true; inc(shag); t[num,pl]:=shag; if not marked[1-num,pl+k] and (sss[1-num,pl+k]='-')and(pl<=n) then dfs(1-num,pl+k,shag); if not marked[num,pl+1] and (sss[num,pl+1]='-')and(pl<n+k) then dfs(num,pl+1,shag); if not marked[num,pl-1] and (sss[num,pl-1]='-')and(pl>1) then dfs(num,pl-1,shag); end;
end;
begin {assign (input,'input.txt');reset(input); assign (output,'output.txt'); rewrite(output); } readln(n,k); readln(sss[0]);readln(sss[1]); for i:=1 to 100000 do sss[0]:=sss[0]+'-'; for i:=1 to 100000 do sss[1]:=sss[1]+'-'; for i:=0 to n+k do begin t[0,i]:=1000000; t[1,i]:=1000000; end; t[0,1]:=0; dfs(0,1,0); flag:=false; for i:=n+1 to n+k do if (t[1,i]<1000000) or (t[0,i]<1000000) then begin flag:=true; end; if flag then write('YES') else write('NO'); close(output); end.
Установите размер стека с помощью директивы {$MAXSTACKSIZE [размер в байтах]}. Я обычно ставлю 128МБ (правда, для Java).
Так вот — попробовал поставить очень большую константу — 2М — эффект тот же, те же самые 56465 — граница. При меньших размерах стека граница становится меньше.
Какого черта Вы жлобитесь? Поставьте сразу 128М. Там дефолтный размер-то, вроде бы, 1М.
Все то же. Или даже еще хуже. Может и не в рекурсии дело????
Я сейчас посмотрел: ошибка 216, которую выкидывает Ваша программа (и про которую Вы не удосужились погуглить) — повреждение памяти.
Вопрос первый — из-за чего? И второй — и что делать??? (Я не очень-то и программист).
Вопрос третий: а кто Вы? Вопрос четвертый: почему Вы за полтора года участия на Codeforces так и не стали очень-программистом? Вопрос пятый: почему бы самостоятельно не подумать?
Ой, а можно полную версию анекдота?
Сначала разберусь с проблемой, а потом — анекдот. Утром — деньги, вечером — стулья.
Ну и где анекдот?)
1834980
Кажется в Delphi есть директива MINSTACKSIZE (кроме MAXSTACKSIZE). Её и нужно установить
Спасибо, но пока воз и ныне там — 56465. (При любых размерах стека)
Я почитал: первоначально размер стека устанавливается в значение MINSTACKSIZE, потом, если его не хватает, постепенно увеличивается, но не более, чем до MAXSTACKSIZE.
Да в стеке дело, инфа соточка. Кинь как именно ты написал строку устанавливающую размер стека. А если ты действительно хочешь чтобы хоть кто то глянул на код, то приведи в божеский вид, так читать невозможно.
проще всего отредактировать запись, ну или же сделать ссылку на посылку 1834501
Я пишу на С# и тоже всегда ловлю RE на DFSах. Вот здесь http://codeforces.net/blog/entry/79#comment-94622 я описал подробно почему это случается, и почему это нельзя пофиксить своими силами, видимо тут то же самое. Пока никакой реакции, так что могу посоветовать менять по возможности на BFS, писать нерекурсивную реализацию или учить что-то другое (плюсы)
А на Codeforces код разве запускается как частично доверенный? Мне казалось, что там делается так: клонируется виртуальная машина, на этом клоне запускается решение, а потом этот клон убивается. При такой конфигурации вроде бы вообще нет резона ограничивать "доверенность".
ИМХО, дело в том, что на CF стоит не .NET Framework, а Mono.
Я, кстати, через вкладку "Запуск" запускал исходники, читающие ключи реестра (чтобы узнать, какие процессоры стоят на серверах).
1834680
Парень женился на старшей из трех сестер. Все безмерно рады. Через год приезжает — "Какое горе, жена померла". Ну ему по традиции дали в жены среднюю. Через год тот снова появляется — и прямо с порога : "Папаша , вы таки будете смяться, но Ваша Сонечка таки тоже померла! "
Просто у тебя в рекурсии будет использовать елементы строки которых нет... естественно будет рантайм ерор
А я анекдот не понял.
"по традиции дали в жены среднюю" О_о Какая-то сильно повышенная смертность жён, раз уже традиции появились.
Да, и чуть не забыл, с меня шоколадка. Будете у нас в Новосибирске на Всесибирской (где-то в ноябре )- тут же отдам. Вторая шоколадка тому, кто объяснит, в чем же дело. Важно ведь разобраться, чтобы в дальнейшем подобных проблем не было.
Так вот!!! Дело вовсе не в стеке. Можно вообще про стек ничего не описывать. Достаточно просто к строке добавить не 10^5, а 198000 пробелов (195000 не хватает)- и все OK. Но почему??? Как все-таки работает рекурсия. Кто-нибудь понимает? Вроде бы нигде в проге к далеким элементам строки я не обращаюсь.
(sss[1-num,pl+k]='-') у тебя выходит за 100000 ...
UPD.Всё верно, прошло, вот этому подтверждение 1835200
Omelianenko правильно говорит, что нужно вначале проверить, что не выходит за границы массива, а потом уже смотреть что там в массиве лежит.
Суть в том, что оператор (A and B) работает по такому принципу: вначале проверяется A, если оно верно, то проверяется B, иначе B не проверяется, ибо смысла в этом нет. Поэтому важно вначале проверить выход за границы массива, чтобы если мы вышли, то второе условие не проверялось, если же переставить местами, то вначале мы проверяем ячейку массива, которой фактически нет, а дальше мы уже ничего не будем проверять, потому что у нас вылетит рантайм, ибо мы не можем проверять того чего нет.
Оператор (A or B), кстати, тоже работает интересно: если A — true, то смысла проверять B нету, поэтому вот такой код хорошо сработает:
Нужно очень тщательно следить за тем, не выходите ли вы за границы массива, причём не просто лепить проверки, а в каждой строчке кода понимать, какие значения могут принимать индексы массива, к которым обращаемся.
И ещё хочу кое-что сказать. В С++ проверки за границы массива выключены по умолчанию (не знаю, можно ли их включить), поэтому если создать массив int a[10] (это массив int размера 10, с индексами от 0, то есть 0..9) и обращаться например к 20-му элементу массива a[20], то может так произойти, что рантайма не выскочит, хоть может и выскочить, зависит это от того, что будет храниться в ячейке памяти отстоящей на 20*4 байт от начала массива a, если будет ваша программа, то права на эту ячейку памяти у неё есть и она просто возьмёт оттуда данные (понятно, что совсем некорректные и ненужные и вообще чужие), и ещё хуже будет если она туда запишет данные, тем самым испортив какие-то чужие данные, если же эта ячейка памяти вообще не принадлежит вашей программе, то будет сгенерирован рантайм ошибка доступа. В паскале так тоже может происходить, но там по умолчанию включена проверка на выход за границы массива, но какая-то директива (не помню какая, можно погуглить) отключает эту проверку. Так что, ещё раз говорю, нужно быть осторожным с границами, иначе можно не просто рантайм получить, а вообще неадекватное поведение программы (например можно случайно в результате выхода за границы массива и обращения к ячейке памяти, в которой лежит например значение переменной n, от которой зависит текущий цикл, затереть это значение n и уйти в бесконечный цикл).
Директива для отключения проверки выхода в паскале —
{$R-}Может, строки в Delphi, как C++ vector-ы, автоматически ресайзятся, когда это необходимо? Вот и получается несколько нулей про запас в конце.
Попробуй написать в самом верху кода {$M 128000000}