## PAT (Advanced Level)-1041. Be Unique (20)

PAT (Advanced Level)-1041. Be Unique (20)

## 1041. Be Unique (20)

100 ms

65536 kB

CHEN, Yue

Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1, 104]. The first one who bets on a unique number wins. For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.

### Input Specification:

Each input file contains one test case. Each case contains a line which begins with a positive integer N (<=105) and then followed by N bets. The numbers are separated by a space.

### Output Specification:

For each test case, print the winning number in a line. If there is no winner, print “None” instead.

### Sample Input 1:

``7 5 31 5 88 67 88 17``

### Sample Output 1:

``31``

### Sample Input 2:

``5 888 666 666 888 888``

### Sample Output 2:

``None``

## 完整代码

``````#include<iostream>
#include<vector>
#include<map>

int main()
{
int N;
std::cin >> N;
std::vector<int> record_num;
std::map<int, int> record_unique;
for (int i = 0; i < N; i++)
{
int num;
std::cin >> num;
record_unique[num]++;
record_num.push_back(num);
}

bool flag_num = false;
int result;
for (int i = 0; i < record_num.size(); i++)
{
if (record_unique[record_num[i]] == 1)
{
flag_num = true;
result = record_num[i];
break;
}
}

if (flag_num == false)
{
std::cout << "None" << std::endl;
}
else
{
std::cout << result << std::endl;
}
return 0;
}``````

## PAT (Advanced Level)-1027. Colors in Mars (20)

PAT (Advanced Level)-1027. Colors in Mars (20)

## 1027. Colors in Mars (20)

400 ms

65536 kB

16000 B

People in Mars represent the colors in their computers in a similar way as the Earth people. That is, a color is represented by a 6-digit number, where the first 2 digits are for Red, the middle 2 digits for Green, and the last 2 digits for Blue. The only difference is that they use radix 13 (0-9 and A-C) instead of 16. Now given a color in three decimal numbers (each between 0 and 168), you are supposed to output their Mars RGB values.

### Input

Each input file contains one test case which occupies a line containing the three decimal color values.

### Output

For each test case you should output the Mars RGB value in the following format: first output “#”, then followed by a 6-digit number where all the English characters must be upper-cased. If a single color is only 1-digit long, you must print a “0” to the left.

### Sample Input

``15 43 71``

### Sample Output

``#123456``

## 完整代码

``````#include<iostream>
#include<string>
#include<cstring>

std::string mars_base[] = { "0","1","2","3","4","5","6","7","8","9","A","B","C" };

std::string transform_to_mars(int n)
{
std::string RGB_mars;
int base = 0, higher = 0;
base = n % 13;
higher = n / 13;

RGB_mars = mars_base[higher] + mars_base[base];

return RGB_mars;
}

int main()
{
int R, G, B;
std::cin >> R >> G >> B;

std::string mR, mG, mB;
mR = transform_to_mars(R);
mG = transform_to_mars(G);
mB = transform_to_mars(B);

std::cout << "#" << mR << mG << mB << std::endl;

return 0;
}``````

## PAT (Advanced Level)-1100. Mars Numbers (20)

PAT (Advanced Level)-1100. Mars Numbers (20)

## 1100. Mars Numbers (20)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

People on Mars count their numbers with base 13:

Zero on Earth is called “tret” on Mars.
The numbers 1 to 12 on Earch is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively. For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.
For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

### Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (< 100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

### Output Specification:

For each number, print in a line the corresponding number in the other language.

### Sample Input:

``````4
29
5
elo nov
tam``````

### Sample Output:

``````hel mar
may
115
13``````

## 完整代码

``````#include<iostream>
#include<string>
#include<sstream>
#include<cstring>
#include<vector>

// [mars_base] records the 0-12 on the mars
std::string mars_base[] = { "tret","jan","feb","mar","apr","may","jun","jly","aug","sep","oct","nov","dec" };
// [mars_higher] records the next higher digit on the mars
std::string mars_higher[] = { "tam","hel","maa","huh","tou","kes","hei","elo","syy","lok","mer","jou" };
//using namespace std;

std::string earth_to_mars(int x)
{
if (x / 13 == 0)// 0-12
{
return mars_base[x];
}
else if (x / 13 != 0 && x%13 == 0)// 13 26 39 ....146 except 0, because 0 is in the [mars_base]
{
return mars_higher[x / 13 - 1];
}
else// the rest of double_digit which uses " "(space)
{
return mars_higher[x / 13 - 1] + " " + mars_base[x % 13];
}
}

int mars_to_earth(std::string x)
{
int num_0 = x.find(" ");// find out whether there is a " "(space) in the string
if (num_0 == std::string::npos)
{
for (int i = 0; i < 13; i++)
{
if (mars_base[i] == x)
{
return i;
}
else if (mars_higher[i] == x)
{
return (i + 1) * 13;
}
}
}
else
{
// to split the string in two with " "(space)
std::string str1, str2;
std::istringstream is(x);
is >> str1 >> str2;

int high=0, base=0;
for (; high < 12; high++)
{
if (str1 == mars_higher[high])
break;
}
for (; base < 13; base++)
{
if (str2 == mars_base[base])
{
break;
}
}
return (high + 1) * 13 + base;
}
}

int main()
{
int N;
std::cin >> N;
getchar();// handle the ENTER in the cin after you input N
std::vector<std::string> input(N);
for (int i = 0; i < N; i++)
{
getline(std::cin,input[i]);
}

for (int j = 0; j < N; j++)
{
if (input[j][0] <= '9' && input[j][0] >= '0') // earth
{
std::cout << earth_to_mars(std::stoi(input[j])) << std::endl;
}
else // mars
{
std::cout << mars_to_earth(input[j]) << std::endl;
}
}
return 0;
}``````

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.

### Input Specification:

Each input file contains one test case. Each case contains a positive integer N (<= 1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.

### Output Specification:

For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line “There are N accounts and no account is modified” where N is the total number of accounts. However, if N is one, you must print “There is 1 account and no account is modified” instead.

### Sample Input 1:

``````3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa``````

### Sample Output 1:

``````2
Team000002 RLsp%dfa
Team000001 R@spodfa``````

### Sample Input 2:

``````1
team110 abcdefg332``````

### Sample Output 2:

``There is 1 account and no account is modified``

### Sample Input 3:

``````2
team110 abcdefg222
team220 abcdefg333``````

### Sample Output 3:

``There are 2 accounts and no account is modified``

## 完整代码

``````#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

typedef struct user
{
bool legal;
char Account[11];
}User_info;

//determind if the password is legal, and modify it if illegal.
bool Is_legal(user& User_info)
{
bool legal = true;

for (int i = 0; i < len; ++i)
{
{
legal = false;
}
{
legal = false;
}
{
legal = false;
}
{
legal = false;
}
}
return legal;
}

int main()
{
int N;
cin >> N;
vector<User_info> User_infoVec(N);

int legal = 0;
for (int i = 0; i < N; ++i)
{
cin >> User_infoVec[i].Account;
if (Is_legal(User_infoVec[i]))
{
User_infoVec[i].legal = true;
legal++;
}
else
{
User_infoVec[i].legal = false;
}
}

//Output
if (legal == N)
{
if (N <= 1)
{
cout << "There is " << N << " account and no account is modified" << endl;
}
else
{
cout << "There are " << N << " accounts and no account is modified" << endl;
}
}
else
{
cout << N - legal << endl;
for (int i = 0; i < N; ++i)
{
if (User_infoVec[i].legal == false)
{
cout << User_infoVec[i].Account << " " << User_infoVec[i].Password << endl;
}
}
}
return 0;
}``````

## PAT (Advanced Level)-1004. Counting Leaves (30)

PAT (Advanced Level)-1004. Counting Leaves (30)

### 1004. Counting Leaves (30)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

Output

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.

Sample Input

``````2 1
01 1 02``````

Sample Output

``0 1``

### 完整代码

``````#include<iostream>
#include<vector>
#include<map>

using namespace std;

map<int, vector<int>> List;

void DFS(int, int, int[]);

int main()
{
int N, M;
int LeavesOfLevel[101] = { 0 };//统计每级上面的叶子节点

//输入部分
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int ID, K, ID_Son;
cin >> ID >> K;
for (int j = 0; j < K; j++)
{
cin >> ID_Son;
List[ID].push_back(ID_Son);
}
}

int Leaves = N - M;//统计总叶子数
//深度优先搜索
DFS(1, 0, LeavesOfLevel);

//输出部分
int LeavesCount = LeavesOfLevel[0];//辅助记录
cout << LeavesOfLevel[0];
for (int i = 1; LeavesCount < Leaves; i++)
{
cout << " " << LeavesOfLevel[i];
LeavesCount += LeavesOfLevel[i];
}

return 0;
}

//深度优先，统计每层级的叶子数
void DFS(int id, int level,int LeavesOfLevel[])
{
if (List[id].empty())
{
LeavesOfLevel[level]++;
return;
}

vector<int>::iterator item = List[id].begin();

for (; item != List[id].end(); item++)
{
DFS(*item, level+1, LeavesOfLevel);
}
}``````