글 읽기 - 반례를 못찾겠습니다..

dbsah328 5년 전 0

맞게 짠거 같은데 틀렸습니다가 나와요...반례도 어케 더 찾아봐야할지 모르겠고..

#include <stdio.h>
int head, tail, ch[10001];
char ans[10005];
typedef struct
{
	int x, y;//x는 값, y는 부모번호
}asd;
asd Q[2000000];

int main(void)
{
	int  T, A, B, i, j, a, b, c, d, k, q=0;
	scanf("%d", &T);
	for (i = 1; i <= T; i++)
	{
		head = 0, tail = 0;
		scanf("%d %d", &A, &B);
		ch[0] = i, ch[A] = i, Q[tail++].x = A;
		while (head < tail)
		{
			if (ch[(2 * Q[head].x) % 10000] != i)
			{
				Q[tail].x = (2 * Q[head].x) % 10000;
				ch[Q[tail].x]=i;
				Q[tail++].y = head;
				if (Q[tail-1].x == B)
				{
					head = tail-1;
					break;
				}
			}
			if (Q[head].x == 0&&ch[9999]!=i)
			{
				Q[tail].x = 9999;
				ch[9999] = i;
				Q[tail++].y = head;
				if (Q[tail - 1].x == B)
				{
					head = tail - 1;
					break;
				}
				head++;
				continue;
			}
			if (Q[head].x!=0&&ch[Q[head].x-1]!=i)
			{

				Q[tail].x =Q[head].x-1;
				ch[Q[tail].x] = i;
				Q[tail++].y = head;
				if (Q[tail - 1].x == B)
				{
					head = tail-1;
					break;
				}
			}
				k = Q[head].x;
				a = k / 1000;
				k -= a * 1000;
				b = k / 100;
				k -= b * 100;
				c = k / 10;
				k -= c * 10;
				d = k / 1;
				if (ch[b * 1000 + c * 100 + d * 10 + a] != i)
				{
					Q[tail].x = b * 1000 + c * 100 + d * 10 + a;
					ch[Q[tail].x] = i;
					Q[tail++].y = head;
					if (Q[tail - 1].x == B)
					{
						head = tail-1;
						break;
					}
				}
				if (ch[d * 1000 + a * 100 + b * 10 + c] != i)
				{
					Q[tail].x = d * 1000 + a * 100 + b * 10 + c;
					ch[Q[tail].x] = i;
					Q[tail++].y = head;
					if (Q[tail - 1].x == B)
					{
						head = tail-1;
						break;
					}
				}
			head++;
		}
		q = 0;
		while (head!=0)
		{
			k = Q[Q[head].y].x;
			a = k / 1000;
			k -= a * 1000;
			b = k / 100;
			k -= b * 100;
			c = k / 10;
			k -= c * 10;
			d = k / 1;
			k= Q[Q[head].y].x;
			if ( k == 0)
			{
				ans[q] = 'S';
				q++;
				head = Q[head].y;
				continue;
			}
			if (2 * k % 10000 == Q[head].x)
			{
				ans[q] = 'D';
			}
			else if (k - 1 == Q[head].x)
			{
				ans[q] = 'S';
			}
			else if (b * 1000 + c * 100 + d * 10 + a == Q[head].x)
			{
				ans[q] = 'L';
			}
			else if (d * 1000 + a * 100 + b * 10 + c == Q[head].x)
			{
				ans[q] = 'R';
			}
			q++;
			head = Q[head].y;
		}
		q--;
		for (; q >= 0; q--)
		{
			printf("%c", ans[q]);
		}
		printf("\n");
	}
	return 0;
}

seico75 5년 전 1

많이 본 소스다 했는데 어제 올리셨다가 지우신 분이네요.

어제 말씀 드린 부분을 32~44에 넣으셨는데, 마지막에 continue 하면 LR 를 건너뛰게 되어서 정답이 안나올 것 같습니다.

32, 45 는 같은 S를 처리하기 위한 부분이니 else 로 연결하는 것도 좋을 것 같습니다.

그리고, S는 after = (before + 9999) % 10000 으로 구현이 가능합니다. (before - 1 + 10000) % 10000

D : (2*x) % 10000

S : (x + 9999) % 10000

L : (x * 10) % 10000 + (x/1000)

R : x / 10 + (x % 10) * 1000

그리고 답을 찾으셨어도 올리신 글은 안지우는 것이 규칙인 것 같습니다.

djm03178 5년 전 0

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

dbsah328 5년 전 0

죄송합니다. 그 질문을 받고 고쳤는데 제가 지금 이 코드만 봐도 이상한 곳이 많아서 지우고 다시 올릴려고 했었는데 이제는 그렇게 하면 안되겠네요! 감사합니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다..

dbsah328 5년 전 0

seico75 5년 전 1

djm03178 5년 전 0

dbsah328 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말