HowManyPiecesOfLand？/문보창

소감

2006-01-08 Accepted 4.244 444

Closed Form 구하는데 약 3~4시간 걸린 것 같다. 계차수열을 이용해서 다음과 같은 Closed Form을 구했다.

T(n) = (n4 - 6n3 + 23n2 - 18n + 24) / 24

이론상으론 O(1) 시간만에 되겠지만 문제는 입력범위가 2 ³¹ - 1 까지 들어올 수 있기 때문에 고정도 연산을 수행해야 한다. GNU C++ 이나 Java는 고정도 연산을 수행할 수 있는 클래스를 포함하고 있으나, 윈도우 C++에는 없다(혹, 내가 못찾는 것일수도 있다). 따라서 고정도 연산을 수행할 수 있는 클래스를 짰다. 성능이 너무 떨어진다. O(1) 을 O(n⁵) 정도로 바꿔 놓은 듯한 느낌이다. 이 Class를 개선한뒤 다시 테스트 해봐야 겠다.

코드

BigInteger.h

//////////////////////////////////////////////////////////////////////////
// Big Integer Class - C++
// 만든이 : Moon, Bo-chang.
// 만든 날짜 : 2006 / 1 / 7
// 마지막으로 수정한 날짜 : 
// 주의 : 오버플로우 처리 안함
// 지원하는 연산 : +(덧셈), -(뺄셈), *(곱셈), /(나눗셈) - 나눗셈 연산에서 나머지는 버린다.
// 함수 호출이 모두 복사로 이루어지므로 성능이 크게 떨어진다.
//////////////////////////////////////////////////////////////////////////

#pragma once

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

#define MAXDIGITS	100
#define PLUS		1				
#define MINUS		-1			
#define MAX(a,b) (((a) > (b)) ? (a) : (b))

class BigInteger 
{
public:
	char digit[MAXDIGITS];	
	int signbit;			
	int lastdigit;
public:
	BigInteger(int n)
	{
		int i;
		lastdigit = 0;
		signbit = (n < 0) ? MINUS : PLUS;
		while (n / 10)
		{
			digit[lastdigit++] = n % 10;
			n /= 10;
		}
		digit[lastdigit] = n % 10;
		for (i = lastdigit + 1; i < MAXDIGITS; i++)
			digit[i] = 0;	
	}
	BigInteger()
	{
		int i;
		for (i = 0; i < MAXDIGITS; i++)	
			digit[i] = 0;
		signbit = PLUS;
		lastdigit = 0;
	}
	void print()
	{
		if (signbit == MINUS) cout << "-";
		for (int i = lastdigit; i >= 0; i--)
			cout << (int)digit[i];
	}
	void input()
	{
		int startI = 0;
		int i, j;
		char temp[MAXDIGITS];

		while (cin.peek() == ' ' || cin.peek() == '\n')
			cin.get();

		cin >> temp;
		lastdigit = strlen(temp) - 1;
		signbit = PLUS;
		if (temp[0] == '-') 
		{
			signbit = MINUS;
			startI = 1;
			lastdigit--;
		}
		else if (temp[0] == '+')
		{
			startI = 1;
			lastdigit--;
		}
		j = 0;
		for (i = lastdigit + startI; i >= startI; i--)
			digit[j++] = temp[i] - '0';
	}
public:
	friend void elminatePreZero(BigInteger& n)
	{
		while (n.lastdigit > 0 && n.digit[n.lastdigit] == 0)	
			n.lastdigit--;
		if (n.lastdigit == 0 && n.digit[0] == 0)
			n.signbit = PLUS;
	}
	friend int compare(BigInteger& a, BigInteger& b)
	{
		int i;
		if (a.signbit == MINUS && b.signbit == PLUS) return PLUS;
		if (a.signbit == PLUS && b.signbit == MINUS) return MINUS;
		if (b.lastdigit > a.lastdigit) return (PLUS * a.signbit);
		if (a.lastdigit > b.lastdigit) return (MINUS * a.signbit);
		for (i = a.lastdigit; i >= 0; i--)
		{
			if (a.digit[i] > b.digit[i])
				return (MINUS * a.signbit);
			if (b.digit[i] > a.digit[i])
				return (PLUS * a.signbit);
		}
		return 0;
	}
	friend void shiftDigit(BigInteger& n, int d)
	{
		int i;
		if (n.lastdigit == 0 && n.digit[0] == 0) return;
		for (i = n.lastdigit; i >= 0; i--)
			n.digit[i+d] = n.digit[i];
		for (i = 0; i < d; i++) n.digit[i] = 0;
		n.lastdigit = n.lastdigit + d;
	}
	friend BigInteger operator+(BigInteger a, BigInteger b)
	{
		int carry;
		BigInteger ret;
		int i;

		if (a.signbit == MINUS && b.signbit == PLUS)
		{
			a.signbit = PLUS;
			ret = b - a;
			a.signbit = MINUS;
		}
		else if (a.signbit == PLUS && b.signbit == MINUS)
		{
			b.signbit = PLUS;
			ret = a - b;
			b.signbit = MINUS;
		}
		else
		{
			ret.signbit = a.signbit;
			ret.lastdigit = MAX(a.lastdigit, b.lastdigit) + 1;
			carry = 0;
			for (i = 0; i <= ret.lastdigit; i++)
			{
				ret.digit[i] = (carry + a.digit[i] + b.digit[i]) % 10;
				carry = (carry + a.digit[i] + b.digit[i]) / 10;
			}
			elminatePreZero(ret);
		}
		return ret;
	}
	friend BigInteger operator-(BigInteger a, BigInteger b)
	{
		BigInteger ret;
		int borrow, v;
		int i;

		if (a.signbit == MINUS || b.signbit == MINUS)
		{
			b.signbit = -1 * b.signbit;
			ret = a + b;
			b.signbit = -1 * b.signbit;
			return ret;
		}
		if (compare(a,b) == PLUS)
		{
			ret = b - a;
			ret.signbit = MINUS;
			return ret;
		}
		ret.lastdigit = MAX(a.lastdigit,b.lastdigit);
		borrow = 0;
		for (i = 0; i <= ret.lastdigit; i++)
		{
			v = a.digit[i] - borrow - b.digit[i];
			if (a.digit[i] > 0)
				borrow = 0;
			if (v < 0)
			{
				v = v + 10;
				borrow = 1;
			}
			ret.digit[i] = v % 10;
		}
		elminatePreZero(ret);
		return ret;
	}
	friend BigInteger operator*(BigInteger a, BigInteger b)
	{
		BigInteger row, tmp, ret;
		int i, j;

		row = a;
		for (i = 0; i <= b.lastdigit; i++)
		{
			for (j = 1; j <= b.digit[i]; j++)
			{
				tmp = ret + row;
				ret = tmp;
			}
			shiftDigit(row, 1);
		}
		ret.signbit = a.signbit * b.signbit;
		elminatePreZero(ret);
		return ret;
	}
	friend BigInteger operator/(BigInteger a, BigInteger b)
	{
		BigInteger row, tmp, ret;
		int asign, bsign;
		int i;

		ret.signbit = a.signbit * b.signbit;
		asign = a.signbit;
		bsign = b.signbit;
		a.signbit = PLUS;
		b.signbit = PLUS;
		ret.lastdigit = a.lastdigit;
		
		for (i = a.lastdigit; i >= 0; i--)
		{
			shiftDigit(row, 1);
			row.digit[0] = a.digit[i];
			ret.digit[i] = 0;
			while (compare(row, b) != PLUS)
			{
				ret.digit[i]++;
				tmp = row - b;
				row = tmp;
			}
		}
		elminatePreZero(ret);
		a.signbit = asign;
		b.signbit = bsign;
		return ret;		
	}
};

main.cpp

#include "BigInteger.h"

int main()
{
	int nCase;
	BigInteger a(6), b(23), c(18), d(24);
	BigInteger n, result;
	cin >> nCase;
	for (int i = 0; i < nCase; i++)
	{
		n.input();
		result = (n * n * n * n - a * n * n * n + b * n * n - c * n + d) / d;
		result.print();
		cout << endl;
	}
	return 0;
}

---

HowManyPiecesOfLand？