August Circuits '21 Non-decreasing arrays Solution

Non-decreasing arrays

Max. score: 100

You are given an array $A$ consisting of $N$ positive integers. Your task is to find an array $B$ of length $N$ satisfying the following conditions:

• $B_i>0$ for all $1\le i\le N$
• $B_i\le B_{i+1}$, for all $1\le i<N$
• $B_i$ is divisible by $A_i$ for all $1\le i\le N$
• $\sum _{i=1}^N{B}_i$ is minimum

You are given $T$ test cases.

Input format

• The first line contains a single integer $T$ denoting the number of test cases.
• The first line of each test case contains a single integer $N$ denoting the length of the array.
• The second line of each test case contains $N$ space-separated integers denoting the integer array $A$.

Output format

For each test case (in a separate line), print $N$ space-separated integers denoting $B_1,B_2,..,B_N$. If there are multiple answers, you can print any of them. It is guaranteed that under the given constraints at least 1 $B$ exists.

Constraints

$$\begin{gathered} 1\le T\le 1000 \\ 1\le N\le 2.5\times {10}^5 \\ 1\le A_i\le {10}^9 \\ \text{Sum of N over all test cases does not exceed }7.5\times {10}^5 \end{gathered}$$

SAMPLE INPUT

 

2
3
2 1 3
2
5 1

SAMPLE OUTPUT

 

2 2 3
5 5

Explanation

Self explanatory.

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Score is assigned if any testcase passes.

Allowed Languages:Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

Solution In C++

#include <iostream>

#include <cmath>

using namespace std;

int main(){

    int t;

    cin>>t;

    while(t--){

        long long int n;

        cin>>n;

        int a[n];

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

            cin>>a[i];

        }

        long long int res=a[0];

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

            if(res%a[i]!=0){

                res=ceil(res/(1.0*a[i]))*a[i];

            }

            cout<<res<<" ";

        }

        cout<<endl;

    }

}

Solution In C

#include <stdio.h>

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        long long int n;

        scanf("%d",&n);

        int a[n];

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

            scanf("%d",&a[i]);

        }

        long long int res=a[0];

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

            if(res%a[i]!=0){

                res=ceil(res/(1.0*a[i]))*a[i];

            }

            printf("%d ",res);

        }

        printf("\n");

    }

}