Apocalypse - APCLYPSE CodeChef Beginner level Question
Hello Everyone , welcome back to my blog on competitive programming .
Today we will be discussing a very easy question APOCALYPSE - code named APCLYSE
Here is a link to the PROBLEM
So the question is very straightforward , we just need to find in how many days the whole earth will get infected.
The prerequisite for this question is just simple geometry and logic.
Solution :-
So the key to the solution is to check the sum of the absolute value of the row number and the column number with respect to the starting block.
In each day , the various will cover a sum it initially had +1 starting from 0.
This can very easily be proved by induction diagramatically .
Do , draw the figure and check it out.
Next , just check the 4 outermost blocks . If all of them are infected means that the whole Earth is infected .
So , check the sum of the row number and the column number with respect to the starting block of each of the 4 blocks and display the highest of them . This would be our answer .
Please take a look at the following C++ code to understand the solution
Code:-
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
long int r,c;
cin>>r>>c;
long int x,y;
cin>>x>>y;
r--;c--;
long int u=0,v=0;
long int arr[4]={0,0,r,r};
long int arr1[4]={0,c,0,c};
long int max=0;
for(int i=0;i<4;i++)
{
u=abs(arr[i]-x);
v=abs(arr1[i]-y);
if(u+v>max)
{
max=u+v;
}
}
cout<<max<<endl;
}
// your code goes here
return 0;
}
Today we will be discussing a very easy question APOCALYPSE - code named APCLYSE
Here is a link to the PROBLEM
So the question is very straightforward , we just need to find in how many days the whole earth will get infected.
The prerequisite for this question is just simple geometry and logic.
Solution :-
So the key to the solution is to check the sum of the absolute value of the row number and the column number with respect to the starting block.
In each day , the various will cover a sum it initially had +1 starting from 0.
This can very easily be proved by induction diagramatically .
Do , draw the figure and check it out.
Next , just check the 4 outermost blocks . If all of them are infected means that the whole Earth is infected .
So , check the sum of the row number and the column number with respect to the starting block of each of the 4 blocks and display the highest of them . This would be our answer .
Please take a look at the following C++ code to understand the solution
Code:-
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
long int r,c;
cin>>r>>c;
long int x,y;
cin>>x>>y;
r--;c--;
long int u=0,v=0;
long int arr[4]={0,0,r,r};
long int arr1[4]={0,c,0,c};
long int max=0;
for(int i=0;i<4;i++)
{
u=abs(arr[i]-x);
v=abs(arr1[i]-y);
if(u+v>max)
{
max=u+v;
}
}
cout<<max<<endl;
}
// your code goes here
return 0;
}
Do post your doubts in the comments section
Comments
Post a Comment