|
|
1 /* Accepted 1011 C++ 00:00.00 988K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, k;
7 struct TransitionTable
8 {
9 int lSingal, rSingal;
10 TransitionTable * next;
11
12 void insert(int l, int r)
13 {
14 while(next)
15 {
16 next -> insert(l, r);
17 return;
18 }
19 TransitionTable * p = new TransitionTable;
20 p -> lSingal = l;
21 p -> rSingal = r;
22 p -> next = NULL;
23 next = p;
24 }
25
26 void clear()
27 {
28 TransitionTable *p = next;
29 TransitionTable *q;
30 while(p)
31 {
32 q = p;
33 p = p -> next;
34 delete q;
35 }
36 next = NULL;
37 }
38 }tranT[15][10];
39
40 void readTable()
41 {
42 int l, r;
43 for(int i = 0; i < n; i++)
44 for(int j = 0; j < k; j++)
45 while(1)
46 {
47 cin >> l >> r;
48 tranT[i][j].insert(l, r);
49 if(cin.get() == '\n')
50 break;
51 }
52 }
53
54 int L;
55 struct BinTree
56 {
57 char transmittingElement;
58 int left, right;
59 }Tree[2048 + 1];
60
61 void readTree()
62 {
63 char transmittingElement;
64 for(int i = 1; i <= (1 << (L + 1)) - 1; i++)
65 {
66 cin >> transmittingElement;
67 if(transmittingElement == '*')
68 {
69 Tree[i].transmittingElement = -1;
70 Tree[i / 2].left = Tree[i / 2].right = 0;
71 }
72 else
73 {
74 Tree[i].transmittingElement = transmittingElement - 'a';
75 if(i % 2 == 0)
76 Tree[i / 2].left = i;
77 else
78 Tree[i / 2].right = i;
79 }
80 }
81 }
82
83 int isValid[2048 + 1][15];
84
85 int PreOrder(int cur, int singal)
86 {
87 if(isValid[cur][singal])
88 return isValid[cur][singal];
89 TransitionTable * p = tranT[singal][Tree[cur].transmittingElement].next;
90 if(Tree[cur].left == 0 && Tree[cur].right == 0)
91 {
92 while(p)
93 {
94 if(p -> lSingal >= n - m && p -> rSingal >= n - m)
95 return isValid[cur][singal] = 1;
96 p = p -> next;
97 }
98 return isValid[cur][singal] = -1;
99 }
100
101 while(p)
102 {
103 if(PreOrder(cur * 2, p -> lSingal) == 1 && PreOrder(cur * 2 + 1, p -> rSingal) == 1)
104 return isValid[cur][singal] = 1;
105 p = p -> next;
106 }
107 return isValid[cur][singal] = -1;
108 }
109
110 int main()
111 {
112 int NTA = 0;
113 cin >> n >> m >> k;
114 while(true)
115 {
116 cout << "NTA" << ++NTA << ':' << endl;
117
118 readTable();
119 while(cin >> L)
120 {
121 if(L == -1)
122 break;
123 readTree();
124
125 if(PreOrder(1, 0) == 1)
126 cout << "Valid" << endl;
127 else
128 cout << "Invalid" << endl;
129
130 for(int i = 1; i <= (1 << (L + 1)) - 1; i++)
131 Tree[i].transmittingElement = Tree[i].left = Tree[i].right = 0;
132 memset(isValid, 0, sizeof(isValid));
133 }
134
135 for(int i = 0; i < n; i++)
136 for(int j = 0; j < k; j++)
137 tranT[i][j].clear();
138
139 cin >> n >> m >> k;
140 if(n == 0 && m == 0 && k == 0)
141 break;
142 else
143 cout << endl;
144 }
145
146 return 0;
147 }
148
1 /* Accepted 1042 C++ 00:00.00 852K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int k1, k2, k3;
10 while(cin >> k1 >> k2 >> k3)
11 {
12 if(k1 == 0 && k2 == 0 && k3 == 0)
13 break;
14
15 string message;
16 cin >> message;
17
18 string g1, g2, g3;
19 int pos1[100], c1 = 0, pos2[100], c2 = 0, pos3[100], c3 = 0;
20 for(int i = 0; i < message.size(); i++)
21 {
22 if('a' <= message[i] && message[i] <= 'i')
23 {
24 g1 += message[i];
25 pos1[c1++] = i;
26 continue;
27 }
28 if('j' <= message[i] && message[i] <= 'r')
29 {
30 g2 += message[i];
31 pos2[c2++] = i;
32 continue;
33 }
34 g3 += message[i];
35 pos3[c3++] = i;
36 }
37
38 k1 = (c1 == 0 ? 0 : k1 % c1);
39 k2 = (c2 == 0 ? 0 : k2 % c2);
40 k3 = (c3 == 0 ? 0 : k3 % c3);
41
42 string t1, t2, t3;
43
44 for(int i = g1.size() - k1; i < g1.size(); i++)
45 t1 += g1[i];
46 for(int i = 0; i < g1.size() - k1; i++)
47 t1 += g1[i];
48
49 for(int i = g2.size() - k2; i < g2.size(); i++)
50 t2 += g2[i];
51 for(int i = 0; i < g2.size() - k2; i++)
52 t2 += g2[i];
53
54 for(int i = g3.size() - k3; i < g3.size(); i++)
55 t3 += g3[i];
56 for(int i = 0; i < g3.size() - k3; i++)
57 t3 += g3[i];
58
59 for(int i = 0; i < c1; i++)
60 message[pos1[i]] = t1[i];
61 for(int i = 0; i < c2; i++)
62 message[pos2[i]] = t2[i];
63 for(int i = 0; i < c3; i++)
64 message[pos3[i]] = t3[i];
65
66 cout << message << endl;
67 }
68
69 return 0;
70 }
71
1 /* Accepted 1082 C++ 00:00.00 872K */
2 #include <limits.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int n;
10 while((cin >> n) && n)
11 {
12 unsigned dist[101][101];
13 memset(dist, 0XFF, sizeof(dist));
14
15 int s, t, m;
16 for(s = 1; s <= n; s++)
17 {
18 cin >> m;
19 while(m--)
20 {
21 cin >> t;
22 cin >> dist[s][t];
23 }
24 }
25
26 for(int k = 1; k <= n; k++)
27 for(int i = 1; i <= n; i++)
28 for(int j = 1; j <= n; j++)
29 if(i != j && dist[i][k] != UINT_MAX && dist[k][j] != UINT_MAX)
30 dist[i][j] <?= dist[i][k] + dist[k][j];
31
32 int min = INT_MAX;
33 for(int i = 1; i <= n; i++)
34 {
35 int max = 0;
36 bool flag = 1;
37 for(int j = 1; j <= n; j++)
38 if(i != j)
39 {
40 if(dist[i][j] != UINT_MAX)
41 max >?= dist[i][j];
42 else
43 {
44 flag = 0;
45 break;
46 }
47 }
48 if(flag)
49 if(min > max)
50 {
51 min = max;
52 s = i;
53 }
54 }
55
56 if(min == INT_MAX)
57 cout << "disjoint" << endl;
58 else
59 cout << s << ' ' << min << endl;
60 }
61
62 return 0;
63 }
64
1 /* Accepted 1028 C++ 00:00.00 832K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int n;
10 bool track[50];
11
12 cin >> n;
13 while(cin >> n)
14 {
15 int blackOnOdd = 0, blackOnEven = 0;
16 for(int i = 1; i <= n; i++)
17 {
18 cin >> track[i];
19 if(i % 2)
20 blackOnOdd += track[i];
21 else
22 blackOnEven += track[i];
23 }
24
25 if(n % 2)
26 cout << "YES" << endl;
27 else
28 {
29 if(abs(blackOnOdd - blackOnEven) <= 1)
30 cout << "YES" << endl;
31 else
32 cout << "NO" << endl;
33 }
34 }
35
36 return 0;
37 }
38
1 /* Accepted 1068 C++ 00:00.00 868K */
2 #include <map>
3 #include <stack>
4 #include <string>
5 #include <iostream>
6
7 using namespace std;
8
9 int main()
10 {
11 map <char, string> morse;
12 morse['A'] = ".-";
13 morse['B'] = "-...";
14 morse['C'] = "-.-.";
15 morse['D'] = "-..";
16 morse['E'] = ".";
17 morse['F'] = "..-.";
18 morse['G'] = "--.";
19 morse['H'] = "....";
20 morse['I'] = "..";
21 morse['J'] = ".---";
22 morse['K'] = "-.-";
23 morse['L'] = ".-..";
24 morse['M'] = "--";
25 morse['N'] = "-.";
26 morse['O'] = "---";
27 morse['P'] = ".--.";
28 morse['Q'] = "--.-";
29 morse['R'] = ".-.";
30 morse['S'] = "...";
31 morse['T'] = "-";
32 morse['U'] = "..-";
33 morse['V'] = "...-";
34 morse['W'] = ".--";
35 morse['X'] = "-..-";
36 morse['Y'] = "-.--";
37 morse['Z'] = "--..";
38 morse['_'] = "..--";
39 morse[','] = ".-.-";
40 morse['.'] = "---.";
41 morse['?'] = "----";
42
43 int n, count = 0; cin >> n;
44 string message;
45 while(cin >> message)
46 {
47 string code;
48 stack <int> len;
49 for(int i = 0; i < message.size(); i++)
50 {
51 code += morse[message[i]];
52 len.push(morse[message[i]].size());
53 }
54
55 cout << ++count << ':' << ' ';
56
57 int pos = 0;
58 string ch = "ABCDEFGHIJKLMNOPQRSTUVWXYZ_,.?";
59 while(len.empty() == false)
60 {
61 for(int i = 0; i < 30; i++)
62 if(morse[ch[i]].size() == len.top())
63 if(code.find(morse[ch[i]], pos) == pos)
64 {
65 cout << ch[i];
66 break;
67 }
68 pos += len.top();
69 len.pop();
70 }
71 cout << endl;
72 }
73
74 return 0;
75 }
76
1 /* Accepted 1099 C++ 00:00.00 840K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 string word;
10 int curLineLen = 0;
11
12 while(cin >> word)
13 {
14 if(word == "<br>")
15 {
16 curLineLen = 0;
17 cout << endl;
18 continue;
19 }
20 if(word == "<hr>")
21 {
22 if(curLineLen)
23 cout << endl;
24 for(int i = 0; i < 80; i++)
25 cout << '-';
26 cout << endl;
27 curLineLen = 0;
28 continue;
29 }
30 if(curLineLen == 0)
31 {
32 curLineLen = word.size();
33 cout << word;
34 continue;
35 }
36 if(curLineLen + word.size() + 1 <= 80)
37 {
38 if(curLineLen)
39 cout << ' ';
40 cout << word;
41 curLineLen += word.size() + 1;
42 }
43 else
44 {
45 curLineLen = word.size();
46 cout << endl;
47 cout << word;
48 }
49 }
50 cout << endl;
51
52 return 0;
53 }
54
1 /* Accepted 1029 C++ 00:00.01 832K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n;
9 cin >> n;
10 while(cin >> n)
11 {
12 int s, t;
13 int count[201] = {0};
14 for(int i = 0; i < n; i++)
15 {
16 cin >> s >> t;
17 if(s > t)
18 { s = s ^ t; t = s ^ t; s = s ^ t; }
19 s = (s + 1) / 2;
20 t = (t + 1) / 2;
21 for(int j = s; j <= t; j++)
22 count[j]++;
23 }
24 int max = 0;
25 for(int i = 1; i <= 200; i++)
26 max >?= count[i];
27 cout << max * 10 << endl;
28 }
29
30 return 0;
31 }
32
1 /* Accepted 1061 C++ 00:00.05 856K */
2 #include <stack>
3 #include <string>
4 #include <iostream>
5
6 using namespace std;
7
8 int main()
9 {
10 int n;
11 cin >> n;
12 while(n--)
13 {
14 string command, url, curURL = "http://www.acm.org/";
15 stack<string> backward, forward;
16
17 while(1)
18 {
19 cin >> command;
20 if(command == "QUIT")
21 break;
22 if(command == "VISIT")
23 {
24 backward.push(curURL);
25 cin >> curURL;
26 while(forward.empty() == false)
27 forward.pop();
28 }
29 if(command == "BACK")
30 {
31 if(backward.empty())
32 {
33 cout << "Ignored" << endl;
34 continue;
35 }
36 else
37 {
38 forward.push(curURL);
39 curURL = backward.top();
40 backward.pop();
41 }
42 }
43 if(command == "FORWARD")
44 {
45 if(forward.empty())
46 {
47 cout << "Ignored" << endl;
48 continue;
49 }
50 else
51 {
52 backward.push(curURL);
53 curURL = forward.top();
54 forward.pop();
55 }
56 }
57 cout << curURL << endl;
58 }
59 if(n)
60 cout << endl;
61 }
62
63 return 0;
64 }
65
1 /* Accepted 1089 C++ 00:00.03 840K */
2 #include <string.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int n, set[20];
8
9 bool x[20];
10 void search(int i, int j)
11 {
12 if(j > 6)
13 {
14 int count = 0;
15 for(int i = 1; i <= n; i++)
16 if(x[i])
17 {
18 count++;
19 cout << set[i] << (count == 6 ? '\n' : ' ');
20 }
21 return;
22 }
23 if(i > n)
24 return;
25 if(6 - j <= n - i)
26 {
27 x[i] = 1;
28 search(i + 1, j + 1);
29 x[i] = 0;
30
31 search(i + 1, j);
32 }
33 }
34
35 int main()
36 {
37 cin >> n;
38 while(1)
39 {
40 memset(x, 0, sizeof(x));
41 for(int i = 1; i <= n; i++)
42 cin >> set[i];
43
44 search(1, 1);
45
46 cin >> n;
47 if(n)
48 cout << endl;
49 else
50 break;
51 }
52
53 return 0;
54 }
55
1 /* Accepted 1025 C++ 00:00.16 924K */
2 #include <string.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Stick { int l, w; } stick[5000];
8
9 int cmp(const void * a, const void * b)
10 {
11 Stick * c = (Stick*) a;
12 Stick * d = (Stick*) b;
13 if(c -> l == d -> l)
14 return c -> w - d -> w;
15 return c -> l - d -> l;
16 }
17
18 int main()
19 {
20 int n;
21 cin >> n;
22 while(cin >> n)
23 {
24 for(int i = 0; i < n; i++)
25 cin >> stick[i].l >> stick[i].w;
26
27 qsort(stick, n, sizeof(Stick), cmp);
28
29 bool x[5000] = {0};
30 int count = 0, m = n;
31 while(m)
32 {
33 int k, curL, curW;
34 for(k = 0; k < n; k++)
35 if(x[k] == 0)
36 break;
37 curL = stick[k].l;
38 curW = stick[k].w;
39 for(int i = k; i < n; i++)
40 if(x[i] == 0)
41 if(stick[i].l >= curL && stick[i].w >= curW)
42 {
43 m--;
44 x[i] = 1;
45 curL = stick[i].l;
46 curW = stick[i].w;
47 }
48 count++;
49 }
50
51 cout << count << endl;
52 }
53
54 return 0;
55 }
56
|