BELLA CIAO (CHFHIEST) Solution — Codechef JuneLong Challenge

Problem Statement

Chef is planning a heist in the reserve bank of Chefland. They are planning to hijack the bank for D days and print the money. The initial rate of printing the currency is P dollars per day and they increase the production by Q dollars after every interval of d days. For example, after d days the rate is P+Q dollars per day, and after 2d days the rate is P+2Q dollars per day, and so on. Output the amount of money they will be able to print in the given period.

Input

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• Each test case contains a single line of input, four integers D,d,P,Q.

Output

For each test case, output in a single line the answer to the problem.

Constraints

• 1≤T≤10⁵
• 1≤d≤D≤10⁶
• 1≤P,Q≤10⁶

Subtasks

Subtask #1 (15 points): d≤D≤100

Subtask #2 (85 points): original constraints

Sample Input

3
2 1 1 1
3 2 1 1
5 2 1 2

Sample Output

3
4
13

Explanation

Test Case 1:

• On the first day, the rate of production is 1 dollar per day so 1 dollar is printed on the first day.
• On the second day, the rate of production is 1+1=2 dollars per day so 2 dollars are printed on the second day.
• The total amount of money printed in 2 days is 1+2=3 dollars.

Test Case 2:

• For the first two days, the rate of production is 1 dollar per day so 1⋅2=2 dollars are printed on the first two days.
• On the third day, the rate of production is 1+1=2 dollars per day so 2 dollars are printed on the third day.
• The total amount of money printed in 3 days is 2+2=4 dollars.

Test Case 3:

• For the first two days, the rate of production is 1 dollar per day so 1⋅2=2 dollars are printed on the first two days.
• On the next two days, the rate of production is 1+2=3 dollars per day so 3⋅2=6 dollars are printed on the next two days.
• On the last day, the rate of production is 3+2=5 dollars per day so 5 dollars are printed on the last day.
• The total amount of money printed in 5 days is 2+6+5=13 dollars.

Code (Solution)

The code has been implemented in Java

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        //SOLUTION
        FastReader sc = new FastReader();
        long t = sc.nextLong();
        while(t-- > 0){
        long D,d,p,q;
        D = sc.nextLong();
        d = sc.nextLong();
        p = sc.nextLong();
        q = sc.nextLong();
        long n = D/d;
        long sol=0;
        sol= n*p*d + q*d*(n*(n-1))/2 + (D%d)*(p+n*q);
        System.out.println(sol);
        }
    }
    // Below are just the classes needed for fast Input in Java with Fast Reader
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.

References

Contest Page | CodeChef

(Video Editorial Link For Better Explanation)