AOJ 1077 - The Great Summer Contest

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1077

解法

• Math と DP
• Greedy と Graph
• Geometry と Other

はそれぞれ区別しなくていい．

なるべく4のコンテストを開いて，残りの問題で特化したコンテストを開けばいいのでは，と思って提出したが WA．

反例は 4 2 4 0 0 0 のようなケースで，これには 3 と答えるべき．

ということで，4 のコンテストを開く回数を (開くことができる最大の数)-2 から調べて，最大となるものを答えた．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int a, b, c, d, e, f;
 8   while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) != EOF && a+b+c+d+e+f != 0) {
 9     int x = a + d;
10     int y = b + e;
11     int z = c + f;
12     int w = min(x, min(y, z));
13     int ans = 0;
14     for (int i = max(0, w-2); i <= w; i++) {
15       ans = max(ans, i + (x-i)/3 + (y-i)/3 + (z-i)/3);
16     }
17     printf("%d\n", ans);
18   }
19   return 0;
20 }