Codeworks round 639 (Div. 2) cute new problem solution

Codeforces Round #639 (Div. 2) Cute new problem solution

Because of the long queue, the round is unrated. I’m trying to investigate it. Just solve problems for fun. I hope you liked them. Mike. Unfortunately, because the server is not rating 了
A. Puzzle Pieces
The question ： Give several similar puzzles . Ask if you can use these puzzles to make n * m The block .

tips: obviously 1 OK or 1 Column can definitely .

2 * 2 It's fine too .

and 3 * 2 No way. ：

And all greater than 3 * 2 The block of must contain 3 * 2 Sub block of . So none of them .
The code is incredibly simple ：（ Afraid of mistakes, I also checked for a long time hhh）

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int n, m, t;

void solve(){
    
	scanf("%d%d", &n, &m);
	if(n == 1 || m == 1)	printf("YES\n");
	else if(n == 2 && m == 2)	printf("YES\n");
	else	printf("NO\n");
} 

int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}

B. Card Constructions
The question ： use poker Build a poker tower , As shown in the figure below . ask ： give n A playing card , Try to put the biggest tower you can every time , How many can be placed completely at most .

tips:
I practice ： Looking for a regular .
The second is two more sharp than the first （cards standing up） And a flat card （horizontal cards）.2 * 2 + 1
The third one is three more sharp than the third one （cards standing up） And two flat cards （horizontal cards）.3 * 2 + 2
And so on , You can play the table to find the number of cards needed by all towers .（ because n No more than 1e9, about 30000 That's about it ）.
Since the array is incremental , It can be calculated by two points （30000 The amount of data can be equal ）.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int n,t, book[100005] = {
    0, 2};

void makebook(){
    
	for(int i = 2; i <= 30005; ++i)
		book[i] = book[i - 1] + 3 * i - 1;
}

void solve(){
    				// Linear look , No two points  
	scanf("%d",&n);
	int cnt = 0;
	for(int i = 30005; i >= 1;){
    
		if(book[i] > n)	--i;
		else{
    
			cnt++;
			n -= book[i];
		}
		if(n <= 1)	break;
	}
	printf("%d\n",cnt);
} 

void solve2(){
    					// Two point search  
	scanf("%d",&n);
	int cnt = 0, right = 30005;
	while(n >= 2){
    
		int pos = upper_bound(book + 1, book + 1 + right, n) - book - 1;
		right = pos;
		n -= book[pos];
		if(n >= 0)	cnt++;
	}
	printf("%d\n",cnt);
}

int main(){
    
	scanf("%d",&t);
	makebook();
	while(t--){
    
		solve2();
	}
	return 0;
}

Pay attention to the array from small to large ,upper_bound（） What we found was The first one is greater than n The location of , Location -1 Is the last less than or equal to n The location of .
{ Review the ： If the array is in order from large to small , Use greater() Realization ~}

P.S. It's fine too Direct push A formula ~
Let’s count the number of cards in a pyramid of height h. There are 2(1+2+3+⋯+h) cards standing up, and there are 0+1+2+⋯+(h−1) horizontal cards. So, there are 3/2h * h + 1/2 h cards total.

C. Hilbert’s Hotel
The question ： Hilbert Hotel problem ~ Classical discrete mathematical problems . Original k Guest No. 1 lives in k Room number , Now give me a n An array of lengths , After moving according to certain rules , Whether there is still one room for each guest .
tips:1.“More formally, r = k mod n is the smallest non-negative integer such that k−r is divisible by n.”
e.g. (−1337) mod 3 = 1 , instead of -2.
2. The rules ：Then for each integer k, the guest in room k is moved to room number k+a【k mod n】
3. The set of integers is a Countable sets with infinite elements , model n Equivalence class share n individual （0,1,……n-1）. Just look 0-（n-1） Whether these numbers meet the conditions after moving ~ namely ：Checked with a boolean array to make sure each number from 0 to n−1 is included.（ Whether it can be allocated to 0-（n-1） In the equivalence class of ）

#include<bits/stdc++.h>
using namespace std;

int n, t, book[200005];

void solve(){
    
	scanf("%d",&n);
	int flag[n + 5] = {
    0};				// Tag array 
	for(int i = 0; i < n; ++i)
		scanf("%d", &book[i]);
	for(int i = 0; i < n; ++i){
    
		int tmp = (i + book[i]) % n;
		if(tmp < 0)	tmp += n;			// By definition , If the remainder is negative, it should be converted to positive 
		flag[tmp] = 1;
	}
	for(int i = 0; i < n; ++i)
		if(!flag[i]){
    
			printf("NO\n");
			return ;
		}	
	printf("YES\n");
}

int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}

To be continued ing……