Вінницька обласна олімпіада з інформатики 2015

УМОВИ ЗАДАЧ ОЛІМПІАДИ

ЗАДАЧІ З ПРОГРАМУВАННЯ 

Задача Ticket2.   У місті Старопрограмістську  є усього 2 види міського транспорту: метро, де квиток на одну поїздку коштує 3 біта (ось така там грошова одиниця) і автобус, квиток на поїздку у якому коштує 2 біта. Можна придбати проїзний  квиток на обидва види транспорту за 60 біт, на метро – за 40 біт, а на автобус – за 30 біт. Усі проїзні квитки дають право  на необмежену кількість поїздок протягом місяця.  Яку мінімальну суму витратить на міський транспорт за місяць житель міста програміст Байтученко, якщо протягом місяця він планово має виконувати x поїздок на метро та y  поїздок на автобусі?

Технічні умови. Програма Ticket2 читає з пристрою стандартного введення два числа  x та  y через пропуск (0 <=x; y<= 100). Програма виводить на пристрій стандартного виведення мінімально можливу суму місячних витрат Байтученка (зрозуміло, у бітах).

Приклад

Введення            Виведення 

9 30                         57

Програма мовою Паскаль

PROGRAM  Ticket2;

var   x,y,s1,s2,sum:  integer;

 begin

   read(x,y);

    s1:=x*3;

    s2:=y*2;

     if s1>= 40   then   s1:=40;

     if s2>=30   then   s2:=30;

          if s1+s2>=60 then sum:=60

   else

           sum:=s1+s2;

   writeln(sum);

   end.

Задача Clock2015.  У вінницькому  магазині-музеї  «Колоніальні товари. Пан Заваркін та сини»  є N  годинників. Відомо, що К з них показують неправильний  час, а покази решти – правильні. Потрібно написати програму, яка дозволить відвідувачу магазина дізнатися  точний час.

Технічні умови. Програма Clock2015 читає з пристрою стандартного введення  2 числа N і K (0 <= K <= N<= 1000), а далі N рядків по 2 числа – покази відповідного годинника. Перше число  - години (0-23),  друге – хвилини (0-59). Всі числа розділено пропусками. Програма виводить на пристрій стандартного виведення два числа – точний час у годинах та хвилинах.  Якщо однозначно точний час знайти неможливо – виведіть  -1.

Приклад

Введення             Виведення

5 3                        13 20                    

13 20
20 13
9 00
13 20
13 21

Програма мовою Паскаль

var i,m,k,res,n,p,j,r,h:longint;

 a:array[0..10000] of longint;

  begin

    read(n,k);

    p:=n-k;

      for i:= 1 to n do

        begin

          readln(h,m);

          m:=m+h*60;

          inc(a[m]);

        end;

      for j:= 0 to 10000 do

        if a[j]=p  then

         begin

         inc(r);

         res:=j;

         end;

     

 if r=1 then     begin

       write (res div 60,' ' );

          if res mod 60 <10 then write(0,res mod 60)

   else          write(res mod 60);

        end

else          write(-1);

       end.

---

 Задача Money.  У вас є достатня кількість монет 3-х номіналів a, b та c. Потрібно розрахуватися (тобто віддати продавцю) задану суму N максимально можливою кількістю монет. Монет продавцю потрібно дати не менше, ніж 2.  

Технічні умови. Програма Money читає з пристрою стандартного введення через пропуск чотири цілих числа N, a, b, c (1 ≤ N, a, b, c ≤ 40000) – N – задана сума і a, b, c – наявні номінали монет. Числа a, b і c можуть збігатися.

Вихідні дані: Виведіть одне число - максимально можливу кількість монет. Гарантується, що зазначену суму можна виплатити завжди.

Приклади

Введення

Виведення

Пояснення:

5 5 3 2

2

потрібно дати 2 монети: одна з них 2, друга 3.

7 5 5 2

2

потрібно дати 2 монети: одна з них 5, друга 2.

---

var

 g:array[-40000..41000] of LONGINT ;

 n,a,b,c,k,v1,v2,v3,i:longint;

  begin

   read(n,a,b,c);

    for i:= -n to n do   g[i]:=0;

     K:=0;

   g[a]:=1;

   g[b]:=1;

   g[c]:=1;

    for i:= 0 to n do

    if (i>=a) or (i>=b) or (i>=c)  then

       begin

        if (g[i-a]+1>g[i]) and (g[i-a]<>0) and(i>=a) then          g[i]:=g[i-a] +1;

            if (g[i-b]+1>g[i])  and (g[i-b]<>0)and (i>=b) then            g[i]:=g[i-b] +1;

            if (g[i-c]+1>g[i])   and (g[i-c]<>0) and (i>=c) then              g[i]:=g[i-c] +1;

        end;

       write(g[n]);

       end.

Задача  Castle.

Стародавній замок має прямокутну форму. Замок містить щонайменше дві кімнати. Підлогу замка можна умовно поділити на M x N клітин. Кожна така клітинка містить «0» або «1», які задають порожні ділянки та стіни замку відповідно. Напишіть програму, яка б знаходила площу найбільшої кімнати, яку можна утворити шляхом видалення стіни або її частини, тобто, замінивши лише одну «1» на «0». Видаляти зовнішні стіни заборонено.

Технічні умови. Програма  Castle  читає з пристрою стандартного введення «план замку». Перший рядок містить ціле число M, другий – ціле число  N – кількість рядків та кількість стовпчиків (3 ≤ M ≤ 1000, 3 ≤ N ≤ 1000). M наступних рядків містить по N нулів або одиниць, що йдуть поспіль (без пробілів). Перший та останній рядок, а також перший та останній стовпчик формують зовнішні стіни замку і складаються лише з одиниць. Програма виводить на пристрій   площу найбільшої кімнати, яка утвориться в разі видалення внутрішньої стіни.

Приклади:

Введення                       Виведення

6
8
11111111
10011001
10011001
11111001
10101001
11111111                        10                            

9
12
111111111111
101001000001
111001011111
100101000001
100011111101
100001000101
111111010101
100000010001
111111111111            

38                                     

Програма мовою Паскаль

var   n,m,i,j,color,sum,max:longint;

    c:char;

        a:array[-1..1001,-1..1001] of longint;

            s: longint;

   procedure dep(x,y,c:longint);

    begin

   inc(s) ;

    a[x,y]:=c;

     if (a[x,y+1]<>c)and (a[x,y+1]<>-1) then  dep(x,y+1,c);

        if( a[x,y-1]<>c)and (a[x,y-1]<>-1) then  dep(x,y-1,c);

          if (a[x+1,y]<>c) and (a[x+1,y]<>-1) then  dep(x+1,y,c);

            if (a[x-1,y]<>c) and (a[x-1,y]<>-1) then  dep(x-1,y,c);

    end;

      begin

        read(n,m);

        color:=1;

         for i := 1 to n do

         begin

         readln;

           for j:= 1 to m do

           begin

           read(c);

           a[i,j]:=ord(c)-48;

            if a[i,j]=1 then a[i,j]:=-1;

           end;

           end;

         for i:= 2 to n-1 do

             for j:= 2 to m-1 do

             begin

                 if a[i,j]=-1 then

                  begin

                           a[i,j]:=0;

                   dep(i,j,color);

                  if s>max then max:=s;

                   a[i,j]:=-1;

                   inc(color);

                             s:=0;

                                  end;

                        if a[i,j]=0 then

                  begin

                           a[i,j]:=0;

                   dep(i,j,color);

                   if s>max then max:=s;

                   inc(color);

                              s:=0;

                                   end;

                                   end;

        writeln(max);

           end.

Ще один варіант Програма мовою Паскаль через рекурсію

var n,m,i,j,p,x,y:integer;
    a:array[1..1000,1..1000] of longint;
    c:char;
    b:array[1..1000000] of longint;
    col,max,max1,cl,cp,cn,cw,nc,kc:longint;
    cx,cy:array[1..1000000] of integer;


{
procedure paint(q,w:integer);
 begin
   a[q,w]:=col;
   b[col]:=b[col]+1;
   if a[q-1,w]=0 then paint(q-1,w);
   if a[q+1,w]=0 then paint(q+1,w);
   if a[q,w-1]=0 then paint(q,w-1);
   if a[q,w+1]=0 then paint(q,w+1);
 end;}


 procedure paint(q,w:integer);
  begin
    nc:=1; kc:=1;
    cx[nc]:=q;
    cy[nc]:=w;
    while kc>=nc do
      begin
        x:=cx[nc];
        y:=cy[nc];
        a[x,y]:=col;
        b[col]:=b[col]+1;
        nc:=nc+1;
        if a[x-1,y]=0 then begin
                             kc:=kc+1;
                             cx[kc]:=x-1;
                             cy[kc]:=y;
                             a[x-1,y]:=col;
                           end;
        if a[x+1,y]=0 then begin
                             kc:=kc+1;
                             cx[kc]:=x+1;
                             cy[kc]:=y;
                             a[x+1,y]:=col;
                           end;
        if a[x,y-1]=0 then begin
                             kc:=kc+1;
                             cx[kc]:=x;
                             cy[kc]:=y-1;
                             a[x,y-1]:=col;
                           end;
        if a[x,y+1]=0 then begin
                             kc:=kc+1;
                             cx[kc]:=x;
                             cy[kc]:=y+1;
                             a[x,y+1]:=col;
                           end;

      end;
  end;






BEGIN
  readln(m);
  readln(n);
  for i:=1 to m do
    begin
       for j:=1 to n-1 do
         begin
           read(c);
           val(c,a[i,j],p);
         end;
       readln(c);
       val(c,a[i,n],p);
    end;



  col:=1;
  for i:=2 to m-1 do
    for j:=2 to n-1 do
       if a[i,j]=0 then
                      begin
                       col:=col+1;
                       paint(i,j);
                      end;



  max:=0;
  for i:=2 to m-1 do
   for j:=2 to n-1 do
     if a[i,j]=1 then
             begin
                max1:=1;
                cl:=a[i,j-1]; cp:=a[i,j+1];
                cw:=a[i-1,j]; cn:=a[i+1,j];
                if cl>1
                   then max1:=max1+b[cl];
                if ((cp>1) and (cp<>cl))
                   then max1:=max1+b[cp];
                if ((cw>1) and (cw<>cl) and (cw<>cp))
                   then max1:=max1+b[cw];
                if ((cn>1) and (cn<>cl) and (cn<>cp) and (cn<>cw))
                   then max1:=max1+b[cn];

                if max1>max then max:=max1;

             end;


 write(max);



END.