1465:容易でないシリーズの一つ
2042 ワード
容易でないシリーズの一つ
【1】解析すると、状態f[i]の値は、f[i-1]にi番目の人を加えた値と、f[i-1]に1人分の手紙が間違っていない値とが加算される.【2】f[i-1]のうち、1人の手紙が間違っていない値は、i-1通の手紙のうち1通(間違った手紙を送っていない)を選択し、f[i-2]を乗じてすべての手紙を間違って送ったことに等しい.杭電OJテーマリンク
参照
容易でないシリーズの一つ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11107 Accepted Submission(s): 4605
Problem Description
みんなはいつも感慨して、1件の事をしっかりと行うのは本当に容易ではありませんて、確かに、失敗は成功よりずっと簡単です!
「一つ」のことをうまくやるのは容易ではないが、永遠に成功して失敗しないようにするには、お金を使うのはいつもお金を稼ぐより簡単な道理のように難しい.
とはいえ、ある程度失敗するのは容易ではないことをお伝えします.例えば、私の高校の时、不思議な女の子がいて、英語の試験の时、意外にも40の単項の選択問題を全部間違えました!みんな確率論を学んだことがあるので、このような状況が発生する確率を知っているはずなので、今まで不思議なことだと思っていました.もし1つの経典のコメントを套用すれば、私たちはこのようにまとめることができます:一人で1つの選択問題を間違えるのは難しくなくて、難しいのはすべて間違っていて、1つは間違っています.
残念なことに、このような小さな確率の事件がまた発生し、私たちのそばにいます.
HDUには8006という男性の同級生がいて、ネットユーザーが無数に付き合っています.最近、この同級生はロマンを游び始めました.同時に、n人のネットユーザーに1人1通の手紙を書きました.これは何もありません.命がけで、彼はすべての手紙を封筒に入れ間違えました.注意したんだけど、全部間違えたんだよ!
今の問題は:みんなにかわいそうな8006学友を手伝って計算してもらって、全部で何種類の可能性のある間違いの方式がありますか?
Input
入力データには複数のテストインスタンスが含まれ、各テストインスタンスは1行を占有し、各行は正の整数n(1Output
各行の入力に対して可能なエラーの数を出力し、各インスタンスの出力に1行を占有します.
Sample Input
2
3
Sample Output
1
2
説明
本文はオリジナルで、転載は出典を明記してください。
Author
skywolf
【1】解析すると、状態f[i]の値は、f[i-1]にi番目の人を加えた値と、f[i-1]に1人分の手紙が間違っていない値とが加算される.【2】f[i-1]のうち、1人の手紙が間違っていない値は、i-1通の手紙のうち1通(間違った手紙を送っていない)を選択し、f[i-2]を乗じてすべての手紙を間違って送ったことに等しい.杭電OJテーマリンク
#include <stdio.h>
int main() {
__int64 f[25];
int i, n;
f[1] = 0; f[2] = 1; f[3] = 2;
for(i=4; i<21; i++) {
f[i] = f[i-1] * (i - 1) + f[i-2] * (i - 1);
}
while(scanf("%d", &n) != -1) {
printf("%I64d
", f[n]);
}
return 0;
}
参照
容易でないシリーズの一つ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11107 Accepted Submission(s): 4605
Problem Description
みんなはいつも感慨して、1件の事をしっかりと行うのは本当に容易ではありませんて、確かに、失敗は成功よりずっと簡単です!
「一つ」のことをうまくやるのは容易ではないが、永遠に成功して失敗しないようにするには、お金を使うのはいつもお金を稼ぐより簡単な道理のように難しい.
とはいえ、ある程度失敗するのは容易ではないことをお伝えします.例えば、私の高校の时、不思議な女の子がいて、英語の試験の时、意外にも40の単項の選択問題を全部間違えました!みんな確率論を学んだことがあるので、このような状況が発生する確率を知っているはずなので、今まで不思議なことだと思っていました.もし1つの経典のコメントを套用すれば、私たちはこのようにまとめることができます:一人で1つの選択問題を間違えるのは難しくなくて、難しいのはすべて間違っていて、1つは間違っています.
残念なことに、このような小さな確率の事件がまた発生し、私たちのそばにいます.
HDUには8006という男性の同級生がいて、ネットユーザーが無数に付き合っています.最近、この同級生はロマンを游び始めました.同時に、n人のネットユーザーに1人1通の手紙を書きました.これは何もありません.命がけで、彼はすべての手紙を封筒に入れ間違えました.注意したんだけど、全部間違えたんだよ!
今の問題は:みんなにかわいそうな8006学友を手伝って計算してもらって、全部で何種類の可能性のある間違いの方式がありますか?
Input
入力データには複数のテストインスタンスが含まれ、各テストインスタンスは1行を占有し、各行は正の整数n(1
各行の入力に対して可能なエラーの数を出力し、各インスタンスの出力に1行を占有します.
Sample Input
2
3
Sample Output
1
2
説明
本文はオリジナルで、転載は出典を明記してください。
Author
skywolf