liuchuo – 第5页 – 柳婼の blog

1113 钱串子的加法 – PAT乙级真题

人类习惯用 10 进制，可能因为大多数人类有 10 根手指头，可以用于计数。这个世界上有一种叫“钱串子”（学名“蚰蜒”）的生物，有 30 只细长的手/脚，在它们的世界里，数字应该是 30 进制的。本题就请你实现钱串子世界里的加法运算。

输入格式：

输入在一行中给出两个钱串子世界里的非负整数，其间以空格分隔。

所谓“钱串子世界里的整数”是一个 30 进制的数字，其数字 0 到 9 跟人类世界的整数一致，数字 10 到 29 用小写英文字母 a 到 t 顺次表示。

输入给出的两个整数都不超过 10^5 位。

输出格式：

在一行中输出两个整数的和。注意结果数字不得有前导零。

输入样例：

2g50ttaq 0st9hk381

输出样例：

11feik2ir

分析：将两个钱串子货币分别存储在string类型的a和b中，最后的答案存储在ans中。使用num_a、num_b分别储存a、b某一位对应十进制下的数。now为相加过程中的和，jin表示当前的进位。index作为最后输出答案时的下标。首先让a和b数位相等，这里可以让a更短（或相等），如果a的长度大于b的长度，就交换他们。同时，在a前面补上他们长度相差数的’0’，让位数对齐，方便计算。string c(n,’0′)表示创建一个长度为c，全部是’0’字符的字符串c。从右向左让a、b中对应的每一位相加，注意每一次还要加上进位。我们需要先将字符转换成对应的十进制数，如果当前的字符在’1’到’9’之间，那么直接将当前字符减’0’就可以得到我们要的数字，否则，要将当前字符减去’a’再加上10。使用模运算(%30)得到当前位数上应该存什么数字now，使用除法运算(/30)可以得到我们的进位jin。再把now转换成三十进制的字符，保存在ans的对应位置。
结束遍历后，如果还有进位，则在ans的左边在加一个’1’。接下来去除前导0，使用while循环，找到第一个ans内的值不等于0的下标。可以让index的值小于ans的长度-1，可以保证如果全是0的数相加，至少会保留一个零。最后从index到最后就是我们的答案啦。

#include <iostream>
using namespace std;
string a, b, ans;
int num_a, num_b, now, jin, index;
int main(){
    cin >> a >> b;
    if(a.size() > b.size()) swap(a, b);
    string c(b.size() - a.size(), '0');
    a = c + a;
    ans.resize(a.size());
    for (int i = b.size() - 1; i >= 0; i--) {
        if (a[i] >= '0' && a[i] <= '9') num_a = a[i] - '0';
        else num_a = a[i] - 'a' + 10;
        if (b[i] >= '0' && b[i] <= '9') num_b = b[i] - '0';
        else num_b = b[i] - 'a' + 10;
        now = (num_a + num_b + jin) % 30;
        jin = (num_a + num_b + jin) / 30;
        if(now < 10) ans[i] = (char)(now + '0');
        else ans[i] = (char)(now - 10 + 'a');
    }
    if (jin) ans = "1" + ans;
    while(index < ans.size() - 1 && ans[index] == '0') ++index;
    while(index < ans.size()) cout << ans[index++];
    return 0;
}

#include <iostream>

using namespace std;

string a, b, ans;

int num_a, num_b, now, jin, index;

int main(){

cin >> a >> b;

if(a.size() > b.size()) swap(a, b);

string c(b.size() - a.size(), '0');

a = c + a;

ans.resize(a.size());

for (int i = b.size() - 1; i >= 0; i--) {

if (a[i] >= '0' && a[i] <= '9') num_a = a[i] - '0';

else num_a = a[i] - 'a' + 10;

if (b[i] >= '0' && b[i] <= '9') num_b = b[i] - '0';

else num_b = b[i] - 'a' + 10;

now = (num_a + num_b + jin) % 30;

jin = (num_a + num_b + jin) / 30;

if(now < 10) ans[i] = (char)(now + '0');

else ans[i] = (char)(now - 10 + 'a');

}

if (jin) ans = "1" + ans;

while(index < ans.size() - 1 && ans[index] == '0') ++index;

while(index < ans.size()) cout << ans[index++];

return 0;

}

1112 超标区间- PAT乙级真题

上图是用某科学研究中采集的数据绘制成的折线图，其中红色横线表示正常数据的阈值（在此图中阈值是 25）。你的任务就是把超出阈值的非正常数据所在的区间找出来。例如上图中横轴 [3, 5] 区间中的 3 个数据点超标，横轴上点 9 （可以表示为区间 [9, 9]）对应的数据点也超标。

输入格式：

输入第一行给出两个正整数 N（≤10^4）和 T（≤100），分别是数据点的数量和阈值。第二行给出 N 个数据点的纵坐标，均为不超过 1000 的正整数，对应的横坐标为整数 0 到 N−1。

输出格式：

按从左到右的顺序输出超标数据的区间，每个区间占一行，格式为 [A, B]，其中 A 和 B 为区间的左右端点。如果没有数据超标，则在一行中输出所有数据的最大值。

输入样例 1：

11 25
21 15 25 28 35 27 20 24 18 32 23

输出样例 1：

[3, 5]
[9, 9]

输入样例 2：

11 40
21 15 25 28 35 27 20 24 18 32 23

输出样例 2：

分析：使用maxn保存最大的数，数组A存储输入的数据。通过遍历找出超出部分的范围。如果当前这个数字小于等于T，就可以跳过这次的循环。大于T的话，就找一下当前超出部分的区间。使用end记录区间的右端点，使用while语句，当下一个数（下标为end+1）还在范围内并且下一个数也大于T的时候，就让end+1。然后按格式输出当前超出的区间[i,end]。使用maxn是否大于T来判断是否有数据超标。

#include <iostream>
using namespace std;
int N, T, maxn, A[10005];
int main(){
    cin >> N >> T;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        maxn = max(maxn, A[i]);
        if (A[i] <= T) continue;
        int end = i;
        while(end + 1 < N && A[end + 1] > T) ++end;
        cout << "[" << i << ", " << end << "]\n";
        i = end;
    }
    if (maxn <= T) cout << maxn;
    return 0;
}

#include <iostream>

using namespace std;

int N, T, maxn, A[10005];

int main(){

cin >> N >> T;

for (int i = 0; i < N; i++) cin >> A[i];

for (int i = 0; i < N; i++) {

maxn = max(maxn, A[i]);

if (A[i] <= T) continue;

int end = i;

while(end + 1 < N && A[end + 1] > T) ++end;

cout << "[" << i << ", " << end << "]\n";

i = end;

}

if (maxn <= T) cout << maxn;

return 0;

}

1111 对称日- PAT乙级真题

央视新闻发了一条微博，指出 2020 年有个罕见的“对称日”，即 2020 年 2 月 2 日，按照 年年年年月月日日 格式组成的字符串 20200202 是完全对称的。

给定任意一个日期，本题就请你写程序判断一下，这是不是一个对称日？

输入格式：

输入首先在第一行给出正整数 N（1<N≤10）。随后 N 行，每行给出一个日期，却是按英文习惯的格式：Month Day, Year。其中 Month 是月份的缩写，对应如下：

一月：Jan
二月：Feb
三月：Mar
四月：Apr
五月：May
六月：Jun
七月：Jul
八月：Aug
九月：Sep
十月：Oct
十一月：Nov
十二月：Dec

Day 是月份中的日期，为 [1, 31] 区间内的整数；Year 是年份，为 [1, 9999] 区间内的整数。

输出格式：

对每一个给定的日期，在一行中先输出 Y 如果这是一个对称日，否则输出 N；随后空一格，输出日期对应的 年年年年月月日日 格式组成的字符串。

输入样例：

5
Feb 2, 2020
Mar 7, 2020
Oct 10, 101
Nov 21, 1211
Dec 29, 1229

输出样例：

Y 20200202
N 20200307
Y 01011010
Y 12111121
N 12291229

分析：使用字符串M、D、Y分别保存题目输入的月、日、年，日后面会有一个多余的逗号，这里用erase把它擦掉。如果位数不足，则在前面补’0’。使用final保存最后的年份。使用symmetry为”Y”表示是对成日，为”N”表示不是对称日。使用map<string,sintrg> A将月份由英文缩写映射成数字。最后再通过判断前半部分的每个数字和后半部分对应的数字是不是一样的，得出它是不是一个对称数，就可以啦～

#include <iostream>
#include <map>
using namespace std;
int t;
string M, D, Y, final, symmetry;
map<string,string> A = {{"Jan", "01"}, {"Feb", "02"}, {"Mar", "03"}, {"Apr", "04"}, {"May", "05"}, {"Jun", "06"}, {"Jul", "07"}, {"Aug", "08"}, {"Sep", "09"}, {"Oct", "10"}, {"Nov", "11"}, {"Dec","12"}};
int main(){
    for (cin >> t; t; t--) {
        cin >> M >> D >> Y;
        D.erase(D.end() - 1);
        M = A[M];
        if(D.size() == 1) D = "0" + D;
        while(Y.size() < 4) Y = "0" + Y;
        final = Y + M + D;
        symmetry = "Y";
        for (int i = 0; i < 4; i++) {
            if(final[i] != final[8 - i - 1]) {
                symmetry = "N";
                break;
            }
        }
        cout << symmetry << ' ' << final << '\n';
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int t;

string M, D, Y, final, symmetry;

map<string,string> A = {{"Jan", "01"}, {"Feb", "02"}, {"Mar", "03"}, {"Apr", "04"}, {"May", "05"}, {"Jun", "06"}, {"Jul", "07"}, {"Aug", "08"}, {"Sep", "09"}, {"Oct", "10"}, {"Nov", "11"}, {"Dec","12"}};

int main(){

for (cin >> t; t; t--) {

cin >> M >> D >> Y;

D.erase(D.end() - 1);

M = A[M];

if(D.size() == 1) D = "0" + D;

while(Y.size() < 4) Y = "0" + Y;

final = Y + M + D;

symmetry = "Y";

for (int i = 0; i < 4; i++) {

if(final[i] != final[8 - i - 1]) {

symmetry = "N";

break;

}

cout << symmetry << ' ' << final << '\n';

}

return 0;

}

L2-048 寻宝图-PAT团体程序设计天梯赛GPLT

给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。

输入格式：

输入第一行给出 2 个正整数 N 和 M（1<N×M≤10^5），是地图的尺寸，表示地图由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 0 表示水域，1 表示陆地，2–9 表示宝藏。
注意：两个格子共享一条边时，才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。

输出格式：

在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。

输入样例：

10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001

输出样例：

7 2

分析：这是一道BFS应用题。island中存储一共有多少座岛屿，precious中存储有宝藏的岛屿数量。用p标记每座岛屿是否有宝藏，XN与NY数组为上下左右走动的控制数组。将地图信息存储在string字符数组A中，Q存储的是坐标信息。
遍历每一个点，如果该点不为0的话，就进入它。不断向上下左右可以连接的岛屿进军，如果某个岛屿有宝藏，则将p标记成1，进军过的岛屿可以把它修改成’0’，后续就不会重复访问。

#include <iostream>
#include <queue>
using namespace std;
int N, M, island, precious, p, NX[4] = {1, -1, 0, 0}, NY[4] = {0, 0, 1, -1};
string A[100005];
queue<pair<int,int>> Q;
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (A[i][j] != '0') {
                ++island;
                Q.push({i, j});
                p = 0;
                if(A[i][j] >= '2') p = 1;
                A[i][j] = '0';
                while(Q.size()) {
                    int nowx = Q.front().first, nowy = Q.front().second;
                    Q.pop();
                    for (int k = 0; k < 4; k++) {
                        int X = nowx + NX[k], Y = nowy + NY[k];
                        if(X >= 0 && X < N && Y >= 0 && Y < M && A[X][Y] >= '1') {
                            if(A[X][Y] >= '2') p = 1;
                            Q.push({X, Y});
                            A[X][Y] = '0';
                        }
                    }
                }
                if(p) ++precious;
            }
        }
    cout << island << ' ' << precious;
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int N, M, island, precious, p, NX[4] = {1, -1, 0, 0}, NY[4] = {0, 0, 1, -1};

string A[100005];

queue<pair<int,int>> Q;

int main() {

cin >> N >> M;

for (int i = 0; i < N; i++) cin >> A[i];

for (int i = 0; i < N; i++)

for (int j = 0; j < M; j++) {

if (A[i][j] != '0') {

++island;

Q.push({i, j});

p = 0;

if(A[i][j] >= '2') p = 1;

A[i][j] = '0';

while(Q.size()) {

int nowx = Q.front().first, nowy = Q.front().second;

Q.pop();

for (int k = 0; k < 4; k++) {

int X = nowx + NX[k], Y = nowy + NY[k];

if(X >= 0 && X < N && Y >= 0 && Y < M && A[X][Y] >= '1') {

if(A[X][Y] >= '2') p = 1;

Q.push({X, Y});

A[X][Y] = '0';

}

if(p) ++precious;

}

cout << island << ' ' << precious;

return 0;

}

L2-047 锦标赛-PAT团体程序设计天梯赛GPLT

有 2k 名选手将要参加一场锦标赛。锦标赛共有 k 轮，其中第 i 轮的比赛共有 2k−i 场，每场比赛恰有两名选手参加并从中产生一名胜者。每场比赛的安排如下：

对于第 1 轮的第 j 场比赛，由第 (2j−1) 名选手对抗第 2j 名选手。
对于第 i 轮的第 j 场比赛（i>1），由第 (i−1) 轮第 (2j−1) 场比赛的胜者对抗第 (i−1) 轮第 2j 场比赛的胜者。

第 k 轮唯一一场比赛的胜者就是整个锦标赛的最终胜者。
举个例子，假如共有 8 名选手参加锦标赛，则比赛的安排如下：

第 1 轮共 4 场比赛：选手 1 vs 选手 2，选手 3 vs 选手 4，选手 5 vs 选手 6，选手 7 vs 选手 8。
第 2 轮共 2 场比赛：第 1 轮第 1 场的胜者 vs 第 1 轮第 2 场的胜者，第 1 轮第 3 场的胜者 vs 第 1 轮第 4 场的胜者。
第 3 轮共 1 场比赛：第 2 轮第 1 场的胜者 vs 第 2 轮第 2 场的胜者。

已知每一名选手都有一个能力值，其中第 i 名选手的能力值为 ai。在一场比赛中，若两名选手的能力值不同，则能力值较大的选手一定会打败能力值较小的选手；若两名选手的能力值相同，则两名选手都有可能成为胜者。

令 li,j 表示第 i 轮第 j 场比赛败者的能力值，令 w 表示整个锦标赛最终胜者的能力值。给定所有满足 1≤i≤k 且 1≤j≤2k−i 的 li,j 以及 w，请还原出 a1,a2,⋯,an。

输入格式:

第一行输入一个整数 k（1≤k≤18）表示锦标赛的轮数。
对于接下来 k 行，第 i 行输入 2k−i 个整数 li,1,li,2,⋯,li,2k−i（1≤li,j≤10^9），其中 li,j 表示第 i 轮第 j 场比赛败者的能力值。
接下来一行输入一个整数 w（1≤w≤10^9）表示锦标赛最终胜者的能力值。

输出格式:

输出一行 n 个由单个空格分隔的整数 a1,a2,⋯,an，其中 ai 表示第 i 名选手的能力值。如果有多种合法答案，请输出任意一种。如果无法还原出能够满足输入数据的答案，输出一行 No Solution。
请勿在行末输出多余空格。

输入样例1:

3
4 5 8 5
7 6
8
9

输出样例1:

7 4 8 5 9 8 6 5

输入样例2:

2
5 8
3
9

输出样例2:

No Solution

提示:

本题返回结果若为格式错误均可视为答案错误。

分析：整体可以看成一个反过来的满二叉树。ans为数组中存储始参赛选手的能力值，lost[i][j]中存储第i轮第j场内失败的选手最大的能力值，win[i][j]存储第i轮第j场赢的人在ans数组中的下标。
第一轮时，两个人一组，就是说对应0场编号为0、1的人一组，第1场编号为2、3的人一组，第2场编号为4、5的人一组。第j场对应的左边和右边的人的下标就是j*2和j*2+1，可以使用j<<1和j<<1|1来表示。对于第一轮，我们选择将败者的能力值放在左边，那么应该把lost[i][j]存在对应ans数组的j<<1的位置上，win[i][j]则需要存j<<1|1（两个人中右边的那一个）。
对于其它轮次，我们要从前两场的比赛中选择一个人作为当前的败者。上一轮两位落败的选手的能力值分别为lost[i-1][j<<1]以及lost[i-1][j<<1|1]，对应胜者的能力值应该大于或等于他们，那么上一轮中某场次相对应的胜者的能力值至少与败者相等.我们只需要将当前败者的能力值，与上一轮两名败者的能力值进行比较，当前败者能力值大于或等于其中任意一方，就可以说当前败者的能力值是上一轮这一方胜者的能力值。同时记录一下这一轮胜者的下标信息。
如果上一轮落败的两个人的能力值都比现在这一轮落败的大，则输出不可能。还需要注意一下，是不是上一轮某一个败者的的能力值会比这一轮败者的能力值大，我们需要把之前最大的败者的能力值更新到当前项，他就是我们这里条路走上来，能力值最大的那个败者，同时我们当前的胜者能力值应该大于等于他。
最后还要判断一下最终冠军的能力值是不是比其它人的能力值都大，只要和最后一个败者作比较就可以了，因为他已经是之前所有败者里能力值最大的那个人了。如果是的话，把冠军的能力值也加入到ans里，最后输出ans就可以~

#include <iostream>
using namespace std;
int k, w, lost[19][1 << 18], win[19][1 << 18], ans[1 << 18];
int main() {
    cin >> k;
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < (1 << (k - i)); j++) {
            cin >> lost[i][j];
            if (i == 1) {
                ans[j << 1] = lost[i][j];
                win[i][j] = j << 1 | 1;
            } else {
                if (lost[i][j] < lost[i - 1][j << 1] && lost[i][j] < lost[i - 1][j << 1 | 1]) {
                    cout << "No Solution";
                    return 0;
                } else if (lost[i][j] >= lost[i - 1][j << 1]) {
                    ans[win[i - 1][j << 1]] = lost[i][j];
                    win[i][j] = win[i - 1][j << 1 | 1];
                } else {
                    ans[win[i - 1][j << 1 | 1]] = lost[i][j];
                    win[i][j] = win[i - 1][j << 1];
                }
                lost[i][j] = max(lost[i][j], max(lost[i - 1][j << 1], lost[i - 1][j << 1 | 1])); 
            }
        }
    }
    cin >> w;
    if(lost[k][0] > w) {
        cout << "No Solution";
        return 0;
    }
    ans[win[k][0]] = w;
    for (int i = 0; i < 1 << k; i++) {
        if (i) cout << ' ';
        cout << ans[i] ;
    }
    return 0;
}

#include <iostream>

using namespace std;

int k, w, lost[19][1 << 18], win[19][1 << 18], ans[1 << 18];

int main() {

cin >> k;

for (int i = 1; i <= k; i++) {

for (int j = 0; j < (1 << (k - i)); j++) {

cin >> lost[i][j];

if (i == 1) {

ans[j << 1] = lost[i][j];

win[i][j] = j << 1 | 1;

} else {

if (lost[i][j] < lost[i - 1][j << 1] && lost[i][j] < lost[i - 1][j << 1 | 1]) {

cout << "No Solution";

return 0;

} else if (lost[i][j] >= lost[i - 1][j << 1]) {

ans[win[i - 1][j << 1]] = lost[i][j];

win[i][j] = win[i - 1][j << 1 | 1];

} else {

ans[win[i - 1][j << 1 | 1]] = lost[i][j];

win[i][j] = win[i - 1][j << 1];

}

lost[i][j] = max(lost[i][j], max(lost[i - 1][j << 1], lost[i - 1][j << 1 | 1]));

}

cin >> w;

if(lost[k][0] > w) {

cout << "No Solution";

return 0;

}

ans[win[k][0]] = w;

for (int i = 0; i < 1 << k; i++) {

if (i) cout << ' ';

cout << ans[i] ;

}

return 0;

}

L2-046 天梯赛的赛场安排-PAT团体程序设计天梯赛GPLT

天梯赛使用 OMS 监考系统，需要将参赛队员安排到系统中的虚拟赛场里，并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们，以便发放比赛账号。为了尽可能减少教练和监考的沟通负担，我们要求赛场的安排满足以下条件：

每位监考老师负责的赛场里，队员人数不得超过赛场规定容量 C；
每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练，且每个赛场的监考老师都不相同。

为此我们设计了多轮次排座算法，按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n：

如果 n≥C，则新开一个赛场，将 C 位队员安排进去。剩下的人继续按人数规模排队，等待下一轮处理；
如果 n<C，则寻找剩余空位数大于等于 n 的编号最小的赛场，将队员安排进去；
如果 n<C，且找不到任何非空的、剩余空位数大于等于 n 的赛场了，则新开一个赛场，将队员安排进去。

由于近年来天梯赛的参赛人数快速增长，2023年超过了 480 所学校 1.6 万人，所以我们必须写个程序来处理赛场安排问题。

输入格式：

输入第一行给出两个正整数 N 和 C，分别为参赛学校数量和每个赛场的规定容量，其中 0<N≤5000，10≤C≤50。随后 N 行，每行给出一个学校的缩写（为长度不超过 6 的非空小写英文字母串）和该校参赛人数（不超过 500 的正整数），其间以空格分隔。题目保证每所学校只有一条记录。

输出格式：

按照输入的顺序，对每一所参赛高校，在一行中输出学校缩写和该校需要联系的监考人数，其间以 1 空格分隔。
最后在一行中输出系统中应该开设多少个赛场。

输入样例：

10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20

输出样例：

zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16

分析：Q中存储待排考场学校的名字和剩余待排人数，人数少的在前面。Uni数组储存第i个学校叫什么名字。room数组存储第i个数组还能坐下多少个人，num表示当前处理的学校还需要几个座位。Num中存储对应学校需要排几个考场。r表示总共需要几个考场，f用来标记现在待排的人能不能插入到现有的空位足够的教室里。
每次去出待排学校里待排人数最少的那一个。如果待排人数大于等于容量C，则需要安排一间全新的考场。如果不等于容量C的话，需要把学校连着剩余待排人数重新插回到优先队列Q里。否则查询所有已有考场是否有哪一间空余作为大于现在待排人数，有的话就在这间考，没有的话就新开一间，并更新一下新考场空余作为数。

#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
priority_queue<pair<int, string>> Q;
int N, C, t, room[500000], r, num, f;
map<string, int> Num;
vector<string> Uni(5005);
int main() {
    cin >> N >> C;
    for (int i = 1; i <= N; i++) {
        cin >> Uni[i] >> t;
        Q.push({t, Uni[i]});
    }
    while(Q.size()) {
        string SN = Q.top().second;
        num = Q.top().first;
        Q.pop();
        Num[SN]++;
        if (num >= C) {
            room[++r] = 0;
            if(num != C) Q.push({num - C, SN});
        } else {
            f = 0;
            for (int i = 1; i <= r; i++) {
                if (room[i] >= num) {
                    room[i] -= num;
                    f = 1;
                    break;
                }
            }
            if (!f) {
                room[++r] = C - num;
            }
        }
    }
    for (int i = 1; i <= N; i++) cout << Uni[i] << ' ' << Num[Uni[i]] << '\n';
    cout << r;
    return 0;
}

#include <iostream>

#include <queue>

#include <map>

#include <string>

using namespace std;

priority_queue<pair<int, string>> Q;

int N, C, t, room[500000], r, num, f;

map<string, int> Num;

vector<string> Uni(5005);

int main() {

cin >> N >> C;

for (int i = 1; i <= N; i++) {

cin >> Uni[i] >> t;

Q.push({t, Uni[i]});

}

while(Q.size()) {

string SN = Q.top().second;

num = Q.top().first;

Q.pop();

Num[SN]++;

if (num >= C) {

room[++r] = 0;

if(num != C) Q.push({num - C, SN});

} else {

f = 0;

for (int i = 1; i <= r; i++) {

if (room[i] >= num) {

room[i] -= num;

f = 1;

break;

}

if (!f) {

room[++r] = C - num;

}

for (int i = 1; i <= N; i++) cout << Uni[i] << ' ' << Num[Uni[i]] << '\n';

cout << r;

return 0;

}