USACO 3.1.3 – Humble Numbers


#include <cstdio>
using namespace std;

int main() {
	freopen("humble.in", "r", stdin), freopen("humble.out", "w", stdout);
	int INF =(1 << 31) -1, K, N, h, p, humble[100001], pos[101] = {0}, prime[101];
	scanf("%d %d", &K, &N);
	for (h = 1; h <= K; h++)
		scanf("%d", prime+h);

	for (humble[0] = 1, h = 1; h <= N; h++) {

		for (humble[h] = INF, p = 1; p <= K; p++)
			humble[h] = min(humble[h], prime[p] * humble[pos[p]]);

		for (p = 1; p <= K; p++)
			pos[p] += humble[h] >= prime[p] * humble[pos[p]];
	}
	printf("%d\n", humble[N]);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: