글 읽기 - [14674] 데이터 추가해 주세요.

chogahui05 6년 전 1

엡실론으로 처리하는 게 통과되네요.

2 = 99999999/99999998 (가성비 1위)

1 = 100000000/99999999 (2)

4 = 99999999/100000000 (3)

3 = 99999998/99999999 (4)

/*
input
4 4
1 99999999 100000000
2 99999998 99999999
3 99999999 99999998
4 100000000 99999999

output
2
1
4
3
*/

chogahui05 6년 전 0

솔직히 더 추가하고 싶었지만.. 그러면 악랄해 질 거 같아요. ㅋㅋ

ps.

영우와 갓4 0ms에 푸는 게

왜 이렇게 어렵나요? ㅋㅋ

chogahui05 6년 전 0

저게 면접을 위한 알고리즘(?) 코딩 인터뷰 이런 책에 나온 주젯거리긴 했어요.

링크드리스트에서 사이클은 어떻게 찾을까?

Linked List의 a, b가 어느 지점부터 공통될 때 그 지점은 어떻게 찾을까?

이런 주제가 다뤄지긴 했어요.

startlink 6년 전 0

데이터 추가했습니다.

https://www.acmicpc.net/rejudg...

chogahui05 6년 전 0

뭥미?? 앱실론으로 처리한 게 많았었나요?? 매브님거만 그런 줄 알았는데.. ㅡㅡ;;

와.. 이거 진짜 충격이네요.

누군가 분수 비교, 소수 비교를 조금 써 줬으면 좋겠다 싶을 정도로 충격이네요.

이 문제출제자입니다. 원래 이 문제를 낸 의도가 분수 비교나 소수비교없이 앱실론으로도 처리할 수 있는정도를 생각하고 낸거라서 당연히 통과시키는걸로 했었구요. 애초에 난이도를 아무생각 없이 풀 수 있게하는게 목표였습니다. 제가 조건을 너무 넓게 적어놔서 이런 데이터도 허용이 되게 되었네요. 추가된 데이터로 인해 스트레스 받으실 수 있으신 분들도 많을 것 같은데, 제 불찰입니다. 정말 죄송합니다.

olbbemi 6년 전 0

저격당한 1인입니다.. ㅠㅠ.. 앱실론이 무엇인지는 알겠는데 이 문제를 처리하기 위해서는 어떻게 접근해야할지 모르겟습니다.

위에 언급하신 예제인

4 = 99999999/100000000 (3)

3 = 99999998/99999999 (4)

이는 계산기로 구해봐도 최소 소수 10자리이후에 차이가나는데 이는 오차때문에 처리하는데 있어서 완벽하지 못할것같다고 생각이드네요.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning(disable:4996)
struct INFO
{
	int i;
	long double p, s;
	INFO(int i, long double p, long double s) : i(i), p(p), s(s) {}
};

vector<INFO> v;

bool cmp(const INFO &u, const INFO &v);

int main()
{
	int  a, N, K;
	long double b, c;
	scanf("%d%d", &N, &K);

	for (int i = 0; i < N; i++)
	{
		scanf("%d%Lf%Lf", &a, &b, &c);
		v.push_back(INFO(a, b, c / b));
	}

	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < K; i++)
		printf("%d\n", v[i].i);

	return 0;
}

bool cmp(const INFO &u, const INFO &v)
{
	return make_tuple(u.s, -u.p, -u.i) > make_tuple(v.s, -v.p, -v.i);
}

khj94811 6년 전 0

실수를 이용한 대소 비교를 하지 마시고, 분모를 이항하여 정수로 비교를 하시면 됩니다.

chogahui05 6년 전 0

아주대의 9분 9적법 문제도 저격하러 가봐야겠네요.

그 전에 제가 파이선으로 풀어야 말이죠..

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

문제

문제

출처

ICPC

[14674] 데이터 추가해 주세요.

chogahui05 6년 전 1

khj94811 6년 전 0

chogahui05 6년 전 0

khj94811 6년 전 0

chogahui05 6년 전 0

startlink 6년 전 0

khj94811 6년 전 0

chogahui05 6년 전 0

mincl 6년 전 2

olbbemi 6년 전 0

khj94811 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말