google code jam 2019 round 1C all questions solutions

-

1.  ROBOT PROGRAMMING STRATEGY: C++



#include <bits/stdc++.h>
   
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 1e9+7;
   
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; assert(scanf("%lld", &x) == 1); return x;}
ld fin(){double x; assert(scanf("%lf", &x) == 1); return x;}
char yuyushiki[1000010]; string stin(){assert(scanf("%s", yuyushiki) == 1); return yuyushiki;}

// head

string solve(){
  ll n = in();
  vector<string> ss(n);
  REP(i, n){
    ss[i] = stin();
  }
  string ans = "";
  vector<bool> live(n, true);
  REP(q, INF){
    ll r = 0;
    ll s = 0;
    ll p = 0;
    REP(i, n){
      if(live[i]){
        char c = ss[i][q%SZ(ss[i])];
        if(c == 'R'){
          r = 1;
        } else if(c == 'S'){
          s = 1;
        } else if(c == 'P'){
          p = 1;
        }
      }
    }
    if(r + s + p == 0){
      break;
    }
    if(r + s + p == 3){
      return "IMPOSSIBLE";
    }
    if(r + s + p == 1){
      if(r == 1){
        ans += 'P';
      } else if(s == 1){
        ans += 'R';
      } else if(p == 1){
        ans += 'S';
      }
      return ans;
    }
    if(r + s + p == 2){
      if(r == 0){
        // s p
        ans += 'S';
        REP(i, n){
          char c = ss[i][q%SZ(ss[i])];
          if(c == 'P'){
            live[i] = false;
          }
        }
      } else if(s == 0){
        // r p
        ans += 'P';
        REP(i, n){
          char c = ss[i][q%SZ(ss[i])];
          if(c == 'R'){
            live[i] = false;
          }
        }
      } else if(p == 0){
        // r s
        ans += 'R';
        REP(i, n){
          char c = ss[i][q%SZ(ss[i])];
          if(c == 'S'){
            live[i] = false;
          }
        }
      }
    }
  }
  return ans;
}

int main(){

  ll t = in();
  FOR(i, 1, t+1){
    string ans = solve();
    printf("Case #%lld: %s\n", i, ans.c_str());
  }

  return 0;
}


2.     POWER ARRANGERS:C++

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; assert(scanf("%lld", &x) == 1); return x;}
ld fin(){double x; assert(scanf("%lf", &x) == 1); return x;}
char yuyushiki[1000010]; string stin(){assert(scanf("%s", yuyushiki) == 1); return yuyushiki;}

// head

ll t, f;

ll ask(ll a, ll b){
  ll p = a * 5 + b + 1;
  printf("%lld\n", p);
  fflush(stdout);
  string s = stin();
  return s[0] - 'A';
}

void solve(){
  vector<vector<ll>> a(119, vector<ll>(5, -1));
  vector<bool> live(119, true);
  vector<bool> used(5, false);
  vector<ll> ans(5, -1);
  ll al = 120;
  REP(p, 5){
    vector<ll> cnt(5, 0);
    REP(i, 119){
      if(live[i]){
        ll res = ask(i, p);
        a[i][p] = res;
        cnt[res]++;
      }
    }
    // cerr << cnt << " : " << al / (5 - p) - 1 << endl;
    REP(i, 5){
      if(!used[i] && cnt[i] == al / (5 - p) - 1){
        ans[p] = i;
        used[i] = true;
      }
    }
    REP(i, 119){
      if(a[i][p] != ans[p]){
        live[i] = false;
      }
    }
    al /= 5 - p;
  }
  // cerr << ans << endl;
  REP(i, 5){
    printf("%c", (char)(ans[i] + 'A'));
  }
  printf("\n");
  fflush(stdout);
  string s = stin();
  if(s[0] == 'N'){
    exit(0);
  }
}

int main(){

  t = in();
  f = in();

  REP(i, t){
    solve();
  }
  
  
  return 0;
}


3.   BACTERIAL TACTICS:CPP(c++)

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; assert(scanf("%lld", &x) == 1); return x;}
ld fin(){double x; assert(scanf("%lf", &x) == 1); return x;}
char yuyushiki[1000010]; string stin(){assert(scanf("%s", yuyushiki) == 1); return yuyushiki;}

// head

ll n, m;
vector<string> s;

ll memo[16][16][16][16];

ll dfs(ll t, ll l, ll b, ll r){
  if(memo[t][l][b][r] != -1){
    return memo[t][l][b][r];
  }
  vector<bool> nex(256, false);
  FOR(i, t, b){
    FOR(j, l, r){
      if(s[i][j] == '.'){
        // v
        bool f = false;
        FOR(k, t, b){
          if(s[k][j] == '#'){
            f = true;
          }
        }
        if(!f){
          ll res = dfs(t, l, b, j) ^ dfs(t, j+1, b, r);
          nex[res] = true;
        }
        // h
        f = false;
        FOR(k, l, r){
          if(s[i][k] == '#'){
            f = true;
          }
        }
        if(!f){
          ll res = dfs(t, l, i, r) ^ dfs(i+1, l, b, r);
          nex[res] = true;
        }
      }
    }
  }
  REP(i, 256){
    if(!nex[i]){
      return memo[t][l][b][r] = i;
    }
  }
}

ll solve(){
  n = in();
  m = in();
  s.assign(n, "");
  REP(i, n){
    s[i] = stin();
  }
  REP(i, 16){
    REP(j, 16){
      REP(k, 16){
        REP(l, 16){
          memo[i][j][k][l] = -1;
        }
      }
    }
  }
  ll ans = 0;
  ll t = 0, b = n;
  ll l = 0, r = m;
  FOR(i, t, b){
    FOR(j, l, r){
      if(s[i][j] == '.'){
        // v
        bool f = false;
        FOR(k, t, b){
          if(s[k][j] == '#'){
            f = true;
          }
        }
        if(!f){
          ll res = dfs(t, l, b, j) ^ dfs(t, j+1, b, r);
          if(res == 0){
            ans++;
          }
        }
        // h
        f = false;
        FOR(k, l, r){
          if(s[i][k] == '#'){
            f = true;
          }
        }
        if(!f){
          ll res = dfs(t, l, i, r) ^ dfs(i+1, l, b, r);
          if(res == 0){
            ans++;
          }
        }
      }
    }
  }
  return ans;
}

int main(){

  ll t = in();
  FOR(i, 1, t+1){
    ll ans = solve();
    printf("Case #%lld: %lld\n", i, ans);
  }
  
  return 0;
}


Comments

Post a Comment

Popular posts from this blog

Amazon Web Services

-
Image
Domains Of AWS :-  1. Compute 2. Migration 3. Security and Identity compliance 4. Storage 5. Networking and Content Delivery 6. Messaging Domain 7. Database Domain We will discuss about every Domain of AWS in this post . So let's start . AWS SERVICES - A.  EC2 -  Amazon Elastic Compute Cloud (Amazon  EC2 ) is a web service that provides secure, scalable compute capacity in the cloud.   It is like a web server that can be resized according to number of configuration.  Resizable compute capacity in the cloud , which can be customize according to your need . It is used to host your a application . B. Lambda -   AWS Lambda  is a compute service that makes it easy for you to build applications that respond quickly to new information .  This is an aws service that executes background tasks.It is not used to host an application. example : file compression in background . AWS Lambda is an event-driven, serverless computing plat...
Read more

Hacker Rank all java and python problem solutions

-
JAVA : 1.  https://codexmaze.blogspot.com/2019/05/hacker-rank-java-problem-1-solution.html    2. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-2nd-solution.html 3. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-3rd-question-solution.html 4. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-4th-solution.html       5. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-5th-solution.html 6. https://codexmaze.blogspot.com/2019/05/hacker-rank-6th-question-solution.html 7. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-7th-problem-solution.html 8. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-8th-problem-silution.html 9. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-9th-question-solution.html 10. https://codexmaze.blogspot.com/2019/05/hacker-rank-java-10th-problem-solution.html 11. https://codexmaze.blogspot.com/2019/05/hacker-rank-11th-java-problem-solution.html 12  https://c...
Read more

Testing tools for React Apps

-
Image
In today's blog we will discuss some testing tools of react apps .In general we write code to work, but now a days only writing a code is not enough , it should be less complex and more accurate ,efficient too . 1. ESLINT :- There are so many formats in which java Scripts code is written now a days by different developer so before developing a project coding styles parameters are being set for the react apps .(here react app means , reactjs and react native) . example - function add(x, y){     return x+y ; } ES6 syntax - const add = (x, y) => {     return x+y } Both syntax are correct  but setting a parameter is vary important . That's what is done by eslint; It is also use for the testing of a function : example -  // App.js function add(x, y) {     return x+y; } 2. console.log testing :- test : console.warn(add(1,2) === 3 , "this is a error function"); console.warn(add(1,6) === 7 , "this is a error function"); con...
Read more