C++博客-superman

Section 3.3 - Home on the Range

superman — Thu, 04 Jun 2009 06:30:00 GMT

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int min(int a, int b, int c)
 6 {
 7     return min(a, min(b, c));
 8 }
 9 
10 int n;
11 int f[255][255];
12 bool map[255][255];
13 
14 int main()
15 {
16     freopen("range.in", "r", stdin);
17     freopen("range.out", "w", stdout);
18 
19     cin >> n;
20     for (int i = 0; i < n; i++)
21     for (int j = 0; j < n; j++)
22     {
23         char c;
24         cin >> c;
25         map[i][j] = (c == '0' ? false : true);
26     }
27 
28     for (int i = 0; i < n; i++)
29     for (int j = 0; j < n; j++)
30         if (map[i][j])
31         {
32             f[i][j] = 1;
33 
34             int t = 0;
35             if (i - 1 >= 0 && map[i - 1][j] &&
36                 j - 1 >= 0 && map[i][j - 1] && map[i - 1][j - 1])
37                 t = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]);
38 
39             f[i][j] >?= t + 1;
40         }
41 
42     int cnt[255] = { 0 };
43     for (int i = 0; i < n; i++)
44     for (int j = 0; j < n; j++)
45         if (f[i][j] >= 2)
46             for (int k = 2; k <= f[i][j]; k++)
47                 cnt[k]++;
48 
49     for (int i = 2; i <= 250; i++)
50         if (cnt[i])
51             cout << i << ' ' << cnt[i] << endl;
52 
53     return 0;
54 }
55 

superman 2009-06-04 14:30 发表评论

Section 3.3 - Camelot

superman — Thu, 04 Jun 2009 05:50:00 GMT

  1 #include <queue>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 struct point {
  7     int x, y;
  8     point operator+(const point &p) const {
  9         point np = { x + p.x, y + p.y };
 10         return np;
 11     }
 12 }   ;
 13 
 14 int r, c, knightsNum;
 15 point king, knights[30 * 26];
 16 
 17 const point kinghtDir[8] = {
 18     {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
 19     {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
 20 }   ;
 21 
 22 inline bool inside(const point &p) {
 23     return p.x >= 0 && p.x < r && p.y >= 0 && p.y < c;
 24 }
 25 
 26 int dist[30][26][30][26];
 27 void spfa(const point &s)
 28 {
 29     for (int i = 0; i < r; i++)
 30     for (int j = 0; j < c; j++)
 31         dist[s.x][s.y][i][j] = INT_MAX;
 32     dist[s.x][s.y][s.x][s.y] = 0;
 33 
 34     queue<point> q;
 35     q.push(s);
 36 
 37     point cp;   //current point
 38     point np;   //next point
 39     while (q.empty() == false)
 40     {
 41         cp = q.front(); q.pop();
 42         for (int i = 0; i < 8; i++)
 43         {
 44             np = cp + kinghtDir[i];
 45             if (inside(np) && dist[s.x][s.y][cp.x][cp.y] + 1 < dist[s.x][s.y][np.x][np.y])
 46             {
 47                 dist[s.x][s.y][np.x][np.y] = dist[s.x][s.y][cp.x][cp.y] + 1;
 48                 q.push(np);
 49             }
 50         }
 51     }
 52 }
 53 
 54 int ans = INT_MAX;
 55 void gather(int tx, int ty)
 56 {
 57     int sum = 0;
 58     for (int i = 0; i < knightsNum; i++)
 59         sum += dist[knights[i].x][knights[i].y][tx][ty];
 60 
 61     if (sum > ans)
 62         return;
 63 
 64     for (int i = max(0, king.x - 2); i <= min(r - 1, king.x + 2); i++)
 65     for (int j = max(0, king.y - 2); j <= min(c - 1, king.y + 2); j++)
 66     {
 67         int tmp;
 68         if (i == king.x && j == king.y)
 69             tmp = 0;
 70         else
 71         {
 72             if (abs(i - king.x) == 1 || abs(j - king.y == 1))
 73                 tmp = 1;
 74             else
 75                 tmp = 2;
 76         }
 77         for (int k = 0; k < knightsNum; k++)
 78             if (dist[knights[k].x][knights[k].y][i][j] != INT_MAX &&
 79                 dist[i][j][tx][ty] != INT_MAX)
 80             ans  (sum - dist[knights[k].x][knights[k].y][tx][ty]
 81                 + tmp + dist[knights[k].x][knights[k].y][i][j] + dist[i][j][tx][ty]);
 82     }
 83 }
 84 
 85 int main()
 86 {
 87     freopen("camelot.in", "r", stdin);
 88     freopen("camelot.out", "w", stdout);
 89 
 90     cin >> r >> c;
 91 
 92     {
 93         char a; int b;
 94         cin >> a >> b;
 95         king.y = a - 'A', king.x = b - 1;
 96         while (cin >> a >> b)
 97         {
 98             knights[knightsNum].y = a - 'A';
 99             knights[knightsNum].x = b - 1;
100             knightsNum++;
101         }
102     }
103 
104     if (knightsNum == 0)
105     {
106         cout << 0 << endl;
107         return 0;
108     }
109 
110     for (int i = 0; i < r; i++)
111     for (int j = 0; j < c; j++)
112     {
113         point cp = { i, j };
114         spfa(cp);
115     }
116 
117     for (int i = 0; i < r; i++)
118     for (int j = 0; j < c; j++)
119         gather(i, j);
120 
121     cout << ans << endl;
122 
123     return 0;
124 }
125 

superman 2009-06-04 13:50 发表评论

Section 3.3 - Shopping Offers

superman — Wed, 03 Jun 2009 02:17:00 GMT

  1 #include <set>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 class SepcialOffer;
  7 class Cart;
  8 
  9 class SpecialOffer {
 10 private:
 11     int n;
 12     int c[5];   //code of each product
 13     int x[5];   //amount of each product needed
 14 public:
 15     int sp;     //special price
 16 public:
 17     friend class Cart;
 18     friend istream& operator>>(istream &is, SpecialOffer &t) {
 19         is >> t.n;
 20         for (int i = 0; i < t.n; i++)
 21             is >> t.c[i] >> t.x[i];
 22         is >> t.sp;
 23         return is;
 24     }
 25 }   so[100];    //special offers set
 26 
 27 class Cart {
 28 private:
 29     int n;
 30     int c[5];   //code of each product in the cart
 31     int x[5];   //amount of each product int the cart
 32     int p[5];   //the regular price of each product int the cart
 33 public:
 34     int bestp;  //the best price of all products int the cart
 35 public:
 36     int regularPrice() {
 37         int sum = 0;
 38         for (int i = 0; i < n; i++)
 39             sum += p[i] * x[i];
 40         return sum;
 41     }
 42     bool couldUseSpecialOffer(const SpecialOffer &t) const {
 43         for (int i = 0; i < t.n; i++) {
 44             int j;
 45             for (j = 0; j < n; j++)
 46                 if (t.c[i] == c[j] && t.x[i] <= x[j])
 47                     break;
 48             if (j == n)
 49                 return false;
 50         }
 51         return true;
 52     }
 53     Cart useSpecialOffer(const SpecialOffer &t) const {
 54         Cart nc = *this;
 55         for (int i = 0; i < t.n; i++) {
 56             int j;
 57             for (j = 0; j < n; j++)
 58                 if (t.c[i] == c[j] && t.x[i] <= x[j]) {
 59                     nc.x[j] -= t.x[i];
 60                     break;
 61                 }
 62         }
 63         return nc;
 64     }
 65     bool operator<(const Cart &t) const {
 66         for (int i = 0; i < n; i++)
 67             if (x[i] != t.x[i])
 68                 return x[i] - t.x[i] < 0 ? true : false;
 69         return false;
 70     }
 71     friend istream& operator>>(istream &is, Cart &t) {
 72         is >> t.n;
 73         for (int i = 0; i < t.n; i++)
 74             is >> t.c[i] >> t.x[i] >> t.p[i];
 75         return is;
 76     }
 77 }   cart;
 78 
 79 int so_num;   //special offers num
 80 set<Cart> cartSet;
 81 
 82 int search(Cart cart)
 83 {
 84     set<Cart>::iterator it = cartSet.find(cart);
 85     if (it != cartSet.end())
 86         return it->bestp;
 87 
 88 
 89     cart.bestp = INT_MAX;
 90     for (int i = 0; i < so_num; i++)
 91         if (cart.couldUseSpecialOffer(so[i]))
 92             cart.bestp  (search(cart.useSpecialOffer(so[i])) + so[i].sp);
 93 
 94     cart.bestp  cart.regularPrice();
 95 
 96     cartSet.insert(cart);
 97 
 98     return cart.bestp;
 99 }
100 
101 int main()
102 {
103     freopen("shopping.in", "r", stdin);
104     freopen("shopping.out", "w", stdout);
105 
106     cin >> so_num;
107     for (int i = 0; i < so_num; i++)
108         cin >> so[i];
109     cin >> cart;
110 
111     cout << search(cart) << endl;
112 
113     return 0;
114 }
115 

superman 2009-06-03 10:17 发表评论

Section 3.3 - Riding The Fences

superman — Wed, 20 May 2009 02:45:00 GMT

 1 #include <stack>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int n = 1024, m;
 7 int deg[1024];
 8 int map[1024][1024];
 9 
10 stack<int> ans_st;
11 
12 void search(int p)
13 {
14     for (int i = 0; i < n; i++)
15         if (map[p][i])
16         {
17             map[p][i]--, map[i][p]--;
18             search(i);
19         }
20     ans_st.push(p + 1);
21 }
22 
23 int main()
24 {
25     freopen("fence.in", "r", stdin);
26     freopen("fence.out", "w", stdout);
27 
28     cin >> m;
29 
30     int s, t;
31     for (int i = 0; i < m; i++)
32     {
33         cin >> s >> t;
34         deg[s - 1]++; deg[t - 1]++;
35         map[s - 1][t - 1]++; map[t - 1][s - 1]++;
36     }
37 
38     int i;
39     for (i = 0; i < n; i++)
40         if (deg[i] % 2 == 1)
41         {
42             search(i);
43             break;
44         }
45     if (i == n)
46         for (int j = 0; j < n; j++)
47             if (deg[j])
48             {
49                 search(j);
50                 break;
51             }
52 
53     while (ans_st.empty() == false)
54     {
55         cout << ans_st.top() << endl;
56         ans_st.pop();
57     }
58 
59     return 0;
60 }
61 

superman 2009-05-20 10:45 发表评论

Section 3.2 - Sweet Butter

superman — Tue, 19 May 2009 02:30:00 GMT

 1 #include <queue>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int cowNum;
 7 int pastureNum;
 8 int pathNum;
 9 int map[800][800];
10 
11 int CowsInThePasture[800];
12 
13 struct
14 {
15     int x[800][800];
16     int c[800];
17 
18 }   AdjList;
19 
20 int main()
21 {
22     freopen("butter.in", "r", stdin);
23     freopen("butter.out", "w", stdout);
24 
25     cin >> cowNum >> pastureNum >> pathNum;
26     for (int i = 0; i < cowNum; i++)
27     {
28         int t;
29         cin >> t;
30         CowsInThePasture[t - 1]++;
31     }
32 
33     for (int i = 0; i < pastureNum; i++)
34     for (int j = 0; j < pastureNum; j++)
35         map[i][j] = INT_MAX;
36 
37     int s, t, l;
38     for (int i = 0; i < pathNum; i++)
39     {
40         cin >> s >> t >> l;
41         map[s - 1][t - 1]  l;
42         map[t - 1][s - 1]  l;
43     }
44 
45     for (int i = 0; i < pastureNum; i++)
46     for (int j = 0; j < pastureNum; j++)
47         if (map[i][j] != INT_MAX)
48             AdjList.x[i][AdjList.c[i]++] = j;
49 
50     int ans = INT_MAX;
51     for (int k = 0; k < pastureNum; k++)
52     {
53         int d[800];
54         for (int i = 0; i < pastureNum; i++)
55             d[i] = INT_MAX;
56         d[k] = 0;
57 
58         queue<int> q;
59         q.push(k);
60 
61         bool inqueue[800] = { false };
62         inqueue[k] = true;
63 
64         while (q.empty() == false)
65         {
66             int s = q.front(); q.pop();
67 
68             for (int i = 0; i < AdjList.c[s]; i++)
69             {
70                 int t = AdjList.x[s][i];
71                 if (map[s][t] != INT_MAX && d[s] + map[s][t] < d[t])
72                 {
73                     d[t] = d[s] + map[s][t];
74                     if (inqueue[t] == false)
75                     {
76                         inqueue[t] = true;
77                         q.push(t);
78                     }
79                 }
80             }
81 
82             inqueue[s] = false;
83         }
84 
85         int sum = 0;
86         for (int i = 0; i < pastureNum; i++)
87             if (CowsInThePasture[i])
88                 sum += d[i] * CowsInThePasture[i];
89 
90         ans  sum;
91     }
92 
93     cout << ans << endl;
94 
95     return 0;
96 }
97 

superman 2009-05-19 10:30 发表评论

Section 3.2 - Magic Squares

superman — Sun, 17 May 2009 16:16:00 GMT

 1 #include <map>
 2 #include <queue>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int init_state, target_state;
 8 
 9 void get_init_and_target_state()
10 {
11     init_state = 12345678;
12     for (int i = 0, x, t = 10000000; i < 8; i++, t /= 10)
13     {
14         cin >> x;
15         target_state += x * t;
16     }
17 }
18 
19 map<int, string> stateMap;
20 
21 int main()
22 {
23     freopen("msquare.in", "r", stdin);
24     freopen("msquare.out", "w", stdout);
25 
26     get_init_and_target_state();
27 
28     queue<int> q;
29     q.push(init_state);
30     stateMap.insert(make_pair(init_state, ""));
31 
32     while (q.empty() == false)
33     {
34         int cur = q.front(); q.pop();
35 
36         if (cur == target_state)
37         {
38             cout << stateMap.find(cur)->second.size() << endl;
39             cout << stateMap.find(cur)->second << endl;
40             return 0;
41         }
42 
43         int x[10] = { 0 };
44         for (int i = 8, t = cur; t; i--, t /= 10)
45             x[i] = t % 10;
46 
47         int na = x[8] * 10000000 + x[7] * 1000000 + x[6] * 100000 +
48                  x[5] * 10000 + x[4] * 1000 + x[3] * 100 + x[2] * 10 + x[1];
49 
50         int nb = x[4] * 10000000 + x[1] * 1000000 + x[2] * 100000 +
51                  x[3] * 10000 + x[6] * 1000 + x[7] * 100 + x[8] * 10 + x[5];
52 
53         int nc = x[1] * 10000000 + x[7] * 1000000 + x[2] * 100000 +
54                  x[4] * 10000 + x[5] * 1000 + x[3] * 100 + x[6] * 10 + x[8];
55 
56         map<int, string>::iterator it;
57         if ((it = stateMap.find(na)) == stateMap.end())
58         {
59             it = stateMap.find(cur);
60             stateMap.insert(make_pair(na, it->second + 'A'));
61             q.push(na);
62         }
63         if ((it = stateMap.find(nb)) == stateMap.end())
64         {
65             it = stateMap.find(cur);
66             stateMap.insert(make_pair(nb, it->second + 'B'));
67             q.push(nb);
68         }
69         if ((it = stateMap.find(nc)) == stateMap.end())
70         {
71             it = stateMap.find(cur);
72             stateMap.insert(make_pair(nc, it->second + 'C'));
73             q.push(nc);
74         }
75     }
76 
77     return 0;
78 }
79 

superman 2009-05-18 00:16 发表评论

Section 3.2 - Feed Ratios

superman — Sat, 16 May 2009 04:08:00 GMT

摘要: 1 #include 2 3 using namespace std; 4 5 int gcd(const int a, cons... 阅读全文

superman 2009-05-16 12:08 发表评论

Section 3.2 - Spinning Wheels

superman — Wed, 13 May 2009 02:14:00 GMT

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 class Wheel
 6 {
 7 public:
 8     void rotate()
 9     {
10         for (int i = 0; i < wedge_num; i++)
11         {
12             wedges_start_angle[i] += rotation_speed;
13             wedges_start_angle[i] %= 360;
14         }
15     }
16 
17     int rotation_speed;
18     int wedge_num;
19     int wedges_start_angle[5];
20     int wedges_extent[5];
21 }   wheels[5];
22 
23 bool light_can_pass_all_wheels()
24 {
25     int c[360] = { 0 };
26     for (int i = 0; i < 5; i++)
27         for (int j = 0; j < wheels[i].wedge_num; j++)
28         {
29             int s = wheels[i].wedges_start_angle[j];
30             for (int k = 0; k <= wheels[i].wedges_extent[j]; k++)
31                 c[(s + k) % 360] += 1;
32         }
33 
34     for (int i = 0; i < 360; i++)
35         if (c[i] == 5)
36             return true;
37     return false;
38 }
39 
40 int main()
41 {
42     freopen("spin.in", "r", stdin);
43     freopen("spin.out", "w", stdout);
44 
45     for (int i = 0; i < 5; i++)
46     {
47         cin >> wheels[i].rotation_speed >> wheels[i].wedge_num;
48         for (int j = 0; j < wheels[i].wedge_num; j++)
49             cin >> wheels[i].wedges_start_angle[j] >> wheels[i].wedges_extent[j];
50     }
51 
52     if (light_can_pass_all_wheels())
53     {
54         cout << 0 << endl;
55         return 0;
56     }
57     for (int t = 1; t < 360; t++)
58     {
59         for (int i = 0; i < 5; i++)
60             wheels[i].rotate();
61         if (light_can_pass_all_wheels())
62         {
63             cout << t << endl;
64             return 0;
65         }
66     }
67 
68     cout << "none" << endl;
69 
70     return 0;
71 }
72 

superman 2009-05-13 10:14 发表评论

Section 3.2 - Stringsobits

superman — Mon, 11 May 2009 09:40:00 GMT

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     freopen("kimbits.in", "r", stdin);
 8     freopen("kimbits.out", "w", stdout);
 9 
10     int n, m; unsigned t;
11 
12     cin >> n >> m >> t;
13 
14     unsigned f[32][32] = { 0 };
15 
16     for (int i = 0; i <= m; i++)
17         f[0][i] = 1;
18     for (int i = 0; i <= n; i++)
19         f[i][0] = 1;
20 
21     for (int i = 1; i <= n; i++)
22     for (int j = 1; j <= m; j++)
23         f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
24 
25     for (int i = n - 1, j = m; i >= 0; i--)
26     {
27         if (t > f[i][j])
28         {
29             cout << 1;
30             t -= f[i][j];
31             j--;
32         }
33         else
34             cout << 0;
35     }
36     cout << endl;
37 
38     return 0;
39 }
40 

superman 2009-05-11 17:40 发表评论

Section 3.2 - Factorials

superman — Wed, 29 Apr 2009 08:15:00 GMT

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     freopen("fact4.in", "r", stdin);
 8     freopen("fact4.out", "w", stdout);
 9 
10     int n, c2 = 0, c5 = 0, cr = 1;
11 
12     cin >> n;
13 
14     for (int i = 2; i <= n; i++)
15     {
16         int t = i;
17 
18         while (t && t % 2 == 0) c2++, t /= 2;
19         while (t && t % 5 == 0) c5++, t /= 5;
20 
21         cr *= t, cr %= 10;
22     }
23 
24     for (int i = 0; i < c2 - c5; i++)
25         cr *= 2, cr %= 10;
26 
27     cout << cr << endl;
28 
29     return 0;
30 }
31 

superman 2009-04-29 16:15 发表评论