|
|
1 /* Accepted 0.125 1 576 KB */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 void str2digit(string & s, string & digit)
8 {
9 for(int i = 0; i < s.size(); i++)
10 {
11 if(s[i] == 'i' || s[i] == 'j') {
12 digit += '1'; continue;
13 }
14 if(s[i] == 'a' || s[i] == 'b' || s[i] == 'c') {
15 digit += '2'; continue;
16 }
17 if(s[i] == 'd' || s[i] == 'e' || s[i] == 'f') {
18 digit += '3'; continue;
19 }
20 if(s[i] == 'g' || s[i] == 'h') {
21 digit += '4'; continue;
22 }
23 if(s[i] == 'k' || s[i] == 'l') {
24 digit += '5'; continue;
25 }
26 if(s[i] == 'm' || s[i] == 'n') {
27 digit += '6'; continue;
28 }
29 if(s[i] == 'p' || s[i] == 'r' || s[i] == 's') {
30 digit += '7'; continue;
31 }
32 if(s[i] == 't' || s[i] == 'u' || s[i] == 'v') {
33 digit += '8'; continue;
34 }
35 if(s[i] == 'w' || s[i] == 'x' || s[i] == 'y') {
36 digit += '9'; continue;
37 }
38 if(s[i] == 'o' || s[i] == 'q' || s[i] == 'z') {
39 digit += '0'; continue;
40 }
41 }
42 }
43
44 int main()
45 {
46 string num;
47 while((cin >> num) && num != "-1")
48 {
49 int n;
50 cin >> n;
51
52 string * dict = new string[n];
53 string * digit = new string[n];
54
55 for(int i = 0; i < n; i++)
56 {
57 cin >> dict[i];
58 str2digit(dict[i], digit[i]);
59 }
60
61 unsigned opt[101], path[101] = {0}, choice[101] = {0};
62 memset(opt, 0XFF, sizeof(opt));
63
64 opt[0] = 0;
65 for(int i = 0; i < num.size(); i++)
66 {
67 if(opt[i] == 0XFFFFFFFF)
68 continue;
69 for(int j = 0; j < n; j++)
70 if(num.find(digit[j], i) == i)
71 if(opt[i] + 1 < opt[i + digit[j].size()])
72 {
73 opt[i + digit[j].size()] = opt[i] + 1;
74 path[i + digit[j].size()] = i;
75 choice[i + digit[j].size()] = j;
76 }
77 }
78
79 if(opt[num.size()] == 0XFFFFFFFF)
80 cout << "No solution." << endl;
81 else
82 {
83 int x[101], m = 0, pos = num.size();
84 while(pos)
85 {
86 x[m++] = choice[pos];
87 pos = path[pos];
88 }
89 for(int i = m - 1; i >= 0; i--)
90 cout << dict[x[i]] << (i == 0 ? '\n' : ' ');
91 }
92
93 delete []dict;
94 delete []digit;
95 }
96
97 return 0;
98 }
99
1 /* Accepted 1.062 3 060 KB */
2 #include <stack>
3 #include <math.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int main()
9 {
10 double n;
11 stack <double> set;
12 while(cin >> n)
13 set.push(n);
14
15 cout.setf(ios_base::showpoint);
16 cout.setf(ios_base::fixed);
17 cout.precision(4);
18
19 while(set.empty() == false)
20 {
21 cout << sqrt(set.top()) << endl;
22 set.pop();
23 }
24
25 return 0;
26 }
27
1 /* Accepted 1115 C++ 00:00.01 856K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 string num;
10 while((cin >> num) && num != "0")
11 {
12 int sum = 0;
13 for(int i = 0; i < num.size(); i++)
14 sum += num[i] - '0';
15 int n = sum;
16 while(true)
17 {
18 int i = n, sum = 0;
19 while(i)
20 {
21 sum += i % 10;
22 i /= 10;
23 }
24 if(0 <= sum && sum < 10)
25 {
26 cout << sum << endl;
27 break;
28 }
29 else
30 n = sum;
31 }
32 }
33
34 return 0;
35 }
36
1 /* Accepted 1047 C++ 00:00.00 852K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, cnt;
7 char grid[21][21];
8
9 inline bool canGo(int i, int j)
10 {
11 if(i >= 1 && i <= n && j >= 1 && j <= m && grid[i][j] == 'X')
12 return true;
13 return false;
14 }
15
16 void search(int i, int j)
17 {
18 grid[i][j] = '-';
19
20 if(i - 1 < 1 || grid[i - 1][j] == '.')
21 cnt++;
22 if(i + 1 > n || grid[i + 1][j] == '.')
23 cnt++;
24 if(j - 1 < 1 || grid[i][j - 1] == '.')
25 cnt++;
26 if(j + 1 > m || grid[i][j + 1] == '.')
27 cnt++;
28
29 if(canGo(i - 1, j))
30 search(i - 1, j);
31 if(canGo(i + 1, j))
32 search(i + 1, j);
33 if(canGo(i, j - 1))
34 search(i, j - 1);
35 if(canGo(i, j + 1))
36 search(i, j + 1);
37 if(canGo(i - 1, j - 1))
38 search(i - 1, j - 1);
39 if(canGo(i - 1, j + 1))
40 search(i - 1, j + 1);
41 if(canGo(i + 1, j - 1))
42 search(i + 1, j - 1);
43 if(canGo(i + 1, j + 1))
44 search(i + 1, j + 1);
45 }
46
47 int main()
48 {
49 while(cin >> n >> m)
50 {
51 if(n == 0 && m == 0)
52 break;
53 int sx, sy;
54 cin >> sx >> sy;
55 for(int i = 1; i <= n; i++)
56 for(int j = 1; j <= m; j++)
57 switch(cin.get())
58 {
59 case '.' : grid[i][j] = '.'; break;
60 case 'X' : grid[i][j] = 'X'; break;
61 default : j--;
62 }
63 cnt = 0;
64 search(sx, sy);
65 cout << cnt << endl;
66 }
67
68 return 0;
69 }
70
1 /* Accepted 1060 C++ 00:00.06 848K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 class Graph
8 {
9 private:
10 int n, e;
11 int count[26];
12 bool map[26][26];
13 public:
14 Graph(const int nn)
15 {
16 n = nn; e = 0;
17 memset(count, 0, sizeof(count));
18 memset(map, false, sizeof(map));
19 }
20 void AddEdge(const int s, const int t)
21 {
22 e++;
23 if(map[s][t] == false)
24 count[t]++;
25 map[s][t] = true;
26 }
27 bool TopSort(int x[])
28 {
29 int cn = n;
30 int cnt[26];
31 memcpy(cnt, count, sizeof(count));
32
33 while(cn--)
34 {
35 int tot = 0, index;
36 for(int i = 0; i < n; i++)
37 if(cnt[i] == 0)
38 {
39 index = i;
40 tot++;
41 }
42 if(tot > 1)
43 return 0;
44 if(tot == 1)
45 {
46 for(int i = 0; i < n; i++)
47 if(map[index][i])
48 cnt[i]--;
49 x[cn] = index;
50 cnt[index] = -1;
51 }
52 }
53 return 1;
54 }
55 bool ExistCycle()
56 {
57 bool f[26][26];
58 memcpy(f, map, sizeof(map));
59 for(int k = 0; k < n; k++)
60 for(int i = 0; i < n; i++)
61 for(int j = 0; j < n; j++)
62 if(f[i][k] && f[k][j])
63 f[i][j] = 1;
64 for(int i = 0; i < n; i++)
65 if(f[i][i])
66 return 1;
67 return 0;
68 }
69 };
70
71 int main()
72 {
73 int n, m;
74 string relation;
75 while((cin >> n >> m) && n && m)
76 {
77 Graph G(n);
78 bool find = false;
79 for(int i = 1; i <= m; i++)
80 {
81 cin >> relation;
82
83 if(find)
84 continue;
85
86 G.AddEdge(relation[0] - 'A', relation[2] - 'A');
87
88 if(G.ExistCycle())
89 {
90 cout << "Inconsistency found after " << i << " relations." << endl;
91 find = true;
92 continue;
93 }
94
95 int x[26];
96 if(G.TopSort(x))
97 {
98 cout << "Sorted sequence determined after " << i << " relations: ";
99 for(int i = n - 1; i >= 0; i--)
100 cout << char(x[i] + 'A');
101 cout << '.' << endl;
102 find = true;
103 }
104 }
105 if(find == false)
106 cout << "Sorted sequence cannot be determined." << endl;
107 }
108
109 return 0;
110 }
111
摘要: Implement #1:
1 /* Accepted 1098 C++ 00:00.01 844K */ 2 #include <stack> 3 #include <string> 4 #include&nb... 阅读全文
This implement use the map in STL.
1 /* Accepted 1109 C++ 00:04.47 7992K */
2 #include <map>
3 #include <string>
4 #include <iostream>
5
6 using namespace std;
7
8 int main()
9 {
10 map <string, string> dict;
11
12 int n = 0; string s;
13 while(true)
14 {
15 getline(cin, s);
16 if(s == "")
17 break;
18
19 string a, b; int i;
20 for(i = 0; s[i] != ' '; i++)
21 a += s[i];
22 for(i = i + 1; i < s.size(); i++)
23 b += s[i];
24 dict[b] = a;
25 }
26
27 while(cin >> s)
28 {
29 if(dict.count(s))
30 cout << dict[s] << endl;
31 else
32 cout << "eh" << endl;
33 }
34
35 return 0;
36 }
37
This implement use quicksort and binay search.
1 /* Accepted 1109 C++ 00:04.34 6408K */
2 #include <string>
3 #include <stdlib.h>
4 #include <iostream>
5
6 using namespace std;
7
8 struct DICT { string en, mouse; } dict[100005];
9
10 int cmp(const void * a, const void * b)
11 {
12 DICT * c = (DICT *) a;
13 DICT * d = (DICT *) b;
14 return (c -> mouse < d -> mouse ? -1 : 1);
15 }
16
17 int main()
18 {
19 int n = 0; string s;
20 while(true)
21 {
22 getline(cin, s);
23 if(s == "")
24 break;
25 int i;
26 for(i = 0; s[i] != ' '; i++)
27 dict[n].en += s[i];
28 for(i++; i < s.size(); i++)
29 dict[n].mouse += s[i];
30 n++;
31 }
32
33 qsort(dict, n, sizeof(DICT), cmp);
34
35 while(cin >> s)
36 {
37 int l = 0, mid, r = n - 1, find = 0;
38 while(l <= r)
39 {
40 mid = (l + r) / 2;
41 if(dict[mid].mouse == s)
42 {
43 find = 1;
44 break;
45 }
46 if(dict[mid].mouse < s)
47 l = mid + 1;
48 else
49 r = mid - 1;
50 }
51 if(find)
52 cout << dict[mid].en << endl;
53 else
54 cout << "eh" << endl;
55 }
56
57 return 0;
58 }
59
1 /* Accepted 1075 C++ 00:00.00 844K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 string card[12];
10 cin >> card[0];
11 while(true)
12 {
13 for(int i = 1; i < 12; i++)
14 cin >> card[i];
15
16 cout << "CARDS: ";
17 for(int i = 0; i < 12; i++)
18 cout << card[i] << (i == 11 ? '\n' : ' ');
19
20 int count = 0;
21 for(int i = 0; i < 12; i++)
22 for(int j = i + 1; j < 12; j++)
23 for(int k = j + 1; k < 12; k++)
24 {
25 int p;
26 for(p = 0; p < 4; p++)
27 if( (card[i][p] == card[j][p] && card[j][p] == card[k][p] && card[i][p] == card[k][p]) ||
28 (card[i][p] != card[j][p] && card[j][p] != card[k][p] && card[i][p] != card[k][p]) );
29 else
30 break;
31
32 if(p == 4)
33 {
34 count++;
35 if(count == 1)
36 cout << "SETS: ";
37 else
38 cout << " ";
39 cout << count << ". " << card[i] << ' ' << card[j] << ' ' << card[k] << endl;
40 }
41 }
42 if(count == 0)
43 cout << "SETS: *** None Found ***" << endl;
44
45 if(cin >> card[0])
46 cout << endl;
47 else
48 break;
49 }
50
51 return 0;
52 }
53
1 /* Accepted 1073 C++ 00:00.02 848K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 string s;
10 while(cin >> s)
11 {
12 int n = s.size();
13 bool cyclic = true;
14 for(int k = 2; k <= n; k++)
15 {
16 int c[200] = {0};
17 for(int i = n; i > 0; i--)
18 {
19 c[i] += (s[i - 1] - '0') * k;
20 c[i - 1] += c[i] / 10;
21 c[i] %= 10;
22 }
23
24 if(c[0])
25 {
26 cyclic = false;
27 break;
28 }
29
30 string cur;
31 for(int i = 1; i <= n; i++)
32 cur += (c[i] + '0');
33
34 int pos = 0;
35 while(true)
36 {
37 pos = cur.find(s[0], pos);
38 if(pos == string::npos)
39 {
40 cyclic = false;
41 break;
42 }
43
44 string tmp;
45 for(int i = pos; i < n; i++)
46 tmp += cur[i];
47 for(int i = 0; i < pos; i++)
48 tmp += cur[i];
49
50 if(tmp == s)
51 break;
52
53 pos++;
54 }
55 }
56 if(cyclic)
57 cout << s << " is cyclic" << endl;
58 else
59 cout << s << " is not cyclic" << endl;
60 }
61
62 return 0;
63 }
64
1 /* Accepted 1409 C++ 00:00.32 956K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct SYS { int b, p; } sys[100][100];
8
9 int cmp(const void * a, const void * b)
10 {
11 SYS * c = (SYS *) a;
12 SYS * d = (SYS *) b;
13 return c -> p - d -> p;
14 }
15
16 int main()
17 {
18 cout.setf(ios_base::showpoint);
19 cout.setf(ios_base::fixed);
20 cout.precision(3);
21
22 int n;
23 cin >> n;
24 while(cin >> n)
25 {
26 int m[100], b[10000], bc = 0;
27 for(int i = 0; i < n; i++)
28 {
29 cin >> m[i];
30 for(int j = 0; j < m[i]; j++)
31 {
32 cin >> sys[i][j].b >> sys[i][j].p;
33 b[bc++] = sys[i][j].b;
34 }
35 qsort(sys[i], m[i], sizeof(SYS), cmp);
36 }
37
38 double max = 0;
39 for(int k = 0; k < bc; k++)
40 {
41 int sum = 0;
42 bool could = true;
43 for(int i = 0; i < n; i++)
44 {
45 int j;
46 for(j = 0; j < m[i]; j++)
47 if(sys[i][j].b >= b[k])
48 {
49 sum += sys[i][j].p;
50 break;
51 }
52 if(j == m[i])
53 {
54 could = false;
55 break;
56 }
57 }
58 if(could)
59 max >?= double(b[k]) / sum;
60 }
61
62 cout << max << endl;
63 }
64
65
66 return 0;
67 }
68
|