Задачі за 14.12. 2014
Вінницька міська олімпіада 2 етап
8-9 клас
1. Newprize. Три учні за перемогу у конкурсі повинні розіграти між собою один приз – одна запакована коробка з призом. Є ще 2 такі самі, але порожніх коробки. Спочатку кожен має по одній коробці. Потім вони починають швиденько обмінюватися коробками один з другим у певному порядку. Переможцем стає той, у кого опиниться коробка з призом після усіх обмінів.
Технічні умови. Програма читає з
пристрою стандартного введення два числа P та K (1 <= P <= 3, 0 <= K
<= 100), що відповідно вказують на номер учня, що спочатку отримав
коробку з премією та кількість обмінів а далі K пар чисел а і b (1 <= a, b
<= 3, a <> b) - номери учнів, що мінялися коробками на даному
кроці. Програма виводить одне число – номер переможця, якому дістався коробка з
премією.
Приклад
Введення
|
Виведення
|
1 5
1 2 1 3 3 2
13
12
|
2
|
Розв’язання
Спосіб 1.
Program Newprize;
Type
State=Array[1..3] of Boolean;
Var
st: State;
k, p, i, a, b: Integer;
Procedure Exchange (Var st: State; x,y: Integer);
Var
v: Boolean;
Begin
v := st[x];
st[x] := st[y];
st[y] := v;
End;
Begin
For i:=1 to 3 do st[i] := False;
readln(p,k);
st[p] := True;
For i:=1 to k do Begin
Readln(a,b);
exchange(st,a,b);
End;
For i:=1 to 3 do
If st[i] Then p:=i;
writeln(p);
End.
Спосіб 2.
Program Newprize;
Type
State=Array[1..3] of Boolean;
Var
st: State;
k, p, i, a, b: Integer;
Procedure Exchange (Var st: State; x,y: Integer);
Var
v: Boolean;
Begin
v := st[x];
st[x] := st[y];
st[y] := v;
End;
Begin
For i:=1 to 3 do st[i] := False;
readln(p,k);
st[p] := True;
For i:=1 to k do Begin
Readln(a,b);
exchange(st,a,b);
End;
For i:=1 to 3 do
If st[i] Then p:=i;
writeln(p);
End.
Спосіб 2.
var a,v,u:
integer;
b: array [1..100,1..3] of integer;
c: array [1..100,1..3] of integer;
x, z,f, p,k,i,j: integer;
begin
writeln(' ');
read(p,
k);
for i:=1
to k do
for j:=1
to 3 do begin
c[i,j]:=0;
b[i,j]:=0; end;
for i:=1
to k do begin
read(x,
z);
if x=1 then
c[i,1]:=1;
if x=2 then
c[i,2]:=2;
if x=3 then
c[i,3]:=3;
if z=1 then
b[i,1]:=1;
if z=2 then
b[i,2]:=2;
if z=3 then
b[i,3]:=3;
end;
for i:=1 to k
do begin
v:=c[i,1]+c[i,2]+c[i,3];
u:=b[i,1] +b[i,2]+b[i,3];
if v=p
then p:=u else
if
(v<>p)and(u<>p) then p:=p
else
if u=p
then p:=c[i,1]+c[i,2]+c[i,3]; end;
write(p);
writeln;
end;
Задачі 2 етапу Вінницької олімпіади з інформатики за
14 грудня 2014 року
8-9 клас
1. Newprize. Три претенденти на перемогу у
конкурсі повинні розіграти між собою один приз – конверт з премією. Є ще 2
таких самих, але порожніх конверти. Спочатку кожен має по одному конверту.
Потім вони починають швиденько обмінюватися конвертами один з другим у певному
порядку. Переможцем стає той, у кого опиниться конверт з премією після усіх
обмінів.
Технічні умови. Програма Newprize читає з
пристрою стандартного введення 2 числа P та K (1 <= P <= 3, 0 <= K
<= 100), що відповідно вказують на номер претендента, що спочатку тримав
конверт з грішми та кількість обмінів а далі K пар чисел а і b (1 <= a, b
<= 3, a <> b) - номери претендентів, що мінялися конвертами на даному
кроці. Програма виводить одне число – номер переможця, якому дістався конверт з
премією.
Приклад
Введення
|
Виведення
|
1 3
1 2 1 3 3 2 |
3
|
Розв’язання
var a,v,u:
integer;
b: array [1..100,1..3] of integer;
c: array [1..100,1..3] of integer;
x, z,f, p,k,i,j: integer;
begin
writeln(' ');
read(p,
k);
for i:=1
to k do
for j:=1
to 3 do begin
c[i,j]:=0;
b[i,j]:=0; end;
for i:=1
to k do begin
read(x,
z);
if x=1 then
c[i,1]:=1;
if x=2 then
c[i,2]:=2;
if x=3 then
c[i,3]:=3;
if z=1 then
b[i,1]:=1;
if z=2 then
b[i,2]:=2;
if z=3 then
b[i,3]:=3;
end;
for i:=1 to k
do begin
v:=c[i,1]+c[i,2]+c[i,3];
u:=b[i,1] +b[i,2]+b[i,3];
if v=p
then p:=u else
if
(v<>p)and(u<>p) then p:=p
else
if u=p
then p:=c[i,1]+c[i,2]+c[i,3]; end;
write(p);
writeln;
end.
====================================================================
Задача Forecast. Василько та Юлія грають в таку гру.
Спочатку кожен записує на папері свій прогноз – число від 1 до 6. Потім вони
кидають гральний кубик з числами від 1 до 6 на гранях. Чий прогноз виявляється
ближчим до того числа, що випало, той і переміг. Треба написати програму для
визначення переможця.
Технічні умови. Програма Forecast читає з пристрою
стандартного введення три числа через пропуски (пробіли) – прогноз Василька,
Юлі та результат кидання кубика. Програма виводить “V”, якщо переміг Василько,
“J” якщо Юлія або ”D” – якщо прогноз обох однаково близький до результату
(тобто переможця виявити неможливо.
Приклади
Введення
|
Виведення
|
3 4 5
1 6 2 4 4 3 |
J
V D |
Program Candy;
var a,b,c:integer;
BEGIN
read(a,b,c);
if ((abs(c-a))>(abs(c-b))) then write('J');
if ((abs(c-a))<(abs(c-b))) then write('V');
if ((abs(c-a))=(abs(c-b))) then write('D');
end.
====================================================================
Задача Сandy. На вулиці Сонячній треба побудувати 3
будинки, з відомою кількістю поверхів у кожному. Але краєвид буде зіпсовано,
якщо кількість поверхів у будь-яких двох з них відрізняється більше, ніж на Z.
Архітектор може зменшити в якомусь з будинків кількість поверхів на 1, але
обов’язково при цьому збільшити на 1 поверх в іншому, зробивши новий проект.
Потрібно зробити так, аби краєвид не був зіпсований.
Технічні умови. Програма Сandy читає з пристрою
стандартного введення чотири невід'ємних цілих числа b1, b2, b3 , Z через
пропуск, кожне з них не більше за 109 - кількість поверхів у кожному з
будинків згідно першого проекту та дозволену різницю між кількістю поверхів.
Програма виводить одне число – мінімальну к-сть перероблених проектів, Якщо
зберегти краєвид неможливо, вивести - 1.
Приклад
Введення
|
Виведення
|
1 6 3 2
|
2
|
====================================================================
Розвязання. Спосіб 1.
program Сandy;
var a,b,c,z,min,max,k,mini,maxi : longint;
program Сandy;
var a,b,c,z,min,max,k,mini,maxi : longint;
mas : array [1..3] of integer;
BEGIN
read(a,b,c,z);
k:=0;
mas[1]:=a;
mas[2]:=b;
mas[3]:=c;
while ( (abs(mas[1]-mas[2]) > z) or (abs(mas[1]-mas[3]) > z) or (abs(mas[2]-mas[3]) > z) ) do
begin
if mas[1]>=mas[2] then begin
max:=mas[1];
maxi:=1;
min:=mas[2];
mini:=2;
end
else begin
max:=mas[2];
maxi:=2;
min:=mas[1];
mini:=1;
end;
if mas[3]>max then begin
max:=c;
maxi:=3;
end;
if mas[3]<min then begin
min:=c;
mini:=3;
end;
dec(max);
inc(min);
inc(k);
mas[mini]:=min;
mas[maxi]:=max;
end;
writeln(k);
readln;
END.
Якщо зберегти краєвид неможливо, а це буде у випадку, коли z=0 і загальна кількість поверхів не ділиться на 3, твоя програма зациклиться. Треба цей випадок перевірити напочатку.
Задача Songs. Петро записав на листочку кількість пісень у своїй фонотеці, але трішки прибрехав - хай друзі заздрять. Та совість замучила, і він зробив запис (знову не дуже чесний ;-) коротшим на одну цифру. Але викреслив одну цифру так, щоб число, яке залишилося, було найбільшим.
Технічні умови. Програма Songs читає з пристрою
стандартного введення одне ціле значення n (10<=n<=99999), і виводить на
пристрій стандартного виведення число без однієї цифри (це число має бути
найбільшим серед усіх можливих варіантів закреслень цифри).
Приклади
Введення
|
Виведення
|
431
138 |
43
38 |
====================================================================
Розв'язання. Спосіб 1. Викоростання рядкових величин string
Розв'язання. Спосіб 1. Викоростання рядкових величин string
var s,r:string;
i,j,n,d,p:integer;
begin
read(s);
r:='';
d:=length(s);
p:=0;
i:=1;
while (i<d) and (p=0) do
begin
if (s[i]>=s[i+1]) and (i<d)
then i:=i+1
else p:=1;
end;
if i=1 then for j:=2 to d do r:=r+s[j]
else if i=d then for j:=1 to d-1 do r:=r+s[j]
else
begin
for j:=1 to i-1 do r:=r+s[j];
for j:=i+1 to d do r:=r+s[j];
end;
write(r);
end.
Спосіб 2. Використання цілочисельних функцій mod i div.
Program Songs;
Var n,d,r,m: Longint;
Function reduce(n: Longint; p: Longint): Longint;
Var h,t: Longint;
Begin
h := n div (p*10);
t := n mod p;
reduce := h*p+t;
End;
Begin
read(n);
d := 1;
m := 0;
repeat
r := reduce(n,d);
If r>m Then m := r;
d := d*10;
Until d>n;
writeln(m);
End.
i,j,n,d,p:integer;
begin
read(s);
r:='';
d:=length(s);
p:=0;
i:=1;
while (i<d) and (p=0) do
begin
if (s[i]>=s[i+1]) and (i<d)
then i:=i+1
else p:=1;
end;
if i=1 then for j:=2 to d do r:=r+s[j]
else if i=d then for j:=1 to d-1 do r:=r+s[j]
else
begin
for j:=1 to i-1 do r:=r+s[j];
for j:=i+1 to d do r:=r+s[j];
end;
write(r);
end.
Спосіб 2. Використання цілочисельних функцій mod i div.
Program Songs;
Var n,d,r,m: Longint;
Function reduce(n: Longint; p: Longint): Longint;
Var h,t: Longint;
Begin
h := n div (p*10);
t := n mod p;
reduce := h*p+t;
End;
Begin
read(n);
d := 1;
m := 0;
repeat
r := reduce(n,d);
If r>m Then m := r;
d := d*10;
Until d>n;
writeln(m);
End.
Задачі
2 етапу Вінницької олімпіади з інформатики за 14 грудня 2014 року
10-11 клас
Задача Forecast. Василько та Юлія грають в таку гру.
Спочатку кожен записує на папері свій прогноз – число від 1 до 6. Потім вони
кидають гральний кубик з числами від 1 до 6 на гранях. Чий прогноз виявляється
ближчим до того числа, що випало, той і переміг. Треба написати програму для
визначення переможця.
Технічні умови. Програма Forecast читає з
пристрою стандартного введення три числа через пропуски (пробіли) – прогноз
Василька, Юлі та результат кидання кубика. Програма виводить “V”, якщо переміг
Василько, “J” якщо Юлія або ”D” – якщо прогноз обох однаково близький до
результату (тобто переможця виявити неможливо.
Приклад
Введення
|
Виведення
|
3 4 5
|
J
|
1 6 2
|
V
|
4 4 3
|
D
|
====================================================================
Program
Forecast;
var a,b,c :
integer;
BEGIN
read(a,b,c);
if (
(abs(c-a)) > (abs(c-b)) ) then
Write('J');
if (
(abs(c-a)) < (abs(c-b)) ) then
Write('V');
if (
(abs(c-a)) = (abs(c-b)) ) then
Write('D');
END.
Задача Сandy. На вулиці Сонячній треба побудувати 3
будинки, з відомою кількістю поверхів у кожному. Але краєвид буде зіпсовано,
якщо, якщо кількість поверхів у будь- яких двох з них відрізняється більше, ніж
на Z. Архітектор може зменшити в якомусь з будинків кількість поверхів на 1,
але обов’язково при цьому збільшити на 1 поверх в іншому, зробивши новий
проект. Потрібно зробити так, аби краєвид не був зіпсований.
Технічні умови. Програма Сandy читає з
пристрою стандартного введення чотири невід'ємних цілих числа b1, b2, b3, Z через
пропуск, кожне з них не більше за 109 - кількість поверхів у кожному з
будинків згідно першого проекту та дозволену різницю між кількістю поверхів.
Програма виводить одне число – мінімальну к-сть перероблених проектів, Якщо
зберегти краєвид неможливо, вивести -1.
Приклад
Введення
|
Виведення
|
1 6 3 2
|
2
|
===================================================================
Розвязання. Спосіб 1.
program Сandy;
var a,b,c,z,min,max,k,mini,maxi : longint;
program Сandy;
var a,b,c,z,min,max,k,mini,maxi : longint;
mas : array [1..3] of
integer;
BEGIN
read(a,b,c,z);
k:=0;
mas[1]:=a;
mas[2]:=b;
mas[3]:=c;
while (
(abs(mas[1]-mas[2]) > z) or (abs(mas[1]-mas[3]) > z) or
(abs(mas[2]-mas[3]) > z) ) do
begin
if mas[1]>=mas[2] then begin
max:=mas[1];
maxi:=1;
min:=mas[2];
mini:=2;
end
else begin
max:=mas[2];
maxi:=2;
min:=mas[1];
mini:=1;
end;
if mas[3]>max then begin
max:=c;
maxi:=3;
end;
if mas[3]<min then begin
min:=c;
mini:=3;
end;
dec(max);
inc(min);
inc(k);
mas[mini]:=min;
mas[maxi]:=max;
end;
writeln(k);
readln;
END.
Задача Circuitry. Для виготовлення новорічних гірлянд
електротехнічна корпорація закупила лампочки коробками по z штук в
кожній. Але гірлянди вони робили за особливою інноваційною схемою: перша
гірлянда складалася лише з 1 лампочки, друга - з 4-х, третя - з 9 і так далі...
Але у світі економічна криза, все треба рахувати, бажано знати, скільки
лампочок залишиться після виготовлення усіх гірлянд. Звичайно, корпорація
закупить мінімально необхідну кількість коробок з лампочками.
Технічні умови. Програма Circuitry читає з
пристрою стандартного введення через пропуск спочатку кількість замовлених
гірлянд n(1<=n<=109 , тобто мільярд), потім кількість лампочок
у коробці z (1<=z<=106 , тобто мільйон), і виводить на
пристрій стандартного виведення єдине ціле число — кількість лампочок, що
залишаться не використаними, якщо купити найменшу можливу кількість коробок.
Приклад
Введення
|
Виведення
|
7 16
|
4
|
Program Circuitry;
var
n,z,k,a,rez : longint;
BEGIN
read(n,z);
k:=(n*(n+1)*(2*n+1)) div 6;
a:=k div z +1;
rez:=z*a-k;
write(rez);
END.====================================================================
спосіб 2
var s1,s2,n,z,i:int64;
begin
read(n,z); s1:=0; s2:=0; i:=0;
if (z=1) then begin writeln('0'); halt; end;
if (n=1) then begin writeln(z-n); halt; end;
repeat
i:=i+1;
s1:=s1+i*i;
until i=n;
if (s1 mod z<>0) then s2:=(s1 div z)+1 else s2:=s1 div z;
i:=z*s2;
writeln(i-s1);
end.
var s1,s2,n,z,i:int64;
begin
read(n,z); s1:=0; s2:=0; i:=0;
if (z=1) then begin writeln('0'); halt; end;
if (n=1) then begin writeln(z-n); halt; end;
repeat
i:=i+1;
s1:=s1+i*i;
until i=n;
if (s1 mod z<>0) then s2:=(s1 div z)+1 else s2:=s1 div z;
i:=z*s2;
writeln(i-s1);
end.
Задача
Pcnet У корпорації «Роги та копита» є багато комп'ютерів (ПК) , ПК з'єднані в
мережу та пронумеровано натуральними числами от 1 до N. У корпорації є кілька філій, у кожній – кілька комп’ютерів. Якщо один і той же
комп’ютер належить кільком філіям, то це маршрутизатор (роутер), який може перенаправляти пакети, інформація може потрапити з
однієї філії у
будь-яку іншу, якщо маршрутизатор належить і їй. Напишіть програму, яка по
даному опису мережі визначить, через яку мінімальну кількість маршрутизаторів
інформація може дістатися із комп’ютера A на комп’ютер B (якщо хоч один із них
чи обидва - маршрутизатори, вони в цю мінімальну кількість не входять, бо
працюють в цьому випадку звичайними ПК). Якщо мережа пошкоджена, то може так
трапитися, що із комп’ютера A на комп’ютер B інформація не потрапить. У цьому
випадку ваша програма повинна на це вказати.
Технічні умови. Програма Pcnet читає з пристрою
стандартного введення спочатку число N — кількість ПК у корпорації
(2<=N<=100), та через пропуск M — кількість філій (1<=M<=20).
Далі слідує опис M мереж кожної філії. Він складається з числа Pi —
кількість ПК у цій філїї (2<=Pi <=50) і з Pi чисел, що
задають номери ПК, увімкнутих у мережу (ніякий ПК не підключено двічі). В
останньому рядку записано два різних числа: A — номер ПК, що передає
інформацію, і B — номер ПК, на котрий інформація має потрапити. Якщо ПК A –
маршрутизатор, то інформація може починати маршрут з будь-якої філії. Якщо ПК B
- маршрутизатор - то байдуже, від якої філії прийде інформація. Програма
виводить на пристрій стандартного виведення єдине число- мінімальну кількість
маршрутизаторів (без початкового та кінцевого, якщо такі були). Якщо інформація
з ПК A на ПК B потрапити не може, виведіть –1 (мінус один).
Приклади
Введення
|
Виведення
|
Введення
|
Виведення
|
Введення
|
Виведення
|
5 2
|
0
|
5 5
|
2
|
4 2
|
-1
|
4 1 2 3 4
|
2 1 2
|
2 1 2
|
|||
2 5 3
|
2 1 3
|
2 3 4
|
|||
3 1
|
2 2 3
|
1 3
|
|||
2 3 4
|
|||||
2 4 5
|
|||||
1 5
|
Program
Pcnet;
var
i,j,x,y,w,m,n,k,i2,j2,g,h,t : integer;
p,mnog,st : set of byte;
ch,mas : array [1..6] of
integer;
a : array
[1..5,1..5] of integer;
BEGIN
read(n,m);
mnog:=[];
p:=[];
st:=[];
k:=0;
for i:=1 to m do
begin
read(w);
for j:=1 to w do
begin
read(x);
mas[j]:=x;
if x in mnog then p:=p+[x]
else mnog:=mnog+[x];
end;
for i2:=1 to w do
for j2:=i2+1 to w do
begin
x:=mas[i2];
y:=mas[j2];
a[x,y]:=1;
a[y,x]:=1;
end;
end;
read(x,y);
if x>y then begin
t:=x;
x:=y;
y:=t;
end;
ch[1]:=x;
g:=1;
h:=2;
st:=st+[x];
while ((g<h) and (not (y in st))) do
Begin
for i:=1 to n do
begin
if ((a[g,i]=1) and (not (i in st))) then
begin
ch[h]:=i;
st:=st+[i];
inc(h);
if (i in p) then inc(k);
end;
end;
inc(g);
End;
if g>=h then k:=0;
Write(k-1);
END.
Примітка. Завдання розраховано на 5 годин. Для
перевірки здаються лише файли з текстом програми однією з мов програмування
(Pascal, C, C++). Тексти програм повинні строго відповідати технічним умовам,
не містити не передбачених умовою введення та виведення.
Немає коментарів:
Дописати коментар