Codechef September Challenge 2021 (Rated for Div 3) Solutions Available

-


 September Challenge 2021 (Rated for Div 3)






                                    Scorable Problems for Division 3



1 Problem.

Codechef September long challenge 2021 | Airline Restrictions Solution

Chef has 33 bags that she wants to take on a flight. They weigh AA, BB, and CC kgs respectively. She wants to check-in exactly two of these bags and carry the remaining one bag with her.

The airline restrictions says that the total sum of the weights of the bags that are checked-in cannot exceed DD kgs and the weight of the bag which is carried cannot exceed EE kgs. Find if Chef can take all the three bags on the flight.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each testcase contains a single line of input, five space separated integers A,B,C,D,EA,B,C,D,E.

Output Format

For each testcase, output in a single line answer "YES" if Chef can take all the three bags with her or "NO" if she cannot.

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≤360001≤T≤36000
  • 1≤A,B,C≤101≤A,B,C≤10
  • 15≤D≤2015≤D≤20
  • 5≤E≤105≤E≤10

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

1 1 1 15 5
8 7 6 15 5
8 5 7 15 6

Sample Output 1 YES

NO
YES

Explanation

Test case 11: Chef can check-in the first and second bag (since 1+1=2≤151+1=2≤15) and carry the third bag with her (since 1≤51≤5).

Test case 22: None of the three bags can be carried in hand without violating the airport restrictions.

Test case 33: Chef can check-in the first and the third bag (since 8+7≤158+7≤15) and carry the second bag with her (since 5≤65≤6).


            <<<< Solution For AIRLINE RESTRICTIONS >>>>


2 Problem.

Codechef September long challenge 2021 | Travel Pass Solution

Chef is going on a road trip and needs to apply for inter-district and inter-state travel e-passes. It takes AA minutes to fill each inter-district e-pass application and BB minutes for each inter-state e-pass application.

His journey is given to you as a binary string SS of length NN where 00 denotes crossing from one district to another district (which needs an inter-district e-pass), and a 11 denotes crossing from one state to another (which needs an inter-state e-pass).

Find the total time Chef has to spend on filling the various forms.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains two lines of input.
  • First line contains three space separated integers N,AN,A and BB.
  • Second line contains the string SS.

Output Format

For each testcase, output in a single line the total time Chef has to spend on filling the various forms for his journey.

Constraints

  • 1≤T≤1021≤T≤102
  • 1≤N,A,B≤1021≤N,A,B≤102
  • Si∈{′0′,′1′}Si∈{′0′,′1′}

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1

3
2 1 2
00
2 1 1
01
4 2 1
1101

Sample Output 12

2
2
5


                          <<<<< Link For Solutions >>>>>>


5 Problem.

Codechef September long challenge 2021 | 2-D Point Meeting Solution

You are given NN distinct points in a 22-D plane, numbered 11 through NN. The X-coordinate of the points are X1,X2,…,XNX1,X2,…,XN respectively and the Y-coordinates are Y1,Y2,…,YNY1,Y2,…,YN respectively. Your goal is to make the location of all the NN points equal to that of each other. To achieve this, you can do some operations.

In one operation, you choose an index i(1≤i≤N)i(1≤i≤N) and a real number KK and change the location of the ithith point in one of the following ways:

  • Set (Xi,Yi)=(Xi+K,Yi)(Xi,Yi)=(Xi+K,Yi)
  • Set (Xi,Yi)=(Xi,Yi+K)(Xi,Yi)=(Xi,Yi+K)
  • Set (Xi,Yi)=(Xi+K,Yi+K)(Xi,Yi)=(Xi+K,Yi+K)
  • Set (Xi,Yi)=(Xi+K,Yi−K)(Xi,Yi)=(Xi+K,Yi−K)

Find the minimum number of operations to achieve the goal.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains three lines of input.
  • The first line contains a single integer NN.
  • The second line contains NN space-separated integers X1,X2,…,XNX1,X2,…,XN.
  • The third line contains NN space-separated integers Y1,Y2,…,YNY1,Y2,…,YN.

Output Format

For each test case, print a single line containing one integer – the minimum number of operations to achieve the goal.

Constraints

  • 1≤T≤3001≤T≤300
  • 2≤N≤1002≤N≤100
  • −109≤Xi,Yi≤109−109≤Xi,Yi≤109
  • (Xi,Yi)≠(Xj,Yj)(Xi,Yi)≠(Xj,Yj) if (i≠j)(i≠j)
  • Sum of NN over all test cases does not exceed 600600.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

2

3
0 1 -4
0 1 5
3
0 1 3
1 1 -1

Sample Output 1 

3

2

                        Click For <<<2-D Point Meeting Solution >>> Solution

6. Problem.

Codechef September long challenge 2021 | Minimize Digit Sum Solution

Let f(n,B)f(n,B) be the sum of digits of the integer nn when written in base BB.

Given QQ queries, each consisting of three integers n,ln,l and rr. Find the value of BB corresponding to which f(n,B)f(n,B) is minimum for all l≤B≤rl≤B≤r. If there are multiple such values, you can print any of them.

Input Format

  • The first line contains in single integer QQ, the number of queries
  • Each of the next Q lines contain three space separated integers n,ln,l and rr respectively.

Output Format

  • For each query (n l r), print the value of base BB which lies within [l,r][l,r] such that f(n,B)f(n,B) is minimum.

Constraints

  • 1≤Q≤1031≤Q≤103
  • 2≤n≤1092≤n≤109
  • 2≤l≤r≤1092≤l≤r≤109

Subtasks

Subtask #1 (50 points): original constraints

This problem is worth a total of 50 points and is meant to be complementary to the problem “MNDIGSM2” (also worth 50 points) which is very similar to this problem, but has slightly different constraints.

Sample Input 1 

3

216 2 7
256 2 4
31 3 5

Sample Output 1

6

2
5

Explanation

Test case 11: We have f(216,2)=f(216,3)=4f(216,2)=f(216,3)=4, f(216,4)=6f(216,4)=6, f(216,5)=8f(216,5)=8, f(216,6)=1f(216,6)=1 and finally f(216,7)=12f(216,7)=12. Clearly the minimum is obtained when B=6B=6.

Test case 22: Note that f(256,2)=f(256,4)f(256,2)=f(256,4) = 22, therefore both the answers 22 and 44 will be considered correct.

Test case 33: f(31,3)=f(31,5)=3f(31,3)=f(31,5)=3 and f(31,4)=7f(31,4)=7, therefore both the answers 33 and 55 will be considered correct.

    Click For <<<Minimize Digit Sum Solution>>> Solution







Comments

Post a Comment