POJ 3824 - Flipper

http://poj.org/problem?id=3824

概要

1 .. n の数字が書かれた n 枚のカードが左から 1 .. n と並べられている． 各カードが表か裏かは入力で与えられる．

このカードに対して n-1 回 right flip か left flip を行う．

right flip は，右端にあるカードを引っくり返してその隣のカードの上に重ねる操作を行う． left flip は左端にあるカードに対して同様の操作を行う．

例えば右端のカードが上から順に A, B, C と重なっており，その隣りのカードが D だったとき，right flip を行うと新たな右端は上から順に C, B, A, D と重なっている．

n-1 回の入力で与えられた操作を行うと最終的に1つの山ができる． この山に対して m 個の「上から i 番目のカードに書かれた数字と，そのカードの表裏」を尋ねるクエリに答える．

制約

解法

愚直にシミュレーションして，最終的な山の状態を求めてからクエリに答える．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N;
 9   for (int T = 1; cin >> N && N != 0; T++) {
10     string line;
11     cin >> line;
12     vector<int> cards(N);
13     for (int i = 0; i < N; i++) {
14       cards[i] = (line[i] == 'U');
15     }
16 
17     cin >> line;
18     vector<int> lp(1, 0), rp(1, N-1);
19     int l = 1, r = N-2;
20     for (int i = 0; i < N-2; i++) {
21       if (line[i] == 'R') {
22         reverse(rp.begin(), rp.end());
23         for (vector<int>::const_iterator it = rp.begin(); it != rp.end(); ++it) {
24           ++cards[*it];
25         }
26         rp.push_back(r);
27         --r;
28       } else {
29         reverse(lp.begin(), lp.end());
30         for (vector<int>::const_iterator it = lp.begin(); it != lp.end(); ++it) {
31           ++cards[*it];
32         }
33         lp.push_back(l);
34         ++l;
35       }
36     }
37     vector<int> pile;
38     if (line[N-2] == 'R') {
39       for (vector<int>::const_reverse_iterator it = rp.rbegin(); it != rp.rend(); ++it) {
40         pile.push_back(*it);
41         ++cards[*it];
42       }
43       for (vector<int>::const_iterator it = lp.begin(); it != lp.end(); ++it) {
44         pile.push_back(*it);
45       }
46     } else {
47       for (vector<int>::const_reverse_iterator it = lp.rbegin(); it != lp.rend(); ++it) {
48         pile.push_back(*it);
49         ++cards[*it];
50       }
51       for (vector<int>::const_iterator it = rp.begin(); it != rp.end(); ++it) {
52         pile.push_back(*it);
53       }
54     }
55 
56     int M;
57     cin >> M;
58     cout << "Pile " << T << endl;
59     while (M--) {
60       int q;
61       cin >> q;
62       cout << "Card " << q << " is a face " << (cards[pile[q-1]] % 2 == 1 ? "up" : "down") << " " << pile[q-1]+1 << "." << endl;
63     }
64   }
65   return 0;
66 }
poj/3824.cc