Городская олимпиада по программированию - 2016 ч. 1

Городская олимпиада по программированию - 2016 

Олимпиада этого года погружала участников в частную жизнь мальчика Васи. Мальчик Вася обладает кучей неприятных особенностей - ленив, туп, жаден... А нам про него задачи решать. Ну, ладно, поехали.

Задач было 4. 

В каждом из классов встретилось 3 из них.

Поэтому я не буду разделять по классам, а просто объясню решение задач.

Задача 1. Тупость.

Папа у Васи силен в математике. А Вася не очень. Папа уехал в командировку, а Васе надо срочно для любого целого числа 0<N<10^9 найти количество пар неотрицательных целых чисел X и Y, таких, что:

X+Y+X*Y = N

Помогите Васе.

Решение.

Прежде, чем решать задачу, надо понять, что именно от вас требуется.

1. Надо искать не САМИ ЧИСЛА и количество пар, удовлетворяющих условию.

2. Для любого числа существует как минимум 2 пары: X=0, Y=N и X=N, Y=0 - точно удовлетворяющие этому условию.

3. X и Y никак ни могут быть больше N - потому, что пункт 2. Но могут быть какие-то числа между 0 и N.

Принцип решения: 

Запускаем цикл от 0 до N по X

Внутри него запускаем цикл от 0 до N по Y

Если равенство X+Y+X*Y = N выполняется, изменяем счетчик пар на 1.

Выводим результат на экран.

Не забываем проверять условия для переменных. В случае некорректного ввода возвращаем программу к вводу чисел.

program rep;

label 1;

var

n,x,y:longint;

k:byte;

begin

1: writeln('Vvedi 0<n<1000000000: ');

Readln(n);

If ((n<0) or (n>1000000000)) then goto 1;

For x:=0 to n do 

  for y:=0 to n do 

     If (x+y+x*y=n) then k:=k+1;

  

 writeln(' Vsego ',k,' par');

 end.

Задача 2. Жадность.

Вася выбирает себе подарок на новый год.  При этом он хочет 2 подарка из одного магазина. Стоимость подарка 0<А<10^9. Родители готовы дать ему X денег. При этом X - целое число, 0<X<10^9. В магазине не более 20 подарков в ассортименте.  Вася выбирает по принципу: 2 самых дорогих подарка, которые в сумме не превышают выделенную родителями сумму денег. Посчитайте максимальную сумму, на которую Вася может выбрать подарки.

При запуске программы необходимо ввести:

1. Количество подарков в магазине (и проверить, не больше ли 20, если что - отправить на повторный ввод)

2. Число, показывающее, сколько можно потратить

3. Стоимость каждого из подарков, имеющихся в магазине.

Программа выводит на экран сумму двух самых ценных подарков, подходящих под условие.

Решение.

1. Мы вводим все необходимые по условию данные, проверяя их на соответствие условию.

2. Узнав количество подарков, в цикле запрашиваем стоимость для каждого. Для этого мы зададим массив А[1..20], чтоб можно было запомнить стоимость каждого из подарков, мы помним, что их максимум 20.

3. Получив стоимость подарков, мы сортируем массив в порядке убывания (или возрастания, это не важно. В принципе, можно и не сортировать, но с сортировкой красивее...

program pod;

label 1,2;

var

x,s, max,z:longint;

n,i,j:byte;

a:array[1..20] of longint;

begin

1:Write('Skolko podarkov v magazine?  ');

Readln(n);

If ((n<=0) or (n>20)) then goto 1;

2:Write('Skolko deneg mogno potratit?  ');

Readln(x);

If ((x<0) or (x>1000000000)) then goto 2;

For i:= 1 to n do begin

write ('Stoimost ',i,' podarka = ');

Readln(a[i]);

end;

For j:=1 to n do 

For i:=1 to n-1 do 

if a[i]<a[i+1] then

begin

z:=a[i];

a[i]:=a[i+1];

a[i+1]:=z;

end;

For i:=1 to n-1 do 

For j:=i+1 to n do begin

if ((a[i]<x)and (a[j]<x) and (a[i]+a[j]>max) and (i<>j) and (a[i]+a[j]<=x)) then 

max:=a[i]+a[j];

End;

writeln('Max summa = ',max);

end.

О двух других задачах я расскажу в следующем посте.

Районная олимпиада по программированию 10-11 класс 2016.

Задача 1.

В одном государстве налоговая система выглядела так: 

• Налог составлял 1% от дохода гражданина, но при этом:
• Если при вычислении 1% получалось целое число, то налог составляет именно это целое число.
• Если при вычислении 1% получается дробное число (не важно, чему равна дробная часть - просто исходя из факта её наличия) - то налог составляет целую часть процента + 1.

Например: если доход составляет 300 тугриков, то 1% равен 3 и налог тоже 3. Если доход составляет 315 тугриков, то 1% равен 3,15, а налог равен 4.

Трудности у участников олимпиады вызвал тот момент, что округление по правилам математики в данном случае не удовлетворяют условию задачи.

Решение:

Вводим доход гражданина.

Проверяем наличие дробной части в 1%.

Напрягаемся, и вспоминаем, что 1% можно получить, разделив число на 100.

Напрягаемся 2, вспоминаем, что div позволяет получить целую часть от деления, а mod выводит ОСТАТОК от деления.

program z10_1_2016;

var

a,b:integer;

begin

Writeln('Vvedite dohod gragdanina');

readln(a);

if (a mod 100>0) then b:=(a div 100)+1

else b:=(a div 100);

writeln('Procent naloga sostavljaet ',b);

end.

Задача 2.

Задача № 2 в этом году, не поверите, палиндром. Определить, является ли строка палиндромом.

Эта задача подробно описана с различными вариантами решений в статье "Аргентина манит негра" этого блога, поэтому я не буду объяснять её здесь еще раз, а просто дам текст оптимального решения.

Program pal_2;

Var

s: string;  

i,f: byte; 

begin 

   write('String: '); 

   readln(s);            

   f := 0;                   

for i := 1 to length(s) div 2 do  

if s[i] <> s[length(s)-i+1] then 

   begin                                        

        writeln('No palindrome');  

        f := 1;                                   

        break                       

    end;                                            

 if f = 0 then write('Palindrome');                                                                    

end.    

Задача № 3.

Это тоже задача из прошлогодней олимпиады.

Если ход решения этой задачи не понятен - сходите СЮДА - мы решили аналог этой задачи в Scratch. Получилась такая веселая программка:

Видео доступно по ССЫЛКЕ

Из одного порта в другой необходимо перевезти 15 различных грузов. Грузоподъемность судна, на котором будет проходить перевозка, 50 тонн. Грузы пронумерованы, и информация о массах грузов хранится в массиве М(15). Определить, сколько рейсов необходимо сделать судну, если грузы неделимы и могут перевозиться только подряд в порядке их нумерации. (Предполагается, что масса отдельного груза не превышает 50 тонн). 

Смысл решения: берем кораблик номер  k и начинаем в него закладывать грузы по порядку. Если сумма того, что там уже есть, и масса текущего груза превышают 50, мы отправляем текущий кораблик, добавляем к k единичку и начинаем грузить дальше с того груза, который не влез в предыдущий кораблик.

program z3;

var

   m:array[1..15] of integer;

   k,i,s:integer;

Begin

   for i:=1 to 15 do

      begin

         writeln ('Введите m','[',i,']');

         readln (m[i]);

      end;

      k:=1; i:=1; s:=0;

##Внимание! Используем цикл   repeat - until. Подробности - в словаре сайта.##

      repeat

         if s+m[i]<=50 then

           begin

             s:=s+m[i];

             i:=i+1;

           end

              else

                 begin

                   k:=k+1;

                   s:=0;

                 end;

       until i>15;

       writeln ('Потребовалось ', k,' рейсов');

end.

Районная олимпиада 2016. 8-9 класс.

Задача 1.

Вкусный завтрак в школьной столовой стоит A гривен и B копеек. Степан заплатил C гривен и D копеек. Напишите программу, которая считает сдачу, полученную Степаном.

Логика решения:

1. Перевести все деньги в копейки, чтобы получать решение в меньшее количество действий.
2. Проверить, может ли Степан в принципе позволить себе завтрак.
3. От денег Степана отнять стоимость завтрака. Поскольку мы все перевели в копейки, то выводить надо два числа:
• Целая часть от полученной разности делить на 100 - гривны
• Остаток от деления полученной разности делить на 100 - копейки

Решение:

program z9_1;

var

a,b,c,d,e,f:integer;

begin

writeln('Vvedi cenu zavtraka');

readln(a,b);

writeln('Vvedi summu Stepana');

readln(c,d);

If (a*100+b<c*100+d) then 

begin

e:=((c*100+d)-(a*100+b))div 100;

f:=((c*100+d)-(a*100+b))mod 100;

Writeln('Sdacha=',e,'grn ',f,' kop');

end

else

writeln ('U Stepana malo deneg!');

end.

Задача 2.

Задана строка символов. Среди литер этого текста особую роль играет знак #, появление которого означает отмену предыдущей литеры текста; k знаков # отменяют k предыдущих литер (если такие есть) Напечатать строку с учетом роли знака #. Например, строка "VR#Y##HELO#LO" должна быть напечатана в виде: "HELLO". 

Решение: 

Обозначим s - исходную строку, dl - длину этой строки. 

Для решения создадим ещё одну строку s1(вначале пустую). 

Далее организуем цикл по номеру символа в строке s. 

Если очередной символ не #, то добавим его к строке s1, если это знак # и строка s1 не пустая, то удалим из неё последний символ.
Программа, реализующая данный алгоритм, будет иметь следующий вид:

program z9_2;

var 

s,s1:string;

dl,i,k:integer;

begin
  writeln('Введите строку');
  readln(s);
  dl:=length(s);
  s1:='';
  k:=0;

  for i:=1 to dl do
  if (s[i]='#')and(k<>0) then
    begin
    delete(s1,k,1);
    k:=k-1;
   end
  else
    begin
     k:=k+1;
     s1:=s1+s[i];
    end;
writeln(s1);
end.

Задача 3.

Полностью совпадает с задачей про компьютеры из прошлогодней олимпиады.
Посмотрите ЗДЕСЬ