ICPC Regionals 2011 :: Asia - Phuket

5723.cpp

#include <stdio.h>

#define INFINITE 18446744073709551615

typedef unsigned long long ull;

int n;
ull flow[21];
ull cost[21];
ull minimal_cost;
ull required_flow;


void recurse(int index, ull accu_cost, ull accu_flow) {
	if (index >= n) return;
	ull accu_cost_1 = accu_cost + cost[index];
	ull accu_flow_1 = accu_flow + flow[index];
	if (accu_flow_1 >= required_flow) {
		if (accu_cost_1 < minimal_cost) {
			minimal_cost = accu_cost_1;
			recurse(index + 1, accu_cost_1, accu_flow_1);
		} else {
			// no need to go through this line
		}
	} else {
		recurse(index + 1, accu_cost_1, accu_flow_1);
	}
	recurse(index + 1, accu_cost, accu_flow);
} 

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%llu %llu", &flow[i], &cost[i]);
	}

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		minimal_cost = INFINITE;
		int hour;
		scanf("%llu %d", &required_flow, &hour);
		required_flow = (required_flow + hour - 1) / hour;

		recurse(0, 0, 0);
		
		if (minimal_cost < INFINITE)
			printf("Case %d: %llu\n", i + 1, minimal_cost);
		else
			printf("Case %d: IMPOSSIBLE\n", i + 1);

	}

	return 0;
}

5724.cpp

#include <stdio.h>
#include <iostream>

typedef struct node_t {
	unsigned int value;
	node_t *left, *right;
} node_t;

void reset(node_t *root) {
	if (root == NULL) return;
	if (root->left != NULL) reset(root->left);
	if (root->right != NULL) reset(root->right);
}

void add(node_t *&root, unsigned int value) {
	if (root == NULL) {
		root = new node_t;
		root->value = value;
		root->left = root->right = NULL;
	} else {
		if (value < root->value) add(root->left, value);
		else add(root->right, value);
	}
}

void print(node_t *root) {
	if (root == NULL) return;
	print(root->left);
	print(root->right);
	printf("%u\n", root->value);
}

int main() {
	node_t *root = NULL;
	
	reset(root);

// #define DEBUG

	unsigned int v;
	while (scanf("%u", &v) != EOF
#ifdef DEBUG
		&& v != 0
#endif
		) {
	add(root, v);
	}

	print(root);

	return 0;
}

5730.cpp

#include <stdio.h>

#define PI 3.14159265358979e0

typedef unsigned long long ull;

ull c(ull d, ull r, ull s) {
	double area_all = s * (4 * r + 4 * d);
	double area_row = 2e0 * ((2 * d + 2 * r) * (2 * d + 2 * r) - PI * r * r);
	ull x = area_all / area_row;
	
	// test whether it is ok to jump from x - 1 to x
	double area_remains = area_all - area_row * (x - 1);
	while (area_remains < (2 * r + 2 * d) * (4 * r + 4 * d)) {
		x--;
		area_remains = area_all - area_row * (x - 1);
	}
	return 2 * x;
}

int main() {
	ull r_0, r_1, d_0, d_1, s;

	while (scanf("%llu %llu %llu %llu %llu", &r_0, &r_1, &d_0, &d_1, &s) != EOF && r_0 + r_1 + d_0 + d_1 + s > 0) {
		ull count = 0;
		for (ull r = r_0; r <= r_1; ++r)
			for (ull d = d_0; d <= d_1; ++d) {
				count += c(d, r, s);
			}
		printf("%llu\n", count);
	}

	return 0;
}