[Solution] Slow Solution solution codechef

Slow Solution solution codechef – Chef is trying to solve a problem having TT test cases, where, for each test case he is given a single integer NN.

Table of Contents

[Solution] Slow Solution solution codechef

Chef has an algorithm which takes exactly N2N2 iterations for a test case with value NN.

The constraints of the problem are as follows:

  • 1TmaxT1≤T≤maxT
  • 1NmaxN1≤N≤maxN
  • Sum of NN over all test cases does not exceed sumNsumN.

Given the values maxT,maxN,maxT,maxN, and sumNsumN, determine the maximum number of iterations Chef’s algorithm can take for any valid input file satisfying all the constraints.

Formally speaking, find the maximum value of N21+N22++N2TN12+N22+⋯+NT2 for any valid input file satisfying all the constraints.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of single line consisting of three integers maxT,maxN,maxT,maxN, and sumNsumN.

[Solution] Slow Solution solution codechef

For each test case, output the the maximum number of iterations Chef’s algorithm can take in any valid test file.

Constraints

  • 1T10001≤T≤1000
  • 1maxTmaxNsumN1041≤maxT≤maxN≤sumN≤104

Sample Input 1 

4
10 100 200
3 10 100
1000 1000 2200
100 100 100

Sample Output 1 

20000
300
2040000
10000

[Solution] Slow Solution solution codechef Explanation

Test Case 11: Worst case for Chef’s algorithm would be where T=2T=2 and N=100N=100 for both the test cases. In this case, Chef’s algorithm will take 1002+1002=200001002+1002=20000 iterations.

Test Case 22: Worst case for Chef’s algorithm would be where T=3T=3 and N=10N=10 for all the 33 test cases. In this case, Chef’s algorithm will take 102+102+102=300102+102+102=300 iterations.

Test Case 33: Worst case for Chef’s algorithm would be where T=3T=3 and N=1000,1000,N=1000,1000, and 200200 for the three test cases respectively. In this case, Chef’s algorithm will take 10002+10002+2002=204000010002+10002+2002=2040000 iterations.

Test Case 44: Worst case for Chef’s algorithm would be where T=1T=1 and N=100N=100. In this case Chef’s algorithm will take 1002=100001002=10000 iterations.

For Solution

Click Here

Leave a Comment