21-22.12.2012. Информатикадан аудандық олимпиада Көп сандар E есебі (пікір).

Ергали Курмангалиев

21-22.12.2012. Информатикадан аудандық олимпиада есептері шығаруларымен. 10-11сынып. І-ІІ тур мақаласына пікір

Көп сандар (E есебі) есебінде сандарды қос-қостан алып, көбейтіп салыстырған тиімсіз. Себебі 1 <= N <= 1000000 шектеуі тұр. Мысалы N=1000000 болғанда (ондай тест жасауға болады) алгоритм уақыттан ұтылып қалады. Қос-қостан салыстырғанда алгоритмнің қиындығы N*(N-1)/2, яғни N=1000000 болғанда алгоритм 499 999  500 000 қадам орындайды деген сөз. Тактілі жиілігі орта есеппен 3 ГГц болатын компьютер, секундына 3*10^9 операция ғана орындай алады десек бұл есепті 166,67 секундта орындап шығады. Ал олимпиаданың талабы бойынша есеп 1-2 секундта (есеп шартына байланысты) шығуы керек.

Сондықтан мынадай тиімді алгоритм ұсынылады: Әуелі максимал элемент және одан кейінгі екінші максимал, сондай-ақ минимал және одан кейінгі екінші минимал элементтер табылады. Екі максимумның көбейтіндісі немесе екі минимумның көбейтіндісі есептелінеді. Осылардың қайсысы үлкен сол есептің жауабы болады. Бұл жерде екі үлкен санның көбейтіндісі үлкен сан болады деген математикадан белгілі ережеге сүйенеміз. Екі минимал элемент теріс сандар болған кезде қолданылады. Бұл алгоритмнің қиындығы 4 салыстыру болғандықтан 4*1000000=4000000. Яғни, есеп 1 секундқа жетпейтін уақытта шығады.

Есептің шешімі (Free Pascal):
Var a:array[1..1000000] of longint;
n,i,max,min,p,q:longint;
t1,t2:int64;
begin
assign(input,’e.in’);
assign(output,’e.out’);
reset(input);rewrite(output);
read(n);
for i:=1 to n do read(a[i]);
max:=a[1]; p:=1;
min:=a[1]; q:=1;
for i:=2 to n do begin
if a[i]>max then begin max:=a[i]; p:=i; end;
if a[i]<min then begin min:=a[i]; q:=i; end; end;
t1:=max; t2:=min;
a[p]:=a[1]; a[1]:=max;
max:=a[2];
for i:=3 to n do
if a[i]>max then max:=a[i];
a[1]:=a[p]; a[p]:=t1;
t1:=t1*max;
a[q]:=a[1]; a[1]:=min;
min:=a[2];
for i:=3 to n do
if a[i]<min then min:=a[i];
t2:=t2*min;
if t1>t2 then write(t1) else write(t2);
close(input);
close(output);
end.

Төмендегідей кодпен үлкен көлемді тест жасап тексерілген:
var i:longint;
begin
randomize;
assign(output,’e.in’);rewrite(output);
writeln(1000000);
for i:=1 to 1000000 do write(round(2000000*random-1000000),’ ‘);
close(output);
end.

Check Also

Информатитка пәнінен олимпиадаға даярлаудың тиімді жолдары

Жуалы ауданы, №2 Мыңбұлақ орта мектебі информатика пәні мұғалімі Сабиев Бахытжан Төребайұлы.  Олимпиада – бұл …

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.