hdu2045
12375 ワード
説明:1列に並ぶn個の四角い格子があり、赤(Red)、ピンク(Pink)、緑(Green)の3色で各格子を塗り、各格子に1色を塗り、隣接する四角い格子が同色でなく、首尾の2つの格子も異なる色を要求する.すべての要求を満たす塗り方を求める.以上が有名なRPGの難題である.
Input
入力データは複数のテストインスタンスを含み、各テストインスタンスは1行を占め、1つの整数Nからなる(0Output
各試験例について、要求を満たすすべての塗布方法を出力し、各例の出力が1行を占めます.
Sample Input
Sample Output
どのようなプッシュ問題がいつもそんなに手応えがないのか分からないし、しかもこの問題はそんなに簡単だ.
考え方は簡単で、n+1番目の場合とnおよびn-1の関係は2つの場合に分けられる.
1.n番目の色が1番目と同じである(この場合、nの配列ではありえないので、n-1の配列に関係する)場合、f 1(n+1)=2*f(n-1)(注:関数f 1は1番目の場合の数、関数fは総数)
2.n番目の色が1番目と異なる場合、f 2(n+1)=f(n)となる.
従ってf(n+1)=f(n)+2*f(n-1)
初期条件f(1)=3,f(2)=f(3)=6
Input
入力データは複数のテストインスタンスを含み、各テストインスタンスは1行を占め、1つの整数Nからなる(0
各試験例について、要求を満たすすべての塗布方法を出力し、各例の出力が1行を占めます.
Sample Input
1
2
Sample Output
3
6
どのようなプッシュ問題がいつもそんなに手応えがないのか分からないし、しかもこの問題はそんなに簡単だ.
考え方は簡単で、n+1番目の場合とnおよびn-1の関係は2つの場合に分けられる.
1.n番目の色が1番目と同じである(この場合、nの配列ではありえないので、n-1の配列に関係する)場合、f 1(n+1)=2*f(n-1)(注:関数f 1は1番目の場合の数、関数fは総数)
2.n番目の色が1番目と異なる場合、f 2(n+1)=f(n)となる.
従ってf(n+1)=f(n)+2*f(n-1)
初期条件f(1)=3,f(2)=f(3)=6
1
#include
<
stdio.h
>
2
3
4
5
int
main()
6
{
7
long
long
n1
=
3
;
8
long
long
n2
=
6
;
9
long
long
n3
=
6
;
10
int
n;
11
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
12
{
13
if
(n
<=
3
)
14
{
15
if
(n
==
1
)
16
{
17
printf(
"
%lld
"
,n1);
18
}
19
else
20
printf(
"
%lld
"
,n2);
21
continue
;
22
}
//
1 50 ，
23
long
long
result
=
0
;
24
long
long
f1
=
n2;
25
long
long
f2
=
n3;
26
int
i;
27
for
(i
=
n
-
3
;i
>
0
;i
--
)
28
{
29
result
=
f2
+
f1
*
2
;
30
f1
=
f2;
31
f2
=
result;
32
}
33
printf(
"
%lld
"
,result);
34
}
35
return
0
;
36
}
37
38