February Long 2022 - II, Division 3 (Rated)
Chef and NextGen
Chef is currently working for a secret research group called NEXTGEN. While the rest of the world is still in search of a way to utilize Helium-3 as a fuel, NEXTGEN scientists have been able to achieve 2 major milestones:
Finding a way to make a nuclear reactor that will be able to utilize Helium-3 as a fuel
Obtaining every bit of Helium-3 from the moon's surface
Moving forward, the project requires some government funding for completion, which comes under one condition: to prove its worth, the project should power Chefland by generating at least A units of power each year for the next B years.
Help Chef determine whether the group will get funded assuming that the moon has X grams of Helium-3 and 1 gram of Helium-3 can provide Y units of power.
Input Format
The first line of input contains an integer T, the number of testcases. The description of T test cases follows.
Each test case consists of a single line of input, containing four space-separated integers A,B,X,Y respectively.
Output Format
For each test case print on a single line the answer — Yes if NEXTGEN satisfies the government's minimum requirements for funding and No otherwise.
You may print each character of the answer string in either uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).
Constraints
1≤T≤1000
1≤A,B,X,Y,≤1000
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4
1 2 3 4
4 3 2 1
2 18 9 4
1 100 2 49
Sample Output 1
Yes
No
Yes
No
Explanation
Test case 1: Chefland requires A=1 units of power for the next B=2 years. In total, the moon must be capable of providing A⋅B=2 units of power. There are in total X=3 grams of Helium-3 on the moon which is capable of providing X⋅Y=12 units of power. 12>2, so the project satisfies the minimum requirements for funding. Thus, the answer is Yes.
Test case 2: The total amount of power needed by Chefland is A⋅B=12, whereas the total that can be provided by the Helium-3 present on the moon is X⋅Y=2, which is insufficient to receive funding, so the answer is No.
Test case 3: The total amount of power needed by Chefland is A⋅B=2⋅18=36, and the total that can be provided by the Helium-3 present on the moon is X⋅Y=9⋅4=36, which is sufficient to receive funding, so the answer is Yes.
Test case 4: The total amount of power needed by Chefland is A⋅B=1⋅100=100, and the total that can be provided by the Helium-3 present on the moon is X⋅Y=2⋅49=98, which is insufficient to receive funding, so the answer is No.
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
long int a,b,x,y;
cin>>a>>b>>x>>y;
if(a*b<=x*y) {
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
return 0;
}
World Chess Championship
The World Chess Championship 2022 is about to start. 14 Classical games will be played between Chef and Carlsen in the championship, where each game has one of three outcomes — it can be won by Carlsen, won by Chef, or it can be a draw. The winner of a game gets 2 points, and the loser gets 0 points. If it’s a draw, both players get 1 point each.
The total prize pool of the championship is 100⋅X. At end of the 14 Classical games, if one player has strictly more points than the other, he is declared the champion and gets 60⋅X as his prize money, and the loser gets 40⋅X.
If the total points are tied, then the defending champion Carlsen is declared the winner. However, if this happens, the winner gets only 55⋅X, and the loser gets 45⋅X.
Given the results of all the 14 games, output the prize money that Carlsen receives.
The results are given as a string of length 14 consisting of the characters C, N, and D.
C denotes a victory by Carlsen.
N denotes a victory by Chef.
D denotes a draw.
Input Format
The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains one integer X, denoting that the total prize pool is 100⋅X.
The second line contains the results of the match, as a string of length 14 containing only the characters C, N, and D.
Output Format
For each test case, output in a single line the total prize money won by Carlsen.
Constraints
1≤T≤1000
1≤X≤106
|S|=14
S contains only characters D, C, N.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4
100
CCCCCCCCCCCCCC
400
CDCDCDCDCDCDCD
30
DDCCNNDDDCCNND
1
NNDNNDDDNNDNDN
Sample Output 1
6000
24000
1650
40
Explanation
Test case 1: Since Carlsen won all the games, he will be crowned the champion and will get 60⋅X as the prize money which is 60⋅100=6000
Test case 2: Carlsen won 7 games and drew 7, so his score is 2⋅7+1⋅7=21. Chef lost 7 games and drew 7, so his score is 0⋅7+1⋅7=7. Since Carlsen has more points, he will be crowned the champion and will get 60⋅X as the prize money which is 60⋅400=24000
Test case 3: Carlsen and Chef both end up with 14 points. So, Carlsen is declared the winner, but because the points were tied, he receives 55⋅X=55⋅30=1650 in prize money.
Solution :
t=int(input())
for i in range(t):
x=int(input())
l=list(input())
c=l.count('C')
n=l.count('N')
d=l.count('D')
c+=d
n+=d
if c>n:
print(60*x)
elif c<n:
print(40*x)
else:
print(55*x)
Avoid Fixed Points
Chef has a sequence of N integers A=[A1,A2,…,AN]. He can perform the following operation any number of times (possibly, zero):
Choose any positive integer K and insert it at any position of the sequence (possibly the beginning or end of the sequence, or in between any two elements).
For example, if A=[5,3,4] and Chef selects K=2, then after the operation he can obtain one of the sequences [2–,5,3,4],[5,2–,3,4],[5,3,2–,4], or [5,3,4,2–].
Chef wants this sequence to satisfy the following condition: for each 1≤i≤∣A∣, Ai≠i. Here, ∣A∣ denotes the length of A.
Help Chef to find the minimum number of operations that he has to perform to achieve this goal. It can be proved that under the constraints of the problem, it's always possible to achieve this goal in a finite number of operations.
Input Format
The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output Format
For each test case, print a single line containing one integer — the minimum number of operations that Chef has to perform to achieve the given condition.
Constraints
1≤T≤104
1≤N≤105
1≤Ai≤109
Sum of N over all test caes does not exceed 2⋅105.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
3
3
2 4 5
3
4 1 3
4
3 2 4 2
Sample Output 1
0
1
2
Explanation
Test case 1: The given sequence does not contain any index i such that Ai=i. Hence Chef does not have to perform any operation.
Test case 2: In the given sequence, A3=3. Chef can choose K=2 and insert it before the first element, making the sequence A=[2–,4,1,3], which does not contain any index i for which Ai=i.
Test case 3: In the given sequence, A2=2. Chef can perform the following sequence of operations:
Choose K=5 and insert it before the first element. The sequence becomes A=[5–,3,2,4,2], and now A4=4.
Choose K=3 and insert it between the third and fourth element. The sequence becomes A=[5,3,2,3–,4,2], which does not contain any index i for which Ai=i.
It can be verified that there is no way to satisfy the given condition in less than two operations.
Solution :
Coming soon
Xor Palindrome
A (1-indexed) binary string S of length N is called a xor palindrome if the value of Si⊕S(N+1−i) is the same for all 1≤i≤N.
For example, 0, 1111 and 0101 are xor palindromes, while 1110 and 110101 are not.
You are given a binary string S of length N. Determine if it is possible to rearrange it to form a xor palindrome or not.
Input Format
The first line of input contains a single integer T — the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N — the length of the binary string S.
The second line of each test case contains the binary string S containing 0s and 1s only.
Output Format
For each test case, output YES if it is possible to rearrange S to convert it into a xor palindrome. Otherwise output NO.
You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).
Constraints
1≤T≤1000
1≤N≤105
S is a binary string, i.e, contains only the characters 0 and 1
It is guaranteed that the sum of N over all test cases does not exceed 2⋅105.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4
2
00
4
0011
3
001
4
0001
Sample Output 1
YES
YES
YES
NO
Explanation
Test case 1: 00 is already a xor palindrome. [The value of Si⊕S(N+1−i) is 0 for all 1≤i≤N.]
Test case 2: 0011 is already a xor palindrome. [The value of Si⊕S(N+1−i) is 1 for all 1≤i≤N.]
Test case 3: 001 can be rearranged to form 010 which is a xor palindrome. [The value of Si⊕S(N+1−i) is 0 for all 1≤i≤N.]
Test case 4: It can be proved that 0001 can not be rearranged to form a xor palindrome.
Solution :
Aajayega
Bitwise swaps
Given an array A consisting of N integers A1,A2,…,AN, determine if you can sort this array by applying the following operation several times (possibly, zero):
Pick a pair of indices (i,j) with i≠j and Ai&Aj≠0, and swap the values of Ai and Aj. Here, & denotes the bitwise AND operation.
For example, if A=[6,4,2], the two possible operations are (1,2) and (1,3). (2,3) cannot be performed because A2&A3=4&2=0.
Input Format
The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN
Output Format
For each test case, output the answer on a new line — YES if the given array can be sorted by repeatedly applying the given operation, and NO otherwise.
You may print each character of the answer string in either uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).
Constraints
1≤T≤104
1≤N≤3⋅105
0≤Ai<231 for each 1≤i≤N
The sum of N over all test cases does not exceed 3⋅105
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4
3
6 4 2
6
9 34 4 24 1 6
6
9 34 24 4 1 6
2
1 0
Sample Output 1
Yes
Yes
No
No
Explanation
Test case 1: A can be sorted by applying the single operation (1,3).
Test case 2: A can be sorted by applying the following operations in order: (1,5),(2,6),(2,3),(4,5).
Test cases 3 and 4: It can be shown that no sequence of operations will sort A.
Solution :
SOON