-
Notifications
You must be signed in to change notification settings - Fork 5
/
UVA-12333.cpp
121 lines (112 loc) · 2.08 KB
/
UVA-12333.cpp
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
#include<stdio.h>
#include<string.h>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
struct BigInt {
static const long long BASE = 1000000000000000000;
static const int WIDTH = 18;
static const int LEN = 4;
vector<long long> s;
BigInt(long long num = 0) {
*this = num;
}
BigInt operator= (long long num) {
s.clear();
do {
s.push_back(num % BASE);
num /= BASE;
} while(num > 0);
return *this;
}
BigInt operator+ (const BigInt &b) {
BigInt c;
c.s.clear();
long long g = 0, x;
int ssize = s.size(), bssize = b.s.size();
for(int i = 0; ; i++) {
if(g == 0 && i >= ssize && i >= bssize) break;
x = g;
if(i < ssize) x += s[i];
if(i < bssize) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
string outN() {
string str, st;
int i = s.size() - 1, j = LEN;
while(i >= 0 && j > 0) {
st = to_string(s[i]);
while(i != s.size() - 1 && st.length() < WIDTH) {
st = "0" + st;
}
str += st;
--i;
--j;
}
return str.substr(0, 40);
}
};
struct Node {
int id;
int num;
Node* childs[10] = {NULL};
};
vector<string> v;
Node* createTree() {
int i, j, n, num;
Node * tree = new Node;
tree->id = -1;
tree->num = -1;
for(i = 0; i < v.size(); ++i) {
n = v[i].size();
Node *p = tree;
for(j = 0; j < n; ++j) {
num = v[i][j] - '0';
if(!p->childs[num]) {
p->childs[num] = new Node;
p->childs[num]->id = i;
p->childs[num]->num = num;
}
p = p->childs[num];
}
}
return tree;
}
int main() {
char s[45];
int i, j, T, n, num, res;
BigInt bv[3];
bv[0] = 1;
bv[1] = 1;
v.push_back("1");
v.push_back("1");
for(i = 2; i < 100000; ++i) {
bv[i % 3] = bv[(i-1) % 3] + bv[(i-2) % 3];
v.push_back(bv[i % 3].outN());
}
scanf("%d", &T);
Node * tree = createTree();
for(i = 0; i < T; ++i) {
scanf("%s", s);
n = strlen(s);
Node * p = tree;
for(j = 0; j < n; ++j) {
num = s[j] - '0';
if(!p->childs[num]) {
break;
}
p = p->childs[num];
}
if(j == n) {
res = p->id;
} else {
res = -1;
}
printf("Case #%d: %d\n", i+1, res);
}
return 0;
}