Maintenance script: Table transclusion repair v1

2026-03-27T12:46:17Z

Table transclusion repair v1

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:25Z

New page

== 소감 ==
{| class="wikitable"
|-
| 2006-01-08 Accepted 4.244 444
|}
Closed Form 구하는데 약 3~4시간 걸린 것 같다. 계차수열을 이용해서 다음과 같은 Closed Form을 구했다.
{{| T(n) = (n4 - 6n3 + 23n2 - 18n + 24) / 24 |}}
이론상으론 O(1) 시간만에 되겠지만 문제는 입력범위가 2 31 - 1 까지 들어올 수 있기 때문에 고정도 연산을 수행해야 한다. GNU C++ 이나 Java는 고정도 연산을 수행할 수 있는 클래스를 포함하고 있으나, 윈도우 C++에는 없다(혹, 내가 못찾는 것일수도 있다). 따라서 고정도 연산을 수행할 수 있는 클래스를 짰다. 성능이 너무 떨어진다. O(1) 을 O(n5) 정도로 바꿔 놓은 듯한 느낌이다. 이 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？]]

HowManyPiecesOfLand？/문보창 - Revision history

Maintenance script: Table transclusion repair v1

imported>Unknown at 05:23, 7 February 2021