*[[Problem 736:https://projecteuler.net/problem=736]] 「同じになる径路」 [#s83f3d18]

格子点に関して 2 つの関数を定義する。

&tex{r};(&tex{x};, &tex{y};) = (&tex{x}; + 1, 2&tex{y};)&br;
&tex{s};(&tex{x};, &tex{y};) = (2&tex{x};, &tex{y}; + 1)

(&tex{a};, &tex{b};) から「関数 &tex{r};, &tex{s}; を施して &tex{a}; と &tex{b}; が同じ値になるまでの長さ &tex{n}; の径路」は,[ (&tex{a_{1}};, &tex{b_{1}};), (&tex{a_{2}};, &tex{b_{2}};), ..., (&tex{a_{n}};, &tex{b_{n}};) ] として,

- (&tex{a_{1}};, &tex{b_{1}};) = (&tex{a};, &tex{b};)
- &tex{k}; > 1 において,(&tex{a_{k}};, &tex{b_{k}};) = &tex{r};(&tex{a_{k-1}};, &tex{b_{k-1}};) または
(&tex{a_{k}};, &tex{b_{k}};) = &tex{s};(&tex{a_{k-1}};, &tex{b_{k-1}};) 
- &tex{k}; < &tex{n}; において &tex{a_{k}}; ≠ &tex{b_{k}};
- &tex{a_{n}}; = &tex{b_{n}};

たとえば,&br;
(45, 90) -&tex{r};-> (46, 180) -&tex{s};-> (92, 181) -&tex{s};-> (184, 182) -&tex{s};-> (368, 183) -&tex{s};-> 
(736, 184) -&tex{r};->&br;
(737, 368) -&tex{s};-> (1474, 369) -&tex{r};-> (1475, 738) -&tex{r};-> (1476, 1476)

これが,(45, 90) が同じ値になるまでの長さ 10 の径路であり,最終的な値は 1476 である。(45, 90) が同じ値になるまでの長さが 10 未満の径路はない。

(45, 90) が同じ値になるまでの長さが奇数で,かつ最小の径路を捜し,最終的な値を答えなさい。

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS