2.18 codeforces supplement

---

B. Squares and Cubes

time limit per test1 second
memory limit per test256 megabytes

Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: 1, 4, 8, 9, …

For a given number n, count the number of integers from 1 to n that Polycarp likes. In other words, find the number of such x that x is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).

Input
The first line contains an integer t (1≤t≤20) — the number of test cases.

Then t lines contain the test cases, one per line. Each of the lines contains one integer n (1≤n≤109).

Output
For each test case, print the answer you are looking for — the number of integers from 1 to n that Polycarp likes.

Example
input
6
10
1
25
1000000000
999999999
500000000
output
4
1
6
32591
32590
23125

Their thinking ：

According to the example ,1000000000 The opening direction is rounded down to 32591, To the power of three is 1000, So we just need to traverse 1 To 32591 And record the square of the input , Traverse 1 To 1000 And record its Cube .

There will be some coincidence between the two numbers （ for example 64 Both are 8 The square of is 4 The cube of ）, So the total must not exceed 33591 A digital , Most samples 20 Group , Make an approximate estimate of , Violence never goes out of time . What else do you say , Direct violence solution ！ violence yyds！

We can use STL In the library set function , This function can be understood as a set , We put numbers into this set , It will remove the repeated numbers by itself and arrange them from small to large , I was born for this problem .

Attach my AC Code ：

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
    
	set<long long>a;
	int i,j=0;
	for(i=1;i<=32591;i++) a.insert(i*i);
	
	for(i=2;i<=1000;i++) a.insert(i*i*i);
	
	long long n;
	cin>>n;
	while(n--){
    
		long long x;
		cin>>x;
		long long sum=0;
		
		for(set<long long>::iterator it = a.begin();it!=a.end();++it)
		{
    
			if(*it<=x)sum++;
			else break;
		}
		cout<<sum<<endl;
	}
	return 0; 
}

In fact, during the game last night , My teammates have come up with other ways , But when I tried today, I found that the accuracy would be lost （ I doubt it. pow Function problem ）, So this method needs to be studied and discussed .

C. Wrong Addition

time limit per test1 second
memory limit per test256 megabytes

Tanya is learning how to add numbers, but so far she is not doing it correctly. She is adding two numbers a and b using the following algorithm:

If one of the numbers is shorter than the other, Tanya adds leading zeros so that the numbers are the same length.
The numbers are processed from right to left (that is, from the least significant digits to the most significant).
In the first step, she adds the last digit of a to the last digit of b and writes their sum in the answer.
At each next step, she performs the same operation on each pair of digits in the same place and writes the result to the left side of the answer.
For example, the numbers a=17236 and b=3465 Tanya adds up as follows:

 	  17236
 	 +03465
 	————————
	1106911

calculates the sum of 6+5=11 and writes 11 in the answer.
calculates the sum of 3+6=9 and writes the result to the left side of the answer to get 911.
calculates the sum of 2+4=6 and writes the result to the left side of the answer to get 6911.
calculates the sum of 7+3=10, and writes the result to the left side of the answer to get 106911.
calculates the sum of 1+0=1 and writes the result to the left side of the answer and get 1106911.
As a result, she gets 1106911.

You are given two positive integers a and s. Find the number b such that by adding a and b as described above, Tanya will get s. Or determine that no suitable b exists.

Input
The first line of input data contains an integer t (1≤t≤104) — the number of test cases.

Each test case consists of a single line containing two positive integers a and s (1≤a<s≤1018) separated by a space.

Output
For each test case print the answer on a separate line.

If the solution exists, print a single positive integer b. The answer must be written without leading zeros. If multiple answers exist, print any of them.

If no suitable number b exists, output -1.

Example
input
6
17236 1106911
1 5
108 112
12345 1023412
1 11
1 20

output
3465
4
-1
90007
10
-1
Note
The first test case is explained in the main part of the statement.

In the third test case, we cannot choose b that satisfies the problem statement.

Their thinking ：

No, family , This question is revised bug I almost broke down . When making up questions WA 了 6 Time , It turns out that I didn't type the code carefully , Some details are missing .

My idea for this problem is to save in an array , Then operate bit by bit . There is nothing to say about the basic process , Everyone will , Just say some points that need attention ：

• Remove the lead 0 Take into account that the answer is 0 Its own situation .
• When in the case of two digits minus one digit , It should be noted that the reduced number is greater than or equal to 0 And less than 10.
• Judge -1 The situation should be considered comprehensively .

There should be no big problem if you pay attention to these points , many WA A few times .
My code is as follows ：

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    
	int n;
	cin>>n;
	while(n--){
    
		string x,y;
		cin>>x>>y;
		int len1=x.size();
		int len2=y.size();
		int k=-1,flag=0,i,j;
		if(len2<len1) cout<<"-1"<<endl;
		else 
		{
    
			int ans[len2],a[len2];//ans[] Used to store the subtracted amount ,a[] It is used to merge and store the results and delete the leading zeros of the last and second digits .
			// Don't ask me why I don't have to ans[] To store the results , The question is that my mind is out of my head .
			for(i=len1-1,j=len2-1;i>=0;i--,j--)
			{
    
				if(x[i]<=y[j]) ans[++k]=y[j]-x[i];
				else
				{
    
					ans[++k]=(y[j-1]-'0')*10+(y[j]-'0')-(x[i]-'0');
					j--;
					if(ans[k]>=10||ans[k]<0){
    
						flag=1;
						break;
					}
				}
				
				if(j<0)// If the first number still has digits, but the second number is used up , So it's not eligible 
				{
    
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
    
				int v=-1,f=0;
				for(i=0;i<=j;i++) a[++v]=y[i]-'0';// The extra digits of the second number are directly written into the result array 
				for(;k>=0;k--) a[++v]=ans[k];// The subtracted number is written into the result array 
				for(i=0;i<=v;i++)
				{
    
					if(v==0)cout<<a[v];
					else 
					{
    
						while(f==0)
						{
    
							if(a[i]==0)i++;// Delete leading zeros 
							else f=1;
						}
						cout<<a[i];
					}
				
				}
				cout<<endl;
			}else cout<<"-1"<<endl;
			
		}
	}
	return 0;
}

---

summary

• The title is not difficult. , But my code ability is still too weak , Many details were not noticed .
• First team game , There will be some confusion when typing the code , Practice more later , Try to be as clear as possible 、 everything in good order and well arranged .
• Reading English problems is a big problem for me , Thanks to my teammates' reading this time , Try to read English questions by yourself in the future .
• Try to make the frame clear when writing questions , Use variables that are easy to distinguish and understand .

D Title and F I also tried today , I haven't knocked it out all afternoon , It can be seen that my current code strength is weak . Fight another day .