• Document: 3-я командная олимпиада
  • Size: 147.84 KB
  • Uploaded: 2019-01-12 12:12:30
  • Status: Successfully converted


Some snippets from your converted document:

3-я командная олимпиада по программированию 16.04.2009 3-я командная олимпиада Задача A. Количество путей в лабиринте (Время: 1 сек. Память: 16 Мб) Карта лабиринта представляет собой квадратное поле размером NxN. Некоторые квадраты этого поля запрещены для прохождения. Шаг в лабиринте – перемещение из одной разрешенной клетки к другой разрешенной клетке, смежной с первой по стороне. Путь – это некоторая последовательность таких шагов. При этом каждую клетку, включая начальную и конечную, можно посещать несколько раз. Требуется написать программу, которая подсчитает количество различных путей из клетки (1, 1) в клетку (N, N) ровно за K шагов (то есть оказаться в клетке (N, N) после K-го шага). Входные данные Входной файл INPUT.TXT содержит в первой строке числа N и K, разделенные пробелом (1 < N ≤ 15, 0 < K ≤ 30). Следующие N строк, по N символов в каждой, содержат карту лабиринта, начиная с клетки (1, 1). Символ «0» означает не запрещенную для прохождения клетку, а символ «1» - запрещенную. Начальная и конечная клетки всегда разрешены для прохождения. Выходные данные Выходной файл OUTPUT.TXT должен содержать количество возможных различных путей длины K. Во всех тестах это значение не будет превышать 2147483647. Примеры № INPUT.TXT OUTPUT.TXT 3 6 5 000 1 101 100 2 8 0 2 01 10 Разбор Обозначим через A(i, x, y) – количество путей длины i в клетку (x, y). Ответом тогда будет значение A(K, N, N). Верно следующее соотношение A(i+1, x, y)=A(i, x-1, y)+A(i, x+1, y)+A(i, x, y- 1)+A(i, x, y+1), так как в каждую клетку можно попасть из четырех соседних. Это утверждение будет верно для всех клеток доски, если рассматривать расширенную доску, дополнив заданную по краям рядами клеток, в которых обнулить значения A(i, x, y). Если клетка непроходима, то для неё A(i+1, x, y)=0. Так как соотношение связывает только два значения для i – следующее через найденное, то можно использовать для вычисления A не трёхмерный массив, а два двухмерных или хранить только два слоя трёхмерного массива, как это сделано в приведённой ниже программе. Программа {$R+,N+,E+} var A : array [0..1,0..16,0..16] of longint; c : array[1..15,1..15] of char; n, k, i, j, k0, k1, m : integer; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); readln(n,k); for i:=1 to n do begin for j:=1 to n do read(c[i,j]); readln Югорский НИИ информационных технологий http://www.acmu.ru 1 3-я командная олимпиада по программированию 16.04.2009 end; for i:=0 to n+1 do for j:=0 to n+1 do begin a[0,i,j]:=0; a[1,i,j]:=0 end; a[0,1,1]:=1; k0:=0; k1:=1; for m:=1 to k do begin for i:=1 to n do for j:=1 to n do if c[i,j]='0' then a[k1,i,j]:=a[k0,i,j-1]+a[k0,i-1,j]+a[k0,i,j+1]+a[k0,i+1,j] else a[k1,i,j]:=0; k0:=1-k0; k1:=1-k1 end; if k1=1 then write(a[0,n,n]) else write(a[1,n,n]) end. Задача B. Торт (Время: 1 сек. Память: 16 Мб) На свой день рождения Петя купил красивый и вкусный

Recently converted files (publicly available):