|
|
1 /* Accepted 1372 C++ 00:00.33 848K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, map[50][50];
9
10 while(cin >> n >> m)
11 {
12 for(int i = 0; i < n; i++)
13 for(int j = 0; j < n; j++)
14 map[i][j] = INT_MAX;
15
16 int s, t, l;
17 for(int i = 0; i < m; i++)
18 {
19 cin >> s >> t >> l;
20 s--, t--;
21 if(l < map[s][t] && l < map[t][s])
22 map[s][t] = map[t][s] = l;
23 }
24
25 if(n == 0 || m == 0)
26 {
27 cout << 0 << endl; continue;
28 }
29
30 //prim
31 int ans = 0;
32 int lowcost[50];
33 bool vset[50] = { true };
34
35 for(int i = 1; i < n; i++)
36 lowcost[i] = map[0][i];
37 int v = 0;
38 for(int k = 1; k < n; k++)
39 {
40 int min = INT_MAX, idx;
41 for(int i = 0; i < n; i++)
42 if(vset[i] == false && lowcost[i] < min)
43 min = lowcost[i], idx = i;
44
45 vset[idx] = true;
46 v = idx;
47
48 ans += min;
49
50 for(int i = 0; i < n; i++)
51 if(vset[i] == false && map[v][i] < lowcost[i])
52 lowcost[i] = map[v][i];
53 }
54
55 cout << ans << endl;
56 }
57
58 return 0;
59 }
60
1 /* Accepted 1366 C++ 00:09.36 936K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int cash, N, n[11], d[11];
9 bool x[100001];
10
11 while(cin >> cash >> N)
12 {
13 for(int i = 1; i <= N; i++)
14 scanf("%d %d", n + i, d + i);
15
16 memset(x, false, cash + 1);
17
18 x[0] = true;
19 for(int i = 1; i <= N; i++)
20 for(int j = cash; j >= d[i]; j--)
21 for(int k = 1; k <= n[i]; k++)
22 if(d[i] * k <= j)
23 x[j] = x[j] || x[j - d[i] * k];
24 else
25 break;
26 for(int i = cash; i >= 0; i--)
27 if(x[i])
28 {
29 cout << i << endl; break;
30 }
31 }
32
33 return 0;
34 }
35
1 /* Accepted 1008K 579MS G++ 1655B */
2 #include <iostream>
3
4 using namespace std;
5
6 const int maxn = 50000;
7
8 int main()
9 {
10 int n, m;
11 int x[maxn + 1];
12 int l[maxn + 1], r[maxn + 1];
13
14 scanf("%d", &m);
15 while(m--)
16 {
17 scanf("%d", &n);
18 bool AllNegative = true;
19 for(int i = 1; i <= n; i++)
20 {
21 scanf("%d", x + i);
22 if(x[i] > 0)
23 AllNegative = false;
24 }
25 if(n == 2)
26 {
27 cout << x[1] + x[2] << endl; continue;
28 }
29 if(AllNegative)
30 {
31 int max = INT_MIN, a, b;
32 for(int i = 1; i <= n; i++)
33 if(x[i] > max)
34 {
35 max = x[i];
36 a = i;
37 }
38 max = INT_MIN;
39 for(int i = 1; i <= n; i++)
40 if(x[i] > max && i != a)
41 {
42 max = x[i];
43 b = i;
44 }
45 cout << x[a] + x[b] << endl;
46 continue;
47 }
48
49 int max, sum;
50
51 max = sum = 0;
52 for(int i = 1; i <= n; i++)
53 {
54 sum += x[i];
55 max >?= sum;
56 sum >?= 0;
57 l[i] = max;
58 }
59
60 max = sum = 0;
61 for(int i = n; i >= 1; i--)
62 {
63 sum += x[i];
64 max >?= sum;
65 sum >?= 0;
66 r[i] = max;
67 }
68
69 int ans = 0;
70 for(int i = 1; i <= n - 1; i++)
71 ans >?= (l[i] + r[i + 1]);
72
73 printf("%d\n", ans);
74 }
75
76 return 0;
77 }
78
1 /* Accepted 1180 C++ 00:01.39 1816K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 bool x[1000001] = { false };
9 for(int i = 1; i <= 1000000; i++)
10 {
11 int n = i, sum = i;
12 while(n)
13 {
14 sum += n % 10;
15 n /= 10;
16 }
17 if(sum <= 1000000)
18 x[sum] = true;
19 }
20 for (int i = 1; i <= 1000000; i++)
21 if(x[i] == false)
22 cout << i << endl;
23
24 return 0;
25 }
26
1 /* Accepted 1284 C++ 00:00.01 836K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n;
9 cout << "PERFECTION OUTPUT" << endl;
10 while(cin >> n && n)
11 {
12 int sum = 0;
13 for(int i = 1; i * 2 <= n; i++)
14 if(n % i == 0)
15 sum += i;
16 printf("%5d ", n);
17 if(sum == n)
18 cout << "PERFECT" << endl;
19 if(sum < n)
20 cout << "DEFICIENT" << endl;
21 if(sum > n)
22 cout << "ABUNDANT" << endl;
23 }
24 cout << "END OF OUTPUT" << endl;
25
26 return 0;
27 }
28
1 /* Accepted 1224 C++ 00:00.01 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n;
9 int HIT[56] = { 0 };
10 int ERR[56] = { 0 };
11 int DIG[56] = { 0 };
12 int KILL[56] = { 0 };
13 int BLOCK[56] = { 0 };
14 int GAMES[56] = { 0 };
15
16 char key;
17 int GameCount = 0;
18 int CurrentPlayerNumber;
19 while(cin >> key)
20 {
21 if(key == 'C')
22 {
23 cin >> n;
24 for(int i = 0; i < n; i++)
25 {
26 cin >> CurrentPlayerNumber;
27 GAMES[CurrentPlayerNumber]++;
28 }
29 GameCount++;
30 continue;
31 }
32 if(key == 'H')
33 {
34 cin >> CurrentPlayerNumber;
35 HIT[CurrentPlayerNumber]++;
36 continue;
37 }
38 if(key == 'K')
39 {
40 cin >> CurrentPlayerNumber;
41 KILL[CurrentPlayerNumber]++;
42 continue;
43 }
44 if(key == 'E')
45 {
46 cin >> CurrentPlayerNumber;
47 ERR[CurrentPlayerNumber]++;
48 continue;
49 }
50 if(key == 'B')
51 {
52 cin >> CurrentPlayerNumber;
53 BLOCK[CurrentPlayerNumber]++;
54 continue;
55 }
56 if(key == 'D')
57 {
58 cin >> CurrentPlayerNumber;
59 DIG[CurrentPlayerNumber]++;
60 continue;
61 }
62 //key == 'R'
63 cout << "Player Hit Pct KPG BPG DPG" << endl;
64 cout << "-----------------------------------------" << endl;
65
66 for(int i = 0; i <= 55; i++)
67 if(GAMES[i])
68 {
69 double HitPct = 0.0;
70 if(KILL[i] + ERR[i] + HIT[i])
71 HitPct = double(KILL[i] - ERR[i]) / (KILL[i] + ERR[i] + HIT[i]);
72 double KPG = double(KILL[i]) / GAMES[i];
73 double BPG = double(BLOCK[i]) / GAMES[i];
74 double DPG = double(DIG[i]) / GAMES[i];
75
76 printf("%02d %+5.3f % 7.3f % 7.3f % 7.3f", i, HitPct, KPG, BPG, DPG);
77 cout << endl;
78 }
79
80 int SumBLOCK = 0;
81 int SumKILL = 0;
82 int SumERR = 0;
83 int SumDIG = 0;
84 int SumHIT = 0;
85
86 for(int i = 0; i <= 55; i++)
87 if(GAMES[i])
88 {
89 SumBLOCK += BLOCK[i];
90 SumKILL += KILL[i];
91 SumERR += ERR[i];
92 SumDIG += DIG[i];
93 SumHIT += HIT[i];
94 }
95 double HitPct = 0.0;
96 if(SumKILL + SumERR + SumHIT)
97 HitPct = double(SumKILL - SumERR) / (SumKILL + SumERR + SumHIT);
98 double KPG = double(SumKILL) / GameCount;
99 double BPG = double(SumBLOCK) / GameCount;
100 double DPG = double(SumDIG) / GameCount;
101
102 printf("team %+5.3f % 7.3f % 7.3f % 7.3f", HitPct, KPG, BPG, DPG);
103 cout << endl << endl;
104
105 memset(HIT, 0, sizeof(HIT));
106 memset(ERR, 0, sizeof(ERR));
107 memset(DIG, 0, sizeof(DIG));
108 memset(KILL, 0, sizeof(KILL));
109 memset(BLOCK, 0, sizeof(BLOCK));
110 memset(GAMES, 0, sizeof(GAMES));
111
112 GameCount = 0;
113 }
114
115 return 0;
116 }
117
1 /* Accepted 1201 C++ 00:00.00 836K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, x[100];
9
10 while(cin >> n && n)
11 {
12 char operation;
13 cin >> operation;
14 for(int i = 1; i <= n; i += 1)
15 cin >> x[i];
16 int ans[100] = { 0 };
17 if(operation == 'P')
18 {
19 int pos[100];
20 for(int i = 1; i <= n; i++)
21 pos[x[i]] = i;
22
23 for(int i = 1; i <= n; i++)
24 for(int j = 1; j < pos[i]; j++)
25 if(x[j] > i)
26 ans[i]++;
27 }
28 if(operation == 'I')
29 {
30 for(int i = 1; i <= n; i++)
31 {
32 int cnt = 0, j = 1;
33 while(true)
34 {
35 if(ans[j] == 0)
36 cnt++;
37 if(cnt == x[i] + 1)
38 break;
39 j++;
40 }
41 ans[j] = i;
42 }
43 }
44 for(int i = 1; i <= n; i++)
45 cout << ans[i] << (i == n ? '\n' : ' ');
46 }
47
48 return 0;
49 }
50
1 /* Accepted 1268 C++ 00:00.00 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int s, t, c = 1;
9 while(true)
10 {
11 cin >> s >> t;
12 if(s == -1 && t == -1)
13 break;
14
15 cout << "Case " << c++;
16
17 if(s == 0 && t == 0)
18 {
19 cout << " is a tree." << endl;
20 continue;
21 }
22
23 int cnt[2008] = { 0 };
24 bool x[2008] = { false };
25
26 x[s] = x[t] = true;
27 int max = 0;
28 max >?= s;
29 max >?= t;
30
31 cnt[t]++;
32 while(cin >> s >> t && s && t)
33 cnt[t]++, max >?= s, max >?= t, x[s] = x[t] = true;
34
35 //count the number of roots
36 int rootCnt = 0;
37 for(int i = 1; i <= max; i++)
38 if(x[i] && cnt[i] == 0)
39 rootCnt++;
40 if(rootCnt != 1)
41 {
42 cout << " is not a tree." << endl;
43 continue;
44 }
45
46 //check if each node has only one parent
47 int i;
48 for(i = 1; i <= max; i++)
49 if(x[i] && cnt[i] > 1)
50 break;
51 if(i <= max)
52 {
53 cout << " is not a tree." << endl;
54 continue;
55 }
56
57 cout << " is a tree." << endl;
58 }
59
60 return 0;
61 }
62
1 /* Accepted 1259 C++ 00:00.10 848K */
2 #include <stack>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int n, s[1001];
10 while(scanf("%d", &n) && n)
11 while(true)
12 {
13 scanf("%d", s + 1);
14 if(s[1] == 0)
15 {
16 cout << endl; break;
17 }
18 for(int i = 2; i <= n; i++)
19 scanf("%d", s + i);
20
21 stack <int> st;
22
23 int lp = 1, rp = 1;
24 while(lp <= n)
25 {
26 if(rp <= n && s[lp] == rp)
27 {
28 lp++, rp++; continue;
29 }
30 if(st.empty())
31 {
32 if(rp < n)
33 st.push(rp++);
34 else
35 {
36 cout << "No"; goto over;
37 }
38 }
39 else
40 {
41 if(s[lp] == st.top())
42 {
43 lp++; st.pop();
44 }
45 else
46 {
47 if(rp < n)
48 st.push(rp++);
49 else
50 {
51 cout << "No"; goto over;
52 }
53 }
54 }
55 }
56 cout << "Yes";
57 over:
58 cout << endl;
59 }
60
61 return 0;
62 }
63
1 /* Accepted 1251 C++ 00:00.00 832K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, h[50], c = 1;
9
10 while(cin >> n && n)
11 {
12 int sum = 0;
13 for(int i = 0; i < n; i++)
14 {
15 cin >> h[i];
16 sum += h[i];
17 }
18 sum /= n;
19 int ans = 0;
20 for(int i = 0; i < n; i++)
21 ans += abs(h[i] - sum);
22 ans /= 2;
23 cout << "Set #" << c++ << endl
24 << "The minimum number of moves is " << ans << '.'
25 << endl << endl;
26 }
27
28 return 0;
29 }
30
|