codeforces round 99 A~C题
A题 A. Strange Functions
A. Strange Functions
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s define a function f(x) (x is a positive integer) as follows: write all digits of the decimal representation of x backwards, then get rid of the leading zeroes. For example, f(321)=123, f(120)=21, f(1000000)=1, f(111)=111.
Let’s define another function g(x)=xf(f(x)) (x is a positive integer as well).
Your task is the following: for the given positive integer n, calculate the number of different values of g(x) among all numbers x such that 1≤x≤n.
Input
The first line contains one integer t (1≤t≤100) — the number of test cases.
Each test case consists of one line containing one integer n (1≤n<10100). This integer is given without leading zeroes.
Output
For each test case, print one integer — the number of different values of the function g(x), if x can be any integer from [1,n].
Example
inputCopy
5
4
37
998244353
1000000007
12345678901337426966631415
outputCopy
1
2
9
10
26
Note
Explanations for the two first test cases of the example:
if n=4, then for every integer x such that 1≤x≤n, xf(f(x))=1;
if n=37, then for some integers x such that 1≤x≤n, xf(f(x))=1 (for example, if x=23, f(f(x))=23,xf(f(x))=1); and for other values of x, xf(f(x))=10 (for example, if x=30, f(f(x))=3, xf(f(x))=10). So, there are two different values of g(x).
题意：已知f（x）函数是求逆运算---------忽略前导零，在所给的n的范围内求有几个不同的m值（m=x/f(f(x))）
题解：通过明显的运算可以得出，m值的求出其实是求n的位数，那么此题可以轻易求解
#include<bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
string n;
cin>>n;
printf("%d\n",n.size());
}
//system("pause");
return 0;
}
B题 Jumps(逆向思维)
B. Jumps
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are standing on the OX-axis at point 0 and you want to move to an integer point x>0.
You can make several jumps. Suppose you’re currently at point y (y may be negative) and jump for the k-th time. You can:
either jump to the point y+k
or jump to the point y−1.
What is the minimum number of jumps you need to reach the point x?
Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.
The first and only line of each test case contains the single integer x (1≤x≤106) — the destination point.
Output
For each test case, print the single integer — the minimum number of jumps to reach x. It can be proved that we can reach any integer point x.
Example
inputCopy
5
1
2
3
4
5
outputCopy
1
3
2
3
4
Note
In the first test case x=1, so you need only one jump: the 1-st jump from 0 to 0+1=1.
In the second test case x=2. You need at least three jumps:
the 1-st jump from 0 to 0+1=1;
the 2-nd jump from 1 to 1+2=3;
the 3-rd jump from 3 to 3−1=2;
Two jumps are not enough because these are the only possible variants:
the 1-st jump as −1 and the 2-nd one as −1 — you’ll reach 0−1−1=−2;
the 1-st jump as −1 and the 2-nd one as +2 — you’ll reach 0−1+2=1;
the 1-st jump as +1 and the 2-nd one as −1 — you’ll reach 0+1−1=0;
the 1-st jump as +1 and the 2-nd one as +2 — you’ll reach 0+1+2=3;
In the third test case, you need two jumps: the 1-st one as +1 and the 2-nd one as +2, so 0+1+2=3.
In the fourth test case, you need three jumps: the 1-st one as −1, the 2-nd one as +2 and the 3-rd one as +3, so 0−1+2+3=4.
题意：在有限步内得出一个步数，使之等于给定的数，操作步骤：当前位置固定为零，可以后退一步，前进则是当前执行的操作是几，就向前进几步，求最小的操作数？
题解：如果正向用等差数列求和的公式去做，那么只有在此时恰好等于给定的n值时，才能是最少的操作数，其他情况此时不易讨论，那不如逆向思维，n值既然是通过步数累加求得，那么不如去倒着依次递减操作数即可。此时只需要考虑n减少为-1时，进行加1的操作数即可求出所得的操作数。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int temp=0;
while(n>0)
{
n-=++temp;
}
if(n==-1)
temp++;
cout<<temp<<"\n";
}
return 0;
}
C题 Strange Functions（水题）
C. Ping-pong
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Alice and Bob play ping-pong with simplified rules.
During the game, the player serving the ball commences a play. The server strikes the ball then the receiver makes a return by hitting the ball back. Thereafter, the server and receiver must alternately make a return until one of them doesn’t make a return.
The one who doesn’t make a return loses this play. The winner of the play commences the next play. Alice starts the first play.
Alice has x stamina and Bob has y. To hit the ball (while serving or returning) each player spends 1 stamina, so if they don’t have any stamina, they can’t return the ball (and lose the play) or can’t serve the ball (in this case, the other player serves the ball instead). If both players run out of stamina, the game is over.
Sometimes, it’s strategically optimal not to return the ball, lose the current play, but save the stamina. On the contrary, when the server commences a play, they have to hit the ball, if they have some stamina left.
Both Alice and Bob play optimally and want to, firstly, maximize their number of wins and, secondly, minimize the number of wins of their opponent.
Calculate the resulting number of Alice’s and Bob’s wins.
Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first and only line of each test case contains two integers x and y (1≤x,y≤106) — Alice’s and Bob’s initial stamina.
Output
For each test case, print two integers — the resulting number of Alice’s and Bob’s wins, if both of them play optimally.
Example
inputCopy
3
1 1
2 1
1 7
outputCopy
0 1
1 1
0 7
Note
In the first test case, Alice serves the ball and spends 1 stamina. Then Bob returns the ball and also spends 1 stamina. Alice can’t return the ball since she has no stamina left and loses the play. Both of them ran out of stamina, so the game is over with 0 Alice’s wins and 1 Bob’s wins.
In the second test case, Alice serves the ball and spends 1 stamina. Bob decides not to return the ball — he loses the play but saves stamina. Alice, as the winner of the last play, serves the ball in the next play and spends 1 more stamina. This time, Bob returns the ball and spends 1 stamina. Alice doesn’t have any stamina left, so she can’t return the ball and loses the play. Both of them ran out of stamina, so the game is over with 1 Alice’s and 1 Bob’s win.
In the third test case, Alice serves the ball and spends 1 stamina. Bob returns the ball and spends 1 stamina. Alice ran out of stamina, so she can’t return the ball and loses the play. Bob, as a winner, serves the ball in the next 6 plays. Each time Alice can’t return the ball and loses each play. The game is over with 0 Alice’s and 7 Bob’s wins.
题解：这个题很水，要求出最明显的分数比，即每个人发球后，二者均不接球，此时的双方的体力值，即为最终的分数比。----------只有Alice的初始体力值减一，才是Alice的分值。
#include<bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
x--;
printf("%d ",x);
printf("%d\n",y);
}
//system("pause");
return 0;
}