#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

const int MAXN = 30;
int n;
vector<int> pile[MAXN];

// 找木块a所在的pile和height，以引用的形式返回调用者
void find_block(int a, int& p, int& h) {
    for (p = 0; p < n; p++) {
        for (h = 0; h < pile[p].size(); h++) {
            if (pile[p][h] == a) {
                return;
            }
        }
    }
}

// 把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p, int h) {
    for (int i = h + 1; i < pile[p].size(); i++) {
        int b = pile[p][i];
        pile[b].push_back(b);
    }
    pile[p].resize(h + 1);
}

// 把第p堆高度h及其上方的木块整体移动到p2堆的顶部
void pile_onto(int p, int h, int p2) {
    for (int i = h; i < pile[p].size(); i++) {
        pile[p2].push_back(pile[p][i]);
    }
    pile[p].resize(h);
}

void print() {
    for (int i = 0; i < n; i++) {
        printf("%d:", i);
        for (int j = 0; j < pile[i].size(); j++) {
            printf(" %d", pile[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int a, b;
    cin >> n;
    string s1, s2;
    for (int i = 0; i < n; i++) {
        pile[i].push_back(i);
    }
    while (cin >> s1 >> a >> s2 >> b) {
        int pa, pb, ha, hb;
        find_block(a, pa, ha);
        find_block(b, pb, hb);
        if (pa == pb) {
            continue;
        }
        if (s2 == "onto") {
            clear_above(pb, hb);
        }
        if (s1 == "move") {
            clear_above(pa, ha);
        }
        pile_onto(pa, ha, pb);
    }
    print();

    return 0;
}

#include<iostream>
#include<string>
#include<set>
#include<sstream>
using namespace std;

set<string> dict;
string s, buf;

int main() {
    while (cin >> s) {
        for (int i = 0; i < s.length(); i++) {
            if (isalpha(s[i])) {
                s[i] = tolower(s[i]);
            } else {
                s[i] = ' ';
            }
        }
        stringstream ss(s);
        while (ss >> buf) {
            dict.insert(buf);
        }
    }
    for (set<string>::iterator it = dict.begin(); it != dict.end(); it++) {
        cout << *it << "\n";
    }

    return 0;
}

#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

map<string, int> cnt;
vector<string> words;

string repr(string s) {
    string res = s;
    for (int i = 0; i < res.length(); i++) {
        res[i] = tolower(res[i]);
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int n = 0;
    string s;
    while (cin >> s) {
        if (s[0] == '#') {
            break;
        }
        words.push_back(s);
        string res = repr(s);
        if (!cnt.count(res)) {
            cnt[res] = 0;
        }
        cnt[res]++;
    }
    vector<string> res;
    for (int i = 0; i < words.size(); i++) {
        if (cnt[repr(words[i])] == 1) {
            res.push_back(words[i]);
        }
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << "\n";
    }

    return 0;
}

#include<iostream>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

typedef set<int> Set;
map<Set,int> IDcache; // 把集合映射成ID
vector<Set> Setcache; // 根据ID取集合

// 查找给定集合x的ID。如果找不到，分配一个新ID
int ID (Set x) {
  if (IDcache.count(x)) return IDcache[x];
  Setcache.push_back(x); // 添加新集合
  return IDcache[x] = Setcache.size() - 1;
}

int main () {
  int T;
  cin >> T;
  while(T--) {
    stack<int> s; // 题目中的栈
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
      string op;
      cin >> op;
      if (op[0] == 'P') s.push(ID(Set()));
      else if (op[0] == 'D') s.push(s.top());
      else {
        Set x1 = Setcache[s.top()]; s.pop();
        Set x2 = Setcache[s.top()]; s.pop();
        Set x;
        if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));
        if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));
        if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }
        s.push(ID(x));
      }      
      cout << Setcache[s.top()].size() << endl;
    }
    cout << "***" << endl;
  }
  return 0;  
}

2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

#include <cstdio>
#include <map>
#include <queue>
using namespace std;

const int MAXT = 1000 + 10;

int main () {
    int t, kase = 1;
    while (scanf("%d", &t) == 1 && t) {
        printf("Scenario #%d\n", kase++);

        map<int, int> team;
        for (int i = 0; i < t; i++) {
            int n, x;
            scanf("%d", &n);
            while (n--) { scanf("%d", &x); team[x] = i; }
        }

        queue<int> q, q2[MAXT];
        for ( ; ; ) {
            int x;
            char cmd[10];
            scanf("%s", cmd);
            if (cmd[0] == 'S') { break; }
            else if (cmd[0] == 'E') {
                scanf("%d", &x);
                int t = team[x];
                if (q2[t].empty()) q.push(t);
                q2[t].push(x);
            }
            else if (cmd[0] == 'D') {
                int t = q.front();
                printf("%d\n", q2[t].front());
                q2[t].pop();
                if (q2[t].empty()) q.pop();
            }
        }
        printf("\n");
    }

    return 0;
}

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int MAXCOL = 60;
const int MAXN = 100 + 5;
string filenames[MAXN];

void print(const string& s, int len, char extra) {
    cout << s;
    for (int i = 0; i < len - s.length(); i++) {
        cout << extra;
    }
}

int main() {
    int n;
    while (cin >> n) {
        int M = 0;
        for (int i = 0; i < n; i++) {
            cin >> filenames[i];
            M = max(M, (int)filenames[i].length());
        }
        // 计算列数cols和行数rows
        int cols = (MAXCOL - M) / (M + 2) + 1;
        // (M+2)(M+2)......M，几个(M+2）加一
        int rows = (n - 1) / cols + 1;
        // 如果clos为3，n为12，那么结果为5，但其实只要4行就可以
        // (n - 1) / cols 避免行列填满的情况导致结果多1
        // +1是为了不够clos的部分也得给他们留一行
        print("", 60, '-');
        cout << "\n";
        sort(filenames, filenames + n);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int idx = c * rows + r;
                // 只能一行一行来，因为每一行需要一个回车
                // 从0行开始，0行0列，0行1列，0行2列，所以一开始r是0
                if (idx < n) print(filenames[idx], c == cols - 1 ? M : M + 2, ' ');
            }
            cout << "\n";
        }
    }

    return 0;
}

// UVa1592 Database
// Rujia Liu
// 本程序只是为了演示STL各种用法，效率较低。实践中一般用C字符串和哈希表来实现。




using namespace std;

typedef pair<int,int> PII;

const int maxr = 10000 + 5;
const int maxc = 10 + 5;

int m, n, db[maxr][maxc], cnt;

map<string, int> id;
int ID(const string& s) {
  if(!id.count(s)) {
    id[s] = ++cnt;
  }
  return id[s];
}

void find() {
  for(int c1 = 0; c1 < m; c1++)
    for(int c2 = c1+1; c2 < m; c2++) {
      map<PII, int> d;
      for(int i = 0; i < n; i++) {
        PII p = make_pair(db[i][c1], db[i][c2]);
        if(d.count(p)) {
          printf("NO\n");
          printf("%d %d\n", d[p]+1, i+1);
          printf("%d %d\n", c1+1, c2+1);
          return;
        }
        d[p] = i;
      }
    }
  printf("YES\n");
}


int main() {
  string s;
  while(getline(cin, s)) {
    stringstream ss(s);
    if(!(ss >> n >> m)) break;
    cnt = 0;
    id.clear();
    for(int i = 0; i < n; i++) {
      getline(cin, s);
      int lastpos = -1;
      for(int j = 0; j < m; j++) {
        int p = s.find(',', lastpos+1);
        if(p == string::npos) p = s.length();
        db[i][j] = ID(s.substr(lastpos+1, p - lastpos - 1));
        lastpos = p;
      }
    }
    find();
  }
  return 0;
}

// 计算两点之间的欧几里德的距离
double dist(double x1, double x2, double y1, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double dist_1(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return hypot(dx, dy);
}

struct Point {
    double x, y;
};

double dist_2(struct Point a, struct Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}

typedef struct {
    double x, y;
}Point_;

double dist_3(Point_ a, Point_ b) {
    return hypot(a.x - b.x, a.y - b.y);
}

// 4.1 组合数（有BUG，中间变量可能会溢出）
long long factorial(int n) {
    long long m = 1;
    for (int i = 1; i <= n; i++) {
        m *= i;
    }
    return m;
}

long long C(int n, int m) {
    return factorial(n) / (factorial(m) * factorial(n - m));
}

// 4.1 组合数
long long C(int n, int m) {
    if (m < n - m) m = n - m;
    long long ans = 1;
    for (int i = m + 1; i <= n; i++) ans *= i;
    for (int i = 1; i <= n - m; i++) ans /= i;
    return ans;
}

// 4.2 素数判定 （有问题）
int is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

// 4.2 素数判定
int is_prime_1(int n) {
    if (n <= 1) return 0;
    int m = floor(sqrt(n) + 0.5);
    for (int i = 2; i <= m, i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

// 4.3 用函数交换变量（错误）
void swap(int a, int b) {
    int t = a; a = b; b = t;
}

    int a, b;
    a = 3; b = 4;
    swap(3, 4);
    printf("a: %d b: %d\n", a, b);

// 4.3 用函数交换变量
void swap(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

    int a =3, b = 4;
    swap(&a, &b);
    printf("a = %d, b = %d\n", a, b);

a = 4, b = 3

// 计算数组的元素和（错误，PS：C++中是可行的，亲测）
int sum(int a[]) {
    int ans = 0;
    for (int i = 0; i < sizeof(a); i++) {
        ans += a[i];
    }
    return ans;
}

    int a[] = {1,2,3};
    printf("%d\n", sum(a));
    
6(C++测得)

#include <stdio.h>

int sum(int a[]) {
    int ans = 0;
    for (int i = 0; i < sizeof(a); i++) {
        ans += a[i];
    }
    return ans;
}

int main() {
    int a[] = {1,2,3};
    printf("%d\n", sum(a));
    return 0;
}

D:\Markdown\Coding\C\Exercises\main.c: In function 'sum':
D:\Markdown\Coding\C\Exercises\main.c:5:31: warning: 'sizeof' on array function parameter 'a' will return size of 'int *' [-Wsizeof-array-argument]
     for (int i = 0; i < sizeof(a); i++) {
                               ^
D:\Markdown\Coding\C\Exercises\main.c:3:13: note: declared here
 int sum(int a[]) {

#include <stdio.h>

int sum(int* a, int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    return ans;
}

int main() {
    int a[] = {1,2,3};
    printf("%d\n", sum(a + 1, 2));
    return 0;
}

5

// 计算数组的元素和（正确）
int sum(int* a, int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    return ans;
}

    int a[] = {1,2,3};
    printf("%d\n", sum(a + 1, 2));
    return 0;

5

// 计算左闭右开区间的元素和（两种写法）
// 方法一
int sum(int* begin, int* end) {
    int n = end - begin;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += begin[i];
    }
    return ans;
}

// 方法二
int sum(int* begin, int* end) {
    int *p = begin;
    int ans = 0;
    for (int *p = begin; p != end; p++) {
        ans += *p;
    }
    return ans;
}

// 用递归计算阶乘
int f(int n){
    return n == 0 ? 1 : f(n - 1) * n;
};

int main() {
  char s1[200], s2[200];
  while(scanf("%s%s", s1, s2) == 2) {
    int n = strlen(s1);
    int cnt1[26] = {0}, cnt2[26] = {0};
    for(int i = 0; i < n; i++) cnt1[s1[i] - 'A']++;
    for(int i = 0; i < n; i++) cnt2[s2[i] - 'A']++;
    sort(cnt1, cnt1 + 26);
    sort(cnt2, cnt2 + 26);
    int ok = 1;
    for(int i = 0; i < 26; i++)
      if(cnt1[i] != cnt2[i]) ok = 0;
    if(ok) printf("YES\n"); else printf("NO\n");
  }
  return 0;
}


JWPUDJSTVP
VICTORIOUS

YES

#include <bits/stdc++.h>
using namespace std;

#define maxn 105
int Left, Chance; // 还要猜left个位置，错chance次后就会输
char s[maxn], s1[maxn];
int win, lose;

void guess(char ch) {
    int bad = 1;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == ch) { Left--; s[i] = ' '; bad = 0; }
    }
    if (bad) Chance--;
    if (!Chance) lose = 1;
    if (!Left) win = 1;
}

int main() {
    int rnd;
    while (scanf("%d%s%s", &rnd, s, s1) == 3 && rnd != -1) {
        printf("Round %d\n", rnd);
        win = lose = 0;
        Left = strlen(s);
        Chance = 7;
        for (int i = 0; i < strlen(s1); i++) {
            guess(s1[i]);
            if (win || lose) break;
        }
        if (win) printf("You win.\n");
        else if (lose) printf("You lose.\n");
        else printf("You chickened out.\n");
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define maxn 25
int n, m, k, cell[maxn];

int go(int p, int d, int t) {
    while (t--) {
        do {
            p = (p + d + n - 1) % n + 1;
        } while (cell[p] == 0);
    }
    return p;
}

int main() {
    while (scanf("%d%d%d", &n, &k, &m) == 3 && n) {
        for (int i = 1; i <= n; i++) cell[i] = i;
        int left = n;
        int p1 = n, p2 = 1;
        while (left) {
            p1 = go(p1, 1, k);
            p2 = go(p2, -1, m);
            printf("%3d", p1); left--;
            if (p2 != p1) { printf("%3d", p2); left--; }
            cell[p1] = cell[p2] = 0;
            if (left) printf(",");
        }
        printf("\n");
    }

    return 0;
}

// UVa213 Message Decoding
// Rujia Liu
// 此版本保留书中展示的调试语句
#include<stdio.h>
#include<string.h>

int readchar() {
  for(;;) {
    int ch = getchar();
    if(ch != '\n' && ch != '\r') return ch;
  }
}

int readint(int c) {
  int v = 0;
  while(c--) v = v * 2 + readchar() - '0';
  return v;
}

int code[8][1<<8];

int readcodes() {
  memset(code, 0, sizeof(code));
  code[1][0] = readchar();
  for(int len = 2; len <= 7; len++) {
    for(int i = 0; i < (1<<len)-1; i++) {
      int ch = getchar();
      if(ch == EOF) return 0;
      if(ch == '\n' || ch == '\r') return 1;
      code[len][i] = ch;
    }
  }
  return 1;
}

// 用于调试
void printcodes() {
  for(int len = 1; len <= 3; len++)
    for(int i = 0; i < (1<<len)-1; i++) {
      if(code[len][i] == 0) return;
      printf("code[%d][%d] = %c\n", len, i, code[len][i]);
    }
}

int main() {
  while(readcodes()) {
//printcodes();
    for(;;) {
      int len = readint(3);
      if(len == 0) break;
//printf("len=%d\n", len);
      for(;;) {
        int v = readint(len);
//printf("v=%d\n", v);
        if(v == (1 << len)-1) break;
        putchar(code[len][v]);
      }
    }
    putchar('\n');
  }
  return 0;
}

// 程序3-1 逆序输出
#define maxn 105
int a[maxn];

    int x, n = 0;
    while (scanf("%d", &x) == 1) {
        a[n++] = x;
    }
    for (int i = n - 1; i >= 1; i--) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[0]);


//测试的时候可以改为这样，方便中断程序
    while (scanf("%d", &x) == 1 && x != -1) 

1 2 3 4 5 6 -1
6 5 4 3 2 1

// 程序3-2 开灯问题
#define maxn 1010
int a[maxn];

    int n, k, first = 1;
    memset(a, 0, sizeof(a));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (j % i == 0) a[j] = !a[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i]) {
            if (first) first = 0;
            else printf(" "); 
            printf("%d", i);
        }
    }
    printf("\n");

7 3
1 5 6 7

10 11 12  1
 9 16 13  2
 8 15 14  3
 7  6  5  4

// 程序3-3 蛇形填数
    int a[20][20];
    int n, x, y, tot = 0;
    scanf("%d", &n);
    memset(a, 0, sizeof(a)); // 数组初始化
    tot = a[x = 0][y = n - 1] = 1;
    while (tot < n * n) {
        while (x + 1< n && !a[x + 1][y]) a[++x][y] = ++tot;
        while (y - 1 >= 0 && !a[x][y - 1]) a[x][--y] = ++tot;
        while (x - 1 >= 0 && !a[x - 1][y]) a[--x][y] = ++tot;
        while (y + 1 < n && !a[x][y + 1]) a[x][++y] = ++tot;
    }
    for (x = 0; x < n; x++) {
        for (y = 0; y < n; y++) 
            printf("%3d", a[x][y]);
        printf("\n"); 
    }

4
 10 11 12  1
  9 16 13  2
  8 15 14  3
  7  6  5  4

// 程序3-4 竖式问题
    int cnt = 0;
    char s[20], buf[99];
    scanf("%s", s);
    for (int abc = 111; abc <= 999; abc++) {
        for (int de = 11; de <= 99; de++) {
            int x = abc * (de % 10), y = abc * (de / 10), z = abc * de;
            sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);
            int ok = 1;
            for (int i = 0; i < strlen(buf); i++) {
                if (strchr(s, buf[i]) == NULL) ok = 0;
            }
            if (ok) {
                printf("<%d>\n", ++cnt);
                printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n", abc, de, x, y, z);
            }
        }
    }
    printf("The number of solution = %d\n", cnt);


2357
<1>
  775
X  33
-----
 2325
2325
-----
25575

The number of solution = 1

char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

int main() {
    int i, c;
    while ((c = getchar()) != EOF) {
        for (i = 1; s[i] && s[i] != c; i++);
        if (s[i]) putchar(s[i - 1]);
        else putchar(c);
    }
}

O S, GOMR YPFSU/
I AM FINE TODAY.

const char* res = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char* msg[] =  {"not a palindrome","a regular palindrome","a mirrored string","a mirrored palindrome"};
char r(char ch) {
    if (isalpha(ch)) return res[ch - 'A'];
    return res[ch - '0' + 25];
}

int main() {
    char s[300];
    while (scanf("%s", s) == 1) {
        int len = strlen(s);
        int p = 1, m = 1;
        for (int i = 0; i < (len + 1 / 2); i++) {
            if (s[i] != s[len - i - 1]) p = 0; // 不是回文串
            if (r(s[i]) != s[len - i - 1]) m = 0; // 不是镜像串
        }
        printf("%s -- is %s.\n\n", s, msg[m * 2 + p]);
    }
}

NOTAPALINDROME
NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI
ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS
2A3MEAS -- is a mirrored string.

ATOYOTA
ATOYOTA -- is a mirrored palindrome.

#define maxn 1010

int main() {
    int n, a[maxn], b[maxn];
    int kase = 0;
    while (scanf("%d", &n) == 1 && n) {
        printf("Game %d:\n", ++kase);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        for (; ;) {
            int A = 0, B = 0;
            for (int i = 0; i < n; i++) {
                scanf("%d", &b[i]);
                if (a[i] == b[i]) A++;
            }
            if (b[0] == 0) break;
            for (int d = 1; d <= 9; d++) {
                int c1 = 0, c2 = 0;
                for (int i = 0; i < n; i++) {
                    if (a[i] == d) c1++;
                    if (b[i] == d) c2++;
                }
                if (c1 < c2) B += c1;
                else         B += c2;
            }
            printf("    (%d,%d)\n", A, B - A);
        }
    }
    return 0;
}

#define maxn 100005
int ans[maxn];

int main() {
    int T, n;
    memset(ans, 0, sizeof(ans));
    for (int m = 1; m < maxn; m++) {
        int x = m, y = m;
        while (x > 0) {
            y = y + x % 10;
            x = x / 10;
        }
        if (ans[y] == 0 || m < ans[y]) ans[y] = m;
    }
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
}

#define maxn 105

int Less(const char* s, int p, int q) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (s[(p + i) % n] != s[(q + i) % n]) {
            return s[(p + i) % n] < s[(q + i) % n];
        }
    }
    return 0;
}

int main() {
    int T;
    char s[maxn];
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        int ans = 0;
        int n = strlen(s);
        for (int i = 1; i < n; i++) {
            if (Less(s, i, ans)) ans = i;
        }
        for (int j = 0; j < n; j++) {
            putchar(s[(j + ans) % n]);
        }
        putchar('\n');
    }
}