PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Utkarsh Gupta
Tester: Samarth Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
Cakewalk
PREREQUISITES
None
PROBLEM
The chef is standing facing North. For the next X second, he rotates exactly 90 degrees in the clockwise direction. Find the direction of Chef after X seconds where 1 \leq X \leq 100
Note: There are only 4 directions: North, East, South, West (in clockwise order).
QUICK EXPLANATION
- After every 4 rotation, the Chef faces the same direction as before. So let’s group all rotations in buckets of 4. The last bucket may be unfilled.
- All buckets containing 4 rotations do not change the direction. We only care about the last bucket, which may have less than 4 rotations.
- We can simulate the last three rotations or write cases to identify the final direction.
EXPLANATION
Since the constraints of this problem are small, a simulation-based solution is acceptable along the following lines.
dir = 'N'
repeat X times:
if(dir == 'N')dir = 'E'
else if(dir == 'E')dir = 'S'
else if(dir == 'S')dir = 'W'
else if(dir == 'W')dir = 'N'
The final value stored in dir represents the final direction. This solution takes O(X) time.
We can also solve it in O(1) as well, by noticing that rotating 4 times is equivalent to not rotating at all.
So we can say that doing X rotation gets same direction as doing X - 4 rotations, X-8 rotations … and (X - 4*C) for some C where X-4*C \geq 0. We can choose C = \lfloor X/4 \rfloor, which makes X-4*C = X \bmod 4.
Hence, we only need to perform up to 3 rotations, as we can replace X with X \bmod 4. We can use the above simulation or write cases to find out the final direction.
TIME COMPLEXITY
The time complexity is O(X) or O(1) per test case.
SOLUTIONS
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
ll n;
cin>>n;
n%=4;
if(n==0)
cout<<"North\n";
else if(n==1)
cout<<"East\n";
else if(n==2)
cout<<"South\n";
else if(n==3)
cout<<"West\n";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int T=1;
cin>>T;
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
t = readIntLn(1, 100);
int sum = 0;
while(t--){
int n;
n = readIntLn(1, 1000);
if(n%4 == 0)
cout << "North\n";
else if(n%4 == 1)
cout << "East\n";
else if(n%4 == 2)
cout << "South\n";
else
cout << "West\n";
}
readEOF();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class FACEDIR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
String[] D = new String[]{"North", "East", "South", "West"};
int dir = ni()%4;
pn(D[dir]);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new FACEDIR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 