Codeforces Round #603 (Div. 2) B. PIN Codes 水题
B. PIN Codes
A PIN code is a string that consists of exactly 4 digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.
Polycarp has n (2≤n≤10) bank cards, the PIN code of the i-th card is pi.
Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all n codes would become different.
Formally, in one step, Polycarp picks i-th card (1≤i≤n), then in its PIN code pi selects one position (from 1 to 4), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.
Polycarp quickly solved this problem. Can you solve it?
Input
The first line contains integer t (1≤t≤100) — the number of test cases in the input. Then test cases follow.
The first line of each of t test sets contains a single integer n (2≤n≤10) — the number of Polycarp's bank cards. The next n lines contain the PIN codes p1,p2,…,pn — one per line. The length of each of them is 4. All PIN codes consist of digits only.
Output
Print the answers to t test sets. The answer to each set should consist of a n+1 lines
In the first line print k — the least number of changes to make all PIN codes different. In the next n lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.
Example
input
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139
output
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139
题意
给了你n个4位数的pin code,你每次可以修改一个数的一个位置,问你最少修改多少次,可以使得每个数都不一样。
题解
视频题解 https://www.bilibili.com/video/av77514280/
数据范围最多为10,所以每个pin code最多修改一个位置就可以了,我们首先给所有字符串标记出现过没有,重复的就把他修改成没有出现过的位置。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
string s[15];
int n,ans;
map<string,int>H;
void change(int x){
H[s[x]]--;
for(int i=0;i<s[x].size();i++){
char ori = s[x][i];
for(int j=0;j<10;j++){
char c = '0'+j;
s[x][i]=c;
if(!H[s[x]]){
ans++;
H[s[x]]=1;
return;
}
}
s[x][i]=ori;
}
}
void solve(){
H.clear();
ans = 0;
cin>>n;
for(int i=0;i<n;i++){
cin>>s[i];
H[s[i]]++;
}
//sort(s,s+n);
for(int i=0;i<n;i++){
if(H[s[i]]>1){
change(i);
}
}
cout<<ans<<endl;
for(int i=0;i<n;i++){
cout<<s[i]<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
最新文章
- 通用数据库操作类,前端easyui-datagrid,form
- Qt 窗口等设置
- BZOJ 2818GCD
- javascript DOM对象转jquery对象
- WEB服务器1--开篇
- MySql命令——show,分页,正则表达式
- DataGridView常用功能
- mysql密码忘记如何处理
- IIS8中添加WCF支持几种方法小结[图文]
- El表达式取map值
- 简单的一句sql
- JSP的内置对象以及作用域。
- 基于Twitter的Snowflake算法实现分布式高效有序ID生产黑科技(无懈可击)
- [2019BUAA人工智能实战_陈泽寅]第1次个人作业
- java课程课后作业190425之一维数组最大子数组(界面实现)
- mfc简单框架的分析和原理记录
- Linux 线程编程2.0——线程同步-互斥锁
- Java中终止线程的三种方法
- 回文日期(NOIP2016)
- 【BZOJ1304】[CQOI2009]叶子的染色(动态规划)