Информатикадан облыстық олимпиада 2012-2013 шешу нұсқасы

kungaksy-140x150Сайтқа орналастырған:

Күнжақсы Жеткізген. Маңғыстау облысы, Ақтау қаласы.

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

Сіз дүкен кассасында кезекте тұрсыз. Қазір түскі ас уақыты, сондықтан бір ғана касса жұмыс істейді. Сіз кезекте ең соңғы болып тұрсыз және қатарда сізбен қоса барлығы N адам бар.

Әр адам кассаға өз кезегі келгенде 1 (бір) минут бойы ақшасын төлейді де дүкеннен кетеді. Сонымен қатар әр М минут сайын кезекті кассир келіп өз кассасын ашады. Кезекті касса ашылған кезде осыған дейін соңғы ашылған касса кезегінің артқы жағындағы адамдардың бір бөлігі осы касса кезегіне сол ретпен ауысып келеді. Яғни, i-касса ашылған кезде (i-1)-кассаның кезегінде K адам болса, i-кассаның кезегіне ауысатын адамдардың саны (k/2)-нің бүтін бөлігіне тең. Мысалы 4-касса ашылған кезде 3-касса кезегінде 5 адам болса 2 адам, ал егер 6 адам болса 3 адам 4-кассаның кезегіне ауысады. Бір кезектен басқа кезекке ауысуға уақыт кетпейді деп есептесек болады.

Сіздің тапсырмаңыз дүкеннен неше минуттан кейін кете алатыныңызды анықтау керек.

Енгізу файлының форматы. Енгізу файлында бос орынмен бөлінген екі бүтін сан N және M берілген. (1 ≤ N ≤ 109, 1 ≤ M ≤ 109)

Шығару файлының форматы. Шығыс файлында бір бүтін сан – неше минуттан кейін дүкеннен кететініңізді шығарыңыз.

Мысалдар

A. in A. out
5    10 5
5       2 3
15      3 7

 

Turbo Pascal тіліндегі бағдарламасы: Түсініктеме:
Program kassa;
Var n,m,k:integer;
f1,f2:text;
Begin
Assign(f1,’A.in’);
Reset(f1);
Assign(f2,’A.out’);
Rewrite(f2);
Readln(f1,n,m);
While n>=m do
begin
n:=(n-m)div 2;
k:=k+m;
end;
writeln(f2,k+n);
close(f1);    close(f2);
Үшінші тесттің мәндерін талдайық. Кассада алдымен сізді қоса есептегенде 15 адам тұрсын, кезекті кассир өз кассасын әр 3 минут сайын ашсын делік. Олай болса 1-кассадан 3 минутта 3 адам кетіп (n-m), 12 адам қалады. Ашылған екінші кассаға қалған адамның жартысы кетеді. Демек 1-кассада 6 адам қалады, сіз+5адам екінші кассаға ауысасыз. Келесі 3 минуттан соң 3-касса ашылады. Енді 2-кассада 6-3=3 адам қалады. Оның екеуі 2-кассада қалып, сіз 3-кассаға ауысасыз. Себебі 2-кассада қалған адамның 2-ге бөлгендегі бүтін бөлігі қалады: (n-m) div 2. Сіз кассаның алдында 1 минут бойы ақша төлейсіз. Демек сіз дүкеннен 3+3+1=7 минуттан соң кетесіз.

 
В есебі. Қала жолдарын бояу

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

Бір қалада N жол қиылысы және осы қиылыстарды байланыстыратын  N  бір жақты жол бар. Және әр қиылысқанда тек бір жолмен ғана келе алатынымыз белгілі.

Қала әкімшілігі жолдарды әр түрлі түстерге бояуды шешті. Бірақ олар бірдей түсті екі жолдың бір қиылыста байланысқанын қаламады. Сонымен қатар, олар барынша аз түс қолданғылары келеді. Басқа қалалардың әкімдері де бұл қаладан артта қалмау үшін өз қалаларындағы жолдарды бояуды шешті.

Сіздің тапсырмаңыз әр берілген қалаға ең аз қанша түс керектігін анықтап беру.

Енгізу файлының форматы. Енгізу файлында бірінші жолында бір бүтін сан K (1 ≤ K ≤ 10) – қалалар саны берілген. Бұдан кейін K қаланың сипаттамасы берілген. Әр сипаттаманың бірінші жолында бір бүтін сан N (1 ≤ N ≤ 100000) – қаладағы жол қиылыстарының саны берілген. Келесі жолда аралары бос орынмен бөлінген N сан – жолдардың сипаттамасы берілген. Егер бұл жолдағы і-сан Хісаны болса, ол Хі-қиылыстан і-қиылысқа жол бар екенін білдіреді (1 ≤ Xi ≤ N, Xi ≠ i).

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

Мысалдар

B. in B.out
2
4
4    1    2     3
2
5
4    1    2     3      4
3

 

Turbo Pascal тіліндегі бағдарламасы: Түсініктеме:
program joldi_boiau;
var n,k:integer;
f1,f2:text;
begin
assign(f1,’B.in’);
reset(f1);
assign(f2,’B.out’);
rewrite(f2);
readln(f1,k);
while k>=1 do
begin
readln(f1,n);
if n mod 2=0 then n:=n div 2
else n:=(n div 2)+1;
writeln(f2,n);
k:=k-1;
end;
close(f1); close(f2);
Берілген тесттердің мәндерін талдайық. Қала саны қанша болса да, жолдар саны тақ немесе жұп болуы мүмкін. Жолдар саны жұп болса n mod 2=0 оларды бояу үшін кем дегенде  n div 2 түс, әйтпесе (n div 2)+1 түс керек болады.

C есебі. Алмастырудың реттік нөмірі

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

N элементтен тұратын алмастыру дегеніміз 1-ден N-ге дейінгі сандардың реттелген тізбегі. N элементтен тұратын алмастырулардың жалпы саны N!=1*2*3*…*N.  Сіздің тапсырмаңыз берілген алмастырудың лексикографиялық қатардағы реттік нөмірін табу. Мысалы, N=3 үшін алмастырулардың лексикографиялық қатары мынадай: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).
Осылайша, (3, 1, 2) алмастырудың реттік нөмірі 5 болады.

Енгізу файлының форматы. Енгізу файлының бірінші жолында N (1 ≤ N ≤ 100000) – алмастырудағы элементтер саны берілген. Екінші жолда N бүтін сан – алмастырудың элементтері берілген.

Шығару файлының форматы. Шығыс файлында бір бүтін сан – берілген алмастырудың реттік нөмірін шығарыңыз. Бұл сан өте үлкен болуы мүмкін, сондықтан оның 1000000007 (109+7)-ге бөлгендегі қалдығын шығарыңыз.

Мысалдар

С. in С. out
3
3     1     2
5
4
2     3     1     4
9

 

Turbo Pascal тіліндегі бағдарламасы: Түсініктеме:
program almastiru;
var n,i,j,s,m,k,c,t:integer;
a, b:array[1..1000] of integer;
f1,f2:text;
begin
assign(f1,’С.in’);    reset(f1);
assign(f2,’С.out’);   rewrite(f2);
readln(f1,n);
for i:=1 to n do read(f1,a[i]);
for i:=1 to n do b[i]:=i;  s:=1;
for i:=n-1 downto 1 do
if b[i]<b[i+1] then begin
for j:=n downto i do if b[i]<b[j] then
begin
m:=b[i];
b[i]:=b[j];
b[j]:=m;
k:=1;
while i+k<n-k+1 do      begin
m:=b[i+k];
b[i+k]:=b[n-k+1];
b[n-k+1]:=m;
k:=k+1;
end;
j:=i;   end;
i:=n;
s:=s+1; c:=0;
for t:=1 to n do
if a[t]=b[t] then c:=c+1;
if c=n then writeln(f2,s);
end;
close(f1);      close(f2); end.
Екінші тестті талдайық.
N = 4 үшін алмастырулар-дың лексикографиялық қата-ры мынадай: (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1).
Осылайша, (2, 3, 1, 4) алмастырудың реттік нөмірі 9 болады.

Check Also

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

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

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

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

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