スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




Network Mess

2007.08.24 22:29  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem G

[解説]


詳細は後日書きたいと思います。

[サンプルプログラム]

001 #include<iostream>
002 #include<vector>
003 #include<queue>
004 #include<algorithm>
005 using namespace std;
006 #define MAX 50
007 #define NMAX 80
008 
009 class Node{
010     public:
011     vector<int> adjList;
012     Node(){}
013     void insert( int i ){ adjList.push_back(i);}
014 };
015 
016 class Network{
017     public:
018     vector<Node> nodes;
019     Network(){}
020     
021     int size(){ return nodes.size(); }
022     void addNode(){ nodes.push_back(Node()); }
023     
024     void connect( int i, int j ){
025         nodes[i].insert(j); nodes[j].insert(i);
026     }
027     
028     void addNewNodes( int target, int diff, int u ){
029         if ( diff == 1 ){
030             connect( target, u );
031         } else {
032             for ( int i = 1; i < diff; i++ ){
033                 addNode();
034                 if ( i == 1 ) connect( target, size()-1 );
035                 else connect( size()-2, size()-1);
036             }
037             connect( size()-1, u );
038         }
039     }
040 };
041 
042 class State{
043     public:
044     int cur, pre, d;
045     State(){}
046     State(int cur, int pre, int d): cur(cur), pre(pre), d(d){}
047 };
048 
049 int N, M[MAX][MAX];
050 Network network;
051 
052 int getDistance(int s, int t){
053     queue<State> Q;
054     Q.push(State(s, -1, 0));
055     State u;
056     while( !Q.empty() ){
057         u = Q.front(); Q.pop();
058         if ( u.cur == t ) return u.d;
059         for ( int i = 0; i < network.nodes[u.cur].adjList.size(); i++ ){
060             int v = network.nodes[u.cur].adjList[i];
061             if ( v != u.pre ){
062                 Q.push(State(v, u.cur, u.d + 1));
063             }
064         }
065     }
066 }
067 
068 int parse( int source, int end ){
069     int pre = M[end+1][0] - getDistance( source, 0 );
070     int d;
071     for ( int t = 1; t <= end; t++ ){
072         d = M[end+1][t] - getDistance( source, t );
073         if ( pre != d ) return -1;
074     }
075     return pre;
076 }
077 
078 void addNewNode( int u ){
079     for ( int target = N; target < network.size(); target++ ){
080         int diff = parse(target, u - 1);
081         if ( diff > 0 ) {
082             network.addNewNodes(target, diff, u);
083             return;
084         }
085     }
086 }
087 
088 void compute(){
089     network = Network();
090     for ( int i = 0; i < N + 1; i++ ) network.addNode();
091     network.connect( 0, network.size()-1);
092     
093     for ( int i = 1; i < N; i++ ) addNewNode(i);
094     
095     vector<int> degree;
096     for ( int i = N; i < network.size(); i++ ) {
097         degree.push_back(network.nodes[i].adjList.size());
098     }
099     sort(degree.begin(), degree.end());
100     
101     for ( int i = 0; i < degree.size(); i++ ){
102         if ( i ) cout << " ";
103         cout << degree[i];
104     }
105     cout << endl;
106 }
107 
108 bool input(){
109     cin >> N;
110     if ( N == 0 ) return false;
111     for ( int i = 0; i < N; i++ ){
112         for ( int j = 0; j < N; j++ ) cin >> M[i][j];
113     }
114     return true;
115 }
116 
117 main(){
118     while ( input() ) compute();
119 }
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Atomic Car Race

2007.08.24 22:27  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem F

[解説]

DAG (Directed Acyclic Graph)上の最短経路問題。動的計画法
詳細は後日書きたいと思います。

[サンプルプログラム]

001 #include<iostream>
002 #include<stdio.h>
003 #include<cfloat>
004 #include<algorithm>
005 using namespace std;
006 #define MAX 100
007 #define DMAX 10000
008 
009 int D[MAX+1];
010 double T[DMAX+1];
011 double C[MAX+1];
012 int n, r;
013 double b, v, e, f;
014 
015 double getCost( int x ){
016     if ( x >= r ) return 1/(v - e*(x - r));
017     else return 1/(v - f*(r - x));
018 }
019 
020 void compute(){
021     T[0] = 0.0;
022     for ( int x = 1; x <= D[n]; x++ ){
023         T[x] = T[x-1] + getCost(x - 1);
024     }
025     
026     for ( int i = 1; i <= n; i++ ) C[i] = FLT_MAX;
027     C[0] = 0.0;
028     for ( int i = 1; i <= n; i++ ){
029         for ( int j = 0; j < i; j++ ){
030             C[i] = min( C[i], C[j] + T[D[i] - D[j]] + (j == 0 ? 0 : b) );
031         }
032     }
033     printf("%.4lf\n", C[n]);
034 }
035 
036 bool input(){
037     cin >> n;
038     if ( n == 0 ) return false;
039     D[0] = 0;
040     for ( int i = 1; i <= n; i++ ) cin >> D[i];
041     cin >> b >> r >> v >> e >> f;
042     return true;
043 }
044 
045 main(){
046     while ( input() ) compute();
047 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Mobile Computing

2007.08.24 22:26  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem E

[解説]

総当り。
詳細は後日書きたいと思います。

[サンプルプログラム]

001 #include<stdio.h>
002 #include<iostream>
003 #include<vector>
004 #include<algorithm>
005 using namespace std;
006 #define MAX 6
007 #define NON -1
008 #define ROOT 0
009 #define TO_LEAF 0
010 #define TO_NODE 1
011 
012 struct Node{
013     int left, right;
014     double weight;
015 };
016 
017 class Tree{
018     public:
019     Node nodes[MAX*2];
020     int size;
021     vector<int> leaves, internals;
022     
023     Tree(){
024         for ( int i = 0; i < MAX*2; i++ ){
025             nodes[i].left = nodes[i].right = NON;
026             nodes[i].weight = 0.0;
027         }
028     }
029     
030     double getWidth(){
031         double maxx, minx;
032         maxx = minx = 0.0;
033         parse(0, 0.0, maxx, minx);
034         return maxx - minx;
035     }
036     
037     void parse(int u, double x, double &maxx, double &minx){
038         maxx = max( maxx, x );
039         minx = min( minx, x );
040         double n, m;
041         int left = nodes[u].left;
042         int right = nodes[u].right;
043         if ( left == NON ) return;
044         n = nodes[left].weight;
045         m = nodes[right].weight;
046         parse(left, x - m/(n+m), maxx, minx);
047         parse(right, x + n/(n+m), maxx, minx);
048     }
049     
050     double getWeight(int u){
051         if ( nodes[u].left == NON ) return nodes[u].weight;
052         nodes[u].weight = getWeight(nodes[u].left) + getWeight(nodes[u].right);
053         return nodes[u].weight;
054     }
055 };
056 
057 double R;
058 int stones[MAX];
059 int nstone;
060 
061 double maxv;
062 
063 void check(Tree u){
064     sort( stones, stones + nstone );
065     do {
066         for ( int i = 0; i < nstone; i++ ){
067             u.nodes[u.leaves[i]].weight = stones[i];
068         }
069         u.getWeight(ROOT);
070         double width = u.getWidth();
071         if ( width < R ) maxv = max( maxv, width );
072     } while ( next_permutation( stones, stones + nstone )) ;
073 }
074 
075 void makeTree(Tree u){
076     if ( u.leaves.size() == nstone && u.internals.size() == 0 ) check(u);
077     if ( u.leaves.size() + u.internals.size()*2 > nstone ) return;
078     
079     Tree v;
080     
081     for ( int i = 0; i < u.internals.size(); i++ ){
082         int parent = u.internals[i];
083         for ( int a = 0; a < 2; a++ ){
084             for ( int b = 0; b < 2; b++ ){
085                 v = u;
086                 v.nodes[parent].left = v.size++;
087                 v.nodes[parent].right = v.size++;
088                 if ( a == TO_LEAF ) v.leaves.push_back(v.size-2);
089                 else v.internals.push_back(v.size-2);
090                 if ( b == TO_LEAF ) v.leaves.push_back(v.size-1);
091                 else v.internals.push_back(v.size-1);
092                 v.internals.erase( v.internals.begin() + i );
093                 makeTree(v);
094             }
095         }
096     }
097 }
098 
099 void compute(){
100     if ( nstone == 1 ) {
101         printf("%.9lf\n", 0.0); return;
102     }
103     Tree root = Tree();
104     root.internals.push_back(ROOT);
105     root.size = 1;
106     maxv = -1;
107     makeTree(root);
108     if ( maxv < 0.0 ) cout << "-1" << endl;
109     else printf("%.9lf\n", maxv);
110 }
111 
112 void input(){
113     cin >> R >> nstone;
114     for ( int i = 0; i < nstone; i++ ) cin >> stones[i];
115 }
116 
117 main(){
118     int tcase; cin >> tcase;
119     for ( int i = 0; i < tcase; i++ ){
120         input();
121         compute();
122     }
123 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Organize Your Train

2007.08.24 22:24  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem D

[解説]

両側幅優先探索。
詳細は後日書きたいと思います。

[サンプルプログラム]

001 #include<iostream>
002 #include<string>
003 #include<queue>
004 #include<map>
005 #define MAX 4
006 #define LIMIT 6
007 #define FORWARD 0
008 #define BACK 1
009 #define WEST 0
010 #define EAST 1
011 #define BUFFER 40
012 
013 using namespace std;
014 
015 class Load{
016     public:
017     char buffer[BUFFER];
018     int head, tail, size;
019     Load(){}
020     Load( string str ){
021         head = tail = BUFFER/2;
022         size = 0;
023         for ( int i = 0; i < str.size(); i++ ){
024             buffer[tail++] = str[i];
025             size++;
026         }
027     }
028     
029     void intoW( char ch ){ buffer[--head] = ch; size++; }
030     void intoE( char ch ){ buffer[tail++] = ch; size++; }
031     char fromW(){ char ch = buffer[head]; head++; size--; return ch; }
032     char fromE(){ char ch = buffer[tail-1]; tail--; size--; return ch; }
033     
034     bool operator < ( const Load &l ) const {
035         if ( size != l.size ) return size < l.size;
036         for ( int i = head, j = l.head; i < tail; i++, j++ ){
037             if ( buffer[i] == l.buffer[j] ) continue;
038             return buffer[i] < l.buffer[j];
039         }
040         return false;
041     }
042     
043     bool operator == ( const Load &l ) const {
044         if ( size != l.size ) return false;
045         for ( int i = head, j = l.head; i < tail; i++, j++ ){
046             if ( buffer[i] != l.buffer[j] ) return false;
047         }
048         return true;
049     }
050     
051     bool operator != ( const Load &l ) const {
052         if ( size != l.size ) return true;
053         for ( int i = head, j = l.head; i < tail; i++, j++ ){
054             if ( buffer[i] != l.buffer[j] ) return true;
055         }
056         return false;
057     }
058 };
059 
060 class Station{
061     public:
062     int nload;
063     Load loads[MAX];
064     int id;
065     
066     Station(){}
067     Station( int nload): nload(nload){}
068     
069     bool operator < ( const Station &s ) const {
070         for ( int i = 0; i < nload; i++ ){
071             if ( loads[i] == s.loads[i] ) continue;
072             return loads[i] < s.loads[i];
073         }
074         return false;
075     }
076     
077     bool operator == ( const Station &s ) const {
078         for ( int i = 0; i < nload; i++ ){
079             if ( loads[i] != s.loads[i] ) return false;
080         }
081         return true;
082     }
083 };
084 
085 
086 Station initial, goal;
087 int nload;
088 bool M[MAX][2][MAX][2];
089 
090 map<Station, int> BS;
091 map<Station, int> FS;
092 
093 Station getNext(Station v, int d, int s, int sd, int t, int td){
094     int nd;
095     
096     if ( sd == WEST ){
097         if ( td == WEST ){
098             for ( int i = 0; i < d; i++  ){
099                 v.loads[t].intoW(v.loads[s].fromW());
100             }
101         } else {
102             for ( int i = 0; i < d; i++  ){
103                 v.loads[t].intoE(v.loads[s].fromW());
104             }
105         }
106     } else {
107         if ( td == WEST ){
108             nd = v.loads[s].size - d;
109             for ( int i = 0; i < nd; i++ ){
110                 v.loads[t].intoW(v.loads[s].fromE());
111             }
112         } else {
113             nd = v.loads[s].size - d;
114             for ( int i = 0; i < nd; i++ ){
115                 v.loads[t].intoE(v.loads[s].fromE());
116             }
117         }
118     }
119     
120     return v;
121 }
122 
123 int bfs( Station source, map<Station, int> &D, int mode ){
124     queue<Station> Q;
125     Q.push(source);
126     D[source] = 0;
127     
128     Station u, v;
129     
130     if ( mode == FORWARD && BS.find(source) != BS.end() ) return BS[source];
131     
132     while(!Q.empty()){
133         u = Q.front(); Q.pop();
134         int dist = D[u];
135         
136         if ( mode == BACK && dist >= 3 ) return 0;
137         
138         for ( int s = 0; s < nload; s++ ){
139             for ( int d = 0; d < u.loads[s].size; d++ ){
140                 for ( int t = 0; t < nload; t++ ){
141                     for ( int sd = 0; sd < 2; sd++ ){
142                         for ( int td = 0; td < 2; td++ ){
143                             if ( M[s][sd][t][td] ){
144                                 v = getNext(u, d, s, sd, t, td );
145                                 if ( D.find(v) == D.end() ){
146                                     D[v] = dist + 1;
147                                     if ( mode == FORWARD ){
148                                         if ( BS.find(v) != BS.end() ) {
149                                             return BS[v] + dist + 1;
150                                         }
151                                     }
152                                     Q.push(v);
153                                 }
154                             }
155                         }
156                     }
157                 }
158             }
159         }
160     }
161     return -1;
162 }
163 
164 void compute(){
165     BS = map<Station, int>();
166     FS = map<Station, int>();
167     bfs(goal, BS, BACK);
168     cout << bfs(initial, FS, FORWARD) << endl;
169 }
170 
171 bool input(){
172     int y;
173     cin >> nload >> y;
174     if ( nload == 0 && y == 0 ) return false;
175     
176     for ( int i = 0; i < nload; i++ ){
177         for ( int j = 0; j < nload; j++ ){
178             M[i][WEST][j][WEST] = false;
179             M[i][WEST][j][EAST] = false;
180             M[i][EAST][j][WEST] = false;
181             M[i][EAST][j][EAST] = false;
182         }
183     }
184     int sl, tl;
185     char sd, td;
186     for ( int i = 0; i < y; i++ ){
187         cin >> sl >> sd >> tl >> td;
188         M[sl][(sd == 'W' ? WEST : EAST)][tl][(td == 'W' ? WEST : EAST)] = true;
189         M[tl][(td == 'W' ? WEST : EAST)][sl][(sd == 'W' ? WEST : EAST)] = true;
190     }
191     
192     initial = Station(nload);
193     goal = Station(nload);
194     
195     string train;
196     for ( int i = 0; i < nload; i++ ) {
197         cin >> train; if ( train == "-" ) train = "";
198         initial.loads[i] = Load(train);
199     }
200     for ( int i = 0; i < nload; i++ ) {
201         cin >> train; if ( train == "-" ) train = "";
202         goal.loads[i] = Load(train);
203     }
204     
205     return true;
206 }
207 
208 main(){
209     while( input() ) compute();
210 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Colored Cubes

2007.08.24 22:22  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem C

[解説]

総当り。
詳細は後日付け足したいと思います。

[サンプルプログラム]

001 #include<iostream>
002 #include<string>
003 #include<map>
004 using namespace std;
005 
006 int RT[24][6] = {
007     {0, 1, 2, 3, 4, 5},
008     {0, 2, 4, 1, 3, 5},
009     {0, 4, 3, 2, 1, 5},
010     {0, 3, 1, 4, 2, 5},
011     {3, 1, 0, 5, 4, 2},
012     {3, 0, 4, 1, 5, 2},
013     {3, 4, 5, 0, 1, 2},
014     {3, 5, 1, 4, 0, 2},
015     {5, 1, 3, 2, 4, 0},
016     {5, 3, 4, 1, 2, 0},
017     {5, 4, 2, 3, 1, 0},
018     {5, 2, 1, 4, 3, 0},
019     {2, 1, 5, 0, 4, 3},
020     {2, 5, 4, 1, 0, 3},
021     {2, 4, 0, 5, 1, 3},
022     {2, 0, 1, 4, 5, 3},
023     {4, 0, 2, 3, 5, 1},
024     {4, 2, 5, 0, 3, 1},
025     {4, 5, 3, 2, 0, 1},
026     {4, 3, 0, 5, 2, 1},
027     {1, 0, 3, 2, 5, 4},
028     {1, 3, 5, 0, 2, 4},
029     {1, 5, 2, 3, 0, 4},
030     {1, 2, 0, 5, 3, 4}
031 };
032 
033 class Cube{
034     public:
035     int faces[6];
036     Cube(){}
037 };
038 
039 int n;
040 Cube cubes[4];
041 Cube buffer[4];
042 int mincost;
043 
044 map<string, int> CT; //color table;
045 int colorID;
046 
047 int check(){
048     int T[25];
049     int diff = 0;
050     for ( int f = 0; f < 6; f++ ){
051         for ( int i = 0; i < 25; i++ ) T[i] = 0;
052         
053         for ( int i = 0; i < n; i++ ){
054             T[buffer[i].faces[f]]++;
055         }
056         
057         int maxv = 0;
058         int maxc;
059         for ( int i = 0; i < 25; i++ ){
060             if ( maxv < T[i] ){
061                 maxv = T[i];
062                 maxc = i;
063             }
064         }
065         
066         for ( int i = 0; i < n; i++ ){
067             if ( buffer[i].faces[f] != maxc ) diff++;
068         }
069     }
070     return diff;
071 }
072 
073 void recursive( int pos ){
074     if ( pos == n ){
075         mincost = min( mincost, check() );
076         return;
077     }
078     
079     Cube tmp = buffer[pos];
080     for ( int i = 0; i < 24; i++ ){
081         for ( int f = 0; f < 6; f++ ){
082             buffer[pos].faces[f] = cubes[pos].faces[RT[i][f]];
083         }
084         recursive( pos+1 );
085     }
086 }
087 
088 int compute(){
089     buffer[0] = cubes[0];
090     mincost = 24;
091     recursive(1);
092     return mincost;
093 }
094 
095 int getColor(string color){
096     if ( CT.find(color) == CT.end() ) CT[color] = colorID++;
097     return CT[color];
098 }
099 
100 bool initialize(){
101     cin >> n;
102     if ( n == 0 ) return false;
103     CT = map<string, int>();
104     colorID = 0;
105     string color;
106     for ( int i = 0; i < n; i++ ){
107         for ( int j = 0; j < 6; j++ ){
108             cin >> color;
109             cubes[i].faces[j] = getColor(color);
110         }
111     }
112     return true;
113 }
114 
115 main(){
116     while( initialize() ) cout << compute() << endl;
117 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Book Replacement

2007.08.24 22:21  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem B

[解説]

シミュレーション。

[サンプルプログラム]

001 #include<iostream>
002 #include<queue>
003 #include<vector>
004 using namespace std;
005 
006 class Student{
007     public:
008     queue<int> requests;
009     Student(){}
010     
011     int getRequest(){
012         int r = requests.front(); requests.pop();
013         return r;
014     }
015 };
016 
017 class Storeroom{
018     public:
019     int capacity, ndesk;
020     vector<vector<int> > buffer;
021     
022     Storeroom(){}
023     Storeroom(int d, int c): ndesk(d), capacity(c){
024         buffer.resize(d+1);
025         for ( int i = 1; i <= 100; i++ ){
026             buffer[d].push_back(i);
027         }
028     }
029     
030     int take( int requested, int &cost ){
031         for ( int d = 0; d <= ndesk; d++ ){
032             for ( int i = 0; i < buffer[d].size(); i++ ){
033                 if ( buffer[d][i] == requested ){
034                     cost += (d+1);
035                     int book = buffer[d][i];
036                     buffer[d].erase( buffer[d].begin() + i );
037                     return book;
038                 }
039             }
040         }
041     }
042     
043     bool isFull(int d){
044         return buffer[d].size() >= capacity;
045     }
046     
047     void put(int d, int book, int &cost){
048         buffer[d].push_back(book);
049         cost += (d+1);
050     }
051     
052     int getNonFullDesk(){
053         for ( int d = 1; d < ndesk; d++ ){
054             if ( buffer[d].size() < capacity ) return d;
055         }
056         return ndesk;
057     }
058     
059     int takePassive(int &cost){
060         int tmp = buffer[0][0];
061         buffer[0].erase( buffer[0].begin() + 0 );
062         cost++;
063         return tmp;
064     }
065 };
066 
067 queue<Student> students;
068 Storeroom storeroom;
069 
070 int simulate(){
071     int cost = 0;
072     Student st;
073     int requested, desk, target;
074     
075     while( !students.empty() ){
076         st = students.front(); students.pop();
077         requested = st.getRequest();
078         
079         target = storeroom.take(requested, cost);
080         
081         if ( !storeroom.isFull(0) ) {
082             storeroom.put(0, target, cost);
083         } else {
084             desk = storeroom.getNonFullDesk();
085             storeroom.put(desk, target, cost);
086             
087             target = storeroom.takePassive(cost);
088             desk = storeroom.getNonFullDesk();
089             storeroom.put(desk, target, cost);
090             
091             target = storeroom.take(requested, cost);
092             storeroom.put(0, target, cost);
093         }
094         
095         if ( st.requests.size() ) students.push(st);
096     }
097     
098     return cost;
099 }
100 
101 bool input(){
102     int m, c, n, k;
103     cin >> m >> c >> n;
104     if ( m == 0 && c == 0 && n == 0 ) return false;
105     storeroom = Storeroom( m, c );
106     students = queue<Student>();
107     
108     for ( int i = 0; i < n; i++ ){
109         cin >> k;
110         Student st;
111         for ( int j = 0; j < k; j++ ){
112             int id; cin >> id;
113             st.requests.push(id);
114         }
115         students.push(st);
116     }
117     
118     return true;
119 }
120 
121 main(){
122     while(input()) cout << simulate() << endl;
123 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Sum of Consecutive Prime Numbers

2007.08.24 22:20  ACM/ICPC 2005

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem A

[解説]

エラトステネスの篩+2重ループ。

[サンプルプログラム]

001 #include<iostream>
002 #include<cmath>
003 using namespace std;
004 #define MAX 10000
005 #define PMAX 1229
006 bool prime[MAX+1]; // prime number table

007 int T[MAX+1];
008 
009 void eratos(int n){
010     fill(prime, prime+MAX, false);
011     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
012     prime[2] = true;
013     for ( int i = 3; i*i <= n; i += 2 ) {
014         if ( !prime[i] ) continue;
015         for ( int j = i * i, k = i * 2; j <= n; j += k ) prime[j] = false;
016     }
017 }
018 
019 void initialize(){
020     eratos(MAX);
021     int plist[1229];
022     int size = 0;
023     for ( int i = 2; i <= MAX; i++ ){
024         if  ( prime[i] ) plist[size++] = i;
025     }
026     for ( int i = 0; i <= MAX; i++ ) T[i] = 0;
027     
028     for ( int i = 0; i < size; i++ ){
029         int sum = 0;
030         for ( int j = i; j < size; j++ ){
031             sum += plist[j];
032             if ( sum >= MAX ) continue;
033             T[sum]++;
034         }
035     }
036 }
037 
038 main(){
039     initialize();
040     int n;
041     while(1){
042         cin >> n;
043         if ( n == 0 ) break;
044         cout << T[n] << endl;
045     }
046 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 2005 Tokyo

2007.08.24 22:16  ACM/ICPC 2005

ID 問題 難易度 考察
A Sum of Consecutive Prime Numbers -
B Book Replacement ★★☆ -
C Colored Cubes ★★☆ -
D Organize Your Train ★★★★ -
E Mobile Computing ★★★ -
F Atomic Car Race ★★☆ -
G Network Mess ★★★☆ -
H Bingo ★★★★☆ -
I Shy Polygons ★★★★★ grave

| コメント(0) | トラックバック(0) | ↑ページトップ |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。