글 읽기 - 반례 좀 알 수 있을 까요?

miles94 5년 전 0

순열을 이용해서 짰구요

operation vector 에 합,차,곱,몫 순으로 1 2 3 4 로 push_back 으로 집어넣고

순열로 돌아가게끔 구현 하였습니다.

일단, 문제에 주어진 기본 예제들은 모두 올바른 출력을 내는데

바로 틀렸습니다가 나오네요 어떤 반례가 있을까요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int divide(int a, int b) {
	if (a > 0 && b > 0) return a / b;
	else if (a < 0 && b > 0) return -((-a) / b);
	else if (a > 0 && b < 0) return -(a / (-b));
	else return (-a) / (-b);
}

int main() {
	int n,plus,minus,multi,div;
	int sum;
	int max = -200000000;
	int min = 200000000;
	cin >> n;
	vector<int> a(n);
	vector<int> op;
	for (int i = 0; i < n; i++) cin >> a[i];
	cin >> plus >> minus >> multi >> div;
	for (int i = 0; i < plus; i++) op.push_back(1);
	for (int i = 0; i < minus; i++) op.push_back(2);
	for (int i = 0; i < multi; i++) op.push_back(3);
	for (int i = 0; i < div; i++) op.push_back(4);

	do{
		sum = a[0];
		for (int i = 0; i < n - 1; i++) {
			switch (op[i]){
				case 1: sum += a[i + 1]; break;
				case 2: sum -= a[i + 1]; break;
				case 3: sum *= a[i + 1]; break;
				case 4: sum = divide(sum, a[i + 1]); break;
			}
		}
		if (sum > max) max = sum;
		if (sum < min) min = sum;
	} while (next_permutation(op.begin(), op.end()));
	printf("%d\n", max);
	printf("%d\n", min);
	return 0;
}

hellogaon 5년 전 1

주어진 문제의 출력 부분에

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 최댓값과 최솟값은 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.

또한, 앞에서 부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

라고 적혀있습니다! 최댓값, 최솟값은 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나올 수 있다고 하네요.

최댓값 또는 최솟값이 10억 또는 -10억이 되는 예제라면 답이 어떻게 되어야할까요?

반례는 다음과 같습니다.

올바른 정답은

1000000000

입니다.

5
100 100 100 100 10
0 0 4 0

miles94 5년 전 2

악...

초기값 20억으로 짠다고 짰는데

새벽에 짠 거라 2억으로 짜놨군요....ㅎㅎ..

감사합니다!

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

문제

문제

출처

ICPC

반례 좀 알 수 있을 까요?

miles94 5년 전 0

hellogaon 5년 전 1

miles94 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말