Posted on 2008-10-03 21:35
Hero 閱讀(116)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1759 Accepted 220K 16MS C++ 1285B PKU
2
3 //單調性 + 二分
4 //驗證性問題
5
6 //an = (n-1)a2 - (n-2)a1 + (n-1)(n-2)
7
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <math.h>
11
12 const double peps = 1e-7 ;
13 const double neps = -1e-7 ;
14
15 int n ;
16 double a1, a2 ;
17 double out, tout ;
18
19 double f( int n )
20 {
21 return ( (n-1)*a2-(n-2)*a1+(n-2)*(n-1) ) ;
22 }
23
24 int main1()
25 {
26 while( scanf( "%d %lf", &n, &a1 ) != EOF )
27 {
28 out = 1e8 ;
29
30 double left = 0.0000 ; double right = a1 ; double mid ;
31
32 while( right-left>0.0000001 )
33 {
34 mid = (left+right) / 2 ; a2 = mid ; bool OK = true ;
35 for( int i=2; i<=n; i++ )
36 {
37 if( f(i) < 0 )
38 {
39 OK = false ; break ;
40 }
41 }
42 if( OK ) right = mid ;
43 else left = mid ;
44 }
45
46 out = f( n ) ;
47
48 printf( "%0.2lf\n", out ) ;
49 }
50
51 return 0 ;
52 }
53
54
55 int inn ;
56 int main()
57 {
58 while( scanf( "%d %lf", &inn, &a1 ) != EOF )
59 {
60 out = 1e9 ;
61
62 for( int i=2; i<=inn; i++ )
63 {
64 //ai = 0 -- 求出a2值
65 a2 = (i-2)*a1/(i-1) - (i-2) ;
66
67 bool OK = true ;
68 for( int k=2; k<=inn; k++ )
69 {
70 if( k == i ) continue ;
71
72 if( f(k) < neps )
73 {
74 OK = false ; break ;
75 }
76 }
77
78 if( OK )
79 {
80 double temp = f( inn ) ;
81 if( out - temp > 0 ) out = temp ;
82 }
83 }
84
85 printf( "%0.2lf\n", out ) ;
86 }
87
88 return 0 ;
89 }