Carribean

[Гост]

Решавам една задача, която според мен се решава с динамично оптимиране (програмиране). Но не се сещам как да я направя. Може ли да ми помогнете за нея? Ако да, ето я задачата:

Ели наскоро завърши гимназия и както повечето абитуриенти имаше бал. След това тя отиде на "втора бална" на морето. В нейния случай морето беше Карибско море.

В околността има три острова и всеки от тях има по N града, разположени по крайбрежието. Островите са населени с канибали, затова пътуването по суша между градовете е много опасно. За сметка на това пътуването с лодка е сравнително сигурно и разпространено (pirates of the Caribbean are overrated). Единственият проблем е, че лодкарите, подобно на шофьорите на такси в Студентски Град, не са вчерашни и не взимат пътници на къси разстояния (тоест между два града на един и същ остров). Така единствените възможности на Ели за пътуване е между градове на различни острови.

Тя се намира в първия град на първия остров и иска да обиколи всички останали 3N – 1 града, като накрая се върне откъдето е тръгнала. Ели се чуди по колко начина може да направи това?

Вход
На единствен ред на стандартния вход ще бъде зададено едно цяло число N – броят градове на всеки от трите острова.

Изход
На стандартния изход изведете едно цяло число – броя възможни маршрути, които Ели може да избере. Тъй като това число може да бъде много голямо, изведете само остатъка му при деление на 1,000,003.

Ограничения
1 ≤ N ≤ 30

Примерен Вход Примерен Изход
1 2
2 32
13 261668

----------------------------------
Сега ще попитате до къде съм стигнал? Ами до никъде, защото нямам никаква идея как да се реши, така че: Моля ви, помогнете ми. Ако решите все пак да ми помогнете с решението на задачата или да я напишете, ще съм ви много благодарен за помощта и ако кода е на Java.

[Гост]

А, и също да попитам въпрос извън задачата. Този сайт на какъв език е написан? Аз сега изучавам HTML.

[Гост]

Аз знам малко и C++, така че ако ви е по-удобно може тези, които искате да помогнете да напишете задачата на C++.

[peyo]

Тя се намира в първия град на първия остров и иска да обиколи всички останали 3N – 1 града, като накрая се върне откъдето е тръгнала. Ели се чуди по колко начина може да направи това?

Вход
На единствен ред на стандартния вход ще бъде зададено едно цяло число N – броят градове на всеки от трите острова.

Изход
На стандартния изход изведете едно цяло число – броя възможни маршрути, които Ели може да избере. Тъй като това число може да бъде много голямо, изведете само остатъка му при деление на 1,000,003.

Ограничения
1 ≤ N ≤ 30

Примерен Вход Примерен Изход
1 2
2 32
13 261668

----------------------------------
Сега ще попитате до къде съм стигнал? Ами до никъде, защото нямам никаква идея как да се реши, така че: Моля ви, помогнете ми. Ако решите все пак да ми помогнете с решението на задачата или да я напишете, ще съм ви много благодарен за помощта и ако кода е на Java.

Хм. Дали може да намерим някаква формула, ако не директна, то поне рекурсивна.
Предполaгаме, че всеки град го посещаваме само веднъж.

Търсим формула $f(o_1,o_2,o_3, i)$ където $o_1,o_2, o_3$ са броя на непосетените градове на сътветния остров, a i е 1,2 или 3 номера на острова на който сме в момента. Ние сме застанали на остров 1. Така в нашия случай в началото имаме:
$f(N-1,N,N, 1)$

Тук може да пробваме да приложим рекурсия.

$f(x,y,z, 1 ) = yf(x, y-1, z, 2) + zf(x, y, z-1, 3)$
$f(x,y,z, 2 ) = xf(x-1, y, z, 1) + zf(x, y, z-1, 3)$
$f(x,y,z, 3 ) = xf(x-1, y, z, 1) + yf(x, y-1, z, 2)$

Първата горна формула казва, че общия брой на комбинациите е равен на сбора от комбинациите ако отидем на 2-рия остров плюс сбора на комбинацитте ако отидем на 3-тия остров. Останалите 2 формули подобно.

Но сега трябва да определим спиращите условия.

$f(0,0,0, 1 ) = 0$
$f(0,0,0, 2 ) = 1$
$f(0,0,0, 3 ) = 1$



И май това е всичко. Да видим дали задачата е решена със следната Python програмка:

Код: Избери целия код

from functools import lru_cache
@lru_cache(maxsize = None)
def f(x,y,z, i):
  if(x<0 or y<0 or z<0):
    return 0
  if(x,y,z,i) == (0,0,0,1):
    return 0
  if(x,y,z,i) == (0,0,0,2):
    return 1
  if(x,y,z,i) == (0,0,0,3):
    return 1
  if i==1:
    return y*f(x, y-1, z, 2) + z*f(x, y, z-1, 3)
  elif i==2:
    return x*f(x-1, y, z, 1) + z*f(x, y, z-1, 3)
  elif i==3:
    return x*f(x-1, y, z, 1) + y*f(x, y-1, z, 2)

N = 13
print( f(N-1,N,N,1) % 1000003 )

261668

Изглежда работи.

[Гост]

Благодаря ти peyo за помощта.

[Гост]

peyo. Сещаш ли се за по-бързо решение, защото имам TL - тоест върви бавно решението на задачата.

[peyo]

peyo. Сещаш ли се за по-бързо решение, защото имам TL - тоест върви бавно решението на задачата.

Това решение на Python за максомума N=30 свършва под секунда. Първо Python работи с целочислени числа с неограничена дължина и този ред:
@lru_cache(maxsize = None)
слага кеш на функцията по параметрите и без него програмата ще е много бавна. Ако се опитваш да преведеш тази програма на Java или C# или нещо друго, трябва да вземеш предвид тези 2 неща.

[Гост]

peyo. Имам време на задачата за всеки тестови пример и то е 0.2 секунди. Опитвам се да сложа отговорите в масив от 30 елемента и да извеждам направо отговора.

[Гост]

Това добра стратегия ли е като върви бавно? Имам предвид бавно като да не ми върви на тестовите примери. Иначе е бързо. Върви за под 1 секунда.

[Гост]

И в каква среда работиш и пишеш на Python?

[Гост]

Не разбирам. Имам един грешен тестов пример.

Ето го кода:

Код: Избери целия код

#include <iostream>

using namespace std;

int main()
{
    int answer[30] = {2, 32, 3168, 926208, 577406, 622691, 941431, 400130, 207237, 765720, 361058, 418214, 261668, 945225, 523140, 761415, 768238, 274367, 526325, 437167, 344467, 450232, 355755, 663095, 57359, 406415, 610196, 883519, 687459, 174574};
    int n;

    cin >> n;

    cout << answer[n - 1] << endl;

    return 0;
}


Мисля, че масива е верен, но моля ви за всеки случай проверете дали съм вкарал правилно числата в масивите.

[Jack]

peyo. Сещаш ли се за по-бързо решение, защото имам TL - тоест върви бавно решението на задачата.

Предлагам бързо решение на $C++$ с мемоизация.

Код: Избери целия код

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e6 + 3;

ll dp[31][31][31][3];

ll solve(ll x, ll y, ll z, ll i) {
    if (x < 0 || y < 0 || z < 0) return 0;

    if (dp[x][y][z][i - 1] != -1) return dp[x][y][z][i - 1];

    if (x == 0 && y == 0 && z == 0 && i == 1) return 0;
    if (x == 0 && y == 0 && z == 0 && i == 2) return 1;
    if (x == 0 && y == 0 && z == 0 && i == 3) return 1;

    if (i == 1) return dp[x][y][z][i - 1] = (y * solve(x, y - 1, z, 2) + z * solve(x, y, z - 1, 3)) % MOD;
    if (i == 2) return dp[x][y][z][i - 1] = (x * solve(x - 1, y, z, 1) + z * solve(x, y, z - 1, 3)) % MOD;
    if (i == 3) return dp[x][y][z][i - 1] = (x * solve(x - 1, y, z, 1) + y * solve(x, y - 1, z, 2)) % MOD;

    return -1;
}

int main() {
    ll N; cin >> N;

    for (ll i = 0; i <= N; i++) {
        for (ll q = 0; q <= N; q++) {
            for (ll j = 0; j <= N; j++) {
                for (ll p = 0; p < 3; p++) dp[i][q][j][p] = -1;
            }
        }
    }

    ll ans = solve(N - 1, N, N, 1) % MOD;

    cout << ans << endl;

    return 0;
}


Ползвам същата логика само добавям мемоизация.