superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

 1 /* Accepted 1250 C++ 00:00.02 904K */
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 struct { int cnt, cost[32]; } map[12][12];
 7 
 8 int main()
 9 {
10     int n, m, c = 1;
11     while(cin >> n >> m && n && m)
12     {
13         for(int i = 1; i <= n; i++)
14             for(int j = 1; j <= n; j++)
15                 if(i != j)
16                 {
17                     cin >> map[i][j].cnt;
18                     for(int k = 1; k <= map[i][j].cnt; k++)
19                         cin >> map[i][j].cost[k];
20                 }
21         
22         int opt[1001][12];
23         for(int i = 0; i <= m; i++)
24             for(int j = 0; j <= n; j++)
25                 opt[i][j] = INT_MAX;
26         opt[0][0= opt[0][1= 0;
27         
28         for(int i = 1; i <= m; i++)
29         for(int j = 1; j <= n; j++)
30         for(int k = 1; k <= n; k++)
31             if(j != k)
32             if(opt[i - 1][k] != INT_MAX)
33             {
34                 int p;
35                 if(i % map[k][j].cnt == 0)
36                     p = map[k][j].cnt;
37                 else
38                     p = i % map[k][j].cnt;
39                 if(map[k][j].cost[p] == 0)
40                     continue;
41                 opt[i][j] <?= opt[i - 1][k] + map[k][j].cost[p];
42             }
43             
44         cout << "Scenario #" << c++ << endl;
45         if(opt[m][n] != INT_MAX)
46             cout << "The best flight costs " << opt[m][n] << '.' << endl;
47         else
48             cout << "No flight possible." << endl;
49         cout << endl;
50     }
51     
52     return 0;
53 }
54 

posted @ 2008-06-01 10:24 superman 阅读(219) | 评论 (0)编辑 收藏

Clod Sandbank With Lonely [Steve Chou]

After you've left me, my heart begins to rot.
The white tung tree is flying in the wind.
The fallen flowers follow the people to express their exquisite fellings in this season.
The wind around the river bank is blowing extremely wildly.
It continues to fiddle with women's tears.
That kind of strong love I can never give out again.
Sadness night after night.

When the lines of memory circling throught the fragmented past.
It's the dusk that occupies the heart.
There're flowers accompany the butterflies.
The lonely swallow can fly together.
In the still of the night I wander alone.
When the happy lovers send their redness to share their joy.
Closing eyes with sadness and not willing to back.
I still hate her gradually.
I'm not willing to rest even thought I fell a bit of regret.
Lonely sandbank, who should I think of?

posted @ 2008-05-31 11:04 superman 阅读(251) | 评论 (0)编辑 收藏

 1 /* Accepted 476K 657MS G++ 1154B */
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int farm; cin >> farm;
 9     
10     while(farm--)
11     {
12         int n, m, w;
13         cin >> n >> m >> w;
14         
15         int cnt = 0;
16         struct { int s, t, l; } e[5200];
17         
18         int s, t, l;
19         for(int i = 0; i < m; i++)
20         {
21             cin >> s >> t >> l; s--, t--;
22             e[cnt].s = s, e[cnt].t = t, e[cnt].l = l, cnt++;
23             e[cnt].s = t, e[cnt].t = s, e[cnt].l = l, cnt++;
24         }
25         for(int i = 0; i < w; i++)
26         {
27             cin >> s >> t >> l; s--, t--, l = -l;
28             e[cnt].s = s, e[cnt].t = t, e[cnt].l = l, cnt++;
29         }
30         
31         int d[500= { 0 };
32         
33         for(int k = 0; k < n - 1; k++)
34             for(int i = 0; i < cnt; i++)
35                 d[e[i].t] <?= d[e[i].s] + e[i].l;
36         
37         for(int i = 0; i < cnt; i++)
38             if(d[e[i].s] + e[i].l < d[e[i].t])
39             {
40                 cout << "YES"goto over;
41             }
42             
43         cout << "NO";
44         over:
45             cout << endl;
46     }
47     
48     return 0;
49 }
50 

posted @ 2008-05-28 18:00 superman 阅读(764) | 评论 (0)编辑 收藏

 1 /* Accepted 1942 C++ 00:00.22 1160K */
 2 #include <math.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     cout.setf(ios_base::showpoint);
10     cout.setf(ios_base::fixed);
11     cout.precision(3);
12     
13     int n, cnt = 1;
14     while(cin >> n && n)
15     {
16         struct { int x, y; } p[200];
17         for(int i = 0; i < n; i++)
18             cin >> p[i].x >> p[i].y;
19         
20         double dist[200][200= { 0.0 };
21         
22         for(int i = 0; i < n; i++)
23         for(int j = 0; j < n; j++)
24             dist[i][j] = pow(p[i].x - p[j].x, 2.0+ pow(p[i].y - p[j].y, 2.0);
25         for(int k = 0; k < n; k++)
26         for(int i = 0; i < n; i++)
27         for(int j = 0; j < n; j++)
28             dist[i][j] <?= max(dist[i][k], dist[k][j]);
29         cout << "Scenario #" << cnt++ << endl;
30         cout << "Frog Distance = " << sqrt(dist[0][1]) << endl << endl;
31     }
32     
33     return 0;
34 }
35 

posted @ 2008-05-28 10:17 superman 阅读(532) | 评论 (1)编辑 收藏

 1 /* Accepted 1708 C++ 00:00.00 836K */
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, m, start;
 9     while(cin >> n >> m >> start)
10     {
11         if(n == 0 && m == 0 && start == 0)
12             break;
13         
14         char map[10][10];
15         for(int i = 0; i < n; i++)
16             for(int j = 0; j < m; j++)
17                 cin >> map[i][j];
18         
19         int sx, sy;
20         for(int i = 0; i < n; i++)
21             for(int j = 0; j < m; j++)
22             {
23                 start--;
24                 if(start == 0)
25                 {
26                     sx = i, sy = j; break;
27                 }
28             }
29         
30         int cnt[10][10= { 0 };
31         cnt[sx][sy] = 1;
32         
33         while(true)
34         {
35             int tx = sx;
36             int ty = sy;
37             
38             switch(map[sx][sy])
39             {
40                 case 'N' : tx--break;
41                 case 'S' : tx++break;
42                 case 'W' : ty--break;
43                 case 'E' : ty++break;
44             }
45             if(tx < 0 || tx == n || ty < 0 || ty == m)
46             {
47                 cout << cnt[sx][sy] << " step(s) to exit" << endl;
48                 break;
49             }
50             if(cnt[tx][ty])
51             {
52                 cout << cnt[tx][ty] - 1 << " step(s) before a loop of "
53                      << cnt[sx][sy] - cnt[tx][ty] + 1  << " step(s)" << endl;
54                 break;
55             }
56             cnt[tx][ty] = cnt[sx][sy] + 1;
57             sx = tx, sy = ty;
58         }
59     }
60     
61     return 0;
62 }
63 

posted @ 2008-05-26 15:08 superman 阅读(161) | 评论 (0)编辑 收藏

 1 /* Accepted 2803 C++ 00:00.02 880K */
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int N;
 9     cin >> N;
10     while(N--)
11     {
12         int a, b, n, m;
13         
14         int px[101];
15         int py[101];
16         int dir[101];
17         
18         int map[101][101= { 0 };
19         
20         cin >> a >> b >> n >> m;
21         for(int i = 1; i <= n; i++)
22         {
23             char c;
24             cin >> px[i] >> py[i] >> c;
25             map[px[i]][py[i]] = i;
26             switch(c)
27             {
28                 case 'N' : dir[i] = 0break;
29                 case 'E' : dir[i] = 1break;
30                 case 'S' : dir[i] = 2break;
31                 case 'W' : dir[i] = 3break;
32             }
33         }
34         
35         bool ok = true;
36         for(int i = 0; i < m; i++)
37         {
38             int robot; char action; int repeat;
39             
40             cin >> robot >> action >> repeat;
41          
42             if(ok == false)
43                 continue;
44             
45             if(action == 'L' || action == 'R')
46             {
47                 repeat %= 4;
48                 if(action == 'L')
49                     dir[robot] = (dir[robot] - repeat + 4% 4;
50                 if(action == 'R')
51                     dir[robot] = (dir[robot] + repeat) % 4;
52                 continue;
53             }
54             //action == 'F'
55             while(repeat--)
56             {
57                 int x = px[robot];
58                 int y = py[robot];
59                 
60                 map[x][y] = 0;
61                 switch(dir[robot])
62                 {
63                     case 0 : y++break;
64                     case 1 : x++break;
65                     case 2 : y--break;
66                     case 3 : x--break;
67                 }
68                 if(map[x][y])
69                 {
70                     cout << "Robot " << robot
71                          << " crashes into robot " << map[x][y] << endl;
72                     break;
73                 }
74                 if(x == 0 || x == a + 1 || y == 0 || y == b + 1)
75                 {
76                     cout << "Robot " << robot << " crashes into the wall" << endl;
77                     break;
78                 }
79                 px[robot] = x;
80                 py[robot] = y;
81                 map[x][y] = robot;
82             }
83             if(repeat != -1)
84                 ok = false;
85         }
86         if(ok)
87             cout << "OK" << endl;
88     }
89     
90     return 0;
91 }
92 

posted @ 2008-05-26 10:41 superman 阅读(243) | 评论 (0)编辑 收藏

 1 /* Accepted 1016 C++ 00:00.00 832K */
 2 #include <cstdio>
 3 #include <string>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int n;
11     cin >> n;
12     while(cin >> n)
13     {
14         string seq;
15         
16         int p[100= {0};
17         for(int i = 1; i <= n; i++)
18         {
19             cin >> p[i];
20             for(int j = 1; j <= p[i] - p[i - 1]; j++)
21                 seq += '(';
22             seq += ')';
23         }
24         bool x[100= {0};
25         for(int i = 0; i < seq.size(); i++)
26             if(seq[i] == ')')
27             {
28                 int count = 0;
29                 for(int j = i - 1; j >= 0 ; j--)
30                     if(seq[j] == '(')
31                     {
32                         count++;
33                         if(x[j] == 0)
34                         {
35                             cout << count << (i == seq.size()- 1 ? '\n' : ' ');
36                             x[j] = 1;
37                             break;
38                         }
39                     }
40             }
41     }
42     
43     return 0;
44 }
45 

posted @ 2008-05-25 17:41 superman 阅读(491) | 评论 (0)编辑 收藏

 1 /* Accepted 6888K 3141MS G++ 1416B */
 2 #include <math.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int n, m;
 8 int A[50000];
 9 int MIN[50000][16];
10 int MAX[50000][16];
11 
12 void init()
13 {
14     for(int i = 0; i < n; i++)
15         MIN[i][0= MAX[i][0= A[i];
16     for(int j = 11 << j <= n; j++)
17         for(int i = 0; i + (1 << j) - 1 < n; i++)
18         {
19             if(MIN[i][j - 1< MIN[i + (1 << (j - 1))][j - 1])
20                 MIN[i][j] = MIN[i][j - 1];
21             else
22                 MIN[i][j] = MIN[i + (1 << (j - 1))][j - 1];
23             
24             if(MAX[i][j - 1> MAX[i + (1 << (j - 1))][j - 1])
25                 MAX[i][j] = MAX[i][j - 1];
26             else
27                 MAX[i][j] = MAX[i + (1 << (j - 1))][j - 1];
28         }
29 }
30 
31 int main()
32 {
33     scanf("%d %d"&n, &m);
34     for(int i = 0; i < n; i++)
35         scanf("%d"&A[i]);
36     
37     //ST algorithm
38     init();
39     
40     //deal with query
41     int s, t;
42     while(m--)
43     {
44         scanf("%d %d"&s, &t);
45         s--, t--;
46         
47         int a, b, k = int(log(t - s + 1/ log(2));
48         
49         if(MIN[s][k] < MIN[t - (1 << k) + 1][k])
50             a = MIN[s][k];
51         else
52             a = MIN[t - (1 << k) + 1][k];
53         
54         if(MAX[s][k] > MAX[t - (1 << k) + 1][k])
55             b = MAX[s][k];
56         else
57             b = MAX[t - (1 << k) + 1][k];
58         
59         cout << b - a << endl;
60     }
61     
62     return 0;
63 }
64 

posted @ 2008-05-25 16:07 superman 阅读(334) | 评论 (0)编辑 收藏

 1 /* Accepted 708K 907MS G++ 1904B */
 2 #include <stack>
 3 #include <queue>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 struct
 9 {
10     unsigned short LastState;
11     char op;
12 }state[65536];
13 
14 int main()
15 {
16     unsigned short InitState = 0;
17     for(int i = 0; i < 16; )
18         switch(getchar())
19         {
20             case '+' : InitState |= (1 << i); i++continue
21             case '-' : i++continue
22         }
23     
24     for(int i = 0; i < 65536; i++)
25         state[i].op = -1;
26     state[InitState].op = -2;
27     
28     queue <unsigned short> q;
29     q.push(InitState);
30     
31     while(q.empty() == false)
32     {
33         unsigned short CurState = q.front(); q.pop();
34         
35         if(state[0].op != -1)
36             break;
37         
38         for(int i = 0; i < 16; i++)
39         {
40             unsigned short tmp = CurState;
41             tmp = tmp ^ (1 << i);
42             
43             int p;
44             
45             p = i - 4;
46             while(p >= 0) { tmp = tmp ^ (1 << p); p -= 4; }
47             
48             p = i + 4;
49             while(p < 16) { tmp = tmp ^ (1 << p); p += 4; }
50             
51             p = i / 4 * 4;
52             while(p < i) { tmp = tmp ^ (1 << p); p++; }
53             
54             p = (i / 4 + 1* 4 - 1;
55             while(p > i) { tmp = tmp ^ (1 << p); p--; }
56             
57             if(state[tmp].op == -1)
58             {
59                 state[tmp].LastState = CurState;
60                 state[tmp].op = i;
61                 q.push(tmp);
62             }
63         }
64     }
65     
66     int p = 0;
67     stack <int> path;
68     while(state[p].op != -2)
69     {
70         path.push(state[p].op);
71         p = state[p].LastState;
72     }
73     
74     cout << path.size() << endl;
75     while(path.empty() == false)
76     {
77         int x = path.top() / 4 + 1;
78         int y = path.top() % 4 + 1;
79         cout << x << ' ' << y << endl;
80         path.pop();
81     }
82     
83     return 0;
84 }
85 

posted @ 2008-05-25 11:05 superman 阅读(441) | 评论 (0)编辑 收藏

 1 /* Accepted 1229 C++ 00:00.06 828K */
 2 #include <fstream>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int n, m;
 8 
 9 bool x[50];
10 
11 void search(int i, int pos)
12 {
13     if(pos <= 0 || pos >= n + 1)
14         return;
15     
16     x[pos] = true;
17     search(i + 1, pos + (2 * i - 1));
18     search(i + 1, pos - (2 * i - 1));
19 }
20 
21 int main()
22 {
23     while(cin >> n >> m)
24     {
25         if(n == 0 && m == 0)
26             break;
27         
28         if(n >= 50)    //i also do not know why
29         {
30             cout << "Let me try!" << endl; continue;
31         }
32         
33         memset(x, falsesizeof(x));
34         
35         search(21);
36         
37         if(x[m])
38             cout << "Let me try!" << endl;
39         else
40             cout << "Don't make fun of me!" << endl;
41     }
42     
43     return 0;
44 }
45 

posted @ 2008-05-21 11:08 superman 阅读(382) | 评论 (0)编辑 收藏

仅列出标题
共19页: First 5 6 7 8 9 10 11 12 13 Last