Today is our favorite math field

• Simple A C D E
• Medium B F G
• Difficulty H

Strange, I think it's very difficult. H has passed so much and G is so simple that no one has passed.
It's a shock that so much is true.

A A Very Hard Question Gym - 101502A

meaning of the title

Give you the number y of oranges and the price increase x. ask how many oranges you can buy with the money you used to buy y oranges.

Problem solution

Junior high school mathematics (pay attention to the changes of floating point numbers and integers, as well as the error of floating point numbers)
It seems that many people have fallen into this pit. Due to the accuracy of floating-point numbers, such as 5, it may be expressed as 4.99999 in the computer because of the accuracy, If you use cast, for example, (int)x, it will directly become 4. Pay special attention to floating-point numbers.

AC code

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int x,y;
		scanf("%d%d", &y, &x);
		printf("%.0f\n", y /( 1 + x * 0.01));
	}
}

B Building Numbers Gym - 101502F

meaning of the title

2 operations

• 1. Add one to the number
• 2. Multiply the number by two

I'll give you an array and q queries. For each query, I'll give you an integer l and an integer R. ask you, how many operations are needed to turn 1 into the l to r of the array.
For example, if the arrays l to r are 1, 2, 8 and 10, it takes 0 + 1 + 3 + 4 operations in total

Problem solution

The number of times of each array in the array is calculated, and then the prefix sum is constructed to deal with the static interval query.
Constructing a number directly from 1 will timeout. In fact, we can construct it reversely, so the two operations become

• 1. Subtract one from the number
• 2. Divide the number by two

For example, 10, we first judge that it is a multiple of two, so 10 - > 5. 5 is not a multiple of two, so 5 - > 4.
So there are 10 - > 5 - > 4 - > 2 - > 1

AC code

typedef long long ll;
ll s[100008];
ll f[100005];
ll func(ll x) {
	ll ans = 0;
	for (; x!=1;x>>=1) {
		if (x & 1)ans ++;
		ans++;
	}
	return ans;
}

int main() {
	int t, n, q;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &q);
		for (int i = 1; i <= n; i++) scanf("%lld", &s[i]);
		for (int i = 1; i <= n; i++) {
			f[i] = func(s[i]) + f[i - 1];
		}
		for (int i = 0; i < q; i++) {
			int l,r;
			scanf("%d%d", &l, &r);
			printf("%lld\n", f[r] - f[l-1]);
		}
	}
	return 0;
}

C Two-gram CodeForces - 977B

meaning of the title

Find the substring with the most length of 2 in the given string, such as AAABA, where AA occurs twice.

Problem solution

Enumerate all substrings of length 2 and find out the ones that appear most

AC code

char s[200];
int vis[26 * 26+5];
int main() {
	int n;
	scanf("%d%s", &n,s);
	for (int i = 0; i < n-1; i++) {
		vis[(s[i] - 'A')*26+(s[i + 1] - 'A')]++;
	}
	int ans = 0;
	int max = 0;
	for (int i = 0; i <= 26 * 26; i++) {
		if (max < vis[i]) {
			ans = i;
			max = vis[i];
		}
	}
	printf("%c%c\n", ans / 26 + 'A', ans % 26 + 'A');
	return 0;
}

D Wrong Subtraction CodeForces - 977A

meaning of the title

Give you n and k, perform k operations on N, and the operation is

• If the single digit is non-zero, subtract one
• Divide by ten if the single digit is zero
  For the final answer. (ensure that the answer is a positive integer)

Problem solution

k is very small, no brain simulation.

AC code

int main() {
	int n,k;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < k; i++) {
		if (n % 10)n--;
		else n /= 10;
	}
	printf("%d\n", n);
	return 0;
}

E Eyad and Math Gym - 101502H

meaning of the title

Determine the size of $a^b $and $c^d $

Problem solution

High school mathematics
It must not be calculated directly. The value is too large. In fact, take log s on both sides and compare them.

AC code

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if (b*log(a) < d*log(c)) 
			printf("<\n");
		else printf(">\n");
	}
	return 0;
}

F Card Constructions CodeForces - 1345B

meaning of the title

Give you n cards to build pyramids. You must build the largest tower you can build at one time. Ask how many towers you can build at last.

Problem solution

Find the rules and type the table.
Calculate the cards consumed by pyramids of different heights, and then find the largest one in two.
(it's OK to traverse directly without bisection, but in theory, bisection speed will be faster)

AC code

int ta[30004];
int main() {
	int t, n;
	int a = 1, b = 0;
	for (int i = 1; i <= 25820; b += i, i++, a += i) {
		ta[i] = a * 2 + b;
	}

	scanf("%d", &t);

	while (t--) {
		scanf("%d", &n);
		int ans = 0;
		while (n >= 2) {
			int k = lower_bound(ta + 1, ta + 25821, n) - ta;
			if (ta[k] != n)k--;
			n -= ta[k];
			ans++;
		}
		printf("%d\n", ans);
	}

	return 0;
}

G Dima and Sequence CodeForces - 272B

meaning of the title

With function $f(x)$

• $ f(0) = 0$
• $ f(2·x) = f(x)$
• $ f(2·x + 1) = f(x) + 1$

Give you an array a and ask how many pairs of $(i,   j) (1   i   j   n) $, so that $f(ai)   =   f(aj) $

Problem solution

Because the value of the array is very large to 1e9, you can't directly tabulate the function. It's similar to question B. we can calculate the function value of a certain number quickly by reverse deduction. The complexity is about $O(logn) $which is completely acceptable. The counting part uses the hash method for the function value deduced by reverse deduction to obtain the same number, and then count it. If there are two identical, then one pair, three identical pairs, four identical pairs, 3 + 2 + 1 pairs, and 1 + 2 + 3 + 4 under preprocessing, It can be accumulated directly.

AC code

int f(int x) {
	int ans = 0;
	while (x) {
		while (x&&x % 2 == 0)x /= 2;
		if (x) {
			x--;
			ans++;
		}
	}
	return ans;
}

int vis[100];
ll fac[100005];
int main() {
	int n,m,q;
	for (ll i = 1;i <=100000 ; i++ ) {
		fac[i] = fac[i - 1] + i;
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &q);
		vis[f(q)]++;
	}
	long long ans = 0;
	for (int i = 0; i < 100; i++) {
		if (vis[i]>1)ans += fac[vis[i] - 1];
	}
	printf("%lld\n",ans);
}

H Moderate Modular Mode CodeForces - 1604D

meaning of the title

There are two even numbers $x $, $y $, satisfying $n;mod;x=y;mod;n $, find any $n $that satisfies the condition.

Problem solution

• When $x=y $, $n=x$

• When $x > y $

  • If $n > y $, then the left side of the formula is $y;mod;n=y $, easy to launch $n=kx+y $.
  • If $n ≤ y $, there is no solution.

• When $x < y $, this direct push formula is more troublesome, but it can determine the range of $n $$[x,y] $. When $y=kx $, $x=y $;
  At the same time, you can also determine the range of the remainder $r $[0,x) $. Suppose $KX < y < (K + 1) x $, then $n=kx+y2 $. Here we suggest you draw the following figure.

AC code

int main(){
	int t;
	scanf("%d",&t);
	long long x,y;
	while(t--){
		scanf("%lld%lld",&x,&y);
		if(x>y){
			printf("%lld\n",x+y);
		}
		else{
			ll ans=y-y%x/2;
			if(ans%x==y%ans)printf("%lld\n",ans);
		}
	}

	return 0;
}