Google Code Jam – Template C++ by vudduu

vudduu: Este es el template de C++ que me gusta usar, pero mas que todo con el que me siento comodo en las rondas del codejam.

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

bool solve() {

}

int main() {
    freopen("a.txt", "r", stdin);
    // freopen("small-input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for(int cas=1; cas<=T ;cas++) {
        printf("Case #%d: ", cas);
        if(solve()) printf("YESn");
        else printf("NOn");
    }
}

Antes de cada competencia es bueno saber cuantas operaciones pueden realizar por segundo en sus equipos. Como Gareve dice necesitamos conocer ese numero magico que seria nuestro tope.

En C++ pueden obtener este numero magico ejecutando el siguiente código.

#include <iostream>
#include <time.h>
using namespace std;

int main() {
    double ini = clock();
    int c = 0;
    while(double(clock()-ini)/1000000.0 < 1.0)
        c++;
    cout<<"operaciones: "<< c << " " << double(clock()-ini)/1000000.0 << endl;
}

Codechef June 2013

I’ll describe my solutions of Codechef – June 2013. In this contest I have solved 5 problems using C++.

  • Lapindromes (Ad Hoc – Implementation)
  • Predictopus (Probability)
  • W String (Ad Hoc – Implementation)
  • Dessert Wizard (Ad Hoc – Implementation)
  • Little Elephant and Mouses(Dynamic Programming)

Sigue leyendo

Google Code Jam – Round 1B 2013

Solution of Problem B. Falling Diamonds small:

It can be solved following the next steps:

  1. Find the center of the pyramid: because each solution has a pyramid.
  2. If the point is in the pyramid 100% of times will have a diamond.
  3. If the point is not up to the pyramid 0% of times will have a diamond.
  4. Calculate the provability with SetsWithDiamondOnXY / TotalValidSets Sigue leyendo

TopCoder – Single Round March 537

Here is my Div1-250 solution.

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

bool oki(int A, int x, int y){
   F(i, 201){
      if(A - (x*i) >= 0)
      if((A - (x*i)) % y == 0) return true;
      if(A - (y*i) >= 0)
      if((A - (y*i)) % x == 0) return true;
   }
   return false;
}

class KingXNewCurrency {
public:
   int howMany(int A, int B, int X) {
      int t = 0;
      FOR(y, 1, 206)
         if(oki(A, X, y) && oki(B, X, y))
            t++;
      if(t == 205) return -1;
      return t;
   }
}

Facebook Hacker Cup 2012 Round 1 – Recover the Sequence

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

int n, its;
string s;

vector<int> merge2(vector<int> arr1, vector<int> arr2){
   vector<int> result;
   int i=0, j=0;
   while(i < arr1.size() && j < arr2.size()) {
      if(s[its] == '1') result.PB(arr1[i++]);
      else result.PB(arr2[j++]);
      its++;
   }
   while(i < arr1.size()) result.PB(arr1[i++]);
   while(j < arr2.size()) result.PB(arr2[j++]);
   return result;
}

vector<int> reverse_sort(vector<int> arr){
   int k = arr.size();
   if(k <= 1) return arr;
   int mid = int(k/2);
   vector<int> first_half, second_half;
   F(i, mid) first_half.PB(arr[i]);
   FOR(i, mid, arr.S) second_half.PB(arr[i]);
   first_half = reverse_sort(first_half);
   second_half = reverse_sort(second_half);
   return merge2(first_half, second_half);
}

int checksum(vector<int> arr) {
    int result = 1;
    for(int i=0; i<arr.size() ;i++)
       result = (31 * result + arr[i]) % 1000003;
    return result;
}

vector<int> solve(){
   vector<int> v(n), r(n);
   F(i, n) v[i] = i;
   v = reverse_sort(v);
   F(i, n) r[ v[i] ] = i+1;
   return r;
}

int main(){
   //freopen("a.in", "r", stdin);
   //freopen("recover_the_sequence.txt", "r", stdin); freopen("a.out", "w", stdout);
   int t;
   scanf("%d", &t);
   F(cas, t){
      cin>>n>>s;
      its = 0;
      printf("Case #%d: %dn", cas+1, checksum(solve()));
   }
}