글 읽기 - DSLR 문제 반례좀 찾아주세요!

gracia 7년 전 0

아무리 생각해도 반례가 떠오르질 않네요

75퍼쯤에서 틀렸다고합니다

char beforechar[10000] / 해당 숫자로 오기전에 행한 연산 ;
int beforeint[10000] / 해당 숫자로 오기전에 연산이 행해진 수;
list<int> todo / 메인 큐;
list<char> way / 해를 구했을떄 경로를 되짚어가며 정답을 구함;

#include<iostream>
#include<list>
using namespace std;

int d(int t) {
	return t * 2 % 10000;
}
int s(int t) {
	return (t?t:10000) - 1;
}
int l(int t) {
	return (t * 10) % 9999;
}
int r(int t) {
	return (t % 10) * 1000 + t/10;
}

char beforechar[10000];
int beforeint[10000];
list<int> todo;
list<char> way;

bool solve(int q, int w) {
	if (q == w)
		return true;
	int dd, ll, rr, ss;
	dd = d(q);
	ll = l(q);
	rr = r(q);
	ss = s(q);
	if (beforechar[dd] == 0) {
		beforechar[dd] = 'D';
		beforeint[dd] = q;
		todo.push_back(dd);
		todo.push_back(w);
	}
	if (beforechar[ss] == 0) {
		beforechar[ss] = 'S';
		beforeint[ss] = q;
		todo.push_back(ss);
		todo.push_back(w);
	}
	if (beforechar[ll] == 0) {
		beforechar[ll] = 'L';
		beforeint[ll] = q;
		todo.push_back(ll);
		todo.push_back(w);
	}
	if (beforechar[rr] == 0) {
		beforechar[rr] = 'R';
		beforeint[rr] = q;
		todo.push_back(rr);
		todo.push_back(w);
	}
	return false;
}


int main() {
	int tqwe;
	cin >> tqwe;
	for (;tqwe--;) {

		for (int i = 0; i < 10000; i++) {
			beforechar[i]=0;
			beforeint[i]=0;
		}
		while(!todo.empty())
			todo.pop_front();
		while (!way.empty())
			way.pop_front();
		
		int ra, ta;
		int tt, ty;
		cin >> ra >> ta;
		todo.push_back(ra);
		todo.push_back(ta);
		bool done = false;
		while (!done) {
			tt = todo.front();
			todo.pop_front();
			ty = todo.front();
			todo.pop_front();

			done = solve(tt, ty);
		}

		int search = ta;
		while (ra != search) {

			way.push_front(beforechar[search]);
			search = beforeint[search];
		}

		for (auto i : way)
			cout << i;
		
		cout << endl;


	}
}

nuclear852 7년 전 3

9999 0

정답은 DDLSLDDRDDDD입니다

gracia 7년 전 1

와 감사합니다

이런 간단한 케이스를 생각못하다니 ㅠㅠ

gracia 7년 전 0

l을 잘못 구현했었네요 ㅋㅋㅋ

기교를 부려보곘답시고 이런 실수를...

kimjh9434 4년 전 0

호옹! 저도 문제를 풀어서 제출했는데, 바~~로 틀렸다고 나와서 반례를 찾는데,

9999 0

를 입력해보니까, 저는 결과가

DDLSLDDLDDDD

이 나오더라고요. 일단, 9999에서 DDLSLDDRDDDD로 가면 0이 되는건 확인했고,

9999에서 제 결과인 DDLSLDDLDDDD로 갔을 때 정답이 안나와서 왜 R이 L로 나왔을 까 해서 확인해보니까,

R명령어 동작에서도 cmd[i] = 'L';를 넣고 있었네요;;; 복붙하고 제대로 안고쳐서 그만... 그거만 R로 고치니까 바로 통과했습니다.

예제 덕분에 문제점을 바로 알 수 있었네요!

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

문제

문제

출처

ICPC

DSLR 문제 반례좀 찾아주세요!

gracia 7년 전 0

nuclear852 7년 전 3

gracia 7년 전 1

gracia 7년 전 0

kimjh9434 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말