Олимпиадная задача

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Олимпиадная задача

Сообщение Vladislav_133 27 апр 2010, 18:07

В минувший понедельник на занятиях по олимпиадному программированию решали одну задачу. Мне показалась она интересной.
Собственно задача одна из многих на нахождение кратчайшего пути. В наших олимпиадах таких задач было несколько (см. http://shgpi.edu.ru/solver/).
Задача.
Пусть имеются две точки (x1,y1) и (x2,y2). Некто передвигается из первой точки во вторую. За один раз можно делать:
1. Шаг влево x-1
2. Шаг вправо x+1
3. Шаг вверх y+1
4. Шаг вниз y-1
1. Необходимо определить минимальное количество шагов от первой точки ко второй.
2. Найти все возможные маршруты с минимальным количеством шагов.

Собственно, если оставить только первый вопрос, то для нахождения минимального количества шагов программы писать не надо.
Действительно минимальное количество шагов можно вычислить по формуле abs(x1-x2) + abs(y1-y2). И все!
А вот что касается второго вопроса, то здесь без программы не обойтись. Типичная задача на нахождения самого короткого пути.
И типичнейшая же проблема - как в процессе перебора шагов отбрасывать пути, заведомо не ведущие к правильному результату.
В разных задачах этот критерий может быть разным. В данном случае критерий очевиден: если на очередном ходу расстояние до
целевой точки увеличилось, то этот шаг сразу следует аннулировать. Заметим, что если не вводить критерий, то движение
шагающего приведет скорее всего к переполнению стека. Вот собственно и все.
Код: Выделить всё
var
    x1,y1,x2,y2,i,j,n,min:integer;...
    r:integer;
    a:array[1..100] of integer;
    b:array[1..100] of integer;

procedure shag(x,y,rr:integer);
var
    rt:integer;
begin
    a[n]:=x; b[n]:=y; inc(n);
    if (x=x2) and (y=y2)  then
    begin
<------>if min>n-1 then min:=n-1;<----->
<------>for j:=1 to n-1 do.
<------>begin
<------>    write(a[j],' ',b[j],'; ');
<------>end;
<------>writeln;
    end
    else
    begin
<------>if rr>(x-x2)*(x-x2)+(y-y2)*(y-y2) then
<------>begin
<------>    rt:=(x-x2)*(x-x2)+(y-y2)*(y-y2);
<------>     shag(x+1,y,rt);.
<------>     shag(x,y+1,rt);.
<------>     shag(x-1,y,rt);.
<------>     shag(x,y-1,rt);.
<------>end;
    end;
    dec(n);
end;
{-------------------------------}....
begin
    readln(x1,y1);
    readln(x2,y2);
    for i:=1 to 100 do
    begin
<------>a[i]:=0;b[i]:=0;
    end;
    min:=200;
    if (not((x1=x2) and (y1=y2))) then
    begin<-----><------>
    r:=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    n:=1;
    shag(x1+1,y1,r);....
    n:=1;
    shag(x1,y1+1,r);....
    n:=1;
    shag(x1-1,y1,r);....
    n:=1;
    shag(x1,y1-1,r);....
    end
<------>else
<------> min:=0;<------>
    writeln(min);
end.



Остается только добавить, что вместо расстояния используется его квадрат, что, конечно, удобнее.
Заметим также, что в задаче предполагается, что минимальное количество шагов не может превзойти 100.
Обычное ограничение.

Замечание.
Однако вот вопрос. Нельзя ли улучшить алгоритм, основываясь на том факте, что минимальное количество шагов может быть вычислено заранее? Подумайте.
Последний раз редактировалось Vladislav_133 28 апр 2010, 11:15, всего редактировалось 1 раз.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиадная задача

Сообщение LMP 27 апр 2010, 20:43

высказывать свои предположения можно всем, или нет?)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение Vladislav_133 28 апр 2010, 08:58

Конечно всем.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиадная задача

Сообщение LMP 28 апр 2010, 11:01

вы проверяете варианты движения во все стороны.

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

Код: Выделить всё
var
  len, p: integer;
  ax, ay: array [0..100] of integer;
  x, y, x1, y1, dx, dy, i: integer;

procedure next;
begin
  ax[p]:= x;
  ay[p]:= y;
  if (len = p) then begin
    for i:= 1 to p do begin
      write(ax[i], ' ', ay[i], '; ');
    end;
    writeln;
  end else begin
    p:= p+1;
    if (x <> x1) then begin
      x:= x+dx;
      next;
      x:= x-dx;
    end;
    if (y <> y1) then begin
      y:= y+dy;
      next;
      y:= y-dy;
    end;
    p:= p-1;
  end;
end;

begin
  readln(x, y);
  readln(x1, y1);
  p:= 0;
  len:= abs(x1-x)+abs(y1-y);
  if (x1 > x) then begin
    dx:= 1;
  end else begin
    dx:= -1;
  end;
  if (y1 > y) then begin
    dy:= 1;
  end else begin
    dy:= -1;
  end;
  next;
  writeln(len);
end.


но на небольших данных оба алгоритма работают быстро по сравнению со скоростью вывода мегабайт, или даже гигабайт данных в результате (если убрать вывод, то работают мгновенно, а с выводом могут работать минуты, и более).
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение Vladislav_133 28 апр 2010, 11:09

Хм, интересно. И все варианты выдает?
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиадная задача

Сообщение LMP 28 апр 2010, 11:13

да (неуверенно)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение Vladislav_133 28 апр 2010, 11:16

А ты сравни мое решение и твое
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиадная задача

Сообщение LMP 28 апр 2010, 11:27

да, результат одинаковый, только в некоторых случаях порядок строк различен.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение LMP 28 апр 2010, 11:30

хотя есть одно отличие, если начальные координаты и конечные равны, то в моём случае выводится пустая строка в начале. но это можно решить добавлением условия в основную программу, аналогичного вашему.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение LMP 28 апр 2010, 11:34

код основной программы, в котором устранён вывод лишней строки:
Код: Выделить всё
begin
  readln(x, y);
  readln(x1, y1);
  len:= abs(x1-x)+abs(y1-y);
  if (len > 0) then begin
    p:= 0;
    if (x1 > x) then begin
      dx:= 1;
    end else begin
      dx:= -1;
    end;
    if (y1 > y) then begin
      dy:= 1;
    end else begin
      dy:= -1;
    end;
    next;
  end;
  writeln(len);
end.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение Vladislav_133 28 апр 2010, 17:00

Кстати насчет моего вопроса, что нельзя ли использовать в качестве критерия уже известное заранее количество минимальных шагов. Можно. Т.е. на каждом шаге, если только мы не пришли в нужную точку, проверяем количество шагов. Если сравнялось, то отбрасываем шаг. Думаю, что таким способом задача решается, только алгоритм будет работать гораздо медленнее.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиадная задача

Сообщение vovan 28 апр 2010, 17:39

Вот еще вариант.
Глубина рекурсии здесь будет похоже меньше.
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int r=1,d=1;
int *ar; //массив для хранения направления движения, если в элементе находится 0, значит на этом шаге некто двигался по вертикали, если 1 то по горизонтали
int sx, sy; // начальные координаты
int len;

void find(int lenx, int leny, int pos) //параметры длина по x, по y и номер элемента массива куда следует записывать направление
{
    int i, j;
    int kx=sx, ky=sy;
    if (!leny || !lenx) {  //если по x или по y некто прошел весь путь, то есть осталось двигаться только по горизонтали или вертикали то все
        for (i=0; i<pos; i++) { /вычисляем координаты движения по направлению
            kx+=r*ar[i]; //если ar[i] не равен 0 то некто шел по горизонтали, если r==1 то вправо, если r==-1 то влево, прибавляем это к текущей координате по x
            ky+=d*(!ar[i]); //тоже самое что и с x, к текущей координате по y прибавляется 1, если ar[i]==0 и d=1; -1, если ar[i]==0 и d=-1; и 0 в случае если ar[i]!=0
            printf("%d %d; ", kx, ky);
        }
        if (!leny) //находим оставшиеся координаты, думаю условие можно убратьи оставить тоько циклы
            for (i=0;i<lenx; i++) {
                kx+=r;
                printf("%d %d; ", kx, ky);
            }
        else
            for (i=0;i<leny; i++) {
                ky+=d;
                printf("%d %d; ", kx, ky);
            }
        printf("\n");
        return;
    }
    for (i=leny; i>-1; i--) { //вычитаем из оставшегося направления по y значение i, заносим 0 в массив  и 1 единицу вычитаем 1 из оставшегося направления по x
        for (j=0;j<i;j++) {
            ar[j+pos]=0;
        }
        ar[i+pos]=1;
        find(lenx-1, leny-i, pos+i+1);
    }
}

int main(void)
{
    int x1,y1, x2,y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    sx=x1;
    sy=y1;
    if (x1==x2)
        if (y1==y2) {
            printf("0");  //случай, когда длна равна 0
            return 0;
        }
    if (x1>x2) r=-1; //если x1 > x2 то двигаться надо влево, то есть координата x уменьшается
    if (y1>y2) d=-1; //если y1 > y2 то двигаться вверх, y -уменьшается
    int lenx=abs(x1-x2); //расстояние по x
    int leny=abs(y1-y2);  //расстояние по y
    len=lenx+leny;
    ar=(int*)malloc(sizeof(int)*lenx*leny);
    find(lenx, leny, 0);
    printf("%d\n", len);
    return 0;
}

Последний раз редактировалось vovan 29 апр 2010, 07:11, всего редактировалось 1 раз.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Олимпиадная задача

Сообщение xdsl 28 апр 2010, 21:20

vovan в своем репертуаре: код есть, объяснялок нема ;)
Вова, имейте жалость к форумчанам, здесь много студентов, которые только-только разбираться начали в хитросплетениях нетривиальных решений, а Вы их сразу по голове исходниками без единого комментария!
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиадная задача

Сообщение vovan 29 апр 2010, 06:58

Я хотел обьяснение написать, только вот никак не удается придумать что написать. Сейчас комментарии хотя бы вставлю тогда
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Олимпиадная задача

Сообщение LMP 29 апр 2010, 18:44

на мой взгляд в данной задаче есть ещё один интересный момент, узнать количество различных вариантов (путей), по которым можно добраться из первой точки до второй. мой алгоритм (при отсутсвии вывода путей, а только подсчёте их количества) на данных
Код: Выделить всё
0 0
15 15

работает приблизительно 10 секунд, получается 155177520 путей. с ограничением в 100 шагов максимальное количество путей получится на данных
Код: Выделить всё
0 0
50 50

и там будет очень большое число (не скажу какое, не считал ещё). но согласитесь и 10 секунд уже много если взять ограничение в 1 секунду ;) .

есть предложения, как можно уменьшить время подсчёта количества путей? (у меня есть вариант, но хочется выслушать предложения других :) )
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение vovan 29 апр 2010, 19:44

Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ULL unsigned long long

ULL getsum(ULL *ar, int c)
{
    int i;
    int r=0;
    for (i=0;i<c;i++)
        r+=ar[i];
    return r;
}


int main(void)
{
    ULL *ar;
    int x, y, x1, y1;
    ULL sum;
    scanf("%d%d%d%d", &x, &y, &x1, &y1);
    int lenx=abs(x1-x);
    int leny=abs(y1-y);
    int len=lenx+leny;
    sum=1;
    ar=(ULL*)malloc(sizeof(ULL)*lenx);
    int i;
    for (i=0; i<lenx; i++) ar[i]=1;
    ULL r;
    ULL n, m;
    while (leny>0) {
        r=getsum(ar, lenx);
        n=ar[0];
        ar[0]=r;
        for (i=1;i<lenx; i++) {
            m=ar[i];
            ar[i]=ar[i-1]-n;
            n=m;
        }
        sum+=r;
        leny--;
    }
    printf("%llu\n%d\n", sum, len);
    return 0;
}


LMP, у тебя опечатка в количестве путей для 0 15 0 15?
у меня в обоих алгоритмах выдает число - 155117520
Последний раз редактировалось vovan 29 апр 2010, 20:03, всего редактировалось 1 раз.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Олимпиадная задача

Сообщение vovan 29 апр 2010, 19:45

вот результат для 0 50 0 50
18446744072770573672(Не уверен, могло быть переполнение)
100

работает моментально
Суть алгоритма
Для случая когда при x=0, некто проходит весь путь вниз возможен только один вариант.
Записываем в сумму единицу
переменной I присваивае значение равное расстоянию по y
Дальше берем массив единиц. Количество элементов в массиве равно расстоянию по x
1. Подсчитываем их сумму и прибавляем к имеющейся сумме
2. В первый элемент массива заносим эту сумму. Каждый последующий элемент формируем из разности текущего значения предыдущего элемента и предыдущего значения предыдущего элемента.
3. уменьшаем количество I, и если I>0 то возвращаемся к первому шагу
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Олимпиадная задача

Сообщение LMP 29 апр 2010, 21:45

LMP писал(а):LMP, у тебя опечатка в количестве путей для 0 15 0 15?

да, точно
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение LMP 29 апр 2010, 22:04

для подсчёта количества путей нам достаточно знать dx и dy.

Код: Выделить всё
dy
5  |  1   6  21  56 126 252
4  |  1   5  15  35  70 126
3  |  1   4  10  20  35  56
2  |  1   3   6  10  15  21
1  |  1   2   3   4   5   6
0  |  1   1   1   1   1   1
---+-----------------------
   |  0   1   2   3   4   5 dx

(в таблице возможны опечатки, подсчёты производились вручную)

на пересечении значения dx и dy находится количество путей, как можно заметить оно равно сумме значения снизу и слева. т.о. два вложенных цикла достаточно для нахождения количества путей. грубо говоря всё что находится в отрицательных значениях dx и dy равно нулю, в позиции 0;0 - значение единица, и на основе этого значения строится вся оставшеяся часть поля.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение xdsl 30 апр 2010, 09:21

to LMP: красиво.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиадная задача

Сообщение LMP 30 апр 2010, 10:36

ещё бы, ручная работа :)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение LMP 30 апр 2010, 20:56

ещё немного отклонимся от начальной задачи.

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

Код: Выделить всё
..........
...####...
...#..#...
...#......
...#..#...
...#..#...
...#B.#...
...####...
A.........
#........#

для данного примера один из ответов будет:

Код: Выделить всё
RRRRRRRUUUUULLLDDD

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

попробуйте обьединить обе подзадачи в один пробег :)

в качестве ограничений возьмём размер карты не более 100x100 клеток.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиадная задача

Сообщение vovan 01 май 2010, 18:13

на тесте 100x100 с небольшими препятствиями(непроходимая полоса чуть выше середины с одной проходимой клеткой по середине этой строки, A — в левом нижнем углу, B — в верхнем правом) выполняется за 2 секунды. Не знаю как можно еще сократить время
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MSIZE 100
#define RSIZE MSIZE*MSIZE
#define MAXINT ((1<<(sizeof(int)*8-1))-1)

int max=MAXINT;

char mat[MSIZE][MSIZE+2];
int path[MSIZE][MSIZE];
char a[RSIZE+1];
char b[RSIZE+1];
int maxx, maxy;

void find(int x, int y, int cnt)
{

    if (cnt>=max) return;
    if (x<0 || y<0 || x>=maxx || y>=maxy) return;
    if (strchr("*#", mat[x][y])) return;
    if (cnt>=path[x][y]) return;
    path[x][y]=cnt;
    if (mat[x][y]=='B') {
        if (cnt<max) {
            memcpy(a, b, RSIZE*sizeof(char)); //в случае если путь короче предыдущего записывает его в основной массив
            max=cnt;
        }
        return;
    }

    char cc=mat[x][y];
    mat[x][y]='*';

    b[cnt]='U'; //записывает путь в резервный массив
    find(x-1, y, cnt+1);

    b[cnt]='L'; //записывает путь в резервный массив
    find(x, y-1, cnt+1);

    b[cnt]='D'; //записывает путь в резервный массив
    find(x+1, y, cnt+1);

    b[cnt]='R'; //записывает путь в резервный массив
    find(x, y+1, cnt+1);

    mat[x][y]=cc;
}

int main(void)
{
    char s[102], *p;
    int i=0, j, n;
    int x=-1,y=-1;
    while (!feof(stdin)) {
        n=scanf("%s", s);
        if (n<1) break;
        p=strchr(s, 'A');
        if (p) {
            y=p-s;
            x=i;
        }
        strcpy(mat[i++], s);
    }

    maxx=i;
    maxy=strlen(mat[0]);
    for (i=0; i<maxx; i++)
        for (j=0; j<maxy; j++)
            path[i][j]=MAXINT;
    if (x==-1 || y==-1) {
        printf("Invalid data\n");
        return 0;
    }
    find(x, y, 0);

    a[max]='\0';
    printf("%s\n%d", a, max);

    return 0;
}

vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Олимпиадная задача

Сообщение Vladislav_133 01 май 2010, 20:49

Ну народ раззодорился. Тряхнуть что ли и мне. Задачка интересная. Пока не пойму, как оптимально найти путь.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиадная задача

Сообщение LMP 01 май 2010, 21:29

у меня опять таки есть предположение, но решать ещё сам не пробовал.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

След.

Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2