неділю, 7 вересня 2014 р.

Розв’язки завдань II етапу Всеукраїнської учнівської олімпіади з інформатики

Розв’язки завдань II етапу Всеукраїнської учнівської олімпіади з інформатики

(Волинська область)

2009-2010 н.р.


Задача 1. «Фотокартка» (PHOTO) – 15 балів.
Кольорове зображення має N кольорів. Розмір зображення AxB cм. Роздільна здатність R точок на дюйм (1 дюйм = 2,54 см).
Завдання
Визначити скільки Кбайт пам'яті потрібно для зберігання зображення в нестисненому вигляді?
Вхідні дані
Перший рядок містить натуральне число N кількість кольорів. Наступні два рядки містять дійсні числа, які задають розмір фотокартки. Останній  рядок містить натуральне число, яке задає роздільну здатність. Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить шуканий розмір фотокартки, як дійсне число з двома знаками після коми.
Приклад

photo.dat
photo.sol
8
10
15
300
766.29
Розв’язок
Для розв’язку задачі необхідно визначити кількість біт яку займає точка та підрахувати їх кількість.
Для визначення кількості біт використовується співвідношення   (де n- кількість точок k – кількість біт),
Звідси . Дана формула використовується для визначенні кількості двійкових кодів в бінарному дереві.
n
b
2
1
4
2
8
3
16
4
32
5
. . .

256
8
65536
16
16777216
24
Програма
Варіант 1
Варіант 2
program photo;
var bit,n,a,b,r:integer;
k:real;
f1,f2:text;

begin
assign(f1,'photo.dat');
reset(f1);
read(f1,n,a,b,r);
close(f1);
bit:=round(ln(n-1)/ln(2)+1);
k:=(a/2.54)*(b/2.54)*r*r*bit/8/1024;
k:=int(k*100)/100;
assign(f2,'photo.sol');
rewrite(f2);
writeln(f2,k:2:2);
close(f2);


end.
program photo;
var bit,n,a,b,r:integer;
k:real;
f1,f2:text;

begin
assign(f1,'photo.dat');
reset(f1);
read(f1,n,a,b,r);
close(f1);
bit:=1;
n:=n-1;
while n>1 do begin
bit:=bit+1;
n:=n div 2;
end;
if n>2 then bit:=bit+1;
k:=(a/2.54)*(b/2.54)*r*r*bit/8/1024;
k:=int(k*100)/100;
assign(f2,'photo.sol');
rewrite(f2);
writeln(f2,k:2:2);
close(f2);
end.


Задача 2. «Комп’ютери» (COMPUTER) – 25 балів.
Між школами поділили N комп’ютерів Pentium і M комп’ютерів Celeron. Скільки було шкіл, якщо відомо їх не менше  ніж K і кожна школа отримала однакову кількість комп’ютерів кожного виду.

Вхідні дані
Перший рядок містить натуральні числа N, M, K. Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить знайдену кількість шкіл. Якщо результатів декілька, то вивести всі через пропуск в зростаючому порядку.
Приклад

 

computer.dat
computer.sol
92
138
25
46

 

Розв’язок
Необхідно знайти спільні дільники чисел M та N, які не менші за число K.
Для i:=K до мінімум(N,M)
пц
якщо ост(i,N)=0 та ост(i,M)=0 то вивести (i)
кц

Програма :
program computer;
var n,a,b,c,min:integer;
f1,f2:text;
begin
assign(f1,'COMPUTER.dat');
reset(f1);
read(f1,a,b,c);
close(f1);
assign(f2,'COMPUTER.sol');
rewrite(f2);
if a>b then min:=b else min:=a;
for n:=c to min do
begin
if (a mod n=0)and(b mod n=0) then write(f2,n,' ');
end;
writeln(f2);
close(f2);
end.



 



Задача 3. Збирання мита (TALLAGE) -60 балів.
Король країни Аріїв завоював N міст на території сусідніх держав.
Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.
Вхідні дані:
Перший рядок вхідного файлу містить натуральне число N (1<=N<=100) – кількість міст у країні, а також цілі числа X та Y – координати столиці.
Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.
Значення координат по модулю менші 50000.
Вихідні дані:
Перший рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.
Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі:
<номер міста> => <номер міста>
При цьому столицю позначте номером 0.
Якщо відповідей декілька, виведіть одну довільну з них.
Приклади:
TALLAGE.DAT
TALLAGE.SOL
6  0 0
 1  1
-1  1
 0  2
 1 -1
-1 -1
 0 -2
8.485
2 3
3 1
1 0
0 4
4 6
6 5

Розв’язок

Теорія графів-Жадібні алгоритми –  каркас мінімальної ваги (остове дерево)
Визначити довжини шляхів за формулою довжини відрізка .
На основі довжин побудувати навантажений, неорієнтований граф.
На основі алгоритма Прима або Крускала побудувати каркас мінімальної ваги, який і буде розв’язком задачі.

Подпись: 0 1
0 4
1 3
0 2
2 6
6 2
        




Програма:
program tallage;
{$apptype console}
var a:array[0..100,0..100] of extended;
x,y:array[0..100] of integer;
f1:text;
kol_ver,v:array[0..100] of integer;
n,k,i,j,vi,vj:integer;
min,s:real;
ver:array[0..100,1..2] of integer;
f:boolean;
cc:char;
begin
assign(f1,'tallage.dat');
reset(f1);
read(f1,n);
for i:=0 to n do begin
read(f1,x[i],y[i]);
end;
close(f1);

for i:=0 to n do
for j:=i to n do begin
a[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
a[j,i]:=a[i,j];
end;



k:=0;
v[k]:=0;
s:=0;
while (k<n) do begin
min:=maxint;
for i:=0 to k do
for j:=0 to n do
if a[v[i],j]<min then begin min:=a[v[i],j];vi:=v[i];vj:=j;end;
f:=true;
for i:=0 to k do if vj=v[i] then f:=false;
if f then
begin
k:=k+1;
ver[k,1]:=vi;
ver[k,2]:=vj;
v[k]:=vj;
kol_ver[vj]:=kol_ver[vj]+1;
kol_ver[vi]:=kol_ver[vi]+1;
s:=s+a[vi,vj];
end;
a[vi,vj]:=1e30;a[vj,vi]:=1e30;
end;
assign(f1,'tallage.sol');
rewrite(f1);
writeln(f1,s:3:3);
for i:=1 to n do
writeln(f1,ver[i,1],' ',ver[i,2]);
close(f1);
end.


Немає коментарів:

Дописати коментар