Posted on 2008-10-09 21:27
Hero 閱讀(100)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 /*
2 ID: wangzha4
3 LANG: C++
4 TASK: hidden
5 */
6 /*
7 Executing
8 Test 1: TEST OK [0.000 secs, 3496 KB]
9 Test 2: TEST OK [0.011 secs, 3496 KB]
10 Test 3: TEST OK [0.000 secs, 3496 KB]
11 Test 4: TEST OK [0.011 secs, 3492 KB]
12 Test 5: TEST OK [0.000 secs, 3492 KB]
13 Test 6: TEST OK [0.000 secs, 3492 KB]
14 Test 7: TEST OK [0.011 secs, 3496 KB]
15 Test 8: TEST OK [0.022 secs, 3492 KB]
16 Test 9: TEST OK [0.032 secs, 3496 KB]
17 Test 10: TEST OK [0.022 secs, 3492 KB]
18 Test 11: TEST OK [0.022 secs, 3492 KB]
19 Test 12: TEST OK [0.011 secs, 3496 KB]
20 Test 13: TEST OK [0.000 secs, 3496 KB]
21 Test 14: TEST OK [0.000 secs, 3496 KB]
22 */
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27
28 const int size = 100100 ;
29
30 int strnum[size*2] ;
31
32 int inn ;
33
34 void input()
35 {
36 char inch = getchar() ;
37 for( int i=1; i<=inn; i++ )
38 {
39 scanf( "%c", &inch ) ;
40 if( inch == '\n' ) scanf( "%c", &inch ) ;
41 strnum[i] = strnum[i+inn] = inch - 'a' ;
42 }
43 getchar() ;
44 }
45
46 int cmp( int p1, int p2 )
47 {
48 for( int i=0; i<inn; i++ )
49 {
50 if( strnum[p1+i] > strnum[p2+i] ) return i ;
51 else if( strnum[p1+i] < strnum[p2+i] ) return -i ;
52 }
53
54 return 0 ;
55 }
56
57 void process()
58 {
59 int minstrnum = strnum[1] ;
60 for( int i=2; i<=inn; i++ ) if( minstrnum > strnum[i] )
61 minstrnum = strnum[i] ;
62
63 int p1, p2 ;
64 for( p1=1; strnum[p1]!=minstrnum; p1++ ) ; p2 = p1 + 1 ;
65
66 for( p2=p1+1; p2<=inn; p2++ )
67 {
68 if( strnum[p2] <= minstrnum )
69 {
70 int cmpval = cmp( p1, p2 ) ;
71 if( cmpval == 0 ) break ;
72 else if( cmpval > 0 ) p1 = p2 ;
73 else p2 += (-1*cmpval) ;
74 }
75 }
76
77 printf( "%d\n", p1-1 ) ;
78 }
79
80 int main()
81 {
82 freopen( "hidden.in", "r", stdin ) ;
83 freopen( "hidden.out","w",stdout ) ;
84
85 while( scanf( "%d", &inn ) != EOF )
86 {
87 input() ;
88
89 process() ;
90
91 //output() ;
92 }
93 return 0 ;
94 }