четверг, 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 класс) - вам идти на областной этап.

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

Удачи!


Комментариев нет:

Отправить комментарий