January Long 2022 - I (Rated for Div 3)

Keplers Law 

Keplers Law

Kepler’s Law states that the planets move around the sun in elliptical orbits with the sun at one focus. Kepler's 3rd law is The Law of Periods, according to which:

• The square of the time period of the planet is directly proportional to the cube of the semimajor axis of its orbit.

You are given the Time periods (T1,T2$T_1,T_2$) and Semimajor Axes (R1,R2$R_1,R_2$) of two planets orbiting the same star.

Please determine if the Law of Periods is satisfied or not, i.e, if the constant of proportionality of both planets is the same.

Print "Yes" (without quotes) if the law is satisfied, else print "No".

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• Each test case consists a single line of input, containing four space-separated integers T1,T2,R1,R2$T_1,T_2,R_1,R_2$.

Output Format

For each test case, output a single line containing one string — "Yes" or "No" (without quotes); the answer to the problem.

You may print each character of the answer in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 1≤T1,T2≤10$1\le T_1,T_2\le 10$
• 1≤R1,R2≤10$1\le R_1,R_2\le 10$

Subtasks

Subtask 1(100 points): Original constraints

Sample Input 1 

3
1 1 1 1
1 2 3 4
1 8 2 8

Sample Output 1 

Yes
No
Yes

Explanation

• Test Case 1$1$: 12/13=12/13$1^2/1^3=1^2/1^3$
• Test Case 2$2$: 12/33≠22/43$1^2/3^3\ne 2^2/4^3$
• Test Case 3$3$: 12/23=82/83

Solution in C++ :

#include <bits/stdc++.h>

using namespace std;

int main() {

int t;

cin>>t;

while(t--){

   float a,b,c,d;

   cin>>a>>b>>c>>d;

   if((a*a)/(c*c*c)!=(b*b)/(d*d*d)) cout<<"NO"<<endl;

   else  cout<<"YES"<<endl;

}

return 0;

}

Covid Spread 

Covid Spread 

A disease is spreading through ChefLand!

The disease spreads as follows:

• At the end of day 0$0$, a single person is infected with the disease.
• During the next 10$10$ days, the number of infected people doubles each day, until the disease has spread to all people in ChefLand.
• From day 11$11$ onwards, the number of infected people triples each day, until the disease has spread to all people in ChefLand.

You are given the population of ChefLand N$N$ and a day D$D$. How many people in ChefLand are infected at the end of day D$D$?

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• Each test case consists of a single line containing two space-separated integers N$N$ and D$D$ — the population of ChefLand and the day for which you need to find the number of infected people, respectively.

Output Format

• For each test case, print one line containing a single integer — the number of infected people in ChefLand at the end of day D$D$.

Constraints

• 1≤T≤300$1\le T\le 300$
• 1≤N≤108$1\le N\le {10}^8$
• 0≤D≤108$0\le D\le {10}^8$

Subtasks

Subtask 1 (30 points): D≤20$D\le 20$

Subtask 2 (70 points): Original constraints

Sample Input 1 

4
100 3
2000 10
6000 11
10 11

Sample Output 1 

8
1024
3072
10

Explanation

Test Case 1:

• At the end of day 1$1$, the number of infected people is 2×1=2$2\times 1=2$.
• At the end of day 2$2$, the number of infected people is 2×2=4$2\times 2=4$.
• At the end of day 3$3$, the number of infected people is 2×4=8$2\times 4=8$.

Test Case 2: Following the rules in the statement, it can be seen that at the end of day 10$10$, the total number of infected people is 1024$1024$.

Test Case 3: Note that starting at day 11$11$, the number of infected people triples each day, 3×1024=3072$3\times 1024=3072$.

Test Case 4: At the end of day 3$3$, the number of infected people is 8$8$. Since there are only 10$10$ people in ChefLand (which is less than 2×8=16$2\times 8=16$), at the end of day 4$4$ all people in ChefLand are infected and thus the number of infected people is 10$10$ for all days from day 4$4$ onwards, including day 11$11$.

Solution in C++ :

#include <bits/stdc++.h> using namespace std; int main() { long long int t,i,s=1; cin>>t; while(t--){ long long int a,b,s=1; cin>>a>>b; for(int i=1;i<=b&&s<a;i++){ if(i<11) s*=2; else s*=3; } if(s>=a) s=a; cout<<s<<endl; } return 0; }

Prime in a binary string

Prime in a binary string

You are given a binary string S$S$ of length N$N$. Your task is to check if there exists a substring of S$S$ which is the binary representation of a prime number.

Formally, check if there exist integers L$L$ and R$R$ such that 1≤L≤R≤N$1\le L\le R\le N$, and the substring SLSL+1SL+2…SR$S_L{S}_{L+1}{S}_{L+2}\dots S_R$, when treated as a binary integer, is prime.

Print "Yes" if such a substring exists, and "No" if it doesn't.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• Each testcase consists of a single line of input, containing a binary string S$S$.

Output Format

For each test case, output a single line containing one string — "Yes" or "No", the answer to the problem.

You may print each character of the answer in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

Constraints

• 1≤T≤2.5⋅104$1\le T\le 2.5\cdot {10}^4$
• |S|≤105$|S|\le {10}^5$
• The sum of |S|$|S|$ over all tests does not exceed 3⋅105$3\cdot {10}^5$

Subtasks

Subtask 1 (30 points):

• 1≤T≤103$1\le T\le {10}^3$
• |S|≤10$|S|\le 10$

Subtask 2 (70 points):

• Original constraints

Sample Input 1 

3
1
111
101101

Sample Output 1 

No
Yes
Yes

Explanation

Test case 1$1$: There is only one substring, namely "1", and it isn't prime.

Test case 2$2$: The substrings of the given string are {$\{$"1", "11", "111", "1", "11", "1"}$\}$. Of these, "111" which represents 7$7$ in binary, and "11" which represents 3$3$ in binary, are primes.

Test case 3$3$: One of the substrings of the string is "1101", which is the binary representation of 13$13$ — a prime.

Solution in C++ :

#include <iostream>

using namespace std;

int main() {

int t;

cin>>t;

while(t--){

    int c=0,p=-1;

    string s; cin>>s;

    int n=s.length();

    if(n==1) {cout<<"NO"<<endl;continue;}

    for(int i=0;i<=n;i++) if(s[i]=='1') {c++;p=i+1;}

    if(c==0 ||(c==1&&p==n)) cout<<"NO"<<endl;

    else cout<<"YES"<<endl;

}

return 0;

}