Некоторые способы решения задач

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

Задача 1.

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

Формат входных данных

В строке через пробел передаются следующие данные: скорость передачи в бит/сек (от 100 до 10⁹), время в секундах (от 1 до 10⁹), разрядность в битах (8, 16, 32, 64) и частота в герцах (от 100 до 10⁹), далее 1(моно) или 2 (стерео).

Формат выходных данных

Вывести время в формате: дд:чч:мм:сс - округлив секунды до целых.

Пример входных данных

100 10 16 1000 1

Пример выходных данных

00:00:26:40

Решение: Совершенно простая даже линейная задача на технологию программирования. В чем проблема: найти формулу вычисления времени и правильно перевести ее в целое число, а именно, округлить, а не брать целое от деления; далее - определиться с типом данных, если перемножить все большие числа и разделить на наименьшую скорость получим число порядка 10 в 20. Для такого числа с такой точностью потребуется как минимум 64-разрядное целое беззнаковое число. И, наконец, нужно обратить внимание на вывод чисел: если число меньше 10, то выводить с первым нулем. Итак, получим такой код программы:

var v,t,r,f,z,y,dd,hh,mm,cc:int64;
begin
  readln(v,t,r,f,z);
  y:=round(t/v*r*f*z);
  cc:=y mod 60;
  mm:=(y-cc) div 60 mod 60;
  hh:=(y-cc) div 3600 mod 24;
  dd:=(y-cc) div 86400 ;
  if dd<10 then write('0',dd) else write(dd);
  if hh<10 then write(':0',hh) else write(':',hh);
  if mm<10 then write(':0',mm) else write(':',mm);
  if cc<10 then write(':0',cc) else write(':',cc);
{ writeln(cc+mm*60+hh*3600+dd*86400); }
end.

Эта программа работает меньше секунды.

Задача 2.

Ученые решили собрать компьютер и использовать в качестве разрядов системы счисления члены ряда Фибоначчи, которые вычисляются по правилу: F[0]=0, f[1]=1, f[i]=f[i-1]+f[i-2], где i=2,3,4,5,... Любое натуральное число можно представить в виде суммы этих чисел, например: 7=5+2, 33=21+8+3+1 и так далее. Помогите написать программу, которая по введенному натуральному числу будет выводить кодовое число в виде 0 и 1, где в соответствующей позиции n, начиная справа, ставится 1, если число с номером n присутствует в сумме, иначе 0. Так для 7 кодовое число будет выглядеть так: 10100, для 33 – 10101010.

Формат входных данных

Вводится натуральное число n (от 0 до 10⁹).

Формат выходных данных

Вывести кодовое число.

Пример входных данных

33

Пример выходных данных

10101010

Решение: Задача на нестандартную систему счисления. Обратим внимание, что в этой системе используют только 0 или 1. Похоже на двоичную систему счисления. Разряды начинаются справа налево и обозначают числа 0, 1, 2, 3, 5, 8, и т.д. Здесь две единицы подряд не учитываются. Если в разложении уже есть число Фибоначчи, то можно сразу установить 1 на этот разряд. Таким образом, 0=1, 1=10, 2=100, 3=1000, 5=10000 и т.д. Теперь нужно определиться как долго искать это граничное число Фибоначчи, до какого порядка? Можно оценить это с помощью электронной таблицы. В программе можно считать только до нужного разряда. Затем из исходного числа последовательно вычитаем числа Фибоначчи с конца. Если разность будет больше нуля, то оставляем это число и запоминаем 1 в новом массиве, иначе 0. (В начале программы обязательно обнулить этот массив!) Если разность меньше 0, то переходим к следующему разряду (тоже начиная с конца). Так продолжаем, пока в результате не получим в разности 0. Вот код программы:

var f:array[0..1000]of int64;
    b:array[0..1000]of byte;
    j,k,i,n,m:integer;
begin
  readln(n);
  fillchar(b,sizeof(b),0);//зануляем массив
  f[0]:=0;f[1]:=1;f[2]:=2;
  if n=0 then writeln(1);
  if n=1 then writeln(10);
  if n=2 then writeln(100);
  if n>2 then begin
  for i:=3 to 1000 do begin
    f[i]:=f[i-1]+f[i-2];
    if f[i]>n then begin
     b[i-1]:=1;m:=f[i-1];k:=i-1;break;
    end;
  end;
  m:=n-m; j:=k;
  while m>0 do begin
    if m-f[k-1]>=0 then begin b[k-1]:=1;m:=m-f[k-1];k:=k-1;end
    else begin k:=k-1;end;
  end;
  m:=0;
  for i:=j downto 0 do write(b[i])

  end;
end.

Задача 3.

Миша и Ваня играли в шахматы. Все ходы были записаны судьей Машей (она маленькая и могла записать ходы не всегда верно). Через некоторое время Маше надоело записывать, она перевернула доску и пошла гулять. Восстановите расстановку шахматных фигур по записям Маши, если это возможно.

8
7
6
5
4
3
2
1
	A	B	C	D	E	F	G	H

Белые		Черные		Ходы
	Король		Король	Король ходит в любое поле на 1 клетку
	Ферзь		Ферзь	Ферзь ходит в любом направлении на любое поле
	Ладья		Ладья	Ладья ходит по вертикали или по горизонтали
	Слон		Слон	Слон ходит по диагональным направлениям
	Конь		Конь	Конь ходит «углом»: 2 прямо/назад – 1 влево/вправо или 1 прямо/назад – 2 влево/вправо
	Пешка		Пешка	Пешка ходит прямо, но рубит по диагонали на 1 клетку вперед

Формат входных данных

В каждой строке вводится ход одного из игроков в формате xn:ym, где x, y-символы от a до h; n, m – цифры от 1 до 8. Ходы типа рокировка, смена пешкой фигуры здесь не рассматриваются.

Формат выходных данных

Если входные данные ходов не верны, то в первой строке вывести “No solution”, если решение существует, то вывести таблицу расположения фигур, где для символов определены следующие фигуры:

k – белый король

q – белый ферзь

b - белый слон

r- белая ладья

p – белая пешка

n – белый конь

. – пустая клетка

K – черный король

Q – черный ферзь

B - черный слон

R- черная ладья

P – черная пешка

N – черный конь

Левый верхний угол шахматной доски при выводе начинается с позиции a8 и заканчивается позицией h1 – правый нижний угол.

Пример входных данных	Пример выходных данных
a2:a4 b7:b5 a4:b5 b8:c6 b5:c6 d7:c6	R.BQKBNR P.P.PPPP ..P..... ........ ........ ........ .ppppppp rnbqkbnr
a2:a4 b7:b8 c1:h1	No solution

Решение: Задача  на двумерный массив и последовательную проверку правильности ходов. Сложность состоит в проверке ходов для каждой фигуры и проверке правильности ходов: после черных идут белые, после белых - черные. Примерный код программы:

program project3;
var a:array['1'..'8','a'..'h']of char;
r1,c1,r2,c2,g,r,c,f,d,h:char;
flag:boolean;
k,i,j:integer;
{белый конь}
function hodnw(r1,c1,r2,c2:char):boolean;
begin
      hodnw:=true;
      if ((abs(ord(r1)-ord(r2))=2)and(abs(ord(c1)-ord(c2))=1))or
         ((abs(ord(r1)-ord(r2))=1)and(abs(ord(c1)-ord(c2))=2))
      then begin a[r2,c2]:='n'; a[r1,c1]:='.';end
      else   hodnw:=false;
end;
{черый конь}
function hodnb(r1,c1,r2,c2:char):boolean;
begin
      hodnb:=true;
      if ((abs(ord(r1)-ord(r2))=2)and(abs(ord(c1)-ord(c2))=1))or
         ((abs(ord(r1)-ord(r2))=1)and(abs(ord(c1)-ord(c2))=2))
      then begin a[r2,c2]:='N'; a[r1,c1]:='.';end
      else   hodnb:=false;
end;
{белый король}
function hodkw(r1,c1,r2,c2:char):boolean;
begin
      hodkw:=true;
      if (abs(ord(r1)-ord(r2))<=1)and(abs(ord(c1)-ord(c2))<=1)then begin
        a[r2,c2]:='k'; a[r1,c1]:='.';
       end  else   hodkw:=false;
end;
{черный король}
function hodkb(r1,c1,r2,c2:char):boolean;
begin
      hodkb:=true;
      if (abs(ord(r1)-ord(r2))<=1)and(abs(ord(c1)-ord(c2))<=1)then begin
        a[r2,c2]:='K'; a[r1,c1]:='.';
       end  else   hodkb:=false;
end;
{белая ладья}
function hodrw(r1,c1,r2,c2:char):boolean;
var g,f,h,d,c,r:char;
begin
     hodrw:=true;
     if ((abs(ord(r1)-ord(r2))=0)and (abs(ord(c1)-ord(c2))>0))or
         ((abs(ord(r1)-ord(r2))>0)and (abs(ord(c1)-ord(c2))=0))
     then begin
     if c1=c2 then begin
           if(r1<r2)then begin
           h:=r1; d:=r2;
           end
           else begin
           h:=r2;d:=r1;
           end;
          for r:=chr(ord(h)+1) to chr(ord(d)-1) do
            if a[r,c1]<>'.' then  hodrw:=false;
          end;
          if r1=r2 then begin
          if(c1<c2)then begin g:=c1; f:=c2;end else begin g:=c2;f:=c1; end;
          for c:=chr(ord(g)+1) to chr(ord(f)-1) do
            if a[r1,c]<>'.' then  hodrw:=false;
          end;
      a[r2,c2]:='r'; a[r1,c1]:='.';
      end
      else   hodrw:=false;
end;
{черная ладья}
function hodrb(r1,c1,r2,c2:char):boolean;
var g,f,h,d,c,r:char;
begin
     hodrb:=true;
     if ((abs(ord(r1)-ord(r2))=0)and (abs(ord(c1)-ord(c2))>0))or
         ((abs(ord(r1)-ord(r2))>0)and (abs(ord(c1)-ord(c2))=0))
      then begin
      if c1=c2 then begin
       if(r1<r2)then begin
       h:=r1; d:=r2;
       end
       else begin
       h:=r2;d:=r1;
       end;
      for r:=chr(ord(h)+1) to chr(ord(d)-1) do
        if a[r,c1]<>'.' then  hodrb:=false;
      end;
      if r1=r2 then begin
      if(c1<c2)then begin g:=c1; f:=c2;end else begin g:=c2;f:=c1; end;
      for c:=chr(ord(g)+1) to chr(ord(f)-1) do
        if a[r1,c]<>'.' then  hodrb:=false;
      end;
      a[r2,c2]:='R'; a[r1,c1]:='.';
      end
      else   hodrb:=false;
end;
{белый слон}
function hodbw(r1,c1,r2,c2:char):boolean;
var g,f,h,d,r:char;i:integer;
begin
     hodbw:=true;
    if (abs(ord(r1)-ord(r2))=abs(ord(c1)-ord(c2)))
      then begin
      if(r1<r2)then begin
      h:=r1; d:=r2; g:=c1;f:=c2;
      if(c1<c2)then i:=1 else i:=-1;
      end
      else
      begin
       h:=r2;d:=r1; g:=c2;f:=c1;
       if(c2<c1)then i:=1 else i:=-1;
      end;
      for r:=chr(ord(h)+1) to chr(ord(d)-1) do begin
          g:=chr(ord(g)+i);
          if a[r,g]<>'.' then  hodbw:=false;
      end;
      a[r2,c2]:='b'; a[r1,c1]:='.';
      end
      else   hodbw:=false;
end;
{черный слон}
function hodbb(r1,c1,r2,c2:char):boolean;
var g,f,h,d,r:char;i:integer;
begin
     hodbb:=true;
   if (abs(ord(r1)-ord(r2))=abs(ord(c1)-ord(c2)))
      then begin
      if(r1<r2)then begin
      h:=r1; d:=r2; g:=c1;f:=c2;
      if(c1<c2)then i:=1 else i:=-1;
      end
      else
      begin
       h:=r2;d:=r1; g:=c2;f:=c1;
       if(c2<c1)then i:=1 else i:=-1;
      end;
      for r:=chr(ord(h)+1) to chr(ord(d)-1) do begin
          g:=chr(ord(g)+i);
          if a[r,g]<>'.' then hodbb:=false;
      end;
      a[r2,c2]:='B'; a[r1,c1]:='.';
      end
      else   hodbb:=false;
end;
{белый ферзь}
function hodqw(r1,c1,r2,c2:char):boolean;
begin
     hodqw:=hodbw(r1,c1,r2,c2)or hodrw(r1,c1,r2,c2);
     a[r2,c2]:='q'; a[r1,c1]:='.';
end;
{черный ферзь}
function hodqb(r1,c1,r2,c2:char):boolean;
begin
     hodqb:=hodbb(r1,c1,r2,c2) or hodrb(r1,c1,r2,c2);
     a[r2,c2]:='Q'; a[r1,c1]:='.';
end;
{белая пешка}
function hodpw(r1,c1,r2,c2:char):boolean;
begin
     hodpw:=true;
     if ((ord(r2)-ord(r1)=1)and (ord(c1)-ord(c2)=0))or
        ((ord(r2)-ord(r1)=2)and (ord(c1)-ord(c2)=0)and(r2='4'))or
        ((ord(r2)-ord(r1)=1)and (abs(ord(c1)-ord(c2))=1)and (a[r2,c2]<>'.'))
     then begin a[r2,c2]:='p'; a[r1,c1]:='.'; end
     else hodpw:=false;
end;
{черная пешка}
function hodpb(r1,c1,r2,c2:char):boolean;
begin
     hodpb:=true;
     if ((ord(r1)-ord(r2)=1)and (ord(c1)-ord(c2)=0))or
        ((ord(r1)-ord(r2)=2)and (ord(c1)-ord(c2)=0)and(r2='5'))or
        ((ord(r1)-ord(r2)=1)and (abs(ord(c1)-ord(c2))=1)and (a[r2,c2]<>'.'))
     then begin a[r2,c2]:='P'; a[r1,c1]:='.'; end
     else hodpb:=false;
end;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
{заполняем массив игрового поля перед началом игры}
a['1','a']:='r';
a['1','b']:='n';
a['1','c']:='b';
a['1','d']:='q';
a['1','e']:='k';
a['1','f']:='b';
a['1','g']:='n';
a['1','h']:='r';
for c:='a' to 'h' do begin a['2',c]:='p'; a['7',c]:='P'; a['8',c]:=upcase(a['1',c]);end;
for r:='3' to '6' do
for c:='a' to 'h' do a[r,c]:='.';
{переменная k отвечает за ход: белые k=1, черные k=-1}
k:=0;
{переменная flag отвечает за правильность хода фигуры}
flag:=true;
{считываем первый ход и определяем кто ходит первым}
readln(c1,r1,g,c2,r2);
 if (a[r1,c1]='.') then flag:=false {пустая клетка ходить не может}
else
 if (a[r1,c1] in ['n','p']) and (a[r2,c2] = '.') {первым ходом может быть только конем или пешкой,
причем ее ход должен быть на пустую клетку}
then begin k:=1 ; {если первым ходят белые}
case a[r1,c1] of
'n':flag:=hodnw(r1,c1,r2,c2);
'p':flag:=hodpw(r1,c1,r2,c2);
end
end
else
 if (a[r1,c1] in ['N','P'] )and(a[r2,c2] = '.')
 then begin k:=-1 ;{если первым ходят черные}
case a[r1,c1] of
'N':flag:=hodNB(r1,c1,c2,r2);
'P':flag:=hodPB(r1,c1,c2,r2);
end
end
else flag:=false; {во всех остальных случаях ход не верен}
while flag and not eof() do begin {пока можно ходить и есть еще строки.
В этом случае окончание ввода с клавиатуры Ctrl+Z,Enter}
  readln(c1,r1,g,c2,r2);
  if (a[r1,c1]='.') then begin flag:=false;break; end;
  if (k=-1)and(a[r1,c1] in ['r','n','b','k','q','p'] )and (a[r2,c2] in ['.','N','R','B','K','Q','P'])
  then begin
   k:=1;
   case a[r1,c1] of
   'n':flag:=hodnw(r1,c1,r2,c2);
   'p':flag:=hodpw(r1,c1,r2,c2);
   'k':flag:=hodkw(r1,c1,r2,c2);
   'b':flag:=hodbw(r1,c1,r2,c2);
   'r':flag:=hodrw(r1,c1,r2,c2);
   'q':flag:=hodqw(r1,c1,r2,c2)
   else
    flag:=false;
   end;
  end else
  if (k=1)and(a[r1,c1] in ['R','N','B','K','Q','P'] ) and (a[r2,c2] in ['.','n','r','b','k','q','p'])
  then begin
   k:=-1;
   case a[r1,c1] of
    'N':flag:=hodnb(r1,c1,r2,c2);
    'P':flag:=hodpb(r1,c1,r2,c2);
    'K':flag:=hodkb(r1,c1,r2,c2);
    'B':flag:=hodbb(r1,c1,r2,c2);
    'R':flag:=hodrb(r1,c1,r2,c2);
    'Q':flag:=hodqb(r1,c1,r2,c2)
   else
    flag:=false;
   end;
  end else flag:=false;
end;
{вывод результата}
if flag then
 for r:='8' downto '1' do begin
  for c:='a' to 'h' do write(a[r,c]);
  writeln;
 end else
  write('No solution');
close(output);
end. 

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

Задача 4.

В соревнованиях по бегу принимают участие N спортсменов (3 ≤ N ≤ 1000). Результаты забега занесены в массив по порядку номеров участников. Все результаты участников различны. Определить время (результат) бронзового призёра.

Ввод
Первая строка содержит N - количество участников забега. Следующая строка содержит результаты каждого участника забега (через пробел) в последовательности номеров участников.
Вывод
На экран выводится время (результат) бронзового призёра.

Ввод 1	Ввод 2
10 1 7 4 5 8 9 2 3 6 10	6 8 7 5 4 3 2
Вывод 1	Вывод 2
3	4

Решение: Задача на массив, ее можно решить с помощью сортировки или просто запомнить первые три минимальных значения. Вот код программы:

program project1;
var i,n,a,b,c,d:integer;

begin
readln(n);a:=100000;b:=100000;c:=100000;
for i:=1 to n do begin
read(d);
if d<a then begin c:=b; b:=a; a:=d; end else
if d<b then begin c:=b; b:=d; end else
if d<c then begin c:=d; end;
end;
write(c)
end.