Test A
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
‘X’: a block of wall, which the doggie cannot enter;
‘S’: the start point of the doggie;
‘D’: the Door; or
‘.’: an empty block.
The input is terminated with three 0’s. This test case is not to be processed.
Output
For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.
Sample Input
4 4 5
S.X.
…X.
…XD
…
3 4 5
S.X.
…X.
…D
0 0 0
Sample Output
NO
YES
用到的知识点是DFS，暂时没学过，跳过
Test B
The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.
For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and also the digital root of 39.
Input
The input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero.
Output
For each integer in the input, output its digital root on a separate line of the output.
Sample Input
24
39
0
Sample Output
6
3
#include<iostream>
#include<cstring>
using namespace std;
char number[1000 + 5];
int main() {
memset(number, '\0', sizeof(number));
while (scanf("%s", number)) {
if (!strcmp(number, "0")) {
break;
}
int i;
int sum = 0;
for (i = 0; i < strlen(number); i++) {
sum += number[i] - '0';
}
while (sum >= 10) {
memset(number, '\0', sizeof(number));
int temp = sum;
int j = 0;
do {
int d = temp % 10;
number[j++] ='0'+d;
temp /= 10;
} while (temp > 0);
sum = 0;
for (i = 0; i < strlen(number); i++) {
sum += number[i] - '0';
}
}
if (sum < 10) {
printf("%d\n", sum);
}
}
}
一次性AC，重点在于用字符数组保存大数，题目本身不难
Test C
Given a string containing only ‘A’ - ‘Z’, we could encode it using the following method:
-
Each sub-string containing k same characters should be encoded to “kX” where “X” is the only character in this sub-string.
-
If the length of the sub-string is 1, ‘1’ should be ignored.
Input
The first line contains an integer N (1 <= N <= 100) which indicates the number of test cases. The next N lines contain N strings. Each string consists of only ‘A’ - ‘Z’ and the length is less than 10000.
Output
For each test case, output the encoded string in a line.
Sample Input
2
ABC
ABBCCC
Sample Output
ABC
A2B3C
#include<iostream>
#include<cstring>
using namespace std;
int main() {
int N;
char str[10000 + 5];
scanf("%d", &N);
getchar();
while (N--) {
memset(str, '\0', sizeof(str));
gets(str);
int length = strlen(str);
int i;
int count = 1;
for (i = 0; i < length; i++) {
if (str[i + 1] == str[i]) {
count++;
}
else {
if (count == 1) {
printf("%c", str[i]);
}
else {
printf("%d%c", count, str[i]);
}
count = 1;
}
}
printf("\n");
}
return 0;
}
错误原因：题目中问的是连续相同字母的个数，不是整个串中相同的个数
Test D
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).
Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
Output
Print the word “yes” if 3 divide evenly into F(n).
Print the word “no” if not.
Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no
#include<iostream>
using namespace std;
int main() {
int a[9],b[9];//b数组专门存放余数
a[0] = 7, a[1] = 11;
b[0] = 7 % 3, b[1] = 11 % 3;
for (int i = 2; i <= 8; i++) {//这个没办法，只能自己通过测试找，周期为8，所以数组只需要长度为8
a[i] = a[i - 1] + a[i - 2];
b[i] = a[i] % 3;
}
int n;
while (scanf("%d", &n) != EOF) {
if (b[n % 8] == 0) {
printf("yes\n");
}
else {
printf("no\n");
}
}
}
这种题目前为了防止内存过大，通过余数的周期性做题，可以大幅提高效率，以后学习了dp，动态规划会有更好的方式解题
Test E
Boudreaux and Thibodeaux are on the road again . . .
“Boudreaux, we have to get this shipment of mudbugs to Baton Rouge by tonight!”
“Don’t worry, Thibodeaux, I already checked ahead. There are three underpasses and our 18-wheeler will fit through all of them, so just keep that motor running!”
“We’re not going to make it, I say!”
So, which is it: will there be a very messy accident on Interstate 10, or is Thibodeaux just letting the sound of his own wheels drive him crazy?
Input
Input to this problem will consist of a single data set. The data set will be formatted according to the following description.
The data set will consist of a single line containing 3 numbers, separated by single spaces. Each number represents the height of a single underpass in inches. Each number will be between 0 and 300 inclusive.
Output
There will be exactly one line of output. This line will be:
NO CRASH
if the height of the 18-wheeler is less than the height of each of the underpasses, or:
CRASH X
otherwise, where X is the height of the first underpass in the data set that the 18-wheeler is unable to go under (which means its height is less than or equal to the height of the 18-wheeler).
The height of the 18-wheeler is 168 inches.
Sample Input
180 160 170
Sample Output
CRASH 160
#include<iostream>
#include<cstring>
using namespace std;
int car_height = 168;
int main() {
int a, b, c;
while (scanf("%d %d %d", &a, &b, &c) != EOF) {
if (car_height < a && car_height < b && car_height < c) {
printf("NO CRASH\n");
continue;
}
else {
if (car_height >= a) {
printf("CRASH %d\n", a);
}
else if (car_height >= b) {
printf("CRASH %d\n", b);
}
else if (car_height >= c) {
printf("CRASH %d\n", c);
}
}
}
}
这题纯粹水题一个。。。
Test F
Ignatius likes to write words in reverse way. Given a single line of text which is written by Ignatius, you should reverse all the words and then output them.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single line with several words. There will be at most 1000 characters in a line.
Output
For each test case, you should output the text which is processed.
Sample Input
3
olleh !dlrow
m’I morf .udh
I ekil .mca
Sample Output
hello world!
I’m from hdu.
I like acm.
Hint
Remember to use getchar() to read ‘\n’ after the interger T, then you may use gets() to read a line and process it.
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
int main() {
int T;
cin >> T;
getchar();
while (T--) {
char str[1000 + 5];
gets_s(str,1000+5);
stack<char> sq;
int i;
int if_have_space = 0;
for (i = 0; i <=strlen(str); i++) {
if (str[i] != ' '&&str[i]!='\0') {
sq.push(str[i]);
}
else {
if (str[i] == ' ') {
if_have_space = 1;
}
else {
if_have_space = 0;
}
while (!sq.empty()) {
printf("%c", sq.top());
sq.pop();
}
if (if_have_space) {
cout << " ";
}
}
}
printf("\n");
}
}
逆序用堆栈解题会变的方便
Test G
凡看过功夫熊猫这部电影的人都会对影片中那只憨憨的熊猫阿波留下相当深的印象，胖胖的熊猫阿波自从打败了凶狠强悍的雪豹泰龙以后，在和平谷的地位是越来越高，成为谷中第一的功夫大师。并因此他父亲经营的面馆的生意也越来越好，店里每天都会有许多慕名而来吃面和想拜阿波为师的人。
一日，阿波收到了一张请柬，请柬里说在遥远的美国将召开全球比武大会，特邀请阿波过去做嘉宾。阿波当然很高兴，因为自己长这么大都还没出过和平谷，更何况是出国去那遥远的美国。于是他托人买了当晚的机票，阿波来到机场发现其他乘客们正准备按机票上的号码(1,2,3,…,n)依次排队上飞机，由于阿波是第一次坐飞机，所以他想先一步登机，因此他插队第一个登上了飞机，并且他也不看机票，随机的选择了一个座位坐下了。乘客们都很气氛，他们想：既然阿波都不遵守规定，那么我为什么要遵守呢？因此后面所有的人也都随意地找了位置坐下来，并且坚决不让座给其他的乘客。
现在的问题是这样的：在这样的情况下，第i个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?
Input
输入包含多组测试数据，每组数据占一行，包含两个整数，分别是n和m(n>=m)，n表示共有n个乘客(包括阿波)，m表示第m个乘客。
Output
对于每组数据，请输出第m个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?(结果保留2位小数)
每组输出占一行。
Sample Input
2 1
11 3
Sample Output
0.50
0.09
#include<iostream>
using namespace std;
int main() {
double m, n;
while (cin >> n >> m) {
printf("%.2f\n", 1 / n);
}
return 0;
}
Test H
统计给定文本文件中汉字的个数。
Input
输入文件首先包含一个整数n，表示测试实例的个数，然后是n段文本。
Output
对于每一段文本，输出其中的汉字的个数，每个测试实例的输出占一行。
[Hint:]从汉字机内码的特点考虑~
Sample Input
2
WaHaHa! WaHaHa! 今年过节不说话要说只说普通话WaHaHa! WaHaHa!
马上就要期末考试了Are you ready?
Sample Output
14
9
#include<iostream>
#include<cstring>
using namespace std;
int main() {
int n;
cin >> n;
getchar();
while (n--) {
char str[1000 + 5];
gets_s(str, 1000 + 5);
int i,count=0;
for (i = 0; i < strlen(str); i++) {
if (str[i] < 0) {
count++;
}
}
cout << count / 2 << endl;
}
return 0;
}
一个汉字占两个字节，并且其ASCII码是小于0的
Test I
一日，话说0068与***泛舟湖上。忽见岸边出现他的一大敌人elnil。0068当然不想落入elnil的魔爪，于是他就得想办法逃脱。
这个湖是一个很规则的圆形，半径为R。此时0068正好在圆心位置。小船在湖中的速度为 V1，0068和elnil在岸上的速度都为V2。也就是说，如果0068在刚上岸的时候没被抓到，则他可逃脱。在任意时刻，0068和elnil都可以朝任何方向移动，但是0068不能一直呆上船上（会饿死的），elnil不能下水（他不会游泳）。假设0068和elnil都非常聪明，总能做对自己最有利的事情，而且两个人的体力都是无限的。
请问，0068最终能不能逃脱elnil的魔爪？
Input
本题目包含多组测试。请处理到文件结束。
每组测试包含三个整数，R，V1，V2。
Output
对于每组数据，如果0068能够安全逃脱，输出Yes，否则输出No。
数据不会出现正好抓到的情况，所以你可不用太考虑临界点。
Sample Input
100 10 20
100 10 50
Sample Output
Yes
No
好像是道物理题欸~~没做出来
Test J
有一个离散函数f(x),x = {1, 2, ,N}，f(x)<2^31。现在要找出2个点i,j, 使得函数在这2点之间的点都在这2点连线下方，且此连线的斜率的绝对值越大越好。
Input
输入包括多个测试实例。每个测试实例包括2行，第一行为一个整数N，2 <= N <= 100000, 然后是N个整数f(x),x=1,2…N，读到文件结束符为止.
Output
对于每个测试实例输出找到的i和j,如果有多个答案，输出字典序最小的一个。
Sample Input
3
1 2 3
3
2 6 4
Sample Output
1 2
1 2
use scanf to avoid Time Limit Exceeded
Hint
Hint
京公网安备 11010502036488号