Имеются ли в PascalABC.Net какие либо ключи, позволяющие задать требуемый размер кеша (в частности - больше размера по умолчанию), либо ключи позволяющие для переменной структурированного типа (например массив) данных задать допустимый размер более 2 Гб? Так например, я не могу создать массив типа integer содержащий более 536 870 897 элементов. Существует ли какой то выход из подобной ситуации (вариант разбить на два массива с меньшим количеством элементов не предлагать)?
спасибо, но боюсь этот метод не очень удобен с позиции его использования на ЕГЭ. на ЕГЭ быстрее будет разделить на 2 массива. тем более, тип задач, где такое необходимо, встречается крайне редко. я думал может быть какие-то ключи компилятора можно использовать. тогда можно было бы просто запомнить ключ.
На ЕГЭ такие задачи вообще встречаться не должны. Скорее, вместо использования таких огромных массивов, надо додуматься до более качественного алгоритма.
Они и не встречаются. Задача должна решаться на любом из “допущенных к ЕГЭ” языков программирования, а тот же Python, не умеющий эффективно использовать оперативную память с полумиллиардными массивами просто загнётся. Мы же помним, что там объекты немутабельны и почти любая модификация идет через копирование. Так что это вопрос из области “А что бы еще такое про PascalАВС.NЕТ придумать, чтобы показать, что и на Солнце пятна бывают?”
Речь абсолютно не о том, что я пытаюсь кинуть камень в огород PascalABC.Net. Когда ко мне обратились люди я сразу сказал что готовиться будем на PascalABC.Net, потому что, по моему мнению, возможности, которые дает связка “LINQ+регулярные выражения+Модуль School+Модуль SF+[cache]” является лучшей с точки зрения предоставляемых возможностей на ЕГЭ и в некоторых ситуациях заставляет Python нервно курить в сторонке. В связи с этим, я думаю, следует немного прояснить ситуацию. Речь идет о задачах на рекурсивные функции. Тема №16. По регламенту примерное время, отводимое на решение задачи, составляет 5 минут. Попытка решить задачу используя рекурсивную функцию уперлась в объем кеша. Без кеширования даже нет смысла пытаться (поскольку в этой ситуации бутылочным горлышком станет время). Для решения задачи был выбран другой метод. Я позже его покажу. Я предлагаю коллегам, высказавшим свое мнение по поводу сложившейся ситуации попробовать решить эту задачу за 5 минут с помощью более качественного алгоритма. Когда вы начнете читать следующее сообщение с условием задачи то первым делом взгляните на текущее время в углу экрана. И далее у Вас приблизительно 5 -10 минут. Этих минут должно хватить на то чтобы прочесть условие, осмыслить задачу, придумать решение,написать код и получить ответ. Я сразу информирую о том, что до эффективного решения, до которого нужно додуматься лично я не додумался за 5 минут (то есть до кода и тем более до результата дело вообще не дошло), но возможно у Вас получится, потому что Вы знаете, что решение в лоб (рекурсия с кешем) имеет определенные проблемы. Если вы получите результат за 10 минут, то можно считать задачу успешно решенной. Единственная просьба - быть честными, поскольку можно быстро найти решение в интернет и перевести его на Паскаль (хотя я этого все равно делать не стал). Но сейчас основная проблема в другом: это тема с задачами на “Вычисление рекуррентных вы-
ражений”, решение должно быть достаточно простым чтобы его можно было осмыслить и написать программу - и отсюда вопрос: “по вашему мнению соответствует ли данная задача выше описанным критериям по сложности и времени?”. По моему мнению - нет, но такая задача есть на сайте Полякова (любой, кто хоть как-то связан с ЕГЭ по информатике, знает кто такой К.Ю.Поляков и знает об этом сайте), и нужно решение, которое позволит, размышляя именно логикой рекурсивных вычислений, быстро получить результат (решение это есть и я приведу его позже - после того, как Вы выскажете свое мнение).
##
var values := new List<integer>;
values += 5;
var to_process := new Stack<(integer,integer)>;
to_process += (0,5);
//var res := new HashSet<integer>;
var res_c := 0;
var target := 7;
var max_n := 1000000000;
while to_process.Count<>0 do
begin
var (n,v) := to_process.Pop;
if n>max_n then continue;
if v=target then while n<=max_n do
begin
// Дубликаты никогда не появляются
// if not res.Add(n) then
// $'{n} added twice'.Println;
res_c += 1;
n := n*2+1;
end else
begin
if v>target then raise new System.InvalidOperationException;
to_process += (n*2, v+1);
to_process += (n*2+1, v);
end;
end;
//res.Count.Print;
res_c.Print;
Ответ 4150.
Время 15:41
Я ещё отвлёкся посреди этой задачи, но всё равно - рад что не мне давно не приходилось экрамены на время писать)) Я б под этим давлением быстро согнулся бы…
1 первичный балл не заработали. Значит минус 2 или 3 итоговых балла. а это всего лишь тема 16. и ответ не верный (верный ответ указан в сообщении). Ну как, по Вашему мнению, задача соответствует задаче на 5 минут?
Подождем еще, возможно Александр откликнется на челендж, и объявит свой вердикт.
Нет ну на самом деле я наверняка мог бы потренироваться и решать такое значительно быстрее, если б мне оно надо было.
Но всё же ограничивать время на столько - выглядит странно. Когда я сдавал своё ЗНО (Украинский аналог ЕГЭ) - задачи и время были рассчитаны так, что я с практически 0 подготовкой, за счёт общей логики таки успел всё решить, изобретя несколько велосипедов в процессе. Ну, это по математике, программирования у нас там не было.
С другой стороны мож смысл и есть, и это я оказался разбалован после моих минимальных усилий по подготовке к ЗНО…
эта задача вполне могла бы быть задачей такого типа, с которым ученик ни разу не сталкивался, и за 5 минут он должен прочесть, понять, осмыслить что кеш загнется и рекурсивная функция тут не применима, далее он должен начать думать: какое же математическое решение могло бы быть у этой задачи? затем написать программу для найденного решения. и все это за 5 минут (ну хотя бы за 10). иногда мне кажется что составители задач забывают о времени отведенном на решение задач по теме.
Могу и откликнуться. Годятся числа, имеющие ровно два нуля в двоичном представлении.
function Suited(n: integer): boolean;
begin
var k := 0;
while n >= 2 do
begin
if n mod 2 = 0 then
begin
if k = 2 then
begin
Result := False;
exit
end
else Inc(k)
end;
n := n div 2
end;
Result := k = 2;
end;
begin
var m := 1000000000;
var k := 0;
for var i := 1 to m do
if Suited(i) then Inc(k);
Println(MillisecondsDelta / 1000);
Println(k);
Readln
end.
Составители извращаются, как могут. Не понимаю, то ли это выпендрёж, то ли они забывают о лимите времени и о том, что дети не изучали курс дискретного анализа и не занимаются спортивным программированием.
ну теперь обещанное решение.
оно реализовано заменой функции на массив (можно сказать мы берем на себя процесс кеширования результатов) и разбиением массива на две части:
var (arr0,arr1) := (arrfill(500000001,0),arrfill(500000001,0));
var cnt:=0;
for var n:=0 to 500000000 do
if n=0
then arr0[n]:=5
else arr0[n]:=n mod 2 = 0?1+arr0[n div 2]:arr0[n div 2];
for var n:=0 to 500000000 do
if n=0 then arr1[n]:=arr0[500000000]
else arr1[n]:=n mod 2 = 0?1+arr0[(n+500000000) div 2]:arr0[(n+500000000) div 2];
for var n:=0 to 500000000 do
if arr0[n]=7 then cnt+=1;
for var n:=1 to 500000000 do //пропускаем 0-элем-т, т.к. arr0[500000000]=arr1[0]
if arr1[n]=7 then cnt+=1;
prln(cnt);
дальнейший анализ показал следующее: учитывая что значение функции использует значение на предыдущем шаге, номер которого равен половине номера текущего шага, то для шага с номером 10^9 максимальная длина цепочки шагов рекурсии составляет 29 шагов т.к. 10^9 <2^30. каждый шаг при “удачном” стечении обстоятельств может добавить единицу в общую копилку результата. то есть максимально возможно значение функции на интервале [1,1000000000] составляет 34 = 5 (значение f(0)) + 29. Это позволяет перейти к массиву с типом данных размерностью 2 и менее байт (shortint, smallint,byte,word), что позволяет уложиться в отведенные 2 Гб. и код станет таким.
var arr:=arrfill(1000000001,word(0));
var cnt:=0;
for var n:=0 to 1000000000 do
if n=0
then arr[n]:=5
else arr[n]:=(n mod 2 = 0)?1+arr[n div 2]:arr[n div 2];
for var n:=0 to 1000000000 do
if arr[n]=7 then cnt+=1;
prln(cnt);
на мой взгляд абсолютно нельзя отнести данную задачу к задачам с примерным временем решения - 5 минут (при условии, что сдающий егэ не сталкивался с такой задачей раньше). ну мы не уложились ни в 5, ни в 10 минут. сначала мы с учеником за несколько минут переложили задачу на код в лоб, получили переполнение кеша, переделали используя массив снова получили превышение размера массива в памяти. после чего начали размышлять над поиском “эффективного алгоритма”, не придумав ничего быстро, начали искать верхний потолок для массива, выяснили что он упирается в 2 гига, разбили массив на 2 части и решили задачу. на все потратили в общей сложности около 20 минут, решение с массивом типа (word, byte …) это уже решение найденное путем анализа первоначального решения. собственно решение этой задачи и породило вопросы о возможности изменения максимального размера кеша или размера объектов данных.
И тогда сразу было бы понятно, что четырехбайтный кэш не обеспечит хранение миллиарда значений, следовательно, нужно или иной путь искать, или писать собственный кэш с элементами длиной 1-2 байта для решения “в лоб”. А поскольку для хэша нужно иметь хэш-функцию, все равно пришли бы к количеству нулей в двоичном коде аргумента, а тогда и хэш не нужен, поскольку условию удовлетворяют только значения, имеющие в двоичном коде ровно два нуля.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021