CodeChef October long problem:Covid Run

 CodeChef October long problem:Covid Run

Covid-19$19$ is spreading fast! There are N$N$ cities, numbered from 0$0$ to (N−1)$(N-1)$, arranged in a circular manner. City 0$0$ is connected to city 1$1$, 1$1$ to 2$2$, …$\dots$, city (N−2)$(N-2)$ to city (N−1)$(N-1)$, and city (N−1)$(N-1)$ to city 0$0$.

The virus is currently at city X$X$. Each day, it jumps from its current city, to the city K$K$ to its right, i.e., from city X$X$ to the city (X+K)%N$(X+K)\mathrm{\%}N$. As the virus jumps, the cities in between don't get infected. Cities once infected stay infected. You live in city Y$Y$. Find if it will reach your city eventually. If it will, print YES, else print NO.

Input:

• The first line of the input consists of an integer T$T$, the number of test cases.
• The first and only line of each test case contains four space-separated integers - N$N$, K$K$, X$X$ and Y$Y$, denoting the number of cities, the size of jumps, Covid's current city, and the city that you live in, respectively.

Output:

For each test case, in a new line, print YES if Covid shall reach your city after a finite number of days, else print NO.

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N≤1000$1\le N\le 1000$
• 0≤X,Y≤N−1$0\le X,Y\le N-1$
• 0≤K≤1000$0\le K\le 1000$

Subtasks

• Subtask 1 - 100% - Original constraints

Sample Input:

2
6 2 5 3
12 3 4 2

Sample Output:

YES
NO

Explanation:

• In the first sample, Covid starts at city 5$5$, then goes to city 1$1$, and then from city 1$1$ to city 3$3$. Thus, it reaches the city that you live in.

• In the second sample, Covid starts at city 4$4$, goes to city 7$7$, then 10$10$, 1$1$, then 4$4$, 7$7$, 10$10$, …$\dots$, and so on. It never reaches city 2$2$.

Solution:

#include <iostream>

using namespace std;

int main() {

int test = 0;

        // Insert the number of test cases

cin>>test;

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

    int n=0,k=0,x=0,y=0;

            //Take in the values of the n,k,x,y

    cin>>n>>k>>x>>y;

            //Initialize the array of n to 0

    int arr[n] = {0};

            

            //Mark the initially infected city,we will use 1 for infected and 0 for not infected

    arr[x-1] = 1;

            //the x element in array will be x-1 as numbering starts from 0

    x = x-1;

    while(true){

                //the next infected city

        x = (x+k)%n;

        //if the city is already infected,the cycle has started and no new city can be infected

        if(arr[x] == 1){

            break;

        }

                //else infect the city 

        else{

            arr[x] = 1;

        }

    }

    

            //check if the city is infected

    if(arr[y-1] == 1){

        cout<<"YES"<<"\n";

    }

    else{

        cout<<"NO"<<"\n";

    }

}

return 0;

}

 

Hope this helps ,if you have any doubt,plz put them in comment section

😀