програмування 2014

На цій сторінці розглянуті завдання районної олімпіади з програмування у Косівському районі (2014 рік).

1.Годинник (15 балів)

Старовинний годинник з дванадцятигодинним циферблатом б’є в кінці останньої хвилини кожної години. Бій триває менше однієї хвилини. Кількість ударів відповідає показам годинникової стрілки (1 удар – о першій ночі і о першій дня, по 2 удари – о другій години ночі та о другій дня і так далі, опівночі і опівдні він б’є, відповідно, по 12 разів.
Дано проміжок часу (відомо, що пройшло строго менше 24 годин). Напишіть програму, що визначає, скільки ударів зробив годинник за цей час.

Вхідні дані: ви вводите з клавіатури у першому рядку початковий момент часу, в другому рядку — кінцевий. Моменти часу задаються двома цілими числами, що розділяються пропуском. Перше число задає години (від 0 до 23, друге – хвилини (від 1 до 59).
Вихідні дані: ви виводите на екран одне число — кількість ударів, які зробив годинник за цей відрізок часу
Тести до задачі:             вхід                                          вихід
                                         5 20                                              40

                                        10 25
                                        10 25                                             116
                                         5 20 
                                         5 2                                                0
                                         5 21
Особливих пояснень задача не потребує. Зрозуміло, що дані про хвилини участі у програмі не беруть. При початковому часі більшому за кінцевий, зрозуміло, що потрібен один додатковий повний оберт годинникової стрілки. Цей варіант розглядається на початку програми шляхом надання змінній S початкового значення.

program time;
var
h1, h2, m1, m2, i, s: integer;

begin
writeln('Введіть початковий час');
readln(h1, m1);
writeln('Введіть кінцевий час');
readln(h2, m2);
if h1 > h2 then                           //якшо початковий час більший за кінцевий, то
for i := 1 to 12 do                      //додатково обчилюємо кількість ударів за
     s := s + i else                             //повний оберт циферблата
s := 0;
while h1 <> h2 do
    begin
    h1 := h1 + 1;
    if h1 > 12 then begin; h1 := 1; end;
    s := s + h1;
end;
writeln(s);
end.

 

2. Зелена пляма (20 балів). 

   Два прожектори утворюють на стіні дві плями квадратної форми, одну – блакитного, а другу – жовтого кольору. Визначити площу плями зеленого кольору, яка утворилася внаслідок накладання двох плям – блакитної та жовтої.

 Вхідні дані: ви вводите з клавіатури у першому рядку координати лівої нижньої вершини кожного квадрата (натуральні числа x1,y1, х2, у2 <1000, розділені пропуском), у другому рядку – довжини сторін квадратів (натуральні числа а1, а2<100, розділені пропуском).

Вихідні дані: ви виводите на екран одне число – площу.

 Тести до задачі «Зелена пляма»

Тест №1: Вхід: 1 1 3 5 2 2 Вихід: 0
Тест №2: Вхід: 3 5 4 3 2 3 Вихід: 1
Тест №3:Вхід: 1 1 1 1 9 2 Вихід: 4
Тест №4: Вхід: 300 798 300 700 99 99 Вихід: 99
Тест №5:Вхід: 800 800 810 810 99 10 Вихід: 100

 Ідея розв’язання даної задачі полягає в слідуючому:

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

  program zel_pl;
var
  a: array[1..1000, 1..1000] of integer;
  x1, x2, y1, y2, a1, a2, i, j, s: integer;

begin
  writeln('Ввести координати');
  readln(x1, y1, x2, y2);
  writeln('Ввести довжини сторін');
  readln(a1, a2);
  for i := x1 to x1 + a1 - 1 do
    for j := y1 to y1 + a1 - 1 do a[i, j] := 1;
  for i := x2 to x2 + a2 - 1 do
    for j := y2 to y2 + a2 - 1 do
      if a[i, j] = 1 then a[i, j] := 2;
  for i := 1 to 1000 do
    for j := 1 to 1000 do if a[i, j] = 2 then s := s + 1;
  writeln(s);
end.

3. Номери кімнат (25 балів)

Кімнати в готелі нумеруються натуральними числами починаючи з 1 (послідовно і без пропусків). Столяр готелю отримав завдання поміняти номерки на дверях кімнат на нові. Щоб зекономити час і зусилля він вирішив виготовити необхідні йому цифри із заготовок, які можна купити. Але переплачувати за зайву кількість заготовок він теж не хоче. Допоможіть столяру підрахувати скільки заготовок для цифр йому знадобиться?

Вхідні дані. У вхідному файлі З.in міститься одне натуральне число N — кількість кімнат у готелі (1 <N<5000).

Вихідні дані. У вихідний файлі 3.out потрібно записати одне натуральне число — необхідну кількість заготовок.

Приклади вхідних і вихідних даних:  Тест 1.  Вхід: 9       Вихід 9    Тест 2. Вхід 123       Вихід 261

За логікою третя задача повинна бути складніша за першу і другу. Але проаналізувавши умову можна зрозуміти, що потрібно просто знайти кількість цифр, що використовуються для нумерації кімнат. Тому розв’язання даної задачі є достатньо простим. 

program nomerki;

var
  n, k, i: integer;

begin
  writeln('');
  readln(n);
  for i := 1 to n do
  begin
    if i <= 9 then k := k + 1 else
    if i <= 99 then k := k + 2 else
    if i <= 999 then k := k + 3 else k := k + 4;
  end;
  writeln(k);
end.

   4 Будинок лісника (40 балів)

Лісник Микола вирішив побудувати в лісі будинок. Він дуже любить природу, тому вирішив будувати його так, щоб не довелося зрубувати дерева. А будинок він хоче якомога більший і обов’язково квадратної форми. Микола вибрав прямокутну ділянку лісу і поділив її на умовні квадрати. Зайняті деревами квадрати він позначив 0 а вільні – 1. В результаті він отримав прямокутний масив, який містить М рядків по N цифр 0 або 1 в кожному (1 <= М, N <= 100). Допоможіть ліснику знайти максимально можливу площу квадратного будинку, який можна розмістити на умовних квадратах, позначених 1. Стіни будинку мають бути паралельні сторонам прямокутної ділянки.

Вхідні дані. Перший рядок вхідного файлу 4.in містить число М – кількість стовпчиків прямокутної ділянки. Другий рядок вхідного файлу 4.іn містить число N – кількість рядків прямокутної ділянки. Наступні N рядків файлу містять по М цифр: 0 або 1.

Вихідні дані. У вихідний файлі 4.out потрібно записати одне натуральне число – максимально можливу площу квадратного будинку, або нуль, якщо будинок не можна побудувати взагалі.

Примітка: площа умовних квадратів, на які поділена ділянка рівна 1. Приклади вхідних і вихідних даних:

4.іn

30
20
000000001000000000000000000000
000001111111111100000000000000
000000111111110100000000000000
000000111111110000000000000000
000000111111110000000000000000
000001111111110000000000000000
000011111111110000000000000000
000111111111110000000000000000
001111111111110000000000000000
000000000000000000000000000000
000000000000000011111111110000
000000000000000011111111110000
000000000000000011111111110000
000000000000000011111111110000
000000000000000011111111110000
000000000000000011111111110000
000000000000000011111111110000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000

 

4.out
 64
Для цієї задачі була написана нижче наведена програма.Думаю, що з коментарів буде все зрозуміло.
program lisnik;
var
i, j, n, m, s, s1, smax, r, roz: integer;
a: array[1..100, 1..100] of integer;
f1: text;

procedure bud(istart, jstart, rozmir: integer; var plosh, rez: integer);
var                              {процедура обчислює площу квадратного масиву одиничок.}
i1, j1: integer;                 { Якщо у масив потряпляє ноль, то}
begin               {процедура видає площу=0 і змінна-прапорець(rez) також ноль}
plosh := 0;
for i1 := istart to istart + rozmir - 1 do
for j1 := jstart to jstart + rozmir - 1 do
if a[i1, j1] = 1 then plosh := plosh + 1;
if plosh = rozmir * rozmir then rez := 1 else begin rez := 0; plosh := 0; end;

end;

begin
writeln('введіть кількість рядків');      {зчитуємо вхідні дані}
readln(n);
writeln('введіть кількість стовпчиків');
readln(m);
assign(f1, '1.txt');
reset(f1);
for i := 1 to n do
for j := 1 to m do read(f1, a[i, j]);
close(f1);

smax := 0;r:=0;
for i := 1 to n do         {перебираємо елементи масиву}
for j := 1 to m do
begin
if a[i, j] = 1 then       {якшо попадаємо на 1, тобто на вільне місце}
begin                         {то визначаємо його площу}
s := 1;                       { s-початкова площа ділянки}
r := 1;                       {r- прапорець показує, що є хоча б одна вільна клітинка}
roz := 1;                   {roz-розмір прямокутної ділянки}
while r = 1 do          {організовуємо цикл у якому будемо викликати процедуру}
begin
bud(i, j, roz, s, r);                       {для обчислення площі}
if r = 1 then      {якщо процедура видає площу, то збільшуємо }
begin
s1 := s; roz := roz + 1;        {розмір масиву}
end;                                                                        
end;
if s1 > smax then smax := s1; {якщо знаходимо більшу площу, то переприсвоюємо результат}
end;
end;
writeln(smax);
end.