Вівторок, 21.09.2021, 22:57
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 62
Завдання І етапу Всеукраїнської учнівської олімпіади з інформатики 2012-2013 н.р.

Задача 1. Дині (melons) – 10 балів

Іван Васильович прийшов на базар і вирішив купити дві дині: одну для себя, а другу для тещі. Зрозуміло, що для себе потрібно вибрати диню якомога найважчу, а для тещі найлегшу. Але ось незадача: динь дуже багато і він не знає, як же вибрати саму найлегшу і саму найважчу диню. Допоможіть йому!

Вхідні дані. У першому рядку вхідного файлу melons.dat задано одне натуральне число N (N < 30000) - кількість динь. Другий рядок містить N чисел, записаних через пропуск. Тут кожне число - це маса відповідної дині. Всі маси динь натуральні числа і не перевищують 30000.

Вихідні дані. У вихідний файл melons.sol потрібно вивести два числа через пропуск: масу дині, яку Іван Васильович купить тещі і масу дині, яку він купить собі або вивести повідомлення "Ooops!" (без лапок), якщо хтось залишиться без дині.

Приклад вхідних та вихідних даних:

melons.dat
5
5 1 6 5 9

melons.sol
1 9

Рішення: програма на мові програмування Turbo Pascal 7.0

var f1,f2: text;
     i,n,x,max,min: integer;
begin
   assign(f1,'input.txt');
   reset(f1);
   assign(f2,'output.txt');
   rewrite(f2);
   max:=0;
   min:=30000;
   readln(f1,n);
   for i:=1 to n do
   begin
     read(f1,x);
     if x>max then max:=x;
     if x<min then min:=x;
   end;
   if max=min then writeln(f2,'Ooops!')
                  else writeln(f2,min,' ',max);
   close(f1);
   close(f2);
end.

Завантажити умову задачі, рішення та тести (11,6 Кб)


Задача 2. Хитре сортування (sorting) – 20 балів

Дана послідовність чисел. Необхідно впорядкувати ці числа за неспаданням останньої цифри, апри рівності останніх цифр – за не спаданням самих чисел.
Вхідні дані. Перший рядок вхідного файлу sorting.dat містить число N (1≤ N ≤100), а другий через пропуск самі числа Xi (1≤ i ≤N) – натуральні, що не перевищують 32000.

Вихідні дані. У вихідний файл sorting.sol виведіть послідовність чисел через пропуск, впорядковану згідно з умовою.

Приклад вхідних та вихідних даних:

sorting.dat
7
12 15 43 13 20 1 15

sorting.sol
20 1 12 13 43 15 15

Рішення: програма на мові програмування Turbo Pascal 7.0

var f1,f2: text;
      i,j,n,z: integer;
      x,y: array[1..100] of integer;
begin
   assign(f1,'sorting.dat');
   reset(f1);
   readln(f1,n);
   for i:=1 to n do read(f1,x[i]);
   close(f1);
   assign(f2,'sorting.sol');
   rewrite(f2);
   for i:=1 to n do
     y[i]:=x[i] mod 10;
   for i:=1 to n-1 do
     for j:=i+1 to n do
     begin
       if y[j]<y[i] then begin
                                z:=y[i];
                                y[i]:=y[j];
                                y[j]:=z;
                                z:=x[i];
                                x[i]:=x[j];
                                 x[j]:=z;
                             end;
       if y[j]=y[i] then
       begin
         if x[j]<x[i] then begin
                                  z:=x[i];
                                  x[i]:=x[j];
                                  x[j]:=z;
                                 end;
       end;
     end;
   for i:=1 to n-1 do write(f2,x[i],' ');
   writeln(f2,x[n]);
   close(f2);
end.

Завантажити умову задачі, рішення та тести (11,1 Кб)


Задача 3. Телебашта (tower) – 30 балів

Телевізійна компанія має план країни, на якому вказано розміщення міст і населення кожного міста. Вони хочуть встановити телебашту так, щоб найбільше число жителів змогло дивитись телепередачі. Сигнал від телебашти приймається у всіх точках, які знаходяться на відстані не більше R від неї. Вам пропонується написати програму, яка визначає точку, де потрібно встановити телебашту. При цьому встанавлювати телебашту (із міркувань безпеки самої телебашти) можна лише у якомусь з міст.

Вхідні дані. У вхідному файлі tower.dat записані спочатку радіус R (0≤ R ≤10000) дії телебашти та кількість міст N (1≤ N ≤100) у країні (N, R – цілі числа). Далі в Nрядках записано через пропуск по три числа: інформацію про кожне місто – координати (x, y) та населення. Всі координати - цілі числа, які не превищують по модулю 10000, а кількість жителів – невід'ємне число, яке не перевищує мільон чоловік.

Вихідні дані. У вихідний файл tower.sol виведіть через пропуск наступну інформацію: спочатку максимальну кількість жителів, які зможуть прймати сигнал від телебашти, потім номер міста, у якому необхідно встановити телебашту.

Приклад вхідних та вихідних даних:

tower.dat
1 4
0 1 4
0 0 5
1 0 3
1 1 2

tower.sol
12 2

Рішення: програма на мові програмування Turbo Pascal 7.0

var f1,f2: text;
     i,j,n,nmax,r: integer;
     max,s: longint;
     x,y: array[1..100] of integer;
     z: array[1..100] of longint;
begin
   assign(f1,'tower.dat');
   reset(f1);
   readln(f1,r,n);
   for i:=1 to n do readln(f1,x[i],y[i],z[i]);
   close(f1);
   assign(f2,'tower.sol');
   rewrite(f2);
   max:=0;
   nmax:=1;
   for i:=1 to n do
   begin
     s:=0;
     for j:=1 to n do
       if sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(r)
       then s:=s+z[j];
     if s>max then begin
                           max:=s;
                           nmax:=i;
                        end;
   end;
   writeln(f2,max,' ',nmax);
   close(f2);
end.

Завантажити умову задачі, рішення та тести (12,3 Кб)


Задача 4. Циклічні зсуви (shifts) – 40 балів

Запишемо ціле десяткове число N у двійковій системі числення і утворимо всі ліві циклічні зсуви числа N, при яких перша цифра числа переноситься в кінець числа. Наприклад, якщо N=11, в двійковій системі буде 1011, його циклічні зсуви: 0111, 1110, 1101, 1011. Максимальне значення M з усіх отриманих у такий спосіб чисел буде мати число 11102 = 1410. Для заданого числа N визначити максимальне значення M. prb27

Вхідні дані. Вхідний файл shifts.dat містить єдине число N (1 ≤ N ≤ 2·109).

Вихідні дані. У вихідний файл shifts.sol записати шукане число М.

Приклад вхідних та вихідних даних:

shifts.dat
11

shifts.sol
14

Рішення: програма на мові програмування Turbo Pascal 7.0

var f1,f2: text;
     s,cs: string;
     n,cn,z,x,max,p: longint;
     i,j,o,k: integer;
     y: char;
begin
   assign(f1,'shifts.dat');
   reset(f1);
   readln(f1,n);
   close(f1);
   assign(f2,'shifts.sol');
   rewrite(f2);
   cn:=n;
   s:='';
   while cn<>1 do
   begin
     z:=cn div 2;
     o:=cn mod 2;
     cn:=z;
     if o=0 then s:='0'+s
              else s:='1'+s;
   end;
   s:='1'+s;
   cs:=s;
   max:=0;
   repeat
     k:=length(cs);
     x:=0;
     for i:=k downto 1 do
     begin
       p:=1;
       for j:=1 to k-i do
         p:=p*2;
       if cs[i]='1' then x:=x+p;
     end;
     if x>max then max:=x;
     y:=cs[k];
     for i:=k-1 downto 1 do
       cs[i+1]:=cs[i];
     cs[1]:=y;
   until s=cs;
   writeln(f2,max);
   close(f2);
end.

Завантажити умову задачі, рішення та тести (11,0 Кб)

Наверх