PAT (Advanced Level)-1015. Reversible Primes (20)

PAT (Advanced Level)-1015. Reversible Primes (20)

##1015. Reversible Primes (20)
时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue


A reversible prime in any number system is a prime whose “reverse” in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (< 105) and D (1 < D <= 10), you are supposed to tell if N is a reversible prime with radix D.


Input Specification:

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

Output Specification:

For each test case, print in one line “Yes” if N is a reversible prime with radix D, or “No” if not.

Sample Input:

73 10
23 2
23 10
-2

Sample Output:

Yes
Yes
No

解读

考查进制转换和数字反转。

注意函数

int number_reverse(int num, int basic)

实现了反转和转化。

完整代码

#include<iostream>

using namespace std;

int number_reverse(int num, int basic)
{
	int num_2 = 0;
	for (; num;)
	{
		num_2 *= basic;
		num_2 += num%basic;
		num /= basic;
	}
	return num_2;
}

bool is_Prime(int num)
{
	if (num < 2)
		return false;
	else if (num == 2 || num == 3)
		return true;
	else
	{
		for (int i = 2; i*i <= num; i++)
		{
			if (num%i == 0)
				return false;
		}
		return true;
	}
}

int main()
{
	int N = 0;
	for (;;) 
	{
		cin >> N;
		if (N < 0)
			break;
		int D;
		cin >> D;
		if (is_Prime(N) && is_Prime(number_reverse(N, D)))
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}

	}
	return 0;
}

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

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

1041. Be Unique (20)

时间限制
100 ms
内存限制
65536 kB
代码长度限制 16000 B
判题程序 Standard
作者
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

解读

遍历寻找重复。 用map的捆绑对应,可以将一个数字和它本身出现的次数绑定起来。减少搜索量。

完整代码

#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
判题程序 Standard
作者 CHEN, Yue


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

解读

单纯的一道十进制转换十三进制的题目。而且十三进制下不超过两位数。
进制转换的方式不做累述,PAT (Advanced Level)-1019. General Palindromic Number (20)的解读部分。

由于只有两位数的十三进制数,且有ABC这样的字符出现,所以最终我选择使用string字符串处理所有的火星数,0-9,A-C全部存入mars_base中直接做返回调用。可以减少此题中的额外处理。

完整代码

#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

解读

本题实际上是一道进制转换的问题,13进制。麻烦之处在于,mars数字需要用字符串来表示,所以应该做好转化进制时的数字和字符串的对应。
另外就是输出格式 火星数的整两位数,后面没有空格,所以对于整两位数和其他两位数需要区分处理。

完整代码

#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;
}

PAT (Advanced Level)-1035. Password (20)

PAT (Advanced Level)-1035. Password (20)

1035. Password (20)

时间限制
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

解读

本题目考查点在于对字符串的检索处理,同时也考查对于输入数据的保存。
易忽视的地方: C++中,开数组存储的数组大小,cin缓冲流存在 特殊情况N=0的时候。

另外想吐槽的一句是:这个输出结束之后为什么没有句号啊!!我带了句号为什么还对了三个检查点!!!害我检查问题查了好久才注意到句末不带标点的!!!!

完整代码

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

using namespace std;

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

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

	for (int i = 0; i < len; ++i)
	{
		if (User_info.Password[i] == '1')
		{
			User_info.Password[i] = '@';
			legal = false;
		}
		if (User_info.Password[i] == '0')
		{
			User_info.Password[i] = '%';
			legal = false;
		}
		if (User_info.Password[i] == 'l')
		{
			User_info.Password[i] = 'L';
			legal = false;
		}
		if (User_info.Password[i] == 'O')
		{
			User_info.Password[i] = 'o';
			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;
		cin >> User_infoVec[i].Password;
		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;
}