Информатика. Аудандық олимпиада есептерінің шығарылуы, II этап, 2008-2009

Баймуханбетова Ж.С
«Өскемен қаласының ресурс орталығы» ММ, «Қашықтықтан білім беру және кәсіптік оқыту» тобының әдіскері

A есебі. ШеңберШеңберде бір-бірінен бірдей қашықтықта N нүктелер белгіленген, олар сағат тіліне қарсы 1-ден N-ге дейінгі бүтін сандармен нөмірленген. Сіздерге осы шеңберден бірнеше қос хордалар берілген, ал берілген нүктелер олардың ұштары болып табылады. Әрбір қос хордалар үшін олардың қиылысатындығын немесе қиылыспайтындығын анықтаңыздар (түйісуді (жанасуды) қиылысқан деп санау қажет).

Енгізу файлының аты:            A.in     Шығару файлының аты:              A.out    Уақыт шектеу:                            2 секунд     Жадыға шектеу:                64 мегабайт

Мәліметтерді енгізу форматы

Кіріс файлының бірінші жолында екі бүтін сан N және K (1 <= N <= 109, 1 <= K <= 100) орналасқан. Келесі K жолда 4 бүтін саннан орналасқан: A1, B1, A2, B2 – бірінші хорда (A1, B1) және екінші хорда (A2, B2) ұштарының нөмірлері. Жолдағы сандар бос орын арқылы ажыратылған.

Мәліметтерді шығару форматы

Шығыс файлына әрбір қос хорда үшін бір жолдан шығару –  YES тіркесінен тұратын, егер хордалар қиылысқан болса, немесе NO тіркесін тұратын, егер хордалар қиылыспайтын болса.

Мысал

a.in a.out
4 3
1 3 2 4
1 2 3 4
1 2 3 2
YES
NO
YES

program esep_A;
var n,a1,a2,b1,b2,max,min,i:longint;  k:1..100;
f,f1,f2:boolean;
begin
assign (input,’a.in’);  reset (input);
assign (output,’a.out’);  rewrite(output);
read(n,k);
For i:=1 to k do
begin
read(a1,b1,a2,b2);
if (a1<b1) then  begin max:=b1;min:=a1; end
else  begin max:=a1;min:=b1; end;
f:=(min<a2) and (a2<max);
f1:=(min<b2) and (b2<max);
f2:=(a1=a2) or (a1=b2) or (b1=a2) or (b1=b2);
if (not(f) and f1) or (f and not (f1)) or f2 then writeln(‘YES’)  else writeln(‘NO’);
end;
close(input); close(output);
end.

B есебі. БөлгіштерA оң саны B санының бөлгіші деп аталады,  егер B саны А санына қалдықсыз бөлінсе.  Мысалы, 15 санында 4 бөлгіш бар: 1, 3, 5, 15. Сіздер әрбір берілген сандар үшін, оның бөлгіштерінің саны жұп немесе тақ  екендігін анықтауларыңыз қажет.

Мәліметтерді енгізу форматы

Кіріс файлының бірінші жолында бүтін N (1 < N <= 105) саны жазылған. Келесі жолында N  Xi (1 <= Xi <= 1018) сандары жазылған. Жолдағы сандар бос орын арқылы ажыратылған.

Мәліметтерді шығару форматы

Шығыс файлына аралары бос орын арқылы ажыратылған N сан жазылуы керек. i-ші сан 0 болуы керек, егер Xi бөлгіштерінің саны жұп болса, және 1, егер Xi бөлгіштерінің саны тақ болса.

Мысал

B.in B.out
2
4 5
1 0

Program esep_B;
var n,i:longint;s:extended;
begin
assign(input,’b.in’);
reset(input);
readln(n);
assign(output,’b.out’);
rewrite(output);
for i:=1 to n do
begin
read(s);
if frac(sqrt(s))=0 then write(1,’ ‘) else write(0,’ ‘);
end;
close(input);  close(output);
end.

C есебі.  ПайдаКомпьютер процессор бөлігінен және монитордан құралады. Қоймада  N процессор бөлігі және М монитор бар. і-ші процессор бөлігінің бағасы – Аі тугрик, j –ші монитордың бағасы – Вj тугрик. Дүниежүзілік қаражаттық дағдарысқа байланысты, і-ші процессор бөлігінен және j- ші монитордан құралған компьютердің бағасы Аі ∙ Вj (көбейту) тугрикке тең. Сіздерге мүмкіндігінше бағаларының қосындысы ең үлкен (максималды) болатындай етіп, компьютерлердің ең көп санын құрау қажет.

Мәліметтерді енгізу форматы

Кіріс файлының бірінші жолында екі бүтін сан N және M (1 <= N, M <= 1000) жазылған. Екінші жолында N бүтін сан жазылған: i-ші жолдағы сан – бұл Ai.

Үшінші жолында M бүтін сан жазылған: j-ші жолдағы сан – бұл Bj. (1 <= Ai, Bj <= 1000). Жолдағы сандар бос орын арқылы ажыратылған.

Мәліметтерді шығару форматы

Шығыс файлына бос орын арқылы ажыратылған, екі бүтін сан жазылуы керек – мүмкіндігінше ең көп компьютерлердің саны және олардың ең үлкен бағаларының қосындысы.

Мысал

C.in C.out
3 2
1 2 3
4 5
2 23

 

program esep_C;
type mas=array[1..1000] of longint;
var n,m,i:integer;   a,b:mas;  s:longint;
procedure suryptay(var g:mas;z:integer);
var r,x:integer; f:boolean;
begin
f:=false;
while f=false do
begin
f:=true;
for x:=1 to z-1 do
if g[x]<g[x+1]  then  begin f:=false; r:=g[x]; g[x]:=g[x+1]; g[x+1]:=r; end;
end;
end;
procedure engizy;
begin

assign(input,’c.in’); reset(input);
readln(n,m);
for i:=1 to n do   read(a[i]);
for i:=1 to m do  read(b[i]);
close(input);
end;
procedure shigary;
begin

assign(output,’c.out’);  rewrite(output);
writeln(n,’ ‘,s);   close(output);
end;
procedure eseptey;
begin

s:=0;
if n>m then n:=m;
for i:=1 to n do  s:=s+a[i]*b[i];
end;
begin

engizy;    suryptay(a,n);  suryptay(b,m);  eseptey;   shigary;
end.

D есебі. ЖалқаулықОқытушы емтиханға дайындалу үшін оқушыларына  N  сұрақ берді.  Ол емтихан үшін берілген сұрақтардың ішінен A сұрақты таңдайтынын айтты, ал оқушы, бес алу үшін, осы A сұрақтың ішінен B сұраққа жауап беруі тиіс. Қу оқушы барлық сұрақтарды оқуды қаламайды. Оған кез-келген үлестірімде (таратымда) бес алу үшін, ең аз дегенде неше сұрақ оқуы қажет?

Мәліметтерді енгізу форматы

Кіріс файлында бір ғана жол бар, онда үш бүтін сан жазылған:

N, A және B (1 <= N <= 100000, 1 <= B <= A <= N). Сандар бір-бірінен бос орын арқылы ажыратылған.

Мәліметтерді шығару форматы

Шығыс файлында бір бүтін сан жазылуы керек – есептің жауабы.

Мысал

D.in D.out
10 7 3 6

Program esep_D;
var n,a,b:longint;
begin
assign(input,’d.in’);
reset(input);
readln(n,a,b);
assign(output,’d.out’);
rewrite(output);
write(n-a+b);
close(input);
close(output);
end.

E есебі. Серіппе (спираль)N өлшемді спираль – бұл NxN өлшемді натурал сандар кестесі, кесте ортасында әрқашан 1 тұрады, оның оң жағында 2, спираль сағат тіліне қарсы оралады. N өлшемді спиральді шығарыңыз.

Мәліметтерді енгізу форматы

Кіріс файлында бір ғана жол бар, онда бір бүтін сан жазылған –  N (1 <= N < 100, N – тақ сан).

Мәліметтерді шығару форматы

Шығыс  файлына  N саннан тұратын N жолды жазу керек   –  N өлшемді спираль.  Жолдардағы сандар бір-бірінен бос орын арқылы ажыратылуы керек.

Мысал

E.in E.out
1 1
3 5 4 3
6 1 2
7 8 9
5 17 16 15 14 13
18   5   4   3 12
19   6   1   2 11
20   7   8   9 10
21 22 23 24 25

program esep_E;
var a:array[1..100,1..100] of integer;
k:integer;  n,c,i,j:byte;  s:string;
begin
assign(input,’e.in’);  reset(input);
assign(output,’e.out’);  rewrite(output);
read(n);
k:=n*n+1;c:=n-1;
a[n div 2+1,n div 2+1]:=1;
for i:=1 to n div 2 do
begin
for j:=i to n-i do
begin

k:=k-1;
a[n+1-i,n+1-j]:=k;
a[n+1-j,i]:=k-c;
a[i,j]:=k-2*c;
a[j,n+1-i]:=k-3*c;
end;
k:=k-3*c;c:=c-2;
end;
str(n*n,s);
for i:=1 to n do
begin

for j:=1 to n do
write(a[i,j]:length(s)+1);
writeln;
end;
close(input);  close(output);
end.

F есебі. Дәрежесі

Сіздерге  A,  B және  C бүтін  сандары берілген.  AB (A-ның B дәрежесін)  C-ға  бөлгендегі  қалдығын шығарыңыздар. Назар аударыңыздар:

(X · Y) mod Z = ((X mod Z) · (Y mod Z)) mod Z
(X + Y) mod Z = ((X mod Z) + (Y mod Z)) mod Z

Мәліметтерді енгізу форматы

Кіріс файлында бір ғана жол бар, онда үш бүтін сан жазылған:

A, B, C (0 <=A, B<= 1018, 1<= C<= 1018). Сандардың аралары бос орын арқылы бөлінген.

Мәліметтерді шығару форматы

Шығыс файлында бір бүтін сан жазылуы керек – есептің жауабы.

Мысал

F.in F.out
3 4 5 1

Төмендегі бағдарлама үлкен сандарда уақыттан асып кетеді.
Мысалы, A=4093; B=59855; C=3194 мәндерінде дұрыс жұмыс істейді.

program Esep_F;
var s,a,b,c:0..1000000000000000000; {bul typ Free Pascal yshin oryndalady, al Turbo Pascal
yshin zharamaidy}
begin
assign(input,’f.in’);
reset(input);
assign(output,’f.out’);
rewrite(output);
readln(a,b,c);
s:=a;
if (a=0) or ((c=1) and (b=0)) or (c=1) then s:=0 else
if b=0 then s:=1 else if b=1 then s:=a mod c else
begin
b:=b-1;
while b>0 do
begin

s:=((s mod c)*(a mod c)) mod c;
b:=b-1;
end;
end;

write(s);
close(input);
close(output);
end.

Check Also

i-151

Информатика пәні бойынша республикалық олимпиада, 2014–2015 о.ж., аудандық кезең, есептердің шығарылуы

 Шоңбаев Жеңіс Меңдіғалиұлы, С.Сейфуллин атындағы №11 ДБАМОҚМИК Республиканская олимпиада по информатике 2014–2015; Этап 2; Тур …

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

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

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