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

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.

Ұқсас тақырыптар:

• Информатика бойынша олимпиада есептерінің шығарылуы, II этап, 2009-2010.
• Информатика. Аудандық олимпиада есептерінің шығарылуы, II этап, 2008-2009
• Қалалық олимпиада тапсырмалары 2012.
• 21.12.2012. Информатика аудандық олимпиада. 8-9 сынып. І-тур.
• 21-22.12.2012. Информатикадан аудандық олимпиада есептері шығаруларымен. 10-11сынып. І-ІІ тур.
• 2008-2009 Олимпиада есептері шешулерімен.
• 2012-2013 аудандық олимпиада есептері ІІ тур (Ауданов Махсет, Маңғыстау облысы)
• 2012-2013 орта мектептерге келген олимпиада есептері, шешулерімен (Ақтөбе облысы бойынша).
• Паскалдан жиі қолданыстағы тақырыптық есептер (40 есеп+шешуі).
• 22.12.2012. Информатикадан аудандық олимпиада есептері шығаруларымен. 8-9 сынып. ІІ-тур.