## PAT (Advanced Level)-1019. General Palindromic Number (20)

PAT (Advanced Level)-1019. General Palindromic Number (20)

### 1019. General Palindromic Number (20)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N > 0 in base b >= 2, where it is written in standard notation with k+1 digits ai as the sum of (aibi) for i from 0 to k. Here, as usual, 0 <= ai < b for all i and ak is non-zero. Then N is palindromic if and only if ai = ak-i for all i. Zero is written 0 in any base and is also palindromic by definition.

Given any non-negative decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.

Input Specification:

Each input file contains one test case. Each case consists of two non-negative numbers N and b, where 0 <= N <= 109 is the decimal number and 2 <= b <= 109 is the base. The numbers are separated by a space.

Output Specification:

For each test case, first print in one line “Yes” if N is a palindromic number in base b, or “No” if not. Then in the next line, print N as the number in base b in the form “ak ak-1 … a0”. Notice that there must be no extra space at the end of output.

Sample Input 1:
27 2
Sample Output 1:
Yes
1 1 0 1 1

Sample Input 2:
121 5
Sample Output 2:
No
4 4 1

### 完整代码

``````#include<iostream>

using namespace std;

void OUTPUT(int transArray[], int FLAG)
{
for (int i = FLAG - 1; i >= 0; i--)
{
if (i != 0)
{
cout << transArray[i] << " ";
}
else
cout << transArray[i];
}
if (FLAG == 0)
{
cout << transArray;
}
}

int main()
{
int N, b;
cin >> N >> b;

int transArray;            //数组设置大一些，避免N最大时候，转换2进制时候越界

int FLAG=0;         //标记转换后的数字有多少位
int FLAG_XX = 0;            //标记是否为回文数

if (N == 0)         //输入为0时的特殊处理
{
transArray = N;
}
else            //其他正常输入
{
for (; N; FLAG++)
{
transArray[FLAG] = N%b;
N = N / b;
}

//判断回文，循环次数可以折半
for (int i = FLAG - 1; i >= (int)((FLAG - 1) / 2); i--)
{
if (transArray[i] != transArray[FLAG - 1 - i])
{
FLAG_XX = 1;
}
}
}

//输出
if (FLAG_XX == 0)
{
cout << "Yes" << endl;
OUTPUT(transArray, FLAG);
}
else if (FLAG_XX == 1)
{
cout << "No" << endl;
OUTPUT(transArray, FLAG);
}
return 0;
}``````

## PAT (Advanced Level)-1011. World Cup Betting (20)

PAT (Advanced Level)-1011. World Cup Betting (20)

### 1011. World Cup Betting (20)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.

Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results — namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.

For example, 3 games’ odds are given as the following:

W　T　L

1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1

To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.13.02.5*65%-1)*2 = 37.98 yuans (accurate up to 2 decimal places).

Input

Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.

Output

For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.

Sample Input

``````1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1``````

Sample Output

``T T W 37.98``

### 完整代码

``````#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
double odd;           //记录原始输入数据

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cin >> odd[i][j];

char result;         //存储输出WTL
int signNum = { 0,0,0 };         //标记

for (int i = 0; i < 3; i++)
{
double temp = odd[i];            //大小比较中的临时量

for (int j = 1; j < 3; j++)
{
if (temp <= odd[i][j])
{
temp = odd[i][j];
signNum[i] = j;
}
}
if (signNum[i] == 0)
{
result[i] = 'W';
}
else if (signNum[i] == 1)
{
result[i] = 'T';
}
else if (signNum[i] == 2)
{
result[i] = 'L';
}
}

//计算
double res = (odd[signNum] * odd[signNum] * odd[signNum] * 0.65 - 1.00) * 2.00;

for (int i = 0; i < 3; i++)
cout << result[i] << " ";
cout << fixed << setprecision(2) << res;//这一块我们回到1002题目中，如何限定小数精度并四舍五入。

return 0;
}``````

## PAT (Advanced Level)-1009. Product of Polynomials (25)

PAT (Advanced Level)-1009. Product of Polynomials (25)

### 1009. Product of Polynomials (25)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

``````2 1 2.4 0 3.2
2 2 1.5 1 0.5``````

Sample Output

``3 3 3.6 2 6.0 1 1.6``

### 完整代码

``````#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct Node
{
double sum;
int e;
}Node;
#define MAX 3000
int main()
{
int n1, n2;
cin >> n1;

std::vector<Node> a(n1);
for (int i = 0; i < n1; ++i)
{
cin >> a[i].e;
cin >> a[i].sum;
}

cin >> n2;
std::vector<Node> b(n2);
for (int i = 0; i < n2; ++i)
{
cin >> b[i].e;
cin >> b[i].sum;
}
//product
std::vector<double> p;
p.assign(MAX + 1, 0.0);
for (int i = 0; i < n1; ++i)
{
for (int j = 0; j < n2; ++j)
{
Node tmp;
tmp.e = a[i].e + b[j].e;
tmp.sum = a[i].sum*b[j].sum;
p[tmp.e] += tmp.sum;
}
}
//output
int cnt = 0;
for (int i = MAX; i >= 0; --i)
{
if (std::fabs(p[i]) > 1e-6)
cnt++;
}
printf("%d", cnt);
for (int i = MAX; i >= 0; --i)
{
if (std::fabs(p[i]) > 1e-6)
cout << fixed << setprecision(1) << " " << i << " " << p[i];
}
printf("\n");

return 0;
}``````

## PAT (Advanced Level)-1008. Elevator (20)

PAT (Advanced Level)-1008. Elevator (20)

### 1008. Elevator (20)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.

For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100.

Output Specification:

For each test case, print the total time on a single line.

Sample Input:

``3 2 3 1``

Sample Output:

``41``

### 完整代码

``````#include<iostream>
using namespace std;

int main()
{
int N;
cin >> N;
int now = 0, next = 0, totalTime = 0;
while (N--)
{
cin >> next;
if (next > now)
{
totalTime += (next - now) * 6 + 5;
}
else
{
totalTime += (now - next) * 4 + 5;
}
now = next;
}
cout << totalTime;
return 0;
}``````

## PAT (Advanced Level)-1006. Sign In and Sign Out (25)

### 1006. Sign In and Sign Out (25)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

ID_number Sign_in_time Sign_out_time where times are given in the format HH:MM:SS, and ID number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.
Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

``````3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40``````

Sample Output:

``SC3021234 CS301133``

### 完整代码

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

using namespace std;

//创建结构体，来存储每次输入的员工记录ID和登入时间和登出时间
struct Record
{
char id;
string signInTime;
string signOutTime;
};

int main()
{
//题目中要求的变量M
int M;
cin >> M;

//动态申请大小为M的结构体数组（数组的每个元素都是一个结构体）
Record *recordList = new Record[M];

//标记开门和关门的ID
int unlockID=0, lockID=0;

//比较大小时的临时变量
string unlock, lock;

//输入和比较同时进行
for (int i = 0; i < M; i++)
{
cin >> recordList[i].id;
cin >> recordList[i].signInTime;
cin >> recordList[i].signOutTime;

//初次赋值时候，初始化用来比较大小的临时量
if (i == 0)
{
unlock = recordList[i].signInTime;
lock = recordList[i].signOutTime;
}

//比较开门时间
if (unlock > recordList[i].signInTime)
{
unlock = recordList[i].signInTime;
unlockID = i;
}

//比较关门时间
if (lock < recordList[i].signOutTime)
{
lock = recordList[i].signOutTime;
lockID = i;
}
}

cout << recordList[unlockID].id << " " << recordList[lockID].id;

return 0;
}``````