글 읽기 - [2459] 반례 도움 요청

gumdung 3년 전 0

반례를 찾지를 못해 해매고 있습니다 ㅠㅠㅠ

반례 부탁드리겠습니다 감사합니다.

#include<bits/stdc++.h>

using namespace std;
using lld = long double;

vector<pair<lld, lld>> v;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n,k;
	lld l;
	cin >> n>>k;

	v.resize(k+2);
	for (int i = 1; i <= k; i++)
		cin >> v[i].first >> v[i].second;
	cin >> l;

	l += 0.5;
	//(1,1) 부터 시작 해서 (1,1)로 돌아옴
	v[0].first = v[0].second = 1;
	v[k + 1].first = v[k + 1].second = 1;
	
	int cnt = 0;
	vector<lld> ans;

	for (int i = 1; i <= k + 1; i++) {
		lld x = v[i - 1].first;
		lld y = v[i].first;

		//잘려진 철사의 개수 count
		if ((x <= l && l <= y) || (y <= l && l <= x)) 
			cnt++;
	}
	ans.resize(cnt+1);
	int pos = 0;
	for (int i = 1; i <= k + 1; i++) {
		lld x = v[i - 1].first;
		lld y = v[i].first;

		//만약 잘려진 부분에 포함이 되면 나눠서 계산
		if ((x <= l && l <= y) || (y <= l && l <= x)) {
			pos++;
			ans[pos - 1] += abs(v[i - 1].first - l);
			ans[pos] += abs(v[i].first - l);
		}
		//아니라면 가로/세로 길이 계산
		else {
			if (v[i - 1].first == v[i].first)
				ans[pos] += abs(v[i - 1].second - v[i].second);
			else
				ans[pos] += abs(v[i - 1].first - v[i].first);
		}
	}
	//for (int i = 0; i < ans.size(); i++)
	//	cout << ans[i]<<" ";

	//맨처음과 마지막은 용접으로 연결되어있음
	ans[0] += ans[cnt];
	lld Max = -1;
	for (int i = 0; i < ans.size()-1; i++)
		Max = max(Max, ans[i]);
	cout << Max;
	return 0;
}

gumdung 3년 전 0

자문자답합니다.

https://www.acmicpc.net/board/...

이 게시글에 있는 데이터가 반례입니다.

9.99999e+10 이라고 잘못된 답을 도출합니다.

이유는 실수형을 그대로 썼기 때문입니다.(0.5->1 로 1->2 로 계산해주어 풀어서 맞았습니다.)

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

문제

문제

출처

ICPC

[2459] 반례 도움 요청

gumdung 3년 전 0

gumdung 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말