글 읽기 - 96퍼에서 틀렸습니다가 나옵니다 ㅠㅠ

genius 7년 전 0

내림차순으로 정렬한후에, A[i]가 limited보다 크거나 이전값보다 크거나 sum이 factorial(n-1)과 같지않으면 -1을 출력하도록 알고리즘을 짰는데..... 반례가 있는걸까요?ㅠㅠ 예제도 전부 되고, 데이터도 몇개 테스트해봐도 다 잘되는데... 96퍼에서 틀렸다고 나오는 이유는 뭘까요 ㅠㅠㅠ 감이 안잡힙니다...

#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;
long long fact(int n) {
	long long summ = 0;
	for (long long i = 1; i <= n; i++) summ += i;
	return summ;

}
int n, A[10009];
int main(void) {

	scanf("%d", &n);
	for (int i = 0; i<n; i++) scanf("%d", &A[i]);
	
	sort(A, A + n, greater<int>());

	int before_num = n, limited = n - 1;
	long long sum = 0;

	for (int i = 0; i < n ; i++) {
		if (A[i] <= before_num){
			if (A[i] < limited) { before_num = A[i];}
			else if (A[i] == limited) {
				limited -= 1; before_num = A[i];
			}
			else {
				printf("-1\n");
				return 0;
			}
            
			sum += A[i];
			
            if (sum > fact(n - 1)) {
				printf("-1\n");
				return 0;
			}
		}else{
			printf("-1\n");
			return 0;
		}
	}
	
	if (sum == fact(n - 1)) {
		printf("1\n");
	}else {
		printf("-1\n");
	}
}

cocogod 6년 전 0

해결하셨나요?

저도 96퍼에서 틀린다고 나와요 ㅠㅠㅠㅠ

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <string>

using namespace std;

int temp[10001] = { 0 };
long long sum = 0;
long long total = 0;

int main() {
	int n;
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> temp[i];
	}
	sort(temp, temp + n);
	
	for (int i = 1; i <= n; i++) {
		sum += temp[i];
		if (sum < i*(i - 1) / 2) {
			printf("-1");
			return -1;
		}
	}
	if (sum != n*(n - 1) / 2)
		printf("-1");
	else
		printf("1");
}

jsjsjs0775 5년 전 1

반례

size: 7일 때,

승점: 5 5 5 5 1 0 0

출력이 -1이 되어야 하는데 1이 나와요~~ 도움이 됐기를!

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

문제

문제

출처

ICPC

96퍼에서 틀렸습니다가 나옵니다 ㅠㅠ

genius 7년 전 0

cocogod 6년 전 0

jsjsjs0775 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말