Розв’язки завдань 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 рядків містять через проміжок координати X_i , Y_i завойованих міст.

Значення координат по модулю менші 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

Розв’язок

Теорія графів-Жадібні алгоритми –  каркас мінімальної ваги (остове дерево)

Визначити довжини шляхів за формулою довжини відрізка .

На основі довжин побудувати навантажений, неорієнтований граф.

На основі алгоритма Прима або Крускала побудувати каркас мінімальної ваги, який і буде розв’язком задачі.

        

Програма:

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.