글 읽기 - 반례를 찾았는데 왜그런지 모르겠습니다..

xzvfinet 6년 전 0

코드 작성하고 반례도 찾았습니다. 그런데 왜 저렇게 나오는지 도저히 모르겠어서 질문 올립니다..

N=20

k=2

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2

위와 같이 순열이 역순으로 주어지고, 마지막 두 수만 순서를 바꾼 경우에 잘 못된 정답(마지막 두 수를 바꾸지 않았을 때의 답)이 나옵니다.

즉,

(20 19 ... 2 1) => 2432902008176640000

(20 19 ... 1 2) => 2432902008176640000

와 같이 나옵니다.

이상한건 N=1~18 까지는 정상적으로 나오다는 점입니다...

고수분들께 질문 올립니다 ㅠㅠ

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

double fac(int n) {
	double res = 1;
	for (int i = 2; i <= n; ++i)
		res *= i;
	return res;
}

// arr로 만들어지는 수열 중 k번째 수(단, arr.size() <= k)
void pane(vector<int>& arr, double k) {
	if (k == 1) {
		return;
	}

	double N_1 = fac(arr.size() - 1);
	for (int i = 1; i <= arr.size(); ++i) {
		if (k <= N_1*i) {
			int val = arr[i - 1];
			auto pos = find(arr.begin(), arr.end(), val);
			arr.erase(pos);
			pane(arr, k - N_1*(i - 1));
			arr.insert(arr.begin(), val);

			break;
		}
	}
}

// arr에서 arr[i]가 몇 번째 수인지
// ex) arr={1,4,3}, i=0 ==> 1
// ex) arr={1,4,3}, i=1 ==> 2
// ex) arr={1,4,3}, i=2 ==> 3
int count(vector<int> arr, int i) {
	char ch = arr[i];
	vector<int> a = arr;
	sort(a.begin(), a.end());
	for (int j = 0; j < a.size(); ++j)
		if (a[j] == ch) {
			return j + 1;
		}
}

// arr이 몇 번째 수열인지
double pane2(vector<int>& arr) {
	if (arr.size() == 1)
		return 1;

	double result = (count(arr, 0) - 1) * fac(arr.size() - 1);

	auto next = vector<int>(arr.begin() + 1, arr.end());
	result += pane2(next);

	return result;
}

int main()
{
	int n, type;
	double k;
	scanf("%d %d", &n, &type);
	vector<int> arr;

	if (type == 1) {
		scanf("%lf", &k);
		for (int i = 1; i <= n; ++i)
			arr.push_back(i);

		pane(arr, k);

		for (int i = 0; i < arr.size(); ++i)
			printf("%d ", arr[i]);
		printf("\n");
	}
	else {
		int val;
		for (int i = 0; i < n; ++i) {
			scanf("%d", &val);
			arr.push_back(val);
		}

		double res = pane2(arr);
		printf("%.0lf\n", res);
	}

	return 0;
}

sait2000 6년 전 0

double이 2432902008176639999를 표현 못 하고 있어서 그래요. long long 써보세요. double은 2^53 이상정도 되는 정수에 쓰면 안 된다고 생각하시면 될 것 같아요.

xzvfinet 6년 전 0

감사합니다! 말씀하신대로 long long으로 바꾸니 해결되었습니다!

당연히 double이

1.79E-308(-1.79*10^308) ~ 1.79E+308(1.79*10^308) (15digits)

이니 될 줄 알았는데 아니군요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾았는데 왜그런지 모르겠습니다..

xzvfinet 6년 전 0

sait2000 6년 전 0

xzvfinet 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말