Soluciones Regionals 2010 :: North America - Greater NY

Nim-BSum-wrong.cpp

vector<int> to_num(int t,int base){
	vector<int>	ans;
	while(t){
		ans.push_back(t%base);
		t/=base;
	}
	return ans;
}

int to_dec(vector<int> n,int base){
	int ans = 0;
	reverse(all(n));
	for(int i=0;i<n.size();++i){
		ans*=base;
		ans+=n[i];
	}
	return ans;
}


int solve2(int b,int x,int y){
	vector<int>	n1 = to_num(x,b);
	vector<int>	n2 = to_num(y,b);
	int tope = min(n1.size(),n2.size());
	vector<int> ans(max(n1.size(),n2.size()));
	for(int i = 0;i<tope;++i){
		ans[i] = ((n1[i]+n2[i])%b);
	}	
	if(n2.size() > n1.size())
		for(int i = n1.size();i<n2.size();++i)
			ans[i] = (n2[i]);
	else
		for(int i = n2.size();i<n1.size();++i)
			ans[i] = (n2[i]);
	return to_dec(ans,b);

}

Nim-BSum.cpp

/**
* Manuel Pineda
*/
using namespace std;
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define all(x) x.begin(),x.end()
#define D(x) cout<< #x " = "<<(x)<<endl

/**
* Simulación
*/

int solve(int b,int x,int y){
	int ans = 0;
	int a[1000000];
	int index=0;
	while((x!=0) or (y!=0)){
		int d1 = x%b;
		int d2 = y%b;
		x/=b;
		y/=b;
		int da = (d1+d2)%b;
		a[index++]=da;
	}
	while(index--){
		ans*=b;
		ans+=a[index];
	}
	
	return ans;

}

int main(){
	int numc,cas;cin>>numc;
	int base;
	int n1,n2;
	while(numc--){
		cin>>cas>>base>>n1>>n2;
		cout<<cas<<" "<<solve(base,n1,n2)<<endl;
	}
	return 0;
}

Non-DecreasingDigits.cpp

/**
* Manuel Pineda
*/
using namespace std;
#include<iostream>
#include<map>
#include<string>
#include<cstring>

typedef long long int lli;

// Estructura para hacer memorización.
lli dp[70][15];


/**
* La idea es contar cuántos números existen de longitud a
* con números crecientes, mayores o iguales a b.
* Para esto podemos hacer una función que intente "poner"
* todos los números (i) mayores o iguales a b.
* Con esta idea, vemos que ahora tenemos que solucionar un subproblema
* contar para una longitud a - 1 y todos los números mayores o iguales a i.
* El caso base es cuando la longitud es 1 en cuyo caso la solución es 1.
*/

lli solve(int a,int b){
	if(dp[a][b]!=-1) return dp[a][b];
	
	if(a==1) return dp[a][b] = 1LL;
	lli ans = 0;
	for(int i=b;i<=9;++i){
		ans += solve(a-1,i);
	}
	return dp[a][b] = ans;

}



int main(){
	int c;cin>>c;
	while(c--){
		int k;cin>>k;
		int a;cin>>a;
		memset(dp,-1,sizeof(dp));
		cout<<k<<" "<<solve(a+1,0)<<endl;
	
	}

	return 0;
}

PenneyGame.cpp

/**
* Manuel Pineda
*/
using namespace std;
#include<iostream>
#include<map>
#include<string>
#include<cstring>

map<string,int> cod;

/**
* Simulación
*/

int main(){
	cod["TTT"]=0;
	cod["TTH"]=1;
	cod["THT"]=2;
	cod["THH"]=3;
	cod["HTT"]=4;
	cod["HTH"]=5;
	cod["HHT"]=6;		
	cod["HHH"]=7;
	
	int num;cin>>num;
	int dset;
	int sets[8];
	string cad;
	string t;
	while(num--){
		memset(sets,0,sizeof(sets));
		cin>>dset;
		cin>>cad;
		cout<<dset<<" ";
		for(int i=0;i<cad.size()-2;++i){
			string tmp ="";
			for(int j=0;j<3;++j)
				tmp+=cad[i+j];
			sets[cod[tmp]]++;
		}
		for(int i=0;i<8;++i)
			cout<<sets[i]<<((i<7)?" ":"\n");
	
	}

	return 0;
}