This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
文字列$P1, P2, zeroCount$が与えられる．文字列$S$は$P1$を$1000000$回繰り返した後で$P2$を$1$回繰り返して連結する，この後に$P1$を$1000000$回繰り返した後で$P2$を$2$回繰り返して連結する…と$T$の長さが$10 ^{16}$以上になったら出来ないものとして考える．連続して'0'が$zeroCount$続く部分文字列がある時，その最初のindexを答える．
場合分けをたくさんした．$P1$が全て$0$, $P2$が全て$0$，そうでない場合と分けた．しっかり$P1$と$P2$の境目を考えなければいけなくて，適当にやったら非常にたくさんのWAを出した．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class RepeatedPatterns {
public :
long long findZeroSegment ( string P1 , string P2 , string zeroCount ) {
bool az = true , bz = true ;
rep ( i , P1 . size ()) {
if ( P1 [ i ] == '0' ) continue ;
az = false ;
}
rep ( i , P2 . size ()) {
if ( P2 [ i ] == '0' ) continue ;
bz = 0 ;
}
int afront = 0 , aback = 0 ;
rep ( i , P1 . size ()) {
if ( P1 [ i ] == '0' ) afront ++ ;
else break ;
}
for ( int i = P1 . size () - 1 ; i >= 0 ; i -- ) {
if ( P1 [ i ] == '0' ) aback ++ ;
else break ;
}
int bfront = 0 , bback = 0 ;
rep ( i , P2 . size ()) {
if ( P2 [ i ] == '0' ) bfront ++ ;
else break ;
}
for ( int i = P2 . size () - 1 ; i >= 0 ; i -- ) {
if ( P2 [ i ] == '0' ) bback ++ ;
else break ;
}
ll zc ;
stringstream ss ;
ss << zeroCount ;
ss >> zc ;
if ( az && bz ) {
return 0 ;
} else if ( az ) {
if ( zc <= 1000000 * P1 . size () + bfront ) {
return 0 ;
} else if ( zc <= bback + 1000000 * P1 . size () + bfront ) {
return 1000000 * P1 . size () + P2 . size () - bback ;
} else {
return - 1 ;
}
} else if ( bz ) {
if ( zc <= afront ) {
return 0 ;
} else if ( zc <= aback + afront ) {
return P1 . size () - aback ;
} else {
ll cnt = 1 ;
ll res = 0 ;
while ( true ) {
res += P1 . size () * 1000000 ;
if ( res + P2 . size () * cnt <= 1e16 && zc <= aback + bfront * cnt ) {
return res - aback ;
}
if ( res + P2 . size () * cnt + P1 . size () * 1000000 <= 1e16 && zc <= aback + bfront * cnt + afront ) {
return res - aback ;
}
res += P2 . size () * cnt ; cnt ++ ;
if ( res >= 1e16 ) break ;
}
return - 1 ;
}
} else {
int alen = 0 , len = 0 , aid = 0 ;
for ( int i = P1 . size () - 1 ; i >= 0 ; i -- ) {
if ( P1 [ i ] == '0' ) {
len ++ ;
if ( alen <= len ) {
alen = len ;
aid = i ;
}
} else {
len = 0 ;
}
}
len = 0 ;
int blen = 0 , bid = 0 ;
for ( int i = P2 . size () - 1 ; i >= 0 ; i -- ) {
if ( P2 [ i ] == '0' ) {
len ++ ;
if ( blen <= len ) {
blen = len ;
bid = i ;
}
} else {
len = 0 ;
}
}
if ( zc <= afront ) {
return 0 ;
} else if ( zc <= alen ) {
return aid ;
} else if ( zc <= aback + afront ) {
return P1 . size () - aback ;
} else if ( zc <= aback + bfront ) {
return P1 . size () * 1000000 - aback ;
} else if ( zc <= blen ) {
return P1 . size () * 1000000 + bid ;
} else if ( zc <= bback + afront ) {
return P1 . size () * 1000000 + P2 . size () - bback ;
} else if ( zc <= bback + bfront ) {
return P1 . size () * 1000000LL + P2 . size () + P1 . size () * 1000000 + P2 . size () - bback ;
}
return - 1 ;
}
}
};