Среда "съедает" всю доступную ОЗУ при отладке

Разбираю свои задачи после олимпиады. Я уже нашел алгоритм решения, и написал его, осталось отладить и найте некоторые ошибки. Проблема в том, что входя в режим отладки и переключаясь на вкладку “Локальные переменные”, графиг загруженности ОЗУ - резко начинает стримиться в космос. После - среда зависает, и приходится завершать процесс. При чём, когда я остаюсь во вкладке “Окно вывода” - все прекрасно. Скриншоты и исходники задачи с тестами и самим заданием можно найти в ЭТОМ архиве. В виртуалке с ВинХП на Линуксе - то-же самое.

Я так полагаю это из-за того, что среда пытается прогрузить массивы 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.
1 симпатия

Благодарю за алгоритм! На олимпиаде сначала сам хотел решать через рекурсию, но т.к. я с ней до этого не работал - для меня это было в новинку, и ничего не вышло. И было принято решение, приведенное мной выше. Буду совершенствоваться. : -) Кстати, забыл скинуть таблицу ответов на тесты. Для некоторых 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.

Попробуйте заменить вывод в основном цикле

  Get:= GetVal(i, len, n); 
  write(i, ' - ',Get,'   ' ); 
  ToBinary(i); write('  -  '); ToBinary(Get); 
  writeln(); 

на такой

  Get:= GetVal(i, len, n); 
  ToBinary(i); write('  -  ',Get);
  writeln(); 

И всё тайное станет явным.

Да, нашел взаимосвязь! Одно слово: гениально! Я бы никогда не додумался до такого алгоритма. Как вам это удается?! Но опять, же. Когда нибудь x - выйдет за пределы типа int64. А это произойдет, тогда, когда n будет равно 63, специально проверил. И этот алгоритм будет не дееспособным. Я так понимаю, что дальше - решается только длинной арифметикой(или у вас еще есть гениальные мысли?:smiley: ). К сожалению, плохо знаком с ней. В любом случае, благодарю за помощь и поддержку. Буду думать дальше. Хочу добить эту задачу.

 
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.
1 симпатия