CodeChef – May Cook-off 2013

Problem C – Subtraction Game 1

A simple simulation using a std::set while the set has more than one element solves this problem.

#include <iostream>
#include <vector>
#include <set>
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 S           size()
#define MP          make_pair
typedef long long   LL;

int N;
vector<int> A;

void solve() {
	set<int> conj(ALL(A)), aux;
	while(conj.S != 1) {
		A = vector<int>(ALL(conj));
		FOR(i, 1, A.S) {
			A[i] = A[i]%A[0];
			if(A[i] == 0) A[i] = A[0]; //when the result of module operation is 0
		}
		conj = set<int> (ALL(A));
	}
	printf("%dn", (*conj.begin()) );
}

int main() {
	int T;
	scanf("%d", &T);
	F(cas, T) {
		scanf("%d", &N);
		A.resize(N);
		F(i, N) scanf("%d", &A[i]);
		solve();
	}
}

Problem D – Subtraction Game 2

For this problem the solution is not to difficult but the judge only accept the fast ones. Only sets with Greater Common Divisor equal to 1 are valid. This is my solution using Dynamic Programming.

Recurrence Relation:

[latexpage][ DP [i][ GCD(j, A[i]) ] = sum_{j=1}^{10000}{ DP[i-1][j] } ]

But that needs a “for” from 1 to 10000 and I got some TLE with that, it needs a set of numbers in DP[i][?] that are greater than 0.

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long   LL;

int N, A[61];
LL dp[61][10001];

void solve() {
	int aux, j;
	set<int> its;
	dp[0][A[0]]++;
	its.insert(A[0]);
	for(int i=1; i<N ;i++) {
		for(set<int>::iterator it=its.begin(); it!=its.end() ;it++) {
			j = (*it);
			dp[i][j] += dp[i-1][j];

			aux = __gcd(j, A[i]);
			dp[i][ aux ] += dp[i-1][j];
			its.insert(aux);
		}
		dp[i][A[i]]++;
		its.insert(A[i]);
	}
	printf("%lldn", dp[N-1][1]);
}

int main() {
	int T=0;
	scanf("%d", &T);
	for(int cas=0; cas<T ;cas++) {
		scanf("%d", &N);
		for(int i=0; i<N ;i++)
			scanf("%d", A+i);
		memset(dp, 0, sizeof(dp));
		solve();
	}
}

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s