вторник, 20 декабря 2016 г.

Городская олимпиада по программированию - 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.

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

четверг, 17 ноября 2016 г.

Районная олимпиада по программированию 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.

среда, 16 ноября 2016 г.

Районная олимпиада 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.

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