hdu 3064 twoNumber
7643 ワード
twoNumber
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 2048/1024 K (Java/Others) Total Submission(s): 675 Accepted Submission(s): 210
Problem Description
白さん、ちょっと手伝ってください.ごちゃごちゃした数字の中から、紛失した数字を2つ見つけてください.
この山の数字は雑然としているが、重複した数字がなく、並べ替えた後に最初と最後をつなぐことができるという特徴がある(ただし2つを失った).
数値が多くなる可能性があるため、一部の数値は圧縮されています.
1 2 3 4 5
数値セグメントとして表すことができる[1,5].
Input
1つのnを入力して、何個のデジタルセグメント入力があるかを示します(0次に、連続区間の最小値と最大値(1<=st<=end<=1000000)を表す2つの数字を入力します.もちろん、この数字は失われている可能性があります.
次にn行を入力し、行ごとに2桁(St,End)(1<=st<=end<=1000000)を入力します.
Stはデジタル区間の開始を表し,Endはデジタル区間の末尾を表す.
Output
欠落した2つの数を出力(小さな先頭出力)
データは、2つの異なる数値だけが欠けていることを保証します.
Sample Input
4 1 15 1 3 7 9 4 6 11 14
Sample Output
10 15
Hint
HINT: be careful with the memory limit;
Source
2009 Multi-University Training Contest 16 - Host by NIT
考え方:
1:前のn項と式:1+2+3+...+n=n*(n+1)/2
2:前のn項の二乗和式:
1^2+2^2+.........+n^2=n*(n＋1)*(2n＋1)/6
要求された2つの数はa,bと記す.
あります.
区間のすべての数の和はans 1として算出することができ、与えられた区間の和はsum 1に加算され、ans 1-sum 1は要求された2つの数の和である.すなわちa+b=ans 1-sum 1である.
同じ理屈:
区間のすべての数の平方の和はans 2と表記され、与えられた区間の各項の平方の和はsum 2に加算され、ans 2-sum 2は要求された2つの数の平方の和である.ある
a^2+b^2 = ans2-sum2;
そして方程式を解くだけでいい!
注意:
中の数は_int 64ビットメモリ、演算中のタイプ変換に注意!
コード:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 2048/1024 K (Java/Others) Total Submission(s): 675 Accepted Submission(s): 210
Problem Description
白さん、ちょっと手伝ってください.ごちゃごちゃした数字の中から、紛失した数字を2つ見つけてください.
この山の数字は雑然としているが、重複した数字がなく、並べ替えた後に最初と最後をつなぐことができるという特徴がある(ただし2つを失った).
数値が多くなる可能性があるため、一部の数値は圧縮されています.
1 2 3 4 5
数値セグメントとして表すことができる[1,5].
Input
1つのnを入力して、何個のデジタルセグメント入力があるかを示します(0
次にn行を入力し、行ごとに2桁(St,End)(1<=st<=end<=1000000)を入力します.
Stはデジタル区間の開始を表し,Endはデジタル区間の末尾を表す.
Output
欠落した2つの数を出力(小さな先頭出力)
データは、2つの異なる数値だけが欠けていることを保証します.
Sample Input
4 1 15 1 3 7 9 4 6 11 14
Sample Output
10 15
Hint
HINT: be careful with the memory limit;
Source
2009 Multi-University Training Contest 16 - Host by NIT
考え方:
1:前のn項と式:1+2+3+...+n=n*(n+1)/2
2:前のn項の二乗和式:
1^2+2^2+.........+n^2=n*(n＋1)*(2n＋1)/6
要求された2つの数はa,bと記す.
あります.
区間のすべての数の和はans 1として算出することができ、与えられた区間の和はsum 1に加算され、ans 1-sum 1は要求された2つの数の和である.すなわちa+b=ans 1-sum 1である.
同じ理屈:
区間のすべての数の平方の和はans 2と表記され、与えられた区間の各項の平方の和はsum 2に加算され、ans 2-sum 2は要求された2つの数の平方の和である.ある
a^2+b^2 = ans2-sum2;
そして方程式を解くだけでいい!
注意:
中の数は_int 64ビットメモリ、演算中のタイプ変換に注意!
コード:
1 #include "stdio.h"
2 #include "math.h"
3
4 int main()
5 {
6 int n;
7 __int64 x,y;
8 __int64 ans1,ans2;
9 __int64 sum1,sum2;
10 __int64 t1,t2;
11 __int64 a,b;
12 __int64 deta;
13 while(scanf("%d",&n)!=-1)
14 {
15 ans1 = ans2 = 0;
16 sum1 = sum2 = 0;
17 scanf("%I64d %I64d",&x,&y);
18 ans1 = (x+y)*(y-x+1)/2;
19 t1 = x*(x-1)*(2*x-1)/6;
20 t2 = y*(y+1)*(2*y+1)/6;
21 ans2 = t2-t1;
22
23 while(n--)
24 {
25 scanf("%I64d %I64d",&x,&y);
26
27 sum1 += (x+y)*(y-x+1)/2;
28
29 t1 = x*(x-1)*(2*x-1)/6;
30 t2 = y*(y+1)*(2*y+1)/6;
31 sum2 += t2-t1;
32 }
33 ans1 -= sum1;
34 ans2 -= sum2;
35 a = ans1;
36 b = ans2;
37 deta = (__int64)sqrt((double)(2*b-a*a));
38 x = (a-deta)/2;
39 y = a - x;
40 printf("%I64d %I64d
",x,y);
41 }
42 return 0;
43 }