Codeworks 5 questions per day (average 1500) - day 24

Hyperset

Topic translation

Yes n Zhang card , Each card has k Features , There are three kinds of features （‘S’, ‘E’, ‘T’）, Let you choose three cards to form a set , Make each feature of the three cards equal or different . As in example 3 "SETT", “TEST”, "EEET" It's a set ,“TEST”, “ESTE”, "STES" Is a set of , Ask how many sets you can choose .

Title Description

Bees Alice and Alesya gave beekeeper Polina famous card game “Set” as a Christmas present.

The deck consists of cards that vary in four features across three options for each kind of feature: number of shapes, shape, shading, and color.

In this game, some combinations of three cards are said to make up a set.

For every feature — color, number, shape, and shading — the three cards must display that feature as either all the same, or pairwise different.

The picture below shows how sets look.

Polina came up with a new game called “Hyperset”. In her game, there are $n$ cards with $k$ features, each feature has three possible values: “S”, “E”, or “T”.

The original “Set” game can be viewed as “Hyperset” with $k=4$ .

Similarly to the original game, three cards form a set, if all features are the same for all cards or are pairwise different.

The goal of the game is to compute the number of ways to choose three cards that form a set.

Unfortunately, winter holidays have come to an end, and it’s time for Polina to go to school.

Help Polina find the number of sets among the cards lying on the table.

Input format

The first line of each test contains two integers $n$ and $k$ ( $1\le n\le 1500$ , $1\le k\le 30$ ) — number of cards and number of features.

Each of the following $n$ lines contains a card description: a string consisting of $k$ letters “S”, “E”, “T”.

The $i$ -th character of this string decribes the $i$ -th feature of that card.

All cards are distinct.

Output format

Output a single integer — the number of ways to choose three cards that form a set.

Examples #1

The sample input #1

3 3
SET
ETS
TSE

Sample output #1

1

Examples #2

The sample input #2

3 4
SETE
ETSE
TSES

Sample output #2

0

Examples #3

The sample input #3

5 4
SETT
TEST
EEET
ESTE
STES

Sample output #3

2

Tips

In the third example test, these two triples of cards are sets:

1. “SETT”, “TEST”, “EEET”
2. “TEST”, “ESTE”, “STES”

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,k;
string s[N];
ll ss=0;
map<string,int> gg;
int main(){
    
	cin>>n>>k;
	for(int i=1;i<=n;i++)  cin>>s[i];
	for(int i=1;i<=n;i++){
    
		for(int j=i+1;j<=n;j++){
    
			string p="";
			for(int kk=0;kk<k;kk++){
    
				if(s[i][kk]==s[j][kk]) p+=s[i][kk];
				else{
    
					if(s[i][kk]!='S'&&s[j][kk]!='S') p+='S';
					if(s[i][kk]!='E'&&s[j][kk]!='E') p+='E';
					if(s[i][kk]!='T'&&s[j][kk]!='T') p+='T';
				}
			}
			ss+=gg[p];
		}gg[s[i]]++;
	}
	cout<<ss<<endl;
	return 0;
}

Motarack’s Birthday

Topic translation

$t$ Group data .

Given a $n$ And a length of $n$ Of , except $-1$ A sequence in which all other numbers are non negative $a$, The request will $a$ All in $-1$ Fill in with $k$, Make the difference between the absolute values of adjacent numbers in the sequence minimum .

Output the difference between the minimum absolute value and the filled number $k$, If there are multiple possibilities $k$, Output any one .

Title Description

Dark is going to attend Motarack’s birthday.

Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.

Dark created that array $1000$ years ago, so some elements in that array disappeared.

Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them.

He doesn’t have much time so he wants to choose an integer $k$ ( $0\le k\le 10^9$ ) and replaces all missing elements in the array $a$ with $k$ .

Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i-a_{i+1}|$ for all $1\le i\le n-1$ ) in the array $a$ after Dark replaces all missing elements with $k$ .

Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?

Input format

The input consists of multiple test cases.

The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer $n$ ( $2\le n\le 10^5$ ) — the size of the array $a$ .

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ( $-1\le a_i\le 10^9$ ).

If $a_i=-1$ , then the $i$ -th integer is missing. It is guaranteed that at least one integer is missing in every test case.

It is guaranteed, that the sum of $n$ for all test cases does not exceed $4\cdot 10^5$ .

Output format

Print the answers for each test case in the following format:

You should print two integers, the minimum possible value of $m$ and an integer $k$ ( $0\le k\le 10^9$ ) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$ .

Make sure that after replacing all the missing elements with $k$ , the maximum absolute difference between adjacent elements becomes $m$ .

If there is more than one possible $k$ , you can print any of them.

Examples #1

The sample input #1

7
5
-1 10 -1 12 -1
5
-1 40 35 -1 35
6
-1 -1 9 -1 3 -1
2
-1 -1
2
0 -1
4
1 -1 3 -1
7
1 -1 7 5 2 -1 5

Sample output #1

1 11
5 35
3 6
0 42
0 0
1 2
3 4

Tips

In the first test case after replacing all missing elements with $11$ the array becomes $[11,10,11,12,11]$ .

The absolute difference between any adjacent elements is $1$ .

It is impossible to choose a value of $k$ , such that the absolute difference between any adjacent element will be $\le 0$ .

So, the answer is $1$ .

In the third test case after replacing all missing elements with $6$ the array becomes $[6,6,9,6,3,6]$ .

• $|a_1-a_2|=|6-6|=0$ ;
• $|a_2-a_3|=|6-9|=3$ ;
• $|a_3-a_4|=|9-6|=3$ ;
• $|a_4-a_5|=|6-3|=3$ ;
• $|a_5-a_6|=|3-6|=3$ .

So, the maximum difference between any adjacent elements is $3$ .

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n,kmax,kmin,k,a[N],s=0;
int main(){
    
	cin>>t;
	while(t--){
    
		scanf("%d",&n);
		kmax=-1,kmin=2e9;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		a[n+1]=0;
		for(int i=1;i<=n;i++){
    
			if(a[i]!=-1&&(a[i-1]==-1||a[i+1]==-1)){
    
				kmax=max(kmax,a[i]);
				kmin=min(kmin,a[i]);
			}
		}
		k=(kmin+kmax)/2;
		for(int i=1;i<=n;i++){
    
			if(a[i]==-1) a[i]=k;
			if(i!=1) s=max(s,abs(a[i]-a[i-1]));
		} 
		printf("%d %d\n",s,k);
		s=k=0;
	}
	return 0;
}

Air Conditioner

Topic translation

• There is an air conditioner in a restaurant , You can choose to increase every minute $1$ The temperature of a unit may be lowered $1$ Unit temperature , Of course, you can also choose not to change , The initial temperature is $m$ .

• Yes $n$ Diners , Every diner will be $t_i$ Arrive at , The lowest temperature he can adapt to is $l_i$ , The maximum temperature is $h_i$ , He will only be $t_i$ Always stay .

• If the temperature is not within the adaptive range of diners , He will feel uncomfortable , Please judge , Can the air conditioner make $n$ All the diners who came to dinner felt comfortable .

• Multiple groups of data , The number of data groups is not greater than $500$.

• $1\le n\le 100$,$-10^9\le m,l_i,h_i\le 10^9$,$1\le t_i\le 10^9$.

Title Description

Gildong owns a bulgogi restaurant.

The restaurant has a lot of customers, so many of them like to make a reservation before visiting it.

Gildong tries so hard to satisfy the customers that he even memorized all customers’ preferred temperature ranges!

Looking through the reservation list, he wants to satisfy all customers by controlling the temperature of the restaurant.

The restaurant has an air conditioner that has 3 states: off, heating, and cooling.

When it’s off, the restaurant’s temperature remains the same.

When it’s heating, the temperature increases by 1 in one minute.

Lastly, when it’s cooling, the temperature decreases by 1 in one minute.

Gildong can change the state as many times as he wants, at any integer minutes.

The air conditioner is off initially.

Each customer is characterized by three values: $t_i$ — the time (in minutes) when the $i$ -th customer visits the restaurant, $l_i$ — the lower bound of their preferred temperature range, and $h_i$ — the upper bound of their preferred temperature range.

A customer is satisfied if the temperature is within the preferred range at the instant they visit the restaurant.

Formally, the $i$ -th customer is satisfied if and only if the temperature is between $l_i$ and $h_i$ (inclusive) in the $t_i$ -th minute.

Given the initial temperature, the list of reserved customers’ visit times and their preferred temperature ranges, you’re going to help him find if it’s possible to satisfy all customers.

Input format

Each test contains one or more test cases.

The first line contains the number of test cases $q$ ( $1\le q\le 500$ ).

Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ( $1\le n\le 100$ , $-10^9\le m\le 10^9$ ), where $n$ is the number of reserved customers and $m$ is the initial temperature of the restaurant.

Next, $n$ lines follow.

The $i$ -th line of them contains three integers $t_i$ , $l_i$ , and $h_i$ ( $1\le t_i\le 10^9$ , $-10^9\le l_i\le h_i\le 10^9$ ), where $t_i$ is the time when the $i$ -th customer visits, $l_i$ is the lower bound of their preferred temperature range, and $h_i$ is the upper bound of their preferred temperature range.

The preferred temperature ranges are inclusive.

The customers are given in non-decreasing order of their visit time, and the current time is $0$ .

Output format

For each test case, print “YES” if it is possible to satisfy all customers. Otherwise, print “NO”.

You can print each letter in any case (upper or lower).

Examples #1

The sample input #1

4
3 0
5 1 2
7 3 5
10 -1 0
2 12
5 7 10
10 16 20
3 -100
100 0 0
100 -50 50
200 100 100
1 100
99 -100 0

Sample output #1

YES
NO
YES
NO

Tips

In the first case, Gildong can control the air conditioner to satisfy all customers in the following way:

• At $0$ -th minute, change the state to heating (the temperature is 0).
• At $2$ -nd minute, change the state to off (the temperature is 2).
• At $5$ -th minute, change the state to heating (the temperature is 2, the $1$ -st customer is satisfied).
• At $6$ -th minute, change the state to off (the temperature is 3).
• At $7$ -th minute, change the state to cooling (the temperature is 3, the $2$ -nd customer is satisfied).
• At $10$ -th minute, the temperature will be 0, which satisfies the last customer.

In the third case, Gildong can change the state to heating at $0$ -th minute and leave it be.

Then all customers will be satisfied.

Note that the $1$ -st customer’s visit time equals the $2$ -nd customer’s visit time.

In the second and the fourth case, Gildong has to make at least one customer unsatisfied.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n,m;
struct stu{
    
	int t,l,r;
}s[N];
bool cmp(stu x,stu y){
    
	return x.t<y.t;
}
int main(){
    
	cin>>t;
	while(t--){
    
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
    
			scanf("%d%d%d",&s[i].t,&s[i].l,&s[i].r);
		}
		sort(s+1,s+1+n,cmp);
		int l=m,r=m;
		bool ok=1;
		for(int i=1;i<=n;i++){
    
			int d=s[i].t-s[i-1].t;
			l-=d,r+=d;
			l=max(l,s[i].l);
			r=min(r,s[i].r);
			if(l>r){
    
				ok=0;
				break;
			}
		}
		if(ok) puts("YES");
		else puts("NO");
	}
	return 0;
}

Binary String Reconstruction

Topic translation

Altogether $t$ Group data .

Each set of data has three integers $n_0,n_1,n_2$.

You need to build a $01$ strand , The length is $n_0+n_1+n_2+1$, For each length $2$ A continuous substring of , All in all $n_0$ A and for $0$, Yes $n_1$ A and for $1$, Yes $n_2$ A and for $2$.

Make sure the input is clear , For each set of data , Output one line , For one $01$ strand , There are no spaces , If there are multiple solutions , Output any one .

Title Description

For some binary string $s$ (i.e. each character $s_i$ is either ‘0’ or ‘1’), all pairs of consecutive (adjacent) characters were written.

In other words, all substrings of length $2$ were written.

For each pair (substring of length $2$ ), the number of ‘1’ (ones) in it was calculated.

You are given three numbers:

• $n_0$ — the number of such pairs of consecutive characters (substrings) where the number of ones equals $0$ ;
• $n_1$ — the number of such pairs of consecutive characters (substrings) where the number of ones equals $1$ ;
• $n_2$ — the number of such pairs of consecutive characters (substrings) where the number of ones equals $2$ .

For example, for the string $s=$ “1110011110”, the following substrings would be written: “11”, “11”, “10”, “00”, “01”, “11”, “11”, “11”, “10”.

Thus, $n_0=1$ , $n_1=3$ , $n_2=5$ .

Your task is to restore any suitable binary string $s$ from the given values $n_0,n_1,n_2$ .

It is guaranteed that at least one of the numbers $n_0,n_1,n_2$ is greater than $0$ .

Also, it is guaranteed that a solution exists.

Input format

The first line contains an integer $t$ ( $1\le t\le 1000$ ) — the number of test cases in the input.

Then test cases follow.

Each test case consists of one line which contains three integers $n_0,n_1,n_2$ ( $0\le n_0,n_1,n_2\le 100$ ; $n_0+n_1+n_2>0$ ).

It is guaranteed that the answer for given $n_0,n_1,n_2$ exists.

Output format

Print $t$ lines.

Each of the lines should contain a binary string corresponding to a test case.

If there are several possible solutions, print any of them.

Examples #1

The sample input #1

7
1 3 5
1 1 1
3 9 3
0 1 0
3 1 2
0 0 3
2 0 0

Sample output #1

1110011110
0011
0110001100101011
10
0000111
1111
000

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n0,n1,n2;
int main(){
    
	cin>>t;
	while(t--){
    
		scanf("%d%d%d",&n0,&n1,&n2);
		if(n1==0){
    
			if(n0) for(int i=1;i<=n0+1;i++) cout<<0;
			else for(int i=1;i<=n2+1;i++) cout<<1;
			cout<<endl;
		}
		else{
    
			for(int i=1;i<=n0+1;i++) cout<<0;
			for(int i=1;i<=n2+1;i++) cout<<1;
			n1--;
			for(int i=1;i<=n1;i++){
    
				if(i%2) cout<<0;
				else cout<<1;
			}
			cout<<endl;
		}
	}
	return 0;
}