算法竞赛入门经典第 5 章：C++ 与 STL 入门代码示例

5.1.3 字符串

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main() {
    string line;
    while(getline(cin, line)) {
        int sum = 0, x;
        stringstream ss(line);
        while(ss >> x) sum += x;
        cout << sum << "\n";
    }
    return 0;
}

5.1.4 再谈结构体

// 引入输入输出流库，用于控制台输入输出
#include <iostream>
// 使用标准命名空间，避免每次都要写 std::
using namespace std;
// 定义一个表示二维点的结构体
struct Point {
    int x, y; // 点的 x 和 y 坐标
    // 构造函数，带有默认参数
    // 当创建 Point 对象时，如果没有提供参数，则使用默认值 (0,0)
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    // 使用初始化列表来初始化成员变量，效率更高
    // :x(x), y(y) 表示将参数 x 赋值给成员变量 x，参数 y 赋值给成员变量 y
};
// 重载加法运算符，实现两个 Point 对象的相加
// 参数：两个 Point 对象的常引用（const & 避免拷贝，提高效率）
// 返回：一个新的 Point 对象，其坐标为两个点坐标之和
Point operator+(const Point& A, const Point& B) {
    return Point(A.x + B.x, A.y + B.y); // 创建临时 Point 对象，其 x 为 A.x+B.x，y 为 A.y+B.y
}
// 重载输出运算符 <<，用于输出 Point 对象
// 参数：输出流引用，Point 对象的常引用
// 返回：输出流引用，支持链式调用（如 cout << a << b）
ostream& operator<<(ostream &out, const Point& p) {
    out << "(" << p.x << "," << p.y << ")"; // 输出格式：(x,y)
    return out; // 返回输出流，支持连续输出
}
// 主函数，程序入口点
int main() {
    // 创建两个 Point 对象
    Point a; // 使用默认构造函数，a 的坐标为 (0,0)
    Point b(1, 2); // 使用带参数构造函数，b 的坐标为 (1,2)
    a.x = 3; // 修改 a 的 x 坐标为 3，现在 a 的坐标为 (3,0)
    // 输出 a + b 的结果
    // 等价于：operator<<(cout, operator+(a, b))
    // 先计算 a+b，然后通过重载的 << 运算符输出
    cout << a + b << "\n"; // 输出 (4,2)
    return 0; // 程序正常结束
}

5.2 STL 初步

例题 5-1 大理石在哪儿（Where is the Marble?, UVa 10474）

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int main() {
    int n, q, x, a[maxn], kase = 0;
    while(scanf("%d%d", &n, &q) == 2 && n) {
        printf("CASE# %d:\n", ++kase);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        sort(a, a + n); // 排序
        while(q--) {
            scanf("%d", &x);
            int p = lower_bound(a, a + n, x) - a; // 在已排序数组 a 中寻找 x
            if(a[p] == x)
                printf("%d found at %d\n", x, p + 1);
            else
                printf("%d not found\n", x);
        }
    }
    return 0;
}

例题 5-2 木块问题（The Blocks Problem, UVa 101）

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 30;
int n;
vector<int> pile[maxn]; // 每个 pile[i]是一个 vector
// 找木块 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); // 把木块 b 放回原位
    }
    pile[p].resize(h + 1); // pile 只应保留下标 0~h 的元素
}
// 把第 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;
}

例题 5-3 安迪的第一个字典（Andy's First Dictionary, UVa 10815）

#include <iostream>
#include <string>
#include <set>
#include <sstream>
using namespace std;
set<string> dict; // string 集合
int main() {
    string s, buf;
    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;
}

例题 5-4 反片语（Ananagrams, UVa 156）

#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<string, int> cnt;
vector<string> words; // 将单词 s 进行'标准化'
string repr(const string &s) {
    string ans = s;
    for(int i = 0; i < ans.length(); i++)
        ans[i] = tolower(ans[i]);
    sort(ans.begin(), ans.end());
    return ans;
}
int main() {
    int n = 0;
    string s;
    while(cin >> s) {
        if(s[0] == '#') break;
        words.push_back(s);
        string r = repr(s);
        if(!cnt.count(r)) cnt[r] = 0;
        cnt[r]++;
    }
    vector<string> ans;
    for(int i = 0; i < words.size(); i++)
        if(cnt[repr(words[i])] == 1)
            ans.push_back(words[i]);
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << "\n";
    return 0;
}

例题 5-5 集合栈计算机（The SetStack Computer, ACM/ICPC NWERC 2006, UVa 12096）

#include <string>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
map<set<int>, int> mp;
vector<set<int>> v;
stack<int> st;
int findId(set<int> sse) {
    if(!mp.count(sse)) {
        v.push_back(sse);
        mp[sse] = v.size() - 1;
    }
    return mp[sse];
}
int main() {
    int t, n, i;
    string s;
    cin >> t;
    while(t--) {
        cin >> n;
        while(n--) {
            cin >> s;
            if(s == "PUSH") {
                st.push(findId(set<int>()));
            } else if(s == "DUP") {
                st.push(st.top());
            } else {
                int id1 = st.top(); st.pop();
                int id2 = st.top(); st.pop();
                set<int> sse;
                if(s == "UNION") {
                    set_union(v[id1].begin(), v[id1].end(), v[id2].begin(), v[id2].end(), inserter(sse, sse.begin()));
                    st.push(findId(sse));
                }
                if(s == "INTERSECT") {
                    set_intersection(v[id1].begin(), v[id1].end(), v[id2].begin(), v[id2].end(), inserter(sse, sse.begin()));
                    st.push(findId(sse));
                }
                if(s == "ADD") {
                    sse = v[id2];
                    sse.insert(id1);
                    st.push(findId(sse));
                }
            }
            cout << v[st.top()].size() << endl;
        }
        cout << "***" << endl;
    }
    return 0;
}

例题 5-6 团体队列（Team Queue, UVa 540）

#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int maxt = 1000 + 10;
int main() {
    int t, kase = 0;
    while(scanf("%d", &t) == 1 && t) {
        printf("Scenario #%d\n", ++kase);
        // 记录所有人的团队编号 map<int,int> team; // team[x]表示编号为 x 的人所在的团队编号
        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]; // q 是团队的队列，而 q2[i]是团队 i 成员的队列
        for(;;) {
            int x;
            char cmd[10];
            scanf("%s", cmd);
            if(cmd[0] == 'S') break;
            else if(cmd[0] == 'D') {
                int t = q.front();
                printf("%d\n", q2[t].front());
                q2[t].pop();
                if(q2[t].empty()) q.pop(); // 团体 t 全体出队列
            } else if(cmd[0] == 'E') {
                scanf("%d", &x);
                int t = team[x];
                if(q2[t].empty()) q.push(t); // 团队 t 进入队列
                q2[t].push(x);
            }
        }
        printf("\n");
    }
    return 0;
}

例题 5-7 丑数（Ugly Numbers, UVa 136）

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int coeff[3] = {2, 3, 5};
int main() {
    priority_queue<LL, vector<LL>, greater<LL>> pq;
    set<LL> s;
    pq.push(1);
    s.insert(1);
    for(int i = 1;; i++) {
        LL x = pq.top();
        pq.pop();
        if(i == 1500) {
            cout << "The 1500'th ugly number is " << x << ".\n";
            break;
        }
        for(int j = 0; j < 3; j++) {
            LL x2 = x * coeff[j];
            if(!s.count(x2)) {
                s.insert(x2);
                pq.push(x2);
            }
        }
    }
    return 0;
}
// 答案：859963392。

5.3 应用：大整数类

5.4 竞赛题目举例

例题 5-8 Unix ls 命令（Unix ls, UVa 400）

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxcol = 60;
const int maxn = 100 + 5;
string filenames[maxn];
// 输出字符串 s，长度不足 len 时补字符 extra
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()); // STL 的 max
        }
        // 计算列数 cols 和行数 rows
        int cols = (maxcol - M) / (M + 2) + 1, rows = (n - 1) / cols + 1;
        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;
                if(idx < n)
                    print(filenames[idx], c == cols - 1 ? M : M + 2, ' ');
            }
            cout << "\n";
        }
    }
    return 0;
}

例题 5-9 数据库（Database, ACM/ICPC NEERC 2009, UVa 1592）

例题 5-10 PGA 巡回赛的奖金（PGA Tour Prize Money, ACM/ICPC World Finals 1990, UVa 207）

例题 5-11 邮件传输代理的交互（The Letter Carrier's Rounds, ACM/ICPC World Finals 1999, UVa 814）

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
void parse_address(const string &s, string &user, string &mta) {
    int k = s.find('@');
    user = s.substr(0, k);
    mta = s.substr(k + 1);
}
int main() {
    int k;
    string s, t, user1, mta1, user2, mta2;
    set<string> addr; // 输入所有 MTA，转化为地址列表
    while(cin >> s && s != "*") {
        cin >> s >> k;
        while(k--) {
            cin >> t;
            addr.insert(t + "@" + s);
        }
    }
    while(cin >> s && s != "*") {
        parse_address(s, user1, mta1); // 处理发件人地址
        vector<string> mta; // 所有需要连接的 mta，按照输入顺序
        map<string, vector<string>> dest; // 每个 MTA 需要发送的用户
        set<string> vis;
        while(cin >> t && t != "*") {
            parse_address(t, user2, mta2); // 处理收件人地址
            if(vis.count(t)) continue; // 重复的收件人
            vis.insert(t);
            if(!dest.count(mta2)) {
                mta.push_back(mta2);
                dest[mta2] = vector<string>();
            }
            dest[mta2].push_back(t);
        }
        getline(cin, t); // 把'*'这一行的回车吃掉
        // 输入邮件正文
        string data;
        while(getline(cin, t) && t[0] != '*')
            data += " " + t + "\n";
        for(int i = 0; i < mta.size(); i++) {
            string mta2 = mta[i];
            vector<string> users = dest[mta2];
            cout << "Connection between " << mta1 << " and " << mta2 << endl;
            cout << " HELO " << mta1 << "\n";
            cout << " 250\n";
            cout << " MAIL FROM:<" << s << ">\n";
            cout << " 250\n";
            bool ok = false;
            for(int i = 0; i < users.size(); i++) {
                cout << " RCPT TO:<" << users[i] << ">\n";
                if(addr.count(users[i])) {
                    ok = true;
                    cout << " 250\n";
                } else
                    cout << " 550\n";
            }
            if(ok) {
                cout << " DATA\n";
                cout << " 354\n";
                cout << data;
                cout << ".\n";
                cout << " 250\n";
            }
            cout << " QUIT\n";
            cout << " 221\n";
        }
    }
    return 0;
}

例题 5-12 城市正视图（Urban Elevations, ACM/ICPC World Finals 1992, UVa 221）

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100 + 5;
struct Building {
    int id;
    double x, y, w, d, h;
    bool operator<(const Building &rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
} b[maxn];
int n;
double x[maxn * 2];
bool cover(int i, double mx) {
    return b[i].x <= mx && b[i].x + b[i].w >= mx;
}
// 判断建筑物 i 在 x=mx 处是否可见
bool visible(int i, double mx) {
    if(!cover(i, mx)) return false;
    for(int k = 0; k < n; k++)
        if(b[k].y < b[i].y && b[k].h >= b[i].h && cover(k, mx))
            return false;
    return true;
}
int main() {
    int kase = 0;
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].w, &b[i].d, &b[i].h);
            x[i * 2] = b[i].x;
            x[i * 2 + 1] = b[i].x + b[i].w;
            b[i].id = i + 1;
        }
        sort(b, b + n);
        sort(x, x + n * 2);
        int m = unique(x, x + n * 2) - x; // x 坐标排序后去重，得到 m 个坐标
        if(kase++) printf("\n");
        printf("For map #%d, the visible buildings are numbered as follows:\n%d", kase, b[0].id);
        for(int i = 1; i < n; i++) {
            bool vis = false;
            for(int j = 0; j < m - 1; j++)
                if(visible(i, (x[j] + x[j + 1]) / 2)) {
                    vis = true;
                    break;
                }
            if(vis) printf(" %d", b[i].id);
        }
        printf("\n");
    }
    return 0;
}

5.5 习题

习题 5-1 代码对齐（Alignment of Code, ACM/ICPC NEERC 2010, UVa 1593）

#include <iostream>
#include <sstream>
#include <vector>
#include <string.h>
using namespace std;
int main() {
    vector<vector<string>> v;
    string line, word;
    int i, j, k;
    int vlen[200];
    while(getline(cin, line)) {
        stringstream ss(line);
        vector<string> vs;
        while(ss >> word) vs.push_back(word);
        v.push_back(vs);
    }
    memset(vlen, 0, 200);
    for(i = 0; i < v.size(); ++i) {
        for(j = 0; j < v[i].size(); ++j) {
            vlen[j] = v[i][j].length() > vlen[j] ? v[i][j].length() : vlen[j];
        }
    }
    for(i = 0; i < v.size(); ++i) {
        for(j = 0; j < v[i].size(); ++j) {
            cout << v[i][j];
            if(j != v[i].size() - 1) {
                for(k = vlen[j] - v[i][j].size(); k > 0; --k) cout << ' ';
                cout << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

习题 5-2 Ducci 序列（Ducci Sequence, ACM/ICPC Seoul 2009, UVa 1594）

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
int arr[1005][2005];
int n;
int judge(int i) {
    int j, k;
    for(j = 0; j < n; ++j) {
        if(arr[i][j] != 0) break;
    }
    if(j == n) return 1;
    for(k = 0; k < i; ++k) {
        for(j = 0; j < n; ++j) {
            if(arr[i][j] != arr[k][j]) break;
        }
        if(j == n) return 2;
    }
    return 0;
}
int main() {
    int m, i, j, k;
    int flag;
    cin >> m;
    while(m--) {
        memset(arr, 0, 1005 * 2005);
        cin >> n;
        for(i = 0; i < n; ++i) cin >> arr[0][i];
        i = 0;
        while(1) {
            flag = judge(i);
            if(flag != 0) break;
            ++i;
            arr[i][n - 1] = abs(arr[i - 1][0] - arr[i - 1][n - 1]);
            for(j = 1; j < n; ++j) arr[i][j - 1] = abs(arr[i - 1][j] - arr[i - 1][j - 1]);
        }
        if(flag == 1) cout << "ZERO" << endl;
        else cout << "LOOP" << endl;
    }
    return 0;
}

习题 5-3 卡片游戏（Throwing cards away I, UVa 10935）

#include <queue>
#include <iostream>
using namespace std;
int main() {
    int n, i, j, k;
    while(cin >> n && n) {
        queue<int> qu;
        for(i = 1; i <= n; ++i) qu.push(i);
        cout << "Discarded cards:";
        while(qu.size() > 1) {
            cout << " " << qu.front();
            if(qu.size() > 2) cout << ",";
            qu.pop();
            j = qu.front();
            qu.pop();
            qu.push(j);
        }
        cout << endl;
        cout << "Remaining card: " << qu.front() << endl;
    }
    return 0;
}

习题 5-4 交换学生（Foreign Exchange, UVa 10763）

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, a, b, i, j, k;
    while(scanf("%d", &n) && n) {
        vector<int> lv, rv;
        for(i = 0; i < n; ++i) {
            scanf("%d %d", &a, &b);
            lv.push_back(a);
            rv.push_back(b);
        }
        sort(lv.begin(), lv.end());
        sort(rv.begin(), rv.end());
        for(i = 0; i < n; ++i) {
            if(lv[i] != rv[i]) break;
        }
        if(i != n) puts("NO");
        else puts("YES");
    }
    return 0;
}

习题 5-5 复合词（Compound Words, UVa 10391）

#include <set>
#include <iostream>
#include <string>
using namespace std;
int main() {
    set<string> se;
    string s;
    int size, i;
    bool flag;
    while(cin >> s) se.insert(s);
    for(auto ip = se.begin(); ip != se.end(); ++ip) {
        size = ip->length() - 1;
        flag = false;
        for(i = 1; i < size; ++i) {
            string s1 = ip->substr(0, i);
            string s2 = ip->substr(i);
            if(se.count(s1) && se.count(s2)) {
                flag = true;
                break;
            }
        }
        if(flag == true) cout << *ip << endl;
    }
    return 0;
}

习题 5-6 对称轴（Symmetry, ACM/ICPC Seoul 2004, UVa 1595）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct point {
    int x, y;
};
bool cmp1(const point &lhs, const point &rhs) {
    if(lhs.x != rhs.x) return lhs.x < rhs.x;
    return lhs.y < rhs.y;
}
bool cmp2(const point &lhs, const point &rhs) {
    if(lhs.x != rhs.x) return lhs.x < rhs.x;
    return lhs.y > rhs.y;
}
int main() {
    int t, n, i, j, k, a, b;
    cin >> t;
    bool cut2, flag;
    while(t--) {
        vector<point> v;
        cin >> n;
        for(i = 0; i < n; ++i) {
            point p;
            cin >> p.x >> p.y;
            v.push_back(p);
        }
        sort(v.begin(), v.end(), cmp1);
        int beg1 = 0, end1, beg2, end2 = n - 1, xcut;
        cut2 = false;
        if(n % 2 == 0) {
            end1 = n / 2 - 1;
            beg2 = n / 2;
            int sum = v[beg2].x + v[end1].x;
            xcut = sum / 2;
            if(sum % 2 != 0) cut2 = true;
        } else {
            xcut = v[n / 2].x;
            end1 = n / 2 - 1;
            beg2 = n / 2 + 1;
        }
        sort(v.begin() + beg2, v.end(), cmp2);
        flag = true;
        for(i = beg1; i <= end1; ++i) {
            a = i;
            b = end2 - i;
            if(v[a].x == xcut && v[b].x == xcut) continue;
            if(v[a].y != v[b].y) {
                flag = false;
                break;
            }
            if(!cut2) {
                if((xcut - v[a].x) != (v[b].x - xcut)) {
                    flag = false;
                    break;
                }
            }
            if(cut2) {
                if((xcut - v[a].x) != (v[b].x - xcut - 1)) {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

习题 5-7 打印队列（Printer Queue, ACM/ICPC NWERC 2006, UVa 12100）

#include <stdio.h>
#include <queue>
using namespace std;
int m;
int findTime(queue<int>& qu, priority_queue<int>& qup) {
    int time = 0;
    int k, kt;
    while(1) {
        k = qu.front();
        kt = qup.top();
        qu.pop();
        --m;
        if(k == kt) {
            ++time;
            qup.pop();
            if(m == -1) return time;
        } else {
            qu.push(k);
            if(m == -1) m = qu.size() - 1;
        }
    }
}
int main() {
    int t, n, i, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        queue<int> qu;
        priority_queue<int> qup;
        for(i = 0; i < n; ++i) {
            scanf("%d", &k);
            qu.push(k);
            qup.push(k);
        }
        printf("%d\n", findTime(qu, qup));
    }
    return 0;
}

习题 5-8 图书管理系统（Borrowers, ACM/ICPC World Finals 1994, UVa 230）

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
struct book {
    string title;
    string author;
    int has;
    bool operator<(const book &rhs) {
        if(this->author != rhs.author) return this->author < rhs.author;
        else return this->title < rhs.title;
    }
};
vector<book> v;
map<string, int> mp;
book getBook(string s) {
    book b;
    s = s.substr(1);
    int pos = s.find("\"");
    b.title = s.substr(0, pos);
    b.author = s.substr(pos + 5);
    b.has = 0;
    return b;
}
void shelve() {
    int i;
    string fore = "";
    for(i = 0; i < v.size(); ++i) {
        if(v[i].has == 0) fore = v[i].title;
        if(v[i].has == 2) {
            cout << "Put \"" << v[i].title << "\" ";
            if(fore == "") cout << "first";
            else cout << "after \"" << fore << "\"";
            cout << endl;
            v[i].has = 0;
            fore = v[i].title;
        }
    }
    cout << "END" << endl;
}
int main() {
    string s, out;
    book b;
    int i;
    while(getline(cin, s) && s != "END") {
        b = getBook(s);
        v.push_back(b);
    }
    sort(v.begin(), v.end());
    for(i = 0; i < v.size(); ++i) mp[v[i].title] = i;
    while(getline(cin, s) && s != "END") {
        string st = s.substr(0, 6);
        if(st == "SHELVE") {
            shelve();
            continue;
        }
        string name = s.substr(8, s.length() - 9);
        if(st == "BORROW") v[mp[name]].has = 1;
        if(st == "RETURN") v[mp[name]].has = 2;
    }
    return 0;
}

习题 5-9 找 bug（Bug Hunt, ACM/ICPC Tokyo 2007, UVa 1596）

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stack>
#define MAX 60
using namespace std;
struct Array {
    int size;
    map<int, int> mp;
};
Array arr[MAX];
int bug;
int getValue(string s) {
    stack<int> st;
    int a = 0, av = 0;
    while(s.length()) {
        if(s[0] >= 'A' && s[0] <= 'z') {
            st.push(s[0] - 'A');
            s = s.substr(2, s.length() - 3);
        } else {
            av = atoi(s.c_str());
            break;
        }
    }
    while(st.size()) {
        a = st.top();
        if(av >= arr[a].size || !arr[a].mp.count(av)) {
            bug = 1;
            return 0;
        }
        av = arr[a].mp[av];
        st.pop();
    }
    return av;
}
void handleDecl(string line) {
    Array a;
    int i = line[0] - 'A';
    if(i < 0 || i > MAX) {
        bug = 1;
        return;
    }
    line = line.substr(2, line.length() - 3);
    int num = atoi(line.c_str());
    a.size = num;
    arr[i] = a;
}
void handlAssi(string line) {
    int cut = line.find("=");
    string front, after;
    front = line.substr(0, cut);
    after = line.substr(cut + 1);
    int a1, v1, v2;
    a1 = front[0] - 'A';
    if(a1 < 0 || a1 > MAX) {
        bug = 1;
        return;
    }
    v1 = getValue(front.substr(2, front.length() - 3));
    if(bug) return;
    if(v1 >= arr[a1].size) {
        bug = 1;
        return;
    }
    v2 = getValue(after);
    if(bug) return;
    arr[a1].mp[v1] = v2;
}
void handleLine(string line) {
    int pos = line.find("=");
    if(pos < 0) handleDecl(line);
    else handlAssi(line);
}
int main() {
    string line;
    int i, j, k, lineNum;
    while(getline(cin, line) && line != ".") {
        for(i = 0; i < MAX; ++i) {
            arr[i].size = 0;
            arr[i].mp.clear();
        }
        bug = 0;
        lineNum = 1;
        handleLine(line);
        while(getline(cin, line) && line != ".") {
            if(!bug) {
                ++lineNum;
                handleLine(line);
            }
        }
        if(!bug) lineNum = 0;
        cout << lineNum << endl;
    }
    return 0;
}

习题 5-10 在 Web 中搜索（Searching the Web, ACM/ICPC Beijing 2004, UVa 1597）

#include <iostream>
#include <map>
#include <vector>
#include <sstream>
#include <set>
#include <algorithm>
using namespace std;
struct DID {
    int doci;
    int linei;
    bool hole;
    bool operator==(const DID &rhs) {
        if(this->doci != rhs.doci) return false;
        if(this->hole && rhs.hole) return true;
        return this->linei == rhs.linei;
    }
};
vector<vector<string>> docs;
map<string, vector<DID>> mp;
set<string> se = {"a", "the", "to", "and", "or", "not"};
void getDocs(int i) {
    vector<string> doc;
    string line, word;
    int j, k = 0;
    while(getline(cin, line) && line != "**********") {
        doc.push_back(line);
        for(j = 0; j < line.length(); ++j) {
            if(line[j] >= 'A' && line[j] <= 'Z') line[j] = (line[j] - 'A') + 'a';
            if(line[j] < 'a' || line[j] > 'z') line[j] = ' ';
        }
        stringstream ss(line);
        while(ss >> word) {
            if(!se.count(word)) {
                DID d;
                d.doci = i;
                d.linei = k;
                d.hole = false;
                if(!mp.count(word)) mp[word] = vector<DID>();
                mp[word].push_back(d);
            }
        }
        ++k;
    }
    docs.push_back(doc);
}
vector<DID> EMPTYVEC;
vector<DID>& getWordVec(string word) {
    if(!mp.count(word)) return EMPTYVEC;
    else return mp[word];
}
void putMPV(const vector<DID>& mpv) {
    if(!mpv.size()) {
        cout << "Sorry, I found nothing." << endl;
        return;
    }
    int i, j, k;
    for(i = 0; i < mpv.size(); ++i) {
        if(i != 0 && mpv[i].doci != mpv[i - 1].doci) cout << "----------" << endl;
        if(mpv[i].hole) {
            k = mpv[i].doci;
            for(j = 0; j < docs[k].size(); ++j) cout << docs[k][j] << endl;
            continue;
        }
        cout << docs[mpv[i].doci][mpv[i].linei] << endl;
    }
}
void getNOT(string word) {
    set<int> vse;
    int i;
    vector<DID>& v = getWordVec(word);
    for(i = 0; i < v.size(); ++i) vse.insert(v[i].doci);
    vector<DID> ve;
    for(i = 0; i < docs.size(); ++i) {
        if(!vse.count(i)) {
            DID d;
            d.doci = i;
            d.linei = 0;
            d.hole = true;
            ve.push_back(d);
        }
    }
    putMPV(ve);
}
void getAND(vector<DID>& mpv, vector<DID>& mpv1, vector<DID>& mpv2) {
    set<int> vse1, vse2;
    int i;
    for(i = 0; i < mpv1.size(); ++i) vse1.insert(mpv1[i].doci);
    for(i = 0; i < mpv2.size(); ++i) vse2.insert(mpv2[i].doci);
    for(i = 0; i < mpv1.size(); ++i) {
        if(vse2.count(mpv1[i].doci)) mpv.push_back(mpv1[i]);
    }
    for(i = 0; i < mpv2.size(); ++i) {
        if(vse1.count(mpv2[i].doci)) mpv.push_back(mpv2[i]);
    }
}
bool cmp(const DID &lhs, const DID &rhs) {
    if(lhs.doci != rhs.doci) return lhs.doci < rhs.doci;
    return lhs.linei < rhs.linei;
}
void handleQuery() {
    string query, word;
    int i;
    getline(cin, query);
    stringstream ss(query);
    vector<string> v;
    while(ss >> word) v.push_back(word);
    vector<DID> mpv;
    if(v.size() == 1) mpv = getWordVec(v[0]);
    else if(v.size() == 2) {
        getNOT(v[1]);
        return;
    } else {
        vector<DID>& mpv1 = getWordVec(v[0]), &mpv2 = getWordVec(v[2]);
        if(v[1] == "OR") {
            mpv = mpv1;
            for(i = 0; i < mpv2.size(); ++i) mpv.push_back(mpv2[i]);
        } else {
            getAND(mpv, mpv1, mpv2);
        }
    }
    sort(mpv.begin(), mpv.end(), cmp);
    mpv.erase(unique(mpv.begin(), mpv.end()), mpv.end());
    putMPV(mpv);
}
int main() {
    int N, M;
    int i, j, k;
    string s;
    cin >> N;
    getline(cin, s);
    for(i = 0; i < N; ++i) getDocs(i);
    /* for(auto bi = mp.begin(); bi !=mp.end(); ++bi) { vector<DID> & vt = bi->second; sort(vt.begin(), vt.end(), cmp); vt.erase(unique(vt.begin(), vt.end()), vt.end()); } */
    cin >> M;
    getline(cin, s);
    while(M--) {
        handleQuery();
        cout << "==========" << endl;
    }
    return 0;
}

习题 5-11 更新字典（Updating a Dictionary, UVa 12504）

#include <iostream>
#include <string>
#include <map>
#include <sstream>
using namespace std;
void getMap(map<string, string>& mp, string &line) {
    int i, j, k;
    for(i = 0; i < line.length(); ++i) {
        if((line[i] < 'a' || line[i] > 'z') && (line[i] < '0' || line[i] > '9')) line[i] = ' ';
    }
    stringstream ss(line);
    string word1, word2;
    while(ss >> word1 >> word2) mp[word1] = word2;
}
int main() {
    int n;
    bool flag[3];
    cin >> n;
    string line1, line2;
    getline(cin, line1);
    while(n--) {
        getline(cin, line1);
        getline(cin, line2);
        map<string, string> mp1, mp2;
        getMap(mp1, line1);
        getMap(mp2, line2);
        flag[0] = false;
        flag[1] = false;
        flag[2] = false;
        for(auto i = mp2.begin(); i != mp2.end(); ++i) {
            if(!mp1.count(i->first)) {
                if(flag[0] == false) {
                    flag[0] = true;
                    cout << "+" << i->first;
                } else cout << "," << i->first;
            }
        }
        if(flag[0] == true) cout << endl;
        for(auto i = mp1.begin(); i != mp1.end(); ++i) {
            if(!mp2.count(i->first)) {
                if(flag[1] == false) {
                    flag[1] = true;
                    cout << "-" << i->first;
                } else cout << "," << i->first;
            }
        }
        if(flag[1] == true) cout << endl;
        for(auto i = mp2.begin(); i != mp2.end(); ++i) {
            if(mp1.count(i->first) && i->second != mp1[i->first]) {
                if(flag[2] == false) {
                    flag[2] = true;
                    cout << "*" << i->first;
                } else cout << "," << i->first;
            }
        }
        if(flag[2] == true) cout << endl;
        if(!flag[0] && !flag[1] && !flag[2]) cout << "No changes" << endl;
        cout << endl;
    }
    return 0;
}

习题 5-12 地图查询（Do You Know The Way to San Jose?, ACM/ICPC World Finals 1997, UVa 511）

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
struct LOC {
    double x, y;
};
struct MAP {
    double x1, x2, y1, y2;
    double cenx, ceny;
    double radio;
    double area;
    string name;
};
vector<MAP> vm;
map<string, vector<int>> mp;
double xt, yt;
double compDis(MAP &m, int x, int y) {
    return (m.cenx - x) * (m.cenx - x) + (m.ceny - y) * (m.ceny - y);
}
double compDisRC(MAP &m, int x, int y) {
    return (m.x2 - x) * (m.x2 - x) + (m.y2 - y) * (m.y2 - y);
}
bool cmp(int l, int r) {
    MAP &m1 = vm[l], &m2 = vm[r];
    if(m1.area != m2.area) return m1.area > m2.area;
    double dis1 = compDis(m1, xt, yt), dis2 = compDis(m2, xt, yt);
    if(dis1 != dis2) return dis1 < dis2;
    if(m1.radio != m2.radio) return m1.radio < m2.radio;
    dis1 = compDisRC(m1, xt, yt);
    dis2 = compDisRC(m2, xt, yt);
    if(dis1 != dis2) return dis1 > dis2;
    return m1.x1 < m2.x1;
}
int main() {
    string line, word;
    double x1, x2, y1, y2;
    int i, j, t;
    getline(cin, line);
    while(cin >> word && word != "LOCATIONS") {
        MAP m;
        m.name = word;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 > x2) { m.x1 = x2; m.x2 = x1; }
        else { m.x2 = x2; m.x1 = x1; }
        if(y1 > y2) { m.y1 = y2; m.y2 = y1; }
        else { m.y2 = y2; m.y1 = y1; }
        m.cenx = (m.x1 + m.x2) / 2;
        m.ceny = (m.y1 + m.y2) / 2;
        m.radio = (m.x2 - m.x1) / (m.y2 - m.y1);
        m.radio = m.radio - 0.75;
        if(m.radio < 0) m.radio = -m.radio;
        m.area = (m.x2 - m.x1) * (m.y2 - m.y1);
        vm.push_back(m);
    }
    while(cin >> word && word != "REQUESTS") {
        cin >> xt >> yt;
        vector<int> v;
        for(i = 0; i < vm.size(); ++i) {
            if(vm[i].x1 <= xt && vm[i].x2 >= xt && vm[i].y1 <= yt && vm[i].y2 >= yt) v.push_back(i);
        }
        sort(v.begin(), v.end(), cmp);
        vector<int> vt;
        for(i = 0; i < v.size(); ++i) {
            if(i == 0) { vt.push_back(v[0]); continue; }
            if(vm[vt[vt.size() - 1]].area == vm[v[i]].area) continue;
            vt.push_back(v[i]);
        }
        mp[word] = vt;
    }
    while(cin >> word && word != "END") {
        cin >> t;
        cout << word << " at detail level " << t << ' ';
        if(!mp.count(word)) cout << "unknown location";
        else if(mp[word].size() == 0) cout << "no map contains that location";
        else if(mp[word].size() >= t) cout << "using " << vm[mp[word][t - 1]].name;
        else cout << "no map at that detail level; using " << vm[mp[word][mp[word].size() - 1]].name;
        cout << endl;
    }
    return 0;
}

习题 5-13 客户中心模拟（Queue and A, ACM/ICPC World Finals 2000, UVa 822）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct REQ {
    int id, num, elap, serv, btwe;
};
vector<REQ> reqs;
struct PER {
    int id;
    vector<int> v;
    int eart, endt;
};
vector<PER> pers;
int MAXTOPLEN;
struct TIME {
    int t;
    int flag;
    int i;
    bool operator==(const TIME & rhs) const {
        if(this->t == rhs.t && this->i == rhs.i && this->flag == rhs.flag) return true;
        return false;
    }
    bool operator<(const TIME & rhs) const {
        if(this->t != rhs.t) return this->t < rhs.t;
        if(this->flag != rhs.flag) return this->flag < rhs.flag;
        return this->i < rhs.i;
    }
    bool operator>(const TIME & rhs) const {
        if(*this == rhs || *this < rhs) return false;
        return true;
    }
};
bool cmp(const TIME & lhs, const TIME & rhs) {
    if(lhs.t != rhs.t) return lhs.t < rhs.t;
    return lhs.i < rhs.i;
}
int judgePer(int i, int j) {
    if(pers[i].eart > pers[j].eart) return j;
    if(pers[i].eart < pers[j].eart) return i;
    if(pers[i].id > pers[j].id) return j;
    if(pers[i].id < pers[j].id) return i;
}
int choosePerson(int r, int t) {
    int i, j, k;
    bool flag;
    int choose;
    for(i = 0; i < MAXTOPLEN; ++i) {
        flag = false;
        for(j = 0; j < pers.size(); ++j) {
            if(pers[j].v.size() <= i || pers[j].endt > t) continue;
            if(pers[j].v[i] == reqs[r].id) {
                if(flag == false) {
                    flag = true;
                    choose = j;
                } else {
                    choose = judgePer(j, choose);
                }
            }
        }
        if(flag == true) return choose;
    }
    return -1;
}
int simulate() {
    int t = 0, i, j, k;
    TIME ti, tt;
    priority_queue<TIME, vector<TIME>, greater<TIME>> pq;
    queue<int> qth;
    for(i = 0; i < reqs.size(); ++i) {
        for(j = 0; j < reqs[i].num; ++j) {
            TIME tim;
            tim.t = reqs[i].elap + reqs[i].btwe * j;
            tim.i = i;
            tim.flag = 1;
            pq.push(tim);
        }
    }
    while(pq.size() || qth.size()) {
        if(pq.size()) {
            ti = pq.top();
            pq.pop();
            if(ti.flag > 0) qth.push(ti.i);
            t = ti.t;
            while(pq.size()) {
                tt = pq.top();
                if(tt.t == t) {
                    if(tt.flag > 0) qth.push(tt.i);
                    pq.pop();
                } else break;
            }
        }
        k = qth.size();
        for(i = 0; i < k; ++i) {
            j = qth.front();
            qth.pop();
            int perCho = choosePerson(j, t);
            if(perCho < 0) { qth.push(j); continue; }
            pers[perCho].eart = t;
            pers[perCho].endt = t + reqs[j].serv;
            TIME tim;
            tim.t = pers[perCho].endt;
            tim.flag = -1;
            pq.push(tim);
        }
    }
    return t;
}
int main() {
    int m, n, i, j, k, t = 0;
    while(cin >> m && m != 0) {
        reqs.clear();
        pers.clear();
        MAXTOPLEN = 0;
        while(m--) {
            REQ r;
            cin >> r.id >> r.num >> r.elap >> r.serv >> r.btwe;
            reqs.push_back(r);
        }
        cin >> n;
        while(n--) {
            PER p;
            cin >> p.id >> i;
            if(i > MAXTOPLEN) MAXTOPLEN = i;
            while(i--) {
                cin >> j;
                p.v.push_back(j);
            }
            p.eart = 0;
            p.endt = 0;
            pers.push_back(p);
        }
        k = simulate();
        cout << "Scenario " << ++t << ": All requests are serviced within " << k << " minutes." << endl;
    }
    return 0;
}

习题 5-14 交易所（Exchange, ACM/ICPC NEERC 2006, UVa 1598）

#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
struct MES {
    int id;
    int size;
    int price;
    int bs;
    bool operator<(const MES &rhs) const {
        if(this->price != rhs.price) return this->price < rhs.price;
        return this->id > rhs.id;
    }
    bool operator>(const MES &rhs) const {
        if(this->price != rhs.price) return this->price > rhs.price;
        return this->id > rhs.id;
    }
};
vector<MES> vmes;
priority_queue<MES, vector<MES>, less<MES>> buys;
priority_queue<MES, vector<MES>, greater<MES>> sells;
map<int, int> mpBuy, mpSell;
void deleteMes(int id) {
    if(id >= vmes.size() || !vmes[id].size) return;
    if(vmes[id].bs > 0) mpBuy[vmes[id].price] -= vmes[id].size;
    else mpSell[vmes[id].price] -= vmes[id].size;
    vmes[id].size = 0;
}
void buyMes(MES &m) {
    MES m1, m2;
    int size, price;
    while(!sells.empty() && m.size) {
        m1 = sells.top();
        if(vmes[m1.id].size == 0) { sells.pop(); continue; }
        if(vmes[m1.id].price > m.price) break;
        price = vmes[m1.id].price;
        if(m.size >= vmes[m1.id].size) {
            size = vmes[m1.id].size;
            sells.pop();
        } else size = m.size;
        mpSell[price] -= size;
        m.size -= size;
        vmes[m1.id].size -= size;
        cout << "TRADE " << size << " " << price << endl;
    }
}
void sellMes(MES &m) {
    MES m1, m2;
    int size, price;
    while(!buys.empty() && m.size) {
        m1 = buys.top();
        if(vmes[m1.id].size == 0) { buys.pop(); continue; }
        if(vmes[m1.id].price < m.price) break;
        price = vmes[m1.id].price;
        if(m.size >= vmes[m1.id].size) {
            size = vmes[m1.id].size;
            buys.pop();
        } else size = m.size;
        mpBuy[price] -= size;
        m.size -= size;
        vmes[m1.id].size -= size;
        cout << "TRADE " << size << " " << price << endl;
    }
}
int main() {
    int n, i, j, k;
    int id;
    string s;
    MES m1, m2;
    int size, price;
    bool flag = false;
    while(cin >> n && n != 0) {
        if(flag == false) flag = true;
        else cout << endl;
        priority_queue<MES, vector<MES>, less<MES>> buysT;
        priority_queue<MES, vector<MES>, greater<MES>> sellsT;
        buys = buysT;
        sells = sellsT;
        mpBuy.clear();
        mpSell.clear();
        vmes.clear();
        for(i = 0; i < n; ++i) {
            MES m;
            m.id = i;
            cin >> s;
            if(s == "CANCEL") {
                cin >> id;
                id = id - 1;
                deleteMes(id);
                m.price = 0;
                m.size = 0;
            } else {
                cin >> m.size >> m.price;
                if(s == "BUY") {
                    m.bs = 1;
                    buyMes(m);
                    if(m.size > 0) {
                        if(!mpBuy.count(m.price)) mpBuy[m.price] = 0;
                        mpBuy[m.price] += m.size;
                        buys.push(m);
                    }
                } else {
                    m.bs = -1;
                    sellMes(m);
                    if(m.size > 0) {
                        if(!mpSell.count(m.price)) mpSell[m.price] = 0;
                        mpSell[m.price] += m.size;
                        sells.push(m);
                    }
                }
            }
            vmes.push_back(m);
            cout << "QUOTE ";
            size = 0;
            price = 0;
            while(!buys.empty()) {
                m1 = buys.top();
                if(vmes[m1.id].size == 0) { buys.pop(); continue; }
                price = vmes[m1.id].price;
                size = mpBuy[vmes[m1.id].price];
                break;
            }
            cout << size << " " << price;
            cout << " - ";
            size = 0;
            price = 99999;
            while(!sells.empty()) {
                m1 = sells.top();
                if(vmes[m1.id].size == 0) { sells.pop(); continue; }
                price = vmes[m1.id].price;
                size = mpSell[vmes[m1.id].price];
                break;
            }
            cout << size << " " << price;
            cout << endl;
        }
    }
    return 0;
}

习题 5-15 Fibonacci 的复仇（Revenge of Fibonacci, ACM/ICPC Shanghai 2011, UVa 12333）

#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct BigInt {
    static const long long BASE = 1000000000000000000;
    static const int WIDTH = 18;
    static const int LEN = 4;
    vector<long long> s;
    BigInt(long long num = 0) { *this = num; }
    BigInt operator=(long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while(num > 0);
        return *this;
    }
    BigInt operator+(const BigInt &b) {
        BigInt c;
        c.s.clear();
        long long g = 0, x;
        int ssize = s.size(), bssize = b.s.size();
        for(int i = 0;; i++) {
            if(g == 0 && i >= ssize && i >= bssize) break;
            x = g;
            if(i < ssize) x += s[i];
            if(i < bssize) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }
    string outN() {
        string str, st;
        int i = s.size() - 1, j = LEN;
        while(i >= 0 && j > 0) {
            st = to_string(s[i]);
            while(i != s.size() - 1 && st.length() < WIDTH) st = "0" + st;
            str += st;
            --i;
            --j;
        }
        return str.substr(0, 40);
    }
};
struct Node {
    int id;
    int num;
    Node* childs[10] = {NULL};
};
vector<string> v;
Node* createTree() {
    int i, j, n, num;
    Node* tree = new Node;
    tree->id = -1;
    tree->num = -1;
    for(i = 0; i < v.size(); ++i) {
        n = v[i].size();
        Node* p = tree;
        for(j = 0; j < n; ++j) {
            num = v[i][j] - '0';
            if(!p->childs[num]) {
                p->childs[num] = new Node;
                p->childs[num]->id = i;
                p->childs[num]->num = num;
            }
            p = p->childs[num];
        }
    }
    return tree;
}
int main() {
    char s[45];
    int i, j, T, n, num, res;
    BigInt bv[3];
    bv[0] = 1;
    bv[1] = 1;
    v.push_back("1");
    v.push_back("1");
    for(i = 2; i < 100000; ++i) {
        bv[i % 3] = bv[(i - 1) % 3] + bv[(i - 2) % 3];
        v.push_back(bv[i % 3].outN());
    }
    scanf("%d", &T);
    Node* tree = createTree();
    for(i = 0; i < T; ++i) {
        scanf("%s", s);
        n = strlen(s);
        Node* p = tree;
        for(j = 0; j < n; ++j) {
            num = s[j] - '0';
            if(!p->childs[num]) break;
            p = p->childs[num];
        }
        if(j == n) res = p->id;
        else res = -1;
        printf("Case #%d: %d\n", i + 1, res);
    }
    return 0;
}

习题 5-16 医院设备利用（Use of Hospital Facilities, ACM/ICPC World Finals 1991, UVa 212）

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int oproomNum, reroomNum, startTime, transTime, preop, prere, patiNum;
struct Patient {
    char name[105];
    int opTime, reTime;
    int opNum, opBeg, opEnd, reNum, reBeg, reEnd;
};
vector<Patient> v;
struct Room {
    int useTime;
    bool use;
    int endTime;
};
vector<Room> opV;
vector<Room> reV;
// type 说明
// 1 开始 oproom
// -1 准备 oproom
struct PrioItem {
    int time;
    int type;
    int pai;
    int roomi;
    bool operator<(const PrioItem &rhs) const {
        if(time != rhs.time) return time > rhs.time;
        if(type != rhs.type) return type > rhs.type;
        return roomi > rhs.roomi;
    }
};
int pai, timeNow, endTime;
priority_queue<PrioItem> pq;
// 病人开始手术
void useOpNum(int pai, int roomi) {
    PrioItem pi;
    opV[roomi].use = true;
    opV[roomi].useTime += v[pai].opTime;
    opV[roomi].endTime = timeNow + v[pai].opTime + preop;
    v[pai].opNum = roomi;
    v[pai].opBeg = timeNow;
    v[pai].opEnd = timeNow + v[pai].opTime;
    pi.time = v[pai].opEnd;
    pi.type = 1;
    pi.pai = pai;
    pi.roomi = roomi;
    pq.push(pi);
}
void handleN1(PrioItem pi) {
    if(pai >= patiNum) return;
    for(int i = 0; i < opV.size(); ++i) {
        if(opV[i].endTime <= timeNow) useOpNum(pai++, i);
    }
}
void handle1(PrioItem pi) {
    // 转换步骤
    // 转换的时间需要选择指定
    int i, j, k;
    for(i = 0; i < reroomNum; ++i) {
        if(reV[i].endTime <= timeNow) break;
    }
    if(i == reroomNum) {
        // 怎么转？没有恢复室
        return;
    }
    reV[i].useTime += v[pi.pai].reTime;
    v[pi.pai].reNum = i;
    v[pi.pai].reBeg = timeNow + transTime;
    v[pi.pai].reEnd = v[pi.pai].reBeg + v[pi.pai].reTime;
    if(v[pi.pai].reEnd > endTime) endTime = v[pi.pai].reEnd;
    reV[i].endTime = v[pi.pai].reEnd + prere;
    // 准备恢复室
    PrioItem piNew2;
    piNew2.type = -1;
    piNew2.roomi = pi.roomi;
    piNew2.time = timeNow + preop;
    pq.push(piNew2);
}
void oper() {
    int i, j, k;
    timeNow = startTime;
    PrioItem pi;
    for(pai = 0; pai < oproomNum && pai < patiNum; ++pai) useOpNum(pai, pai);
    while(pq.size()) {
        pi = pq.top();
        pq.pop();
        timeNow = pi.time;
        switch(pi.type) {
            case -1: handleN1(pi); break;
            case 1: handle1(pi); break;
        }
    }
    if(pai != patiNum) {
        // 怎么转？没有病人了
        return;
    }
}
void outTime(int t) {
    int hour = t / 60;
    int min = t % 60;
    printf("%2d:%02d", hour, min);
}
void outPatient() {
    printf(" Patient Operating Room Recovery Room\n");
    printf(" # Name Room# Begin End Bed# Begin End\n");
    printf(" ------------------------------------------------------\n");
    int i;
    for(i = 0; i < v.size(); ++i) {
        printf("%2d %-9s %2d ", i + 1, v[i].name, v[i].opNum + 1);
        outTime(v[i].opBeg);
        printf(" ");
        outTime(v[i].opEnd);
        printf(" %2d ", v[i].reNum + 1);
        outTime(v[i].reBeg);
        printf(" ");
        outTime(v[i].reEnd);
        printf("\n");
    }
}
double outUsed(int i, int type) {
    if(endTime == startTime) return 0.0;
    if(type == 0) return (double)opV[i].useTime / (endTime - startTime) * 100;
    if(type == 1) return (double)reV[i].useTime / (endTime - startTime) * 100;
}
void outFac() {
    printf("Facility Utilization\n");
    printf("Type # Minutes %% Used\n");
    printf("-------------------------\n");
    int i;
    for(i = 0; i < opV.size(); ++i) printf("Room %2d %7d %7.2lf\n", i + 1, opV[i].useTime, outUsed(i, 0));
    for(i = 0; i < reV.size(); ++i) printf("Bed %2d %7d %7.2lf\n", i + 1, reV[i].useTime, outUsed(i, 1));
}
int main() {
    int i, j;
    while(scanf("%d%d%d%d%d%d%d", &oproomNum, &reroomNum, &startTime, &transTime, &preop, &prere, &patiNum) == 7) {
        v.clear();
        opV.clear();
        reV.clear();
        pq = priority_queue<PrioItem>();
        startTime = startTime * 60;
        endTime = startTime;
        for(i = 0; i < oproomNum; ++i) {
            Room m;
            m.use = false;
            m.useTime = 0;
            opV.push_back(m);
        }
        for(i = 0; i < reroomNum; ++i) {
            Room m;
            m.use = false;
            m.useTime = 0;
            m.endTime = 0;
            reV.push_back(m);
        }
        for(i = 0; i < patiNum; ++i) {
            Patient p;
            scanf("%s", p.name);
            scanf("%d%d", &p.opTime, &p.reTime);
            v.push_back(p);
        }
        oper();
        outPatient();
        printf("\n");
        outFac();
        printf("\n");
    }
    return 0;
}