The Dole Queue

// UVa133 The Dole Queue
// Rujia Liu
#include<stdio.h>
#define maxn 25
int n, k, m, a[maxn];

// 逆时针走t步，步长是d（-1表示顺时针走），返回新位置
int go(int p, int d, int t) {
  while(t--) {
    do { p = (p+d+n-1) % n + 1; } while(a[p] == 0); // 走到下一个非0数字
  }
  return p;
}

int main() {
  while(scanf("%d%d%d", &n, &k, &m) == 3 && n) {
    for(int i = 1; i <= n; i++) a[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--; }
      a[p1] = a[p2] = 0;
      if(left) printf(",");
    }
    printf("\n");
  }  
  return 0;
}

Xiangqi

#include<bits/stdc++.h>
using namespace std;
int gdict[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; // 将军4个方向
int hdict[8][2] = {{-1,2},{1,2}, {1,-2},{-1,-2}, {2,1},{2,-1}, {-2,-1},{-2,1}}; // 马8个方向
bool isCheck = false, board[11][10] = {false}; // 标记点是否有子
typedef struct Pos {
    char type; // 类型
    int x, y; // 坐标
    Pos(char _type=0, int _x=0, int _y=0) :  type(_type), x(_x), y(_y) {} // 构造函数
}Pos;
bool isLegal(int x, int y, int isG) { // 判断位置是否合法
    if (isG) return (x >= 1 && x <= 3) && (y >=4 && y <= 6); // 将军，可以吃红子
    else return (x >= 1 && x <= 10) && (y >= 1 && y <= 9); // 普通棋子
}
int hpos(int px, int py, int y) { // 水平方向：判断将军和当前棋子相差个数
    int ans = 0, l = min(py, y), r = max(py, y);
    for (int j = l; j <= r; j ++) if (board[px][j]) ans ++;
    return ans - board[px][py]; // 考虑吃红子情况
}
int vpos(int px, int py, int x) { // 垂直方向：判断将军和当前棋子相差个数
    int ans = 0, l = min(px, x), r = max(px, x);
    for (int i = l; i <= r; i ++) if (board[i][py]) ans ++;
    return ans - board[px][py]; // 考虑吃红子情况
}
int main() {
    int n,  x, y, tx, ty;
    char type;
    while (scanf("%d %d %d", &n, &x, &y) == 3 && n != 0) {
        vector<Pos> red; // 存储红子坐标信息
        fill(board[0], board[0]+110, 0); // 棋盘初始化，仅记录是否有子
        while (n --) {
            cin >>type >>tx >>ty;
            board[tx][ty] = true; // 标记
            red.push_back(Pos{type, tx, ty}); // 存储
        }
        int px = x, py = y; // 将军移动可能达到的位置
        for (int i = 0; i < 4; i ++) { // 黑子将军4个方向
            px = x + gdict[i][0]; py = y + gdict[i][1]; // 黑方将军移动后的位置
            if (isLegal(px, py, 1)) { // 将军位置合法
                isCheck = false; // 初始化
                for (auto& p : red) { // 遍历所有红子
                    if (p.type == 'G' && py == p.y && vpos(px, py, p.x) == 1) isCheck = true; // 可杀死
                    else if (p.type == 'R' && (py == p.y && vpos(px, py, p.x) == 1 || px == p.x && hpos(px, py, p.y) == 1)) isCheck = true;
                    else if (p.type == 'C' && (py == p.y && vpos(px, py, p.x) == 2 || px == p.x && hpos(px, py, p.y) == 2)) isCheck = true;
                    else if (p.type == 'H') {
                        for (int j = 0; j < 8 && !isCheck; j ++) { // 马8个方向
                            int hx = p.x + hdict[j][0], hy = p.y + hdict[j][1]; // 日字格
                            int gx = p.x + gdict[j/2][0], gy = p.y + gdict[j/2][1]; // 马脚
                            if ((hx == px && hy == py) && isLegal(gx, gy, 0) && !board[gx][gy]) isCheck = true;
                        }
                    }
                    if (isCheck) break; // 一发现可以杀死立刻退出，进入下一个方向
                }
                if (!isCheck) break; // 可以不死，找到存活机会
            }
        }
        printf("%s\n", isCheck ? "YES" : "NO");
    }
    return 0;
}

Squares

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, a, b;
char ch;
int main() {
    while (cin >>n >>m) {
        int h[10][10]={0}, v[10][10]={0}; // 存储水平和垂直连线
        while (m --) { // 输入
            cin >>ch >>a >>b;
            if (ch == 'H') h[a][b] = b+1;
            else v[b][a] = b+1; // 注意顺序
        }
        int right[10][10]={0}, down[10][10]={0}, num[10]={0}; // 向右/下最远可达距离，每种长度正方形计数
        for (int i = 1; i <= n; i ++) { // 每一行列
            for (int j = n-1; j >= 1; j --) {
                right[i][j] = (h[i][j] == j+1) ? right[i][j+1]+1 : 0; // 行：左->右
                down[j][i] = (v[j][i] == j+1) ? down[j+1][i]+1 : 0; // 列：上->下
            }
        }
        for (int l = 1; l <= n; l ++) { // 遍历每个正方形长度：l:[1,n]
            for (int i = 1; i <= n - l; i ++) { // x:[1,n-l]
                for (int j = 1; j <= n - l; j ++) { // y:[1,n-l]
                    if (right[i][j] >= l && down[i][j] >= l && down[i][j+l] >= l && right[i+l][j] >= l) num[l] ++, num[0] = 1; // num[0]标记存在解
                }
            }
        }
        if (cnt != 0) printf("\n**********************************\n\n"); // 以下为输出
        printf("Problem #%d\n\n", ++cnt);
        for (int i = 1; i <= n; i ++) 
            if (num[i] != 0) printf("%d square (s) of size %d\n", num[i], i);
        if (num[0] == 0) printf("No completed squares can be found.\n");
    }
    return 0;
}

Othello

#include<bits/stdc++.h>
using namespace std;
int dict[8][2] = {{0,1},{1,0},{-1,0},{0,-1},{-1,1},{1,-1},{1,1},{-1,-1}}; // 8个方向
int n;
char now, rival; // 当前下棋者，对手
string board[9], s; // 棋盘，从1开始
void showResult() { // 打印棋盘
    for (int i = 1; i <= 8; i ++) cout <<board[i].substr(1) <<endl;
}
bool isLegal(int x, int y) { // 判断位置是否合法
    return (x >= 1 && x <= 8) && (y >= 1 && y <= 8);
}
int simulate(int x, int y, int isMoved) { // 模拟单个点8个方向的移动，isMoved控制是否改变值
    int ret = 0, legal=0,  px, py, cntb = 0, cntw = 0;
    for (int i = 0; i < 8; i ++) { // 8个方向
        vector<pair<int,int> > pos; ret = 0; // 存储经过的位置
        px = x + dict[i][0]; py = y + dict[i][1]; // 移动后位置
        if (isLegal(px, py) && board[px][py] == rival) { // 对应方向存在对手棋子
            while (isLegal(px, py)) { // 在此方向尽头是否存在now子
                pos.push_back({px,py}); // 保存路径
                px = px + dict[i][0]; py = py + dict[i][1];
                if (isLegal(px, py) && board[px][py] != rival) { // 发现非对手棋子
                    if (board[px][py] == now) { // 
                        ret = legal = 1; // 用于返回
                        if (isMoved == 1) { // 移动命令，标记点
                            for (auto p : pos) board[p.first][p.second] = now;
                            board[x][y] = now; // 新加入选择的点
                        }
                        break;
                    }
                    else break;
                }
            }
            if (isMoved == 0 && legal == 1) break;
        }
    }
    for (int i = 1; i <= 8 && isMoved == 1; i ++) { // 统计个数 
        for (int j = 1; j <= 8; j ++) {
            if (board[i][j] == 'B') cntb ++;
            else if (board[i][j] == 'W') cntw ++;
        }
    }
    if (isMoved == 1) printf("Black - %2d White - %2d\n", cntb, cntw); // 对齐：2个宽度
    return legal;
}
int move(int isList) { // 模拟遍历移动，isList控制是否打印合法位置信息
    int cnt = 0;
    for (int i = 1; i <= 8; i ++) {
        for (int j = 1; j <= 8; j ++) {
            if (board[i][j] == '-' && simulate(i, j, 0) == 1) { // 该点合法
                if (isList == 1) { // 控制输出
                    if (cnt != 0) printf(" ");
                    printf("(%d,%d)", i, j); 
                }
                cnt ++;
            }
        }
    }
    if (cnt != 0 && isList == 1) puts("");
    if (cnt == 0 && isList == 1) printf("No legal move.\n"); // 无合法移动
    return cnt; // 合法点数量
}
int main() {
    cin >>n; getchar(); // 吸收空行!!
    for (int k = 0; k < n; k ++) {
        if (k != 0) puts(""); // 两组输出间空行
        for (int i = 1; i <= 8; i ++) getline(cin, s), board[i] = "-"+s; // 从1开始
        cin >>now; // 当前玩家
        rival = (now == 'W') ? 'B' : 'W'; // 对手
        while (cin >>s && s[0] != 'Q') {
            if (s[0] == 'L') move(1);
            else if (s[0] == 'M') {
                if (move(0) == 0) { // 无合法位置
                    swap(now, rival); // 当前没有合法移动
                }
                simulate(s[1]-'0', s[2]-'0', 1);
                swap(now, rival); // 交换下棋者
            }
        }
        showResult(); getchar(); // 吸收空行
    }
    return 0;
}

Cube painting

#include<bits/stdc++.h>
using namespace std;
int a[3][4] = {{2,4,5,3}, {2,6,5,1}, {1,4,6,3}}; // 3个旋转轴对应改变的轮换序列
string sa, sb, st;
void rotate(string& sr, int i, int j) { // sr绕i轴旋转j*90度
    string s = sr;
    for (int k = 0; k <= 3; k ++) { // 轮换：模拟旋转
        sr[a[i][k]-1] = s[a[i][(j+k)%4]-1]; // 从0开始存储,正方体标号从1开始
    }
}
int main() {
    while (cin >>st) {
        sa = st.substr(0,6); sb = st.substr(6);
        bool isSame = false; // 判断是否存在一样的情况
        for (int i = 0; i < 4 && !isSame; i ++) { // x轴4种转动角度
            for (int j = 0; j < 4 && !isSame; j ++) { // y轴
                for (int k = 0; k < 4 && !isSame; k ++) { // z轴
                    st = sb; // 更新
                    rotate(st, 0, i); // x轴转i*90角度
                    rotate(st, 1, j); // y轴转j*90角度
                    rotate(st, 2, k); // z轴转k*90角度
                    if (st == sa) isSame = true;
                }
            }
        }
        printf("%s\n", isSame ? "TRUE" : "FALSE");
    }
    return 0;
}

IP Networks

#include<bits/stdc++.h>
using namespace std;
void binstrToIP(string s) { // 二进制字符串转为IP形式
    for (int i = 0; i < 4; i ++) {
        bitset<8> bt(s.substr(i*8,8));
        printf("%u%s", bt.to_ulong(), i == 3 ? "\n" : ".");
    }
}
int main() {
    int n;
    while (cin >>n) {
        string smax, smin, smask, s, st;
        unsigned umin=UINT32_MAX, umax = 0;
        while (n --) {
            cin >>s;
            stringstream input(s);
            unsigned uint = 0;
            while (getline(input, st, '.')) { // 分割每个部分
                uint = (uint << 8) + (unsigned)stoi(st); // 256进制
            }
            if (umin >= uint) umin = uint, smin = s; // 最小值
            if (umax <= uint) umax = uint, smax = s; // 最大值
        }
        bitset<32> bmin(umin), bmax(umax), bmask(0xffffffffu);
        smin = bmin.to_string(); smax = bmax.to_string(); // 转为2进制字符串
        int cnt = 0;
        for (int i = 0; i < 32; i ++) { // 统计从头开始的公共子串长度
            if (smin[i] == smax[i]) cnt ++;
            else break;
        }
        for (int i = 0; i < 32-cnt; i ++) { // 设置IP地址和掩码低32-cnt位为0
            bmin.reset(i); bmask.reset(i); // 注意bitset逆序存储
        }
        binstrToIP(bmin.to_string()); binstrToIP(bmask.to_string());
    }
    return 0;
}

Morse Mismatches

#include<bits/stdc++.h>
using namespace std;
string codetbl[200], code, s;
char ch;
// map<string, set<string> > ctxt; // 上下文，字典序排列
map<string, vector<string> > ctxt; // 上下文，输入顺序排列
int main() {
    while (cin >>ch && ch != '*') {
        cin >>code; codetbl[ch] = code;
    }
    while (cin >>s && s != "*") {
        string st;
        for (auto c : s) st += codetbl[c];
        // ctxt[st].insert(s); // 字典序排列
        ctxt[st].push_back(s);
    }
    while (cin >>s && s != "*") {
        if (ctxt.find(s) != ctxt.end()) { // 存在
            cout <<*ctxt[s].begin();
            if (ctxt[s].size() > 1) cout <<"!";
        }
        else { // 不存在
            int minlen = 0x3ffff; string ans;
            for (auto p : ctxt) {
                if (s == p.first.substr(0,s.size()) || p.first == s.substr(0,p.first.size())) { // 前缀
                    int i = abs((long)p.first.size()-(long)s.size()); 
                    if (minlen >= i) {
                        minlen = i;
                        ans = *p.second.begin();
                    }
                }
            }
            cout <<ans<<"?";
        }
        puts("");
    }
    return 0;
}

RAID!

#include<bits/stdc++.h>
using namespace std;
char parity, trans[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int d, s, b, num = 0;
string disks[10]; // disks[i]表示第i块硬盘
bool isValid() { // 判断是否有效并计算缺失位
    bool ret = true;
    for (int j = 0; j < disks[0].size() && ret; j ++) { // j列
        int idx=-1, cnt=0, ex=(parity == 'E') ? 0 : 1; // x的下标，当前列x个数，列异或值
        for (int i = 0; i < d; i ++) { // i行
            if (disks[i][j] == 'x') idx = i, cnt ++; // 当前bit是x
            else ex ^= disks[i][j] - '0'; // 非x，计算异或值
        }
        if (cnt == 1) disks[idx][j] = ex + '0'; // 仅1个x，可计算恢复
        if (cnt >= 2 || (cnt == 0 && ex != 0)) ret = false; // 大于1个x||当前列和校验位异或值不为0
    }
    return ret; // 返回结果
}
void showContent() { // 显示恢复结果
    string ans;
    for (int j = 0; j < b; j ++) { // 第j列
        for (int i = 0; i < d; i ++) { // 第i行
            if (i != j % d) ans += disks[i].substr(j*s, s); // j%d==i判断是否为校验位
        }
    }
    ans += string((ans.size() % 4 == 0) ? 0 : (4-(ans.size()%4)), '0'); // 末尾补0凑成4整倍数
    for (int i = 0; i < ans.size() / 4; i ++) { // 转为16进制输出
        bitset<4> bt(ans.substr(i*4,4)); // bitset完成2进制字符串转换10进制
        cout <<trans[bt.to_ulong()];
    }
    cout <<endl;
}
int main() {
    while (cin >>d && d != 0) {
        cin >>s >>b >>parity;
        for (int i = 0; i < d; i ++) cin >>disks[i];
        bool valid = isValid();
        if (valid) {
            printf("Disk set %d is valid, contents are: ", ++num);
            showContent();
        }
        else printf("Disk set %d is invalid.\n", ++num);
    }
    return 0;
}

Extraordinarily Tired Students

#include<bits/stdc++.h>
using namespace std;
int n, a, b, c, num=0;
int main() {
    while (cin >>n && n != 0) {
        set<vector<int> > _set; // 死循环判重
        vector<int> stat, tmp, as, bs; // 当前状态，中间变量，清醒持续时间，睡眠持续时间
        for (int i = 0; i < n; i ++) {
            cin >>a >>b >>c;
            as.push_back(a); bs.push_back(b); // 存储左右区间
            stat.push_back(c); // 第一轮状态
            _set.insert(stat); // 保存状态序列
        }
        int cnt = 1, ans = -1;
        while (true) {
            int wknum = 0; // 清醒人数
            for (int i = 0; i < n; i ++) { // 计算清醒人数
                if (1 <= stat[i] && stat[i] <= as[i]) wknum ++;
            }
            if (wknum == n) { // 全部清醒
                ans = cnt;
                break; // 直接结束
            }
            cnt ++;
            tmp = stat; // 开始模拟
            for (int i = 0; i < n; i ++) { // n个人
                if (tmp[i] == as[i]) { // 准备睡觉
                    if (wknum * 2 < n) stat[i] = as[i]+1; // 睡觉人数大于清醒
                    else stat[i] = 1; // 继续清醒
                }
                else stat[i] = (stat[i] == as[i]+bs[i]) ? 1 : stat[i]+1; // 下一个状态 
            }
            if (_set.find(stat) == _set.end()) _set.insert(stat); 
            else break; // 出现重复，死循环
        }
        printf("Case %d: %d\n", ++num, ans);
    }
    return 0;
}

Data Mining

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; // 避免移位溢出
int main() {
    LL n, Sp, Sq;
    while (cin >>n >>Sp >>Sq) {
        LL K=LONG_LONG_MAX, A, B;
        for (int i = 0; i < 32; i ++) { // A
            for (int j = 0; j < 32; j ++) { // B
                if (((Sp + (Sp << i)) >= (Sq << j)) && (K > ((Sp*(n-1)+((Sp*(n-1))<<i))>>j)+Sq)) { // 公差大于Sq且k更大
                    K = ((Sp*(n-1)+((Sp*(n-1))<<i))>>j)+Sq; // 更新KAB
                    A = i; B = j;
                }
            }
        }
        printf("%lld %lld %lld\n", K, A, B); // 第一个即符合条件
    }
    return 0;
}

Flooded!

#include<bits/stdc++.h>
using namespace std;
int m, n, cubic, num = 0;
int main() {
    while (cin >>m >>n && m != 0) {
        vector<int> a(m*n+2); a[m*n+1] = 0x7ffff; // 太大会溢出
        for (int i = 1; i <= m*n; i ++) cin >>a[i];
        cin >>cubic; // 体积
        sort(a.begin()+1, a.end()); // 从小到大排序
        for (int i = 2; i <= m*n; i ++) a[i] += a[i-1]; // a[i]表示前i个长度和
        double ans1, ans2;
        for (int i = 1; i <= m*n; i ++) {
            if (((i+1)*(a[i+1]-a[i]) - a[i+1])*100 >= cubic) { // 必须用乘法，除法会产生误差
                ans1 = (double)(cubic + a[i]*100) / (i*100); // 高度，先乘后除
                ans2 = (double)i / (m*n); // 百分比
                break;
            }
        }
        printf("Region %d\nWater level is %.2lf meters.\n", ++num, round(ans1*100)/100);
        printf("%.2lf percent of the region is under water.\n\n", round(ans2*10000)/100);
    }
    return 0;
}