Вконструкторском бюро проектируют планетоход для исследования поверхности планеты марс. исследования должны проводиться на прямоугольной

Question

Информатика: Вконструкторском бюро проектируют планетоход для исследования поверхности планеты марс. исследования должны проводиться на прямоугольной области планеты без препятствий внутри неё. эта область разделена на единичные квадраты и имеет размеры m×n, где m – длина прямоугольника, а n – его ширина. планируется, что планетоход должен работать по следующей программе. вначале он садится в северо-западном углу заданной области в направлении на восток. после этого планетоход начинает обход и исследование выбранной

Georgiy111111 · Answer

Рассматривая различные прямоугольники и подсчитывая в них число поворотов P, можно прийти к следующему алгоритму. Для любого натурального k получаем:
$P=\begin {cases} 0, \ min(M,N)=1 
\\4k-2, \ min(M,N)=2k, \, M=N, \, k \in \mathbb N \\ 4k-1, \ 
min(M,N)=2k, \, M \neq N, \, k \in \mathbb N \\ 4k, \ min(M,N)=2k+1, \,
 M=N, \, k \in \mathbb N \\ 4k+1, \ min(M,N)=2k+1, \, M \neq N, \, k 
\in \mathbb N \\ \end {cases}$

var
M, N, k, mn, P: integer;
f: Text;

begin
Assign(f, 'input.txt');
Reset(f);
Readln(f, M, N);
Close(f);
if M < N then mn := M else mn := N;
if mn = 1 then P := 0
else begin
    k := mn div 2;
    if mn mod 2 = 0 then
      if M = N then P := 4 * k - 2
      else P := 4 * k - 1
    else
    if M = N then P := 4 * k
    else P := 4 * k + 1
end;
Assign(f, 'output.txt');
Rewrite(f);
Writeln(f, P);
Close(f)
end.

Популярные вопросы