답안 #4880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4880	2014-01-06T11:42:37 Z	ainta	홀-짝 수열 (IZhO11_oddeven)	C++	100 / 100	0 ms	1092 KB

oddeven

#pragma warning(disable:4996)
#include<stdio.h>
char p[110];
int w[150], L;
void Do(int *a){
	int i;
	for (i = 0; i < 133; i++){
		if (a[i] < 0)a[i] += 10, a[i + 1]--;
		if (a[i] > 9)a[i + 1] += a[i]/10, a[i] %= 10;
	}
}
void plusminus(int *T, int *a, int *b, bool k){
	int i;
	for (i = 0; i <= 130; i++){
		if (k)T[i] = a[i] - b[i];
		else T[i] = a[i] + b[i];
	}
	Do(T);
}
void div2(int *a){
	int i;
	for (i = 130; i >= 0; i--){
		if (i && (a[i] & 1))a[i - 1] += 10;
		a[i] >>= 1;
	}
}
void mul(int *T, int *a, int *b){
	int i, j;
	for (i = 0; i <= 130; i++)T[i] = 0;
	for (i = 0; i <= 130; i++){
		for (j = 0; i + j <= 130; j++){
			T[i + j] += a[i] * b[j];
		}
	}
	Do(T);
}
bool Isbigger(int *a, int *b){
	int i, t;
	for (i = 130; i >= 0; i--){
		t = a[i] - b[i];
		if (!t)continue;
		if (t > 0)return true;
		return false;
	}
	return true;
}
int B[150], E[150], T1[150], T2[150], T3[150], M[150], R[150];
void Pro()
{
	int i;
	B[0] = 1;
	T2[0] = 1;
	for (i = 0; i < L / 2 + 1; i++)E[i] = 9;
	while (Isbigger(E,B)){
		plusminus(M, B, E, 0);
		div2(M);
		mul(T1, M, M);
		plusminus(T1, T1, M, 0);
		div2(T1);
		if (Isbigger(T1, w)){
			for (i = 0; i <= 130; i++)R[i] = M[i];
			plusminus(E, M, T2, 1);
		}
		else plusminus(B, M, T2, 0);
	}
	return;
}
int main()
{
	int i;
	scanf("%s", p);
	for (i = 0; p[i]; i++);
	L = i;
	for (i = 0; p[i]; i++)w[L - 1 - i] = p[i] - '0';
	Pro();
	mul(T1, R, R);
	mul(T2, R, R);
	plusminus(T1, T1, R, 0);
	div2(T1);
	plusminus(T3, T1, w, 1);
	for (i = 1; i <= 130; i++)T1[i] = 0;
	T1[0] = 2;
	mul(B, T3, T1);
	plusminus(R, T2, B, 1);
	for (i = 130;; i--)if (R[i])break;
	for (i = i; i >= 0; i--)printf("%d", R[i]);
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1092 KB	Output is correct
2	Correct	0 ms	1092 KB	Output is correct
3	Correct	0 ms	1092 KB	Output is correct
4	Correct	0 ms	1092 KB	Output is correct
5	Correct	0 ms	1092 KB	Output is correct
6	Correct	0 ms	1092 KB	Output is correct
7	Correct	0 ms	1092 KB	Output is correct
8	Correct	0 ms	1092 KB	Output is correct
9	Correct	0 ms	1092 KB	Output is correct
10	Correct	0 ms	1092 KB	Output is correct
11	Correct	0 ms	1092 KB	Output is correct
12	Correct	0 ms	1092 KB	Output is correct
13	Correct	0 ms	1092 KB	Output is correct
14	Correct	0 ms	1092 KB	Output is correct
15	Correct	0 ms	1092 KB	Output is correct
16	Correct	0 ms	1092 KB	Output is correct
17	Correct	0 ms	1092 KB	Output is correct
18	Correct	0 ms	1092 KB	Output is correct
19	Correct	0 ms	1092 KB	Output is correct
20	Correct	0 ms	1092 KB	Output is correct
21	Correct	0 ms	1092 KB	Output is correct
22	Correct	0 ms	1092 KB	Output is correct