PAT basic level
Language used: C++
Just record your experience in the process of brushing questions
Always updated (looking forward to a better solution)
There may be some problems that haven't been solved (that is, I haven't done it yet, and it will be more difficult in the future!)
Welcome to discuss with me √
1001 (3n+1) conjecture that killing people does not pay for their lives
Title:
Callatz conjectures:
For any positive integer n, if it is even, cut it in half; If it is odd, cut (3n+1) in half. This has been repeatedly cut down, and finally you must get n=1 at a certain step. Karaz announced this conjecture at the World Conference of mathematicians in 1950. It is said that at that time, the teachers and students of Yale University mobilized together to try their best to prove this seemingly silly and naive proposition. As a result, the students did not want to study and only proved (3n+1), so that some people said it was a conspiracy. Karaz was deliberately delaying the progress of teaching and scientific research in American Mathematics
Our topic today is not to prove the karatz conjecture, but to simply count any given positive integer n not exceeding 1000. How many steps (cuts) do we need to get n=1?
**Input format:**
Each test input contains one test case, which gives the value of positive integer n.
Output format:
Output the number of steps required to calculate from n to 1.
Input example:
3
Output example:
5
Problem solving ideas:
A very common problem. According to the requirements of the topic, if it is an even number, divide it by 2, if it is an odd number, it becomes 3n+1, and then divide it by 2. In the middle, use a variable to record the number of cuts. When n=1, stop the cycle and output the number of times.
Points worth noting:
nothing
code:
#include <stdio.h>
int main()
{
int n,i,count=0; //Count is used to count
scanf("%d",&n);
while(n!=1)
{
if(n%2==0)
{n=n/2;count++;}
else
{n=(3*n+1)/2;count++;}
}
printf("%d",count);
return 0;
}
1003 I want to pass!
Title:
"Correct answer" is the most gratifying reply given by the automatic question judgment system. This question belongs to PAT's "correct answer" distribution - as long as the read string meets the following conditions, the system will output "correct answer", otherwise it will output "wrong answer".
The conditions for getting "correct answer" are:
The string must contain only three characters: P, A and T, and cannot contain other characters;
Any string shaped like xPATx can get "correct answer", where x is either an empty string or A string composed of only the letter A;
If aPbTc is correct, aPbATca is also correct, where a, b and c are either empty strings or strings composed of only the letter A.
Now please write an automatic referee program for PAT to determine which strings can get the "correct answer".
Input format:
Each test input contains 1 test case. The first line gives a positive integer n (< 10), which is the number of strings to be detected. Next, each string occupies one line. The length of the string does not exceed 100 and does not contain spaces.
Output format:
The detection result of each string occupies one line. If the string can obtain "correct answer", output YES, otherwise output NO.
Input example:
9
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
Output example:
YES
YES
YES
YES
NO
NO
NO
NO
NO
Problem solving ideas:
This question is very difficult! It is necessary to transform the subject conditions for judgment.
Analysis conditions:
1. The string must contain only three characters: P, A and T, and cannot contain other characters;
The number of occurrences of P, T and A must be equal to the length of the string. Therefore, I want to set cnt and record the occurrence times of P, T and A.
2. Any character string such as xPATx can get "correct answer", where x is either an empty character string or A character string composed of only the letter A;
Explain that P and T can only appear once. There needs to be an A between the two.
3. If aPbTc is correct, aPbATca is also correct, where a, b and c are either empty strings or strings composed of only the letter A.
Every time an A is added between P and T, an a needs to be added at the end of the string. It can be concluded that the length of the string before P multiplied by the number of characters between PT is equal to the number of characters after t.
Points worth noting:
It mainly needs to translate the subject conditions, and then make judgment.
code:
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int n,i;
scanf("%d",&n);
while(n--)
{
string str;
cin>>str;
int posP=0,posT=0;//Record the position of P and T
int cntP=0,cntA=0,cntT=0;//Record the number of PTA occurrences
for(i=0;i<str.length();i++)
{
if(str[i]=='P')
{
posP=i;
cntP++;
}
else if(str[i]=='A')
cntA++;
else if(str[i]=='T')
{
posT=i;
cntT++;
}
}
if(cntP+cntA+cntT<str.length()||cntP>1||cntT>1||posT-posP<=1||posP*(posT-posP-1)!=str.length()-posT-1)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
1004 score ranking
Title:
Read in the names, student numbers and grades of n (> 0) students, and output the names and student numbers of the students with the highest and lowest grades respectively.
Input format:
Each test input contains 1 test case in the format of
Line 1: positive integer n
Line 2: name, student number and grade of the first student
Line 3: name, student number and grade of the second student
... ... ...
Line n+1: the name, student number and grade of the nth student
The name and student number are strings of no more than 10 characters, and the score is an integer between 0 and 100. Here, it is guaranteed that no two students have the same score in a group of test cases.
Output format:
Output 2 lines for each test case. The first line is the name and student number of the student with the highest score, the second line is the name and student number of the student with the lowest score, and there is a space between the strings.
Input example:
3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
Output example:
Mike CS991301
Joe Math990112
Problem solving ideas:
A very regular question. Create a structure to store students' information. When entering, write down the subscript values of the maximum and minimum values, so there is no need to sort. Finally, it can be output directly.
Points worth noting:
1. Use structure
2. Record directly while inputting
code:
#include<stdio.h>
#include<iostream>
using namespace std;
struct Node{
string name;
string code;
int grade;
};
int main()
{
int n;
scanf("%d",&n);
struct Node stu[n];
int mmax,mmin,tarmax,tarmin;
for(int i=0;i<n;i++)
{
cin>>stu[i].name>>stu[i].code>>stu[i].grade;
if(i==0)
{
mmax=stu[i].grade;
mmin=stu[i].grade;
tarmax=tarmin=0;
}
else
{
if(mmax<stu[i].grade)
{
mmax=stu[i].grade;
tarmax=i;
}
if(mmin>stu[i].grade)
{
mmin=stu[i].grade;
tarmin=i;
}
}
}
cout<<stu[tarmax].name<<" "<<stu[tarmax].code<<endl;
cout<<stu[tarmin].name<<" "<<stu[tarmin].code<<endl;
return 0;
}
1006 output integer in another format
Title:
Let's use the letter B to represent "100", the letter S to represent "ten", and 12... N to represent non-zero digit n (< 10). Change the format to output any positive integer with no more than 3 digits. For example, 234 should be output as BBSSS1234 because it has 2 "hundreds", 3 "tens", and 4 bits.
Input format:
Each test input contains one test case, giving a positive integer n (< 1000).
Output format:
The output of each test case occupies one line and is output in the specified format n.
Input example 1:
234
Output example 1:
BBSSS1234
Input example 2:
23
Output example 2:
SS123
Problem solving ideas:
Just do as the title says.
If the number of hundreds is n, n B's are output
If n is on the ten digits, n S are output
If the number of bits is n, 123... N is output (this is written in a for loop)
Points worth noting:
Method of taking digits
code:
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n,a,b,c,t=1,i;
scanf("%d",&n);
a=n%10;
b=n/10%10;
c=n/100;
while(c!=0)
{
printf("B");
c--;
}
while(b!=0)
{
printf("S");
b--;
}
for(i=0;i<a;i++)
{
printf("%d",t);
t++;
}
return 0;
}
1008 circular right shift of array elements
Title:
Input format:
Each input contains a test case, and the first line inputs N (1 ≤ N ≤ 100) and M (≥ 0); On line 2, enter N integers separated by spaces.
Output format:
In one line, the integer sequence after M bits of cyclic right shift is output, separated by spaces, and there can be no redundant spaces at the end of the sequence.
Input example:
6 2
1 2 3 4 5 6
Output example:
5 6 1 2 3 4
Problem solving ideas:
The topic requirement is that other arrays are not allowed. All comparisons and exchanges are carried out in array A.
My idea is to save the last digit, then move the remaining number back one digit in turn, and then set the first digit as the last digit.
Cycle M times in the above way to complete the right shift.
code:
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int i,j,temp,N,M,a[1000];
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=0;i<M;i++)
{
temp=a[N-1];
for(j=N-1;j>0;j--)
a[j]=a[j-1];
a[0]=temp;
}
for(i=0;i<N;i++)
{
printf("%d",a[i]);
if(i<N-1)
printf(" ");
}
return 0;
}