UVa – 10276 – Hanoi Tower Troubles Again!

Problem Link : UVa – 10276 – Hanoi Tower Troubles Again!


#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;

int sol[55], top[55];
int peak = 0;
int isSquare(int n) {
	int h = n & 0xF;
	if (h > 9)
		return 0;
	if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8) {
		int t = (int) floor(sqrt((double) n) + 0.5);
		return t * t == n;
	}
	return 0;
}

void put(int ball) {
	if (peak > 50)
		return;
	int inserted = 0;
	for (int i = 1; i <= peak; i++)
		if (isSquare(ball + top[i]))
			sol[peak]++, top[i] = ball, inserted = 1;
	if (!inserted)
		top[++peak] = ball, sol[peak] = sol[peak - 1] + 1;
	put(ball + 1);
}

int main() {
	int T, n;
	memset(top, 0, sizeof top), memset(sol, 0, sizeof sol);
	put(1);
	scanf("%d", &T);
	while (T-- && scanf("%d", &n) != EOF)
		printf("%d\n", sol[n]);
	return 0;
}
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: