글 읽기 - 3%에서 계속 틀리다고 나옵니다 반례 찾는거 도아주세요

ksoosung77 2년 전 0

대체 3%가 뭐길래 계속 틀리다는건지 모르겠습니다 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#pragma warning(disable:4996)
#define nINF -1000000000
#define INF 1000000000

using namespace std;

void loop(int num[10], int dif,long long w,int pos) {
	if (pos == -1 && dif == 0) {
		cout << w;
		exit(0);
	}
	else if (pos == -1)return;
	else {
		if (dif != 0) {
			for (int i = 0; i <= 9; i++) {
				if (num[i] == 0) {
					num[i]++;
					long long tmul = 1;
					for (int j = 0; j < pos; j++) {
						tmul *= 10;
					}
					loop(num, dif-1, w + i * tmul, pos - 1);
					num[i]--;
				}
			}
		}
		else {
			for (int i = 0; i <= 9; i++) {
				if (num[i] != 0) {
					num[i]++;
					long long tmul = 1;
					for (int j = 0; j < pos; j++) {
						tmul *= 10;
					}
					loop(num, dif, w + i * tmul, pos - 1);
					num[i]--;
				}
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long w, k, w2, size = 0, dif = 0;
	int wnum[20] = {};
	int num[10] = {};
	cin >> w >> k;
	w2 = w;
	while (w2) {
		if (num[w2 % 10] == 0)dif++;
		num[w2 % 10]++;
		wnum[size++] = w2 % 10;
		w2 /= 10;
	}
	w2 = w;
	if (dif == k) {
		cout << w2;
		return 0;
	}
	for (int i = 0; i < size; i++) {
		long long tmul = 1;
		for (int j = 0; j < i; j++) {
			tmul *= 10;
		}
		if (i < size) {
			w2 -= wnum[i] * tmul;
			num[wnum[i]]--;
			if (num[wnum[i]] == 0)dif--;
		}
		for (int j = wnum[i] + 1; j <= 9; j++) {
			w2 += j * tmul;
			if (num[j] == 0)dif++;
			num[j]++;
			if (dif <= k && dif + i >= k)loop(num, k - dif, w2, i - 1);
			num[j]--;
			if (num[j] == 0)dif--;
			w2 -= j * tmul;
		}
	}
	cout << 10;
	for (long long i = 0; i <= size - k; i++)cout << 0;
	for (long long i = 2; i < k; i++)cout << i;
}

srand 2년 전 1

아래 샘플 한번 확인해보셔요

325855307508689279 7

Ans : 325855307508700001

srand 2년 전 1

132065848410495398 6
132066000000000004


644705826284435438 5
644706000000000001


542040272246523191 8
542040272246523201

ksoosung77 2년 전 0

헐 세상에 세상에 고맙습니다

ksoosung77 2년 전 1

그 사소한 실수 때문에 하루라는 시간을 다 잡아먹어버렸네요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

반례 알려주셔서 덕분에 저힘으로 풀었습니다 :D

고맙습니다

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

문제

문제

출처

ICPC

3%에서 계속 틀리다고 나옵니다 반례 찾는거 도아주세요

ksoosung77 2년 전 0

srand 2년 전 1

srand 2년 전 1

ksoosung77 2년 전 0

ksoosung77 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말