четверг, 24 декабря 2015 г.

Разбор задач городской олимпиады - 2015.

Итак, задачи городской олимпиады. Давайте рассмотрим, что от нас требовалось...

Задача 1. Камень, ножницы, бумага, ящерица, Спок.
Шелдон: Предлагаю сыграть в «Камень, ножницы бумага, ящерица, Спок».
Радж: Во что?
Шелдон: Это очень просто. Ножницы режут бумагу, бумага накрывает камень, камень давит ящерицу, ящерица травит Спока, Спок ломает ножницы, ножницы отрезают голову ящерице, ящерица ест бумагу, бумага компрометирует Спока, Спок испаряет камень, и, как обычно, камень разбивает ножницы.
Два игрока играют в описанную игру. Каждый из них выбирает одну из 5 фигур: камень (rock), ножницы (scissors), бумага (paper), ящерица (lizard), Спок (Spock). Ваша задача - по их выбору определить, победил первый (first), второй (second) или случилась ничья (draw). Вам даны две строки - выбор первого и второго игрока соответственно. Выведите результат игры.
Ввод
Вывод
paper
first
Spock

lizard
second
scissors

rock
draw
rock






Эта задача могла принести участнику 20 баллов при условии, что программа работает правильно и написана наиболее рациональным способом.

Давайте разберемся, какие данные нам необходимо обработать. Абсолютно все участники олимпиады использовали прямое сравнение, написав примерно так:

If ((g1='rock') and (g2='scissor' or g2='lizard'))  then writeln ('first');

Смысл: если у первого игрока камень, а у второго ножницы или ящерица, то написать, что выиграл первый.

И еще 4 таких же строчки, где перечисляются выигрышные варианты для ножниц, бумаги, ящерицы и Спока.

Потом следовала проверка:

If (g1=g2) then writeln ('drow');

И для всех остальных случаев предлагалось написать, что выиграл второй игрок. При условии правильных расстановок операторов begin, end и else внутри этой конструкции всё работало нормально. Но Научный Консультант Олимпиады - представитель ВУЗа, проверяющий работу жюри из школьных учителей, настаивала на том, что такое решение (без использования циклов) - не рационально и не имеет права на максимальную оценку.

Я вам могу предложить решение с циклом. Однако на мой взгляд оно еще менее рационально. Но желание заказчика - закон...

Итак, давайте рассмотрим таблицу. Столбик с названиями фигур соответствует первому игроку. Строка - второму игроку. Значение на пересечении строки и столбца - это результат конкретного случая игры. При этом 0 соответствует ничьей, 1 соответствует победе, а -1 поражению.

Прочитайте урок про матрицы. Именно матрицу мы будем рассматривать в этом решении.



program Spock;
Var
a:array[1..5,1..5] of integer;
i,j,n:integer;
b:array[1..5] of string;
g1,g2:string;
f,g:text;

В разделе переменных мы задаем: 
  • массив а - это будет наша табличка, как на рисунке выше
  • массив b - это список возможных фигур, показанных в игре
  • три переменных целого типа - счетчики
  • две текстовых переменных - чтоб взять из файла input.txt фигуры первого и второго игроков
  • два файла: с входящими данными и ответом. 

begin
assign (f,'input.txt');
reset (f);
readln (f,g1,g2);
close(f);

В начале программы читаем, какой ход сделал каждый из игроков.

b[1]:='rock';
b[2]:='scissors';
b[3]:='paper';
b[4]:='lizard';
b[5]:='Spock';

Заносим все возможные фигуры в массив b

For i:=1 to 5 do begin
For j:=1 to 5 do begin
if i=j then a[i,j]:=0;
if ((i=1) and ((j=2) or (j=4)))then a[i,j]:=1;
if ((i=2) and (j=3))then a[i,j]:=1;
if ((i=2) and (j=4)) or ((i=3) and (j=1)) then a[i,j]:=1;
if( ((i=3) and (j=5))or ((i=4) and (j=3)))then a[i,j]:=1;
if (((i=4) and (j=5))or ((i=5) and (j=1)))or ((i=5) and (j=2))then 
a[i,j]:=1 else 
a[i,j]:=-1;
end;
end;

Заполнили матрицу значениями, соответствующими исходу игры.

for n:=1 to 5 do begin
if g1=b[n] then i:=n;
if g2=b[n] then j:=n;
end;

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

assign (g,'output.txt');
rewrite (g);

case a[i,j] of

1:write(g,'first');
0:write(g,'draw');
-1:write(g,'second');
end;

Использовали оператор case чтоб вывести необходимый результат.

close(g);
end.

Закончили выполнение программы, закрыв предварительно файл результата.

Вот и все с задачей № 1.

Задача 2. Строки в книге                                                                                                                        
В книге на одной странице помещается к строк. Таким образом, на 1-й странице печатаются строки с 1-й по k-ю, на второй — с (k+1)-й по (2 k)-ю и т.д. Напишите программу, которая по номеру строки в тексте n (1 < n < 109) и количеству строк на странице k (1 < к < 109) определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.
Ввод
Вывод
1 50
1 1
25 20
2 5
43 15
3 13


Тут все совсем просто:

program Kniga;
Var
n,k,s,p:integer;
f,g:text;

begin
assign (f,'input.txt');
reset (f);
readln (f,n,k);
close(f);

Прочитали номер строки в тексте и количество строк на странице.

s:= n div k;
if s=0 then s:=1;

Смотрите. Если у вас 15 строка, а на странице помещается 20 строк, то при ЦЕЛОЧИСЛЕННОМ делении 15 на 20 мы получим 0. Но 15 строка у нас не на 0, а на 1 странице! Поэтому if s=0 then s:=1;

p:= n mod k;
if p=0 then p:=k;

Если у вас 60-я строка, а на странице помещается 20 строк, то при делении 60 на 20 остатка не будет. Но 60 строка будет просто 20 на 3 странице, поэтому if p=0 then p:=k;

assign (g,'output.txt');
rewrite (g);
write(g, s,' ',p);
close (g);
end.

Напечатали ответ и закончили выполнение программы.

Задача 3. Шашки
На доске стоит белая шашка. За один ход она может переместиться на одну клетку по диагонали наверх. Клетка называется достижимой, если шашка может попасть в нее за любое ненулевое число ходов. По начальному положению шашки посчитайте количество достижимых клеток.

Ввод
Вывод
al
19
g7
2

Что надо учесть в задаче? 
Во-первых, что доска имеет только 8 строк и 8 столбцов.
Во-вторых, что шашка ходит по диагонали.

Шахматная доска выглядит условно вот так, как на рисунке выше.

Program Shashki;
label 1;
var
a,b,c,n,k,kol:integer;
f,g:text;
kl:string;
begin

assign (f,'input.txt');
reset (f);
readln (f,kl);
close(f);

Мы получили во входном файле букву и цифру, т.е. переменную типа string , теперь надо в зависимости от первого и второго символа разместить шашку на доске. 

Обрабатываем первый символ:

case kl[1] of
'a':b:=1;
'b':b:=2;
'c':b:=3;
'd':b:=4;
'e':b:=5;
'f':b:=6;
'g':b:=7;
'h':b:=8;
else goto 1;
end;

Обрабатываем второй символ:

case kl[2] of
'1':a:=1;
'2':a:=2;
'3':a:=3;
'4':a:=4;
'5':a:=5;
'6':a:=6;
'7':a:=7;
'8':a:=8;
else goto 1;
end;

Если внезапно нашелся третий символ (доска 8 на 8, не забываем!) - отправляем в конец программы. Собственно, то же самое мы делаем, если буква или цифра из двузначного символа не соответствует клетке доски.

if kl[3]<>' ' then goto 1; 


c:=b;
while a<8 do
 begin
 a:=a+1;
if b>1 then n:=b-1 else n:=b+1;
if c<8 then k:=c+1 else k:=c-1;
b:=n;
c:=k;
kol:=kol+1;
while n<=k-2 do
begin
n:=n+2;
kol:=kol+1;
end;
end;

В блоке выше мы считаем все возможные передвижения шашки. 

assign (g,'output.txt');
rewrite (g);
writeln(g,kol);
close(g);
1:end.

Программа закончена.

Вот, в принципе, и все. Молодцы: Макс Васильев (1 место, 8 класс), Марк Приймак и Павел Карлин (3 места, 10 класс) - вам идти на областной этап.

Молодцы, еще все впереди у тех, кто не занял призовых мест, но сражался с задачами до последнего!

Удачи!


понедельник, 9 ноября 2015 г.

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

Самое главное: из 6 участников от нашей школы все 6 заняли призовые места!


Поздравляю победителей!
Марк Приймак - 10 класс - 1 место
Павел Карлин - 10 класс - 2 место
Александр Купченко - 8 класс - 2 место
Максим Васильев - 8 класс - 2 место
Лев Ливинский - 11 класс - 3 место
Константин Устименков - 8 класс - 3 место


А теперь разберем, что было сделано не совсем так, и как надо было сделать правильно.

Задача 1.

Палиндром. Палиндром, Карл! Смотрим СЮДА, Паша - молодец, повторил перед олимпиадой!

Задача 2.

Цветное изображение имеет N цветов. Размер изображения AxB см. Разрешение R точек на дюйм (1 дюйм = 2,54 см).
Определить, сколько Кбайт памяти нужно для хранения изображения в несжатом виде?

Входные данные
Первая строка содержит натуральное число N количество цветов. Следующие две строки содержат действительные числа, которые задают размер фотографии. Последняя строка содержит натуральное число, которое задает разрешение. Все числа входного файла по абсолютной величине не превышают 1000000000.

Выходные данные
Единственная строка файла содержит искомый размер фотографии, как действительное число с двумя знаками после запятой.

Пример входных и выходных данных
input.txt
output.txt
8
10
15
30
766.29
Решение
Для решения задачи необходимо определить количество бит занимаемая точка и подсчитать их количество. Для определения количества бит используется соотношение n=2k (где n — количество точек, k — количество бит), отсюда


Т.е. мы получаем логарифм по основанию 2 числа n, но, поскольку Паскаль не умеет считать логарифмы по произвольному основанию, по правилам работы с логарифмами приводим нужный результат к натуральным логарифмам, с основанием  числа Эйлера, мы об этом говорили.

Данная формула используется для определении количества двоичных кодов в бинарном дереве.
n
b
2
4
8
16
32

256
65536
16777216
1
2
3
4
5

8
16
24

В итоге, с логарифмами это решается так:

program photo;
var bit,n,a,b,r:integer;
k:real;
f1,f2:text;

begin
assign(f1,'photo.dat');
reset(f1);
read(f1,n,a,b,r);
close(f1);

bit:=round(ln(n-1)/ln(2)+1);
k:=(a/2.54)*(b/2.54)*r*r*bit/8/1024;
k:=int(k*100)/100;

assign(f2,'photo.sol');
rewrite(f2);
writeln(f2,k:2:2);
close(f2);
end.

Можно решить БЕЗ логарифмов. Тогда программа будет выглядеть так:

program photo;
var bit,n,a,b,r:integer;
k:real;
f1,f2:text;
begin
assign(f1,'photo.dat');
reset(f1);
read(f1,n,a,b,r);
close(f1);
bit:=1;
n:=n-1;
while n>1 do begin
bit:=bit+1;
n:=n div 2;
end;
if n>2 then bit:=bit+1;
k:=(a/2.54)*(b/2.54)* r * r * bit/8/1024;
k:=int(k*100)/100;
assign(f2,'photo.sol');
rewrite(f2);
writeln(f2,k:2:2);
close(f2);
end.

Знать математику - выгоднее, чем не знать. Задание: объяснить, в чем разница между двумя вариантами программы.

Задача 3.

Из одного порта в другой необходимо перевезти 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.

Очень рекомендую сходить на сайт: Олимпиады по информатике
И скачать и разобрать задачи с решениями

Районная олимпиада по программированию - 2015 (8-9 класс)

Самое главное: из 6 участников от нашей школы все 6 заняли призовые места!


Поздравляю победителей!
Марк Приймак - 10 класс - 1 место
Павел Карлин - 10 класс - 2 место
Александр Купченко - 8 класс - 2 место
Максим Васильев - 8 класс - 2 место
Лев Ливинский - 11 класс - 3 место
Константин Устименков - 8 класс - 3 место


А теперь разберем, что было сделано не совсем так, и как надо было сделать правильно.

8-9 класс.

Задача 1.

Найти наибольшее отношение трехзначного числа к сумме его цифр.

Решение.
1. Давайте уточним условие. Вы не просите пользователя вводить числа. Это должен сделать компьютер. Причем компьютер должен перебрать все числа от 100 до 999, для каждого считая результат: ЧИСЛО/(Сумму его цифр)

2. На экран требуется вывести только то число, для которого результат из пункта 2 окажется максимальным.

Основная ошибка наших олимпиадников (впрочем. не только наших) - непреодолимое желание поговорить с пользователем. При этом найдя проблемы на свою голову.

Если вам вводят число с клавиатуры, вы должны делить его на разрядные единицы - сотни. десятки, единицы - чтоб потом считать сумму. Я не знаю автора работы, который вплотную приблизился к решению задачи, но все равно сделал не так. как надо. Он упорно считал результат для каждого введенного числа. Но на экран выводил примерно следующее:

Вы ввели число 123
Результат для вашего числа 20,5

НАИБОЛЬШЕЕ ОТНОШЕНИЕ трехзначного числа к сумме его цифр имеет число 100. 
100/1 = 100.

Ребенок вручную посчитал результат и просто сообщал его каждому зашедшему в его программу.

Что НАДО было сделать? Надо было, чтобы компьютер ПЕРЕБРАЛ все варианты от 100 до 999 и выбрал максимальный результат.

Как это нужно было сделать?
Заказываем необходимое количество переменных нужных типов. 
Var
i,j,k,a,b,sum:integer;
max,d:real;

begin
max:=0;  Считаем, для начала, что максимальный результат 0.
a:=0;
b:=0;

А вот тут мы начинаем создавать наши числа, меняя сотни, десятки и                                             единицы. i будет отвечать за количество сотен, поэтому начинается с 1, j будет заведовать десятками, начинается с 0, и k займется единицами, тоже с нуля - таким образом первое из полученных нами чисел будет (i*100+j*10+k), т. е. 100.

For i:=1 to 9 do begin   
  for j:=0 to 9 do begin
    for k:=0 to 9 do begin
     
Сразу считаем сумму цифр. Потом делим наше число на эту сумму. Результат запоминаем в d.
     sum:=i+j+k;
     d:=(i*100+j*10+k)/sum;
Если d оказалось больше максимума, мы запоминаем само число в   a, запоминаем сумму цифр в     b, и меняем максимум на этот улучшенный результат. 
     
 if d>max then 
      begin
        max:=d;
        a:=i*100+j*10+k;
        b:=sum;
        end;
     end;
    end;
   end;

Когда мы отработали все циклы, уже можно поговорить с пользователем - вывести ему сообщение.
   
 Writeln ('Maximum = ',max,' pri delenii ',a,' na ',b);
 end.

Вот и все.


Задача 2.

Дана строка, состоящая из символов, каждый из которых является знаком «+» или цифрой, начинающаяся и заканчивающаяся цифрой. Если в строке встречается сочетание «++», то выдать сообщение об ошибке, в противном случае вычислить получившуюся сумму.

var
  i,res: integer;
begin
  res:=0;
  for i := 1 to length(s) - 1 do
    if (s[i] = '+') and (s[i+1]= '+' ) then
      begin
        write('Error');
        exit;
      end;
  for i := 1 to length(s) do
    if s[i] <> '+' then 
res:= res + StrToInt(s[i]);
  write(res);
end.

Эта задача рассчитана больше на знание языка программирования, чем  на сообразительность. Для решения задачи можно использовать функцию "ORD", которая позволяет получить порядковый номер любого символа согласно таблице ASCII-кодов. Например, номер символа '0' - 48, а номер символа '1' - 49. Как вы понимаете, чтобы получить искомую цифру, необходимо отнять от номера символа 48.

Внимание!
  1. Во входной строке нет пробелов!
  2. Функция ORD будет работать в Turbo Pascal, но не будет работать в Pascal ABC.
  3. Pascal ABS поддерживает синтаксис Delphi, поэтому необходимо заменить строку "res:= res + (ord(s[i])-48);" на "res:= res + StrToInt(s[i]);"

Задача 3.

Между школами поделили N компьютеров Pentium и M компьютеров Celeron. 
Сколько было школ, если известно их не менее K и каждая школа получила 
одинаковое количество компьютеров каждого вида.
Все числа входного файла не превышают 1000000000.
Входные данные
Первая строка содержит натуральные числа N, M, K.
Выходные данные
Единственная строка файла содержит найденное количество школ. Если результатов несколько, то вывести все через пробел в возрастающем
порядке.
Пример входных и выходных данных

input.txt
output.txt
92 138 25
46
Решение
Необходимо найти общие делители чисел M и N, не меньше числа K.
var i,n,m,k,min:integer; f,g:text;
begin assign(f,'input.txt'); reset(f); read(f,n,m,k); close(f);
assign(g,'output.txt'); rewrite(g);
if n>m then min:=m else min:=n;
for i:=k to min do begin if (n mod i=0)and(m mod i=0) then write(g,i,' '); end;
writeln(g); close(g);
end.
В принципе, с задачами 8-9 класса - все. Разобрать. Задать вопросы. Поехали!
Домашняя работа: изучить сайт с олимпиадами за 3 последних года: 

Скачать и разобрать : задачи с решениями