11420 – Chest of Drawers

A Dynamic Programming combinatorics problem.
You start placing the drawers one by one and each time you decide between locked and unlocked. During this process, keep track of the number of drawers placed so far and the number of secure ones. If both reach your target, count that as one solution. The DP solution:

• State S(n, s, l) – n is number of drawers waiting to be placed, s number of secured drawers required and l whether the previous drawer is locked.
• Transition S(n, s, l) = S(n - 1, s - l, true) + S(n - 1, s, false) – You can place a locked drawer which decreases the number of required secured drawers, if and only if the previous drawer is locked. Placing an unlocked drawer only decreases the number of remaining drawers.

Caution!

• long long isn’t enough!

C++ top-down implementation:

#include <iostream>
#include <cstring>
using namespace std;

#define N 128

unsigned long long nWays[N][N][2];

unsigned long long getNWays(int n, int s, bool l) {
	if (n == 0 && s == 0)
		return nWays[n][s][l] = 1;
	if (s > n || n < 0 || s < 0)
		return 0;
	if (nWays[n][s][l] != -1)
		return nWays[n][s][l];
	return nWays[n][s][l] = getNWays(n - 1, s - l, true) + getNWays(n - 1, s, false);
}

int main() {
	memset(nWays, -1, sizeof nWays);
	int n, s;
	while (cin >> n >> s && n >= 0 && s >= 0)
		cout << getNWays(n, s, true) << endl;
	return 0;
}

1213 – Sum of Different Primes

A Dynamic Programming problem.
Simply, you combine primes — which you generated one way or another — that add up to the input. This combination should be executed via Dynamic Programming. Your state consists of:

• n – the number that needs decomposition.
• k – the number of primes n should be divided into.
• i – the lowest prime number that can be used in the next decomposition. This is to avoid repeated primes in the sum.

Your transitions from S(n, k, i) are:

• S(n – prime[i], k – 1, i + 1) – subtract the current prime.
• S(n, k, i + 1) – bypass it.

C++ implementation:

#include <iostream>
#include <cstring>
using namespace std;

#define N 2048
#define P 309
#define K 16

long long nWays[N][K][P], prime[P];

void sieve() {
	int nPrime = 0, isPrime[N];
	memset(isPrime, true, sizeof isPrime);
	isPrime[0] = isPrime[1] = true;
	for (int i = 2; i < N; ++i)
		if (isPrime[i] && (prime[nPrime++] = i))
			for (int j = i * i; j < N; j += i)
				isPrime[j] = false;
}

long long getNWays(int n, int k, int i) {
	if (n == 0 && k == 0)
		return 1;
	if (n < 0 || k < 0 || prime[i] > n || i == P)
		return 0;
	if (nWays[n][k][i] != -1)
		return nWays[n][k][i];
	return nWays[n][k][i] = getNWays(n - prime[i], k - 1, i + 1) + getNWays(n, k, i + 1);
}

int main() {
	// init
	sieve();
	memset(nWays, -1, sizeof nWays);
	// solve
	int n, k;
	while (cin >> n >> k && (n || k))
		cout << getNWays(n, k, 0) << endl;
	return 0;
}

438 – The Circumference of the Circle

A circumcircle problem.
Given a triangle, find the circumference of its circumcircle. There’s an easy way and a hard way.
The hard way is to find the circle’s centre then calculate the radius. I used this solution for a previous problem. Code:

#include <iostream>
#include <complex>
#include <limits>
using namespace std;

typedef long double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
const gtype len_before_point_digits = 1E6;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define perp(p) ( point((p).y, -(p).x) )
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
#define circC(r) (2 * pi * abs(r))
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3], v[2][2], c;
	gtype r;
	cout.precision(2);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		// perp 1
		v[0][0] = 0.5l * (p[0] + p[1]);
		v[0][1] = perp(p[1] - p[0]) + v[0][0];
		// perp 2
		v[1][0] = 0.5l * (p[1] + p[2]);
		v[1][1] = perp(p[2] - p[1]) + v[1][0];
		// intersect
		gtype d = intrD(v[0][0], v[0][1], v[1][0], v[1][1]);
		if (!equ(d, 0, epsLen)) {
			c = intrN(v[0][0], v[0][1], v[1][0], v[1][1]) / d;
			r = abs(c - p[0]);
		} else
			r = 0;
		// out
		cout << fixed << circC(r) << endl;
	}
	return 0;
}

The easy way is to find the circumcircle’s radius through:


And since:



This method is less prone to error. Implementation:

#include <iostream>
#include <complex>
#include <limits>
using namespace std;

typedef long double gtype;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define circC(r) (2 * pi * abs(r))
#define area(a, b, c) ( (gtype) 0.5 * crs((b) - (a), (c) - (a)) )
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3];
	gtype r;
	cout.precision(2);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		r = abs(p[0] - p[1]) * abs(p[1] - p[2]) * abs(p[2] - p[0]) / area(p[0], p[1], p[2]) * 0.25;
		cout << fixed << circC(r) << endl;
	}
	return 0;
}

484 – The Department of Redundancy Department

Count and print. C++ code:

#include <cstdio>
#include <vector>
#include <map>
using namespace std;

typedef long long int64;

map<int64, int64> nInput;
vector<int64> input;
int64 n;

int main() {
	// input
	while (scanf("%lld", &n) == 1) {
		if (!nInput[n])
			input.push_back(n);
		nInput[n]++;
	}
	// output
	for (unsigned int i = 0; i < input.size(); ++i)
		printf("%lld %lld\n", input[i], nInput[input[i]]);
	return 0;
}

993 – Product of digits

A factorization problem.
A straight-forward solution would be dividing the input by the numbers from 9 down to 2 and build the output. If after these divisions the input has value other than 1, then it can’t be solved (there are factors larger than 9).
C++ implementation:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long int64;

int n;
int64 q, d;

int main() {
	int nCase;
	scanf("%d", &nCase);
	while (nCase--) {
		// in
		scanf("%d", &n);
		if (n == 0) {
			printf("10\n");
			continue;
		} else if (n < 10) {
			printf("%d\n", n);
			continue;
		}
		d = (q = 0) + 1;
		// solve
		for (int i = 9; i > 1; --i)
			while (n % i == 0) {
				n /= i;
				q += i * d;
				d *= 10;
			}
		// out
		if (n == 1)
			printf("%lld\n", q);
		else
			printf("-1\n");
	}
	return 0;
}