Разбираю свои задачи после олимпиады. Я уже нашел алгоритм решения, и
написал его, осталось отладить и найте некоторые ошибки. Проблема в том,
что входя в режим отладки и переключаясь на вкладку “Локальные
переменные”, графиг загруженности ОЗУ - резко начинает стримиться в
космос. После - среда зависает, и приходится завершать процесс. При чём, когда я остаюсь во вкладке “Окно вывода” - все
прекрасно. Скриншоты и исходники задачи с тестами и самим заданием можно
найти в ЭТОМ архиве. В виртуалке с ВинХП на Линуксе - то-же самое.
Я так полагаю это из-за того, что среда пытается прогрузить массивы A и TMP. Которые к слову, от 1 до 500 миллионов, но то-же самое происходит(только заполняется память дольше) и если верхний индекс массиа = 1 000, что в принципе, совсем не много.
Версия 3.0. Сборка 1092 (07.12.15)
У меня с массивами размером на 1000 ошибка не воспроизводится. А с исходным размером на 500М элементов – да, памяти не хватает.
Вообще, вполне логичное поведение, зачем там массивы почти по 2 Гб каждый – непонятно. У вас только на данные используется ~3.5 Гб, это явно плохое решение для олимпиадной задачи. Она решается либо совсем без массивов, либо с массивом на 1000 элементов.
Я это к тому, что ошибки вообще нет, когда я нахожусь в окне вывода. Т.е. прогружать массивы он начинает именно для отображения во вкладке Лок. переменных. Но, на вкладку Локальных переменных - переключаться придется в любом случае. Какое решение я предлагаю: отображать в Лок. Переменных не весь массив, а только те его переменные, значения которым присвоено. Ибо логично, что все остальные - будут равны нулю. А если присвоение будет идти, например через один, или через несколько нулей, то указывать например так: 1, 2, 3 …0(5)… ,77, 14 … 0(10). что будет означать что между элементами “3” и “77” - 5 нулей.
Предлагаю добавить эту фичу по галке в настройках, для работы с объемными массивами.
Хотя, возможно и можно как-то по другому решить эту задачу, но решения в голову приходит только это.
Кстати, я на C# где то с месяца 2 назад решал довольно объемную задачу, где были огромные массивы(поболее этих), и ничего не то висло, и памяти много не кушало.
Ув. Константин, тут задача подобрана так, чтобы не решалась через генерацию всей последовательности, и она не решается. Можно, конечно, обратиться к разработчикам PascalABC.Net с просьбой обеспечить поддержку больших массивов, только имейте в виду, что для этой задачи даже простой алгоритм без массивов за 0.13 сек находит все решения для x от 1 до 1000. Код привести?
В исходных данных N избыточно – нам номер последовательности не нужен, только X, т.к. в любой последовательности достаточной длины на заданном месте будет стоять одно и то же значение. Поэтому для решения нужен только X, а номер N и длину последовательности len (она нам тоже понадобится) мы вычисляем сами, на основе значения X (в приведённой программе – до 1000, но можно просто до X). Ну и потом – рекурсивное решение, не самое удачное по эффективности, но достаточно быстро работающее.
function GetVal(x,len,n:integer):integer;
var center : integer;
begin
center := len div 2 + 1;
if x = center then GetVal := n
else
if x<center then GetVal := GetVal(x,center-1,n-1)
else
GetVal := GetVal(x-center,center-1,n-1);
end;
var len,n : integer;
begin
len := 1; n:=1;
while len<1000 do
begin
n:=n+1;
len := 2*len + 1;
end;
for var i:=1 to 1000 do
writeln(i,' - ',GetVal(i,len,n));
writeln('Затрачено ',Milliseconds, ' миллисекунд');
end.
Благодарю за алгоритм! На олимпиаде сначала сам хотел решать через рекурсию, но т.к. я с ней до этого не работал - для меня это было в новинку, и ничего не вышло. И было принято решение, приведенное мной выше. Буду совершенствоваться. : -)
Кстати, забыл скинуть таблицу ответов на тесты. Для некоторых x - ответы не совпадают. Поинтересуюсь у тех, кто составлял тесты. - отпишусь.
Тесты не проходит потому, что они были написаны неверно. Проверяющие сами не верно прочли условие… Они рассматривали последовательность - как последовательность цифр идущих без пробелов, а не чисел. т.е. например, 10 - они разбивали как 1 и 0, и соответственно для n >= 10, а x>=половины последовательности, уже ни один тест задача не проходила. У вас все верно. Еще раз благодарю.
Кстати, это решение, хоть и довольно лаконичное и быстрое, но оно не является самым оптимальным… Я имею ввиду, что для n>35 (уже, используя тип longint), большую часть тестов задача не пройдет, т.к. length уже будет выходить за границы типа. А я напомню, что n может = 1000. Соответственно, правильным решением будет использовать массив. Либо использовать C++, где есть типы с огромными диапазонами значений(и то, не факт что их хватит). Да, на олимпиаде, для решения задач можно использовать С, С++ и Паскаль. Но на данный момент плюсы не знаю. Теперь буду учить. Либо, использовать длинную арифметику, что для меня вовсе темный лес. Либо, у этой задачи нет полного решения вовсе. Ибо, часто на олимпиадах дают задания, которые не решаемы на 100%.
По поводу вашего решения: Я понял, как это все взаимодействует, но так и не понял - чем вы руководствовались, придумывая этот алгоритм, как проходила логическо-следственная цепочка, в процессе написания функции? Ну, не знаю как еще перефразировать. Надеюсь, вы поняли, о чем я вас спросил.
По алгоритму всё очень просто. Там даже на примерах видно, что начало последовательности всегда одинаковое, и в последовательности любой длины на одном и том же месте всегда будет находиться одно и то же значение. Далее, определение последовательности рекурсивное, то есть последовательность длины N строится на основе двух последовательностей длины N-1 – значит, и решать можно тоже рекурсивно. Нужно просто знать, как выразить элемент последовательности F(N) через последовательность F(N-1). Допустим, нам нужен элемент с номером x в последовательности F(N). Если x – это номер центрального элемента последовательности, то сам элемент равен N. Если x меньше половины длины, то точно такой же элемент будет расположен на месте x в последовательности F(N-1). Ну и для третьего случая тоже не слишком сложно.
«Но на данный момент плюсы не знаю. Теперь буду учить» – я бы не советовал. Для олимпиад необходимости особой в этом языке нет, а для самостоятельного обучения язык не подходит. И не потому, что сложный, а потому что многогранный, и очень легко приучиться программировать на нём неправильно.
А по поводу задачи – ну да, есть что улучшать. Приведённый мною код можно улучшить – сократить программу ровно в два раза, обойтись без длины последовательности, и работать будет ещё быстрее. Вот и попробуйте сделать, надеюсь, двоичную систему счисления знаете и сможете использовать. Выпишите решения для разных x, посмотрите на двоичное представление x и на соответствующий ответ, и всё должно получиться.
Предыдущий алгоритм был завязан именно на длине последовательности. Если не использовать длину, то получается уже совсем другой алгоритм. Я так понял, вы хотели натолкнуть меня на то, чтобы я нашел некую взаимосвязь между десятичным и двоичным представлением Х-са. Но, как я только не извращался - не нашел взаимосвязи.
function GetVal(x, len, n: integer): integer;
var
center: integer;
begin
center := len div 2 + 1;
if x = center then GetVal := n
else
if x < center then GetVal := GetVal(x, center - 1, n - 1)
else
GetVal := GetVal(x - center, center - 1, n - 1);
end;
Procedure ToBinary(n: integer);
var
a: array[1..100] of byte;
i, c: integer;
begin
c := 0;
repeat
c := c + 1;
a[c] := n mod 2;
n := n div 2;
until n = 0;
for i := c downto 1 do
write(a[i]);
end;
var
Get, len, n: integer;
begin
len := 1; n := 1;
while len < 1000 do
begin
n := n + 1;
len := 2 * len + 1;
end;
for var i := 1 to 1000 do
begin
Get:= GetVal(i, len, n);
write(i, ' - ',Get,' ' );
ToBinary(i); Write(' - '); ToBinary(Get);
Writeln();
end;
writeln('Затрачено ', Milliseconds, ' миллисекунд');
end.
Да, нашел взаимосвязь! Одно слово: гениально! Я бы никогда не додумался до такого алгоритма. Как вам это удается?!
Но опять, же. Когда нибудь x - выйдет за пределы типа int64. А это произойдет, тогда, когда n будет равно 63, специально проверил. И этот алгоритм будет не дееспособным. Я так понимаю, что дальше - решается только длинной арифметикой(или у вас еще есть гениальные мысли? ). К сожалению, плохо знаком с ней. В любом случае, благодарю за помощь и поддержку. Буду думать дальше. Хочу добить эту задачу.
function Main(n: integer): integer;
var
a: array[1..1000] of byte;
i, ans: integer;
begin
while n <> 0 do
begin
inc(i);
a[i] := n mod 2;
n := n div 2;
if a[i] = 0 then
inc(ans) else
begin
inc(ans); break;
end;
end;
Main := ans;
end;
var
f: text;
x, an: int64;
begin
Assign(f, 'D.in'); reset(f);
Read(f, x); Read(f, x);
an := Main(x);
writeln(an);
writeln('Затрачено ', Milliseconds, ' миллисекунд.');
close(f);
end.
В этой задаче N не нужно и не используется. Это уловка – указать в исходных данных лишнюю информацию, чтобы от неё отталкивались и пытались генерировать последовательность. И я сильно сомневаюсь, что X может быть в условии настолько большим, что не поместится в значение типа uint64 – иначе его просто из файла не прочесть будет, всё же задача предназначена для оценки умения строить алгоритмы, а не учитывать фантастические случаи. Так что идей больше нет, алгоритм разобран до удобоваримого состояния, хотя можно программу немного сократить – зачем тут массив А?
Впрочем, если хотите пример использования длинной арифметики – пожалуйста, PascalABC.Net и это умеет.
Нахождение максимального значения X
begin
var P := BigInteger(1);
var k := 1;
while k<1000 do
begin
P := P*2+1;
k+=1;
end;
writeln('Максимальная длина последовательности = ',P);
end.
А вот так выглядит решение задачи (при условии, что исходные данные читаем из файла ‘D.in’)
begin
var P := BigInteger.Parse(ReadAllText('D.in').ToWords()[1]);
var D := BigInteger(2);
var k := 1;
while P.IsEven do
begin
P := P/2;
inc(k);
end;
writeln(k);
end.
). К сожалению, плохо знаком с ней. В любом случае, благодарю за помощь и поддержку. Буду думать дальше. Хочу добить эту задачу.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021