CodeChef Starters 21 Division 3 (Rated)

 Home » Compete » CodeChef Starters 21 Division 3 (Rated)

Devendra and Water Sports

Recently, Devendra went to Goa with his friends. Devendra is well known for not following a budget.

He had Rs. Z$Z$ at the start of the trip and has already spent Rs. Y$Y$ on the trip. There are three kinds of water sports one can enjoy, with prices Rs. A$A$, B$B$, and C$C$. He wants to try each sport at least once.

If he can try all of them at least once output YES, otherwise output 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 of a single line of input containing five space-separated integers Z,Y,A,B,C$Z,Y,A,B,C$.

Output Format

For each test case, print a single line containing the answer to that test case — YES if Devendra can try each ride at least once, and NO otherwise.

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

Constraints

• 1≤T≤10$1\le T\le 10$
• 104≤Z≤105${10}^4\le Z\le {10}^5$
• 0≤Y≤Z$0\le Y\le Z$
• 100≤A,B,C≤5000$100\le A,B,C\le 5000$

Sample Input 1 

3
25000 22000 1000 1500 700
10000 7000 100 300 500
15000 5000 2000 5000 3000

Sample Output 1 

NO
YES
YES

Solution in C++ :

#include <iostream>

using namespace std;

int main() {

    int t;

    cin>>t;

    int a,b,c,d,e;

    while(t--){

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

        if(a-b>=(c+d+e)) cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

return 0;

}

Covid and Theatre Tickets

Mr. Chef is the manager of the Code cinemas and after a long break, the theatres are now open to the public again. To compensate for the loss in revenue due to Covid-19, Mr. Chef wants to maximize the profits for every show from now on and at the same time follow the guidelines set the by government. The guidelines are:

• If two people are seated in the same row, there must be at least one empty seat between them.
• If two people are seated in different rows, there must be at least one completely empty row between them. That is, if there are people seated in rows i$i$ and j$j$ where i<j$i<j$, there must be some row k$k$ such that i<k<j$i<k<j$ and nobody is seated in row k$k$.

Given the information about the number of rows and the number of seats in each row, find the maximum number of tickets Mr. Chef can sell.

Input Format

• The first line of input will contain 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 of input containing two space-separated integers N,M$N,M$ — the number of rows and the number of seats in each row, respectively.

Output Format

For each test case, output a single line containing one integer – the maximum number of tickets Mr. Chef can sell.

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N,M≤100$1\le N,M\le 100$

Sample Input 1 

3
1 5
3 3
4 4

Sample Output 1 

3
4
4

Explanation

Test Case 1: There is only one row with five seats. Mr. Chef can sell a maximum of 3 tickets for seat numbers 1, 3 and 5.

Test Case 2: There are three rows with three seats each. Mr. Chef can sell a maximum of 4 tickets, for seats at the start and end of row numbers 1 and 3.

Test Case 3: There are four rows with four seats each. Mr. Chef can sell a maximum of 4 tickets, for example by choosing the seats at the start and end of row numbers 1 and 4.

Solution in C++ :

#include <iostream>

using namespace std;

int main() {

    int t;

    cin>>t;

    int a,b;

    while(t--){

        cin>>a>>b;

        if(a%2!=0 && b%2!=0)

        {

            cout<<(a/2+1)*(b/2+1)<<endl;

        }

        else if(a%2==0 && b%2!=0)

        {

            cout<<(a/2)*(b/2+1)<<endl;

        }

         else if(a%2!=0 && b%2==0)

        {

            cout<<(a/2+1)*(b/2)<<endl;

        }

          //if(a%2==0 && b%2==0)

          else

        {

            cout<<(a/2)*(b/2)<<endl;

        }

    }

return 0;

}

Akash and Grid 

Akash is stuck in a N×N$N\times N$ grid, where N$N$ is odd. The rows of the grid are numbered 1$1$ to N$N$ from top to bottom, and the columns are numbered 1$1$ to N$N$ from left to right. The cell at the intersection of the i$i$-th row and j$j$-th column will be denoted (i,j)$(i,j)$.

The grid has a unique center cell — ((N+1)/2,(N+1)/2)$((N+1)/2,(N+1)/2)$. For example, when N=5$N=5$ the center is cell (3,3)$(3,3)$.

Akash is currently at cell (xs,ys)$(x_s,y_s)$. He would like to reach the exit of the grid, which is located at the center. It is guaranteed that (xs,ys)$(x_s,y_s)$ is not the center.

Suppose Akash is at cell (x,y)$(x,y)$. He can make the following movements:

• He can freely move along diagonals, i.e, to cells (x−1,y−1),(x−1,y+1),(x+1,y−1),(x+1,y+1)$(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1)$
• He can move one step horizontally or vertically with the cost of 1$1$ gold coin, i.e, to cells (x,y−1),(x,y+1),(x−1,y),(x+1,y)$(x,y-1),(x,y+1),(x-1,y),(x+1,y)$

Note that Akash is not allowed to make a move that will take him out of bounds of the grid.

Akash would like to minimize the number of coins required to reach the center. Please help him find this number.

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 of input, containing three space-separated integers N,xs,ys$N,x_s,y_s$ — the size of the grid and the coordinates of Akash's starting cell.

Output Format

For each test case, output in a single line the minimum number of gold coins Akash needs to reach the center.

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 3≤N<2⋅104$3\le N<2\cdot {10}^4$
• N$N$ is always odd.
• 1≤xs,ys≤N$1\le x_s,y_s\le N$

Sample Input 1 

2
3 2 1
5 3 1

Sample Output 1 

1
0

Solution in C++ :

#include <iostream>

using namespace std;

int main() {

    int t;

    cin>>t;

    int a,b,c;

    while(t--){

        cin>>a>>b>>c;

        if((b+c)%2==0) cout<<0<<endl;

else cout<<1<<endl;

    }

return 0;

}

And Or Union

You are given an array A$A$ consisting of N$N$ integers.

From array A$A$, we create a new array B$B$ containing all pairwise bitwise ANDs of elements from A$A$. That is, B$B$ consists of N⋅(N−1)/2$N\cdot (N-1)/2$ elements, each of the form Ai&Aj$A_i\mathrm{\&}{A}_j$ for some 1≤i<j≤N$1\le i<j\le N$.

In array B$B$, we repeat the following process till there is only one element remaining:

• Let the current maximum and minimum element of array B$B$ be X$X$ and Y$Y$ respectively.
• Remove X$X$ and Y$Y$ from array B$B$ and insert X|Y$X|Y$ into it.

Determine the last remaining element in array B$B$.

Here, &$\mathrm{\&}$ denotes the Bitwise AND operation and |$|$ denotes the Bitwise OR operation.

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.
• The first line of each test case contains a single integer N$N$, denoting the number of elements in A$A$.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output Format

For each test case, print a single line containing one integer — the last remaining element in array B$B$.

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 2≤N≤105$2\le N\le {10}^5$
• 0≤Ai≤109$0\le A_i\le {10}^9$
• The sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

3
2
1 3
3
2 7 1
4
4 6 7 2

Sample Output 1 

1
3
6

Explanation

Test Case 1$1$: Array B$B$ will be [A1&A2]=[1&3]=[1]$[A_1\mathrm{\&}{A}_2]=[1\mathrm{\&}3]=[1]$. There is only one element in B$B$ so the answer is 1$1$.

Test Case 2$2$: Array B$B$ will be [A1&A2,A1&A3,A2&A3]=[2&7,2&1,7&1]=[2,0,1]$[A_1\mathrm{\&}{A}_2,A_1\mathrm{\&}{A}_3,A_2\mathrm{\&}{A}_3]=[2\mathrm{\&}7,2\mathrm{\&}1,7\mathrm{\&}1]=[2,0,1]$.

Then, we do the following operations on B$B$:

1. Remove 2$2$ and 0$0$ from B$B$ and insert 2|0=2$2|0=2$ into it. Now, B=[1,2]$B=[1,2]$.
2. Remove 2$2$ and 1$1$ from B$B$ and insert 2|1=3$2|1=3$ into it. Now, B=[3]$B=[3]$.

The last remaining element is thus 3$3$.

Solution in C++:

#include <iostream>

#include <math.h>

using namespace std;

int main() {

    int t;

    cin>>t;

    while(t--){

int n,k; cin>>n;

int a[n], s[32]={0};

for(int i=0;i<n;i++){

    cin>>a[i];

    for(int j=0;j<32;j++){

    

        k=a[i]>>j;

        if(k&1) s[j]++;

        

    }

    

}

long long int o = 0;

    for(int i=0;i<32;i++){

    

        if(s[i]>1) o+=pow(2,i);

        

    }

cout<<o<<endl;}

    return 0;

    

}

ChefWM 

Chef recently created a new Tiling Window Manager called ChefWM. He wants to find out the maximum number of columns of windows he can fit on the screen and he needs your help.

Consider the screen to be an axis-aligned rectangle in the xy$xy$-plane, with its bottom-left corner at (0,0)$(0,0)$ and top-right corner at (N,M)$(N,M)$ (that is, the screen has width N$N$ units and height M$M$ units). ChefWM works as follows:

• First, the screen is divided into one or more columns of equal integer width.
• Then, each column is divided into two or more windows of equal integer height. Note that all windows within a column must have the same height, but windows in different columns may have different heights.
• Finally, Chef would like the following condition to hold:
  • No two windows from different columns can have their horizontal boundary share the same y$y$-coordinate (apart from y=0$y=0$ and y=M$y=M$). See the figures below for more details.

It is not allowed to leave any empty space on the screen, i.e, the division performed in the first two steps above must cover the entire screen.

Here is an example of a tiling that satisfies all the conditions, for N=8$N=8$ and M=6$M=6$.

Below are two tilings that satisfy all conditions except the last. The one on the left has a horizontal edge at y=2$y=2$ in both columns, while the one on the right has a horizontal edge at y=2$y=2$ in column 1$1$ and column 3$3$.

 

What is the maximum number of columns that ChefWM can fit on the screen while following the above conditions? Note that you do not need to maximize the number of windows, you only need to maximize the number of columns.

It may be possible that no columns can be created under these conditions, in that case, print 0$0$.

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 of input, containing two space-separated integers N,M$N,M$ — the coordinates of the top-right corner of the screen.

Output Format

For each test case, output a single line containing one integer — the maximum number of columns ChefWM can create for the screen.

Constraints

• 1≤T≤500$1\le T\le 500$
• 1≤N≤109$1\le N\le {10}^9$
• 1≤M≤109$1\le M\le {10}^9$

Sample Input 1 

5
8 210
1 100
100 5
10 1
9 2310

Sample Output 1 

4
1
1
0
3

Explanation

Test Case 1: It is possible to make 4$4$ columns as follows:

• The first column has 7$7$ windows of height 30$30$ each
• The second column has 2$2$ windows of height 105$105$ each
• The third column has 5$5$ windows of height 42$42$ each
• The last column has 3$3$ windows of height 70$70$ each

It can be seen in the diagram below that the edges from any two windows from different columns do not have the same y$y$-coordinate except for y=0$y=0$ and y=m$y=m$.

Solution in C++ :

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define vi vector<int>

#define vll vector<ll>

#define pb push_back

int main() {

int tc=0,tt=1;

cin>>tt;

while(tc++<tt){

    ll n,m;

    cin>>n>>m;

    ll ans=0,temp=m;

    for(ll i=2;i*i<=m;i++){

        if(!(temp%i)){

            ans++;

            while(!(temp%i)){

                temp/=i;

            }

        }

    }

    if(temp>1) ans++;

    vll arr ;

    for(ll i=1;i*i<=n;i++){

    if(!(n%i)){

            arr.pb(i);

            if(i!=(n/i)) arr.pb(n/i);

        

    }

}

ll  val=0;

for(auto x:arr){

    if(x<=ans) val=x;

}

cout<<val<<endl;

}

return 0;

}

Yaar ! Channel ko subscribe jaarur kr dena (Please)