[블 루 브리지 컵 - 역대 시험 문제] 마차 끌 기 (창고 와 대열)

문제 설명 어 렸 을 때 카드 게임 을 해 본 적 이 있 습 니까?마 차 를 끄 는 게임 이 있 는데 규칙 은 간단 하지만 어린 이 를 끌 어 당 긴 다.
그 규칙 은 다음 과 같다. 게임 에 참가 한 어린이 가 A 와 B 라 고 가정 하면 게임 이 시 작 될 때 그들 이 얻 은 랜 덤 카드 서열 은 다음 과 같다. A 측: [K, 8, X, K, A, 2, A, 9, 5, A] B 측: [2, 7, K, 5, J, 5, Q, 6, K, 4]
그 중의 X 는 '10' 을 표시 하고 우 리 는 카드 의 무늬 와 색깔 을 소홀히 했다.
A 측 부터 A, B 쌍방 이 돌아 가면 서 카드 를 낸다.
어느 쪽 이 카드 를 낼 차례 가 되 었 을 때, 그 는 자신의 카드 대열 의 머리 에서 한 장 을 가 져 가서 책상 위 에 놓 고, 맨 위 에 있 는 카드 위 에 눌 렀 다.
이 예 에서 게임 과정: A 출 K, B 출 2, A 출 8, B 출 7, A 출 X. 이때 책상 위의 순 서 는 다음 과 같다.
K,2,8,7,X
B 가 카드 를 낼 차례 가 되 었 을 때 그의 카드 K 는 책상 위의 카드 서열 에 있 는 K 와 같 으 면 K 를 포함 한 두 K 사이 의 카드 를 모두 이 겨 서 자신의 카드 의 꼬리 에 넣 었 다.주의: 조작 이 편리 하도록 카드 를 넣 는 순 서 는 책상 위의 순서 와 반대 입 니 다.이때 A, B 쌍방의 카드 는 A 측: [K, A, 2, A, 9, 5, A] B 측: [5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]
이 긴 쪽 은 계속 패 를 낸다.즉 B 는 5 를 내 고 A 는 K 를 내 고 B 는 J 를 내 고 A 는 A 를 내 고 B 는 5 를 내 고 또 이 겼 다.5, K, J, A, 5 이때 쌍방 이 가지 고 있 는 카드: A 측: [2, A, 9, 5, A] B 측: [Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]
주의: 더 많은 경우 에 카드 를 이 긴 쪽 은 책상 위의 카드 를 모두 이 길 수 없고 같은 카드 와 그 중간 부분 을 가 져 간다.그러나 어쨌든 카드 를 이 긴 쪽 이 계속 카드 를 내 고 어떤 때 는 카드 를 내 자마자 또 이 기 는 것 도 허용 된다.
한 쪽 이 마지막 카드 를 꺼 냈 지만 데스크 톱 에서 이 길 수 없 을 때 게임 은 바로 끝 납 니 다.
본 사례 의 초기 카드 상황 에서 마지막 A 는 질 것 이 고 B 의 마지막 카드 는:
9K2A62KAX58K57KJ5
이 문제 의 임 무 는 쌍방의 초기 카드 순 서 를 알 고 게임 이 끝 날 때 이 긴 쪽 이 가지 고 있 는 카드 순 서 를 계산 하 는 것 이다.게임 이 끝 날 수 없 을 때 출력 - 1.
2 줄, 2 개의 문자열 로 입력 하면 각각 A, B 쌍방 이 처음에 가지 고 있 던 패 서열 을 나타 낸다.출력 은 1 줄, 1 꼬치 로 A 가 먼저 패 를 내 고 마지막 에 이 긴 쪽 이 가지 고 있 는 패 순 서 를 나타 낸다.샘플 입력 96J5A 898 QA 6278 A7Q 973 샘플 출력 2J9A7QA6Q 6889977 샘플 입력 25663 K6X 7448 J88A5KJXX45A 샘플 출력 6KAJ458KXAX885XJ 645 데이터 규모 와 약정, 입력 한 문자열 의 길 이 는 30 을 초과 하지 않 습 니 다.
자원 약정: 피크 메모리 소모 (가상 머 신 포함) < 256 M CPU 소모 < 1000 ms
요구 에 따라 출력 을 엄 격 히 하 십시오. "입력 하 십시오." 와 같은 불필요 한 내용 을 사족 으로 인쇄 하지 마 십시오.
메모: main 함 수 는 0 을 되 돌려 야 합 니 다.ANSI C / ANSI C + + 표준 만 사용 하기;컴 파일 환경 이나 운영 체제 에 의존 하 는 특수 함 수 를 호출 하지 마 십시오.모든 의존 함 수 는 원본 파일 에 명확 하 게 있어 야 합 니 다. \ # include 는 프로젝트 설정 을 통 해 상용 헤더 파일 을 생략 할 수 없습니다.
프로그램 을 제출 할 때 원 하 는 언어 형식 과 컴 파일 러 형식 을 선택 하 십시오.
사고 분석:
뚜렷 한 스 택 과 대기 열 데이터 구조.패 면 은 창고 이 고 A, B 는 대열 이 며 다음은 마 차 를 끄 는 과정 을 모 의 한다.1. A, B 의 초기 카드 를 팀 에 넣는다.2. A 가 팀 에서 나 와 (카드 를 내 고) A 의 팀 원 소 를 카드 면 에 눌 러 넣는다.3. 검색 패 면 에 A 가 낸 패 와 같은 카드 가 있 는 지, 있 으 면 이 패 를 A 팀 의 동시 패 면 에 거꾸로 넣 고 A 가 다시 패 를 낸다. 4. A 가 패 를 낸 후에 A 대열 이 비어 있다 고 판단 하면 B 가 이 긴 패 를 판정한다.B 동 리.
카드 면 은 STL 에 있 는 stack 을 사용 할 수 없습니다. stack 은 용기 어댑터 이기 때문에 옮 겨 다 닐 수 없 기 때문에 검색 과정 을 진행 할 수 없습니다.이 문 제 는 주로 처리 해 야 할 내용 과 세부 사항 이 너무 많 고 어 딘 가 에 틀 리 면 결과 가 틀 리 고 debug 가 어렵다.또한 이 문제 의 모든 테스트 데 이 터 는 결과 가 있 습 니 다. - 1 판정 하지 않 아 도 됩 니 다. 다음 코드 는 겨울방학 에 만 들 었 습 니 다. 그 때 는 STL, 핸드폰 체인 팀 으로 디 테 일 을 모두 인쇄 하지 않 았 습 니 다 (debug 를 원 하기 때 문 입 니 다.)
#include 
#include 
using namespace std;

typedef struct node
{
	char data;
	struct node *next;
}Queue;

void create(Queue *&L, Queue *&r)	//           
{
	char ch;
	L = (Queue *)malloc(sizeof(Queue));
	r = L;
	while((ch = getchar()) != '
'
) { Queue *s = (Queue *)malloc(sizeof(Queue)); s->data = ch; r->next = s; r = s; } r->next = NULL; } void print(Queue *&L) // { Queue *p; p = L->next; while(p != NULL) { printf("%c",p->data); p = p->next; } printf("
"
); } int main() { int i, j, ok1 = 1, ok2 = 1; // ok1 ok2 char a[100], top = -1; // ( ) Queue *L1 = (Queue *)malloc(sizeof(Queue)); Queue *L2 = (Queue *)malloc(sizeof(Queue)); Queue *r1, *r2, *p1, *p2, *s; create(L1, r1); // create(L2, r2); while(L1->next != NULL && L2->next != NULL) { //1 if(ok1 && L2->next != NULL) // A ,B { ok2 = 1; printf("A :"); print(L1); a[++top] = L1->next->data; // a[top+1] = '\0'; p1 = L1->next; if(p1->next == NULL) // r1 = L1; L1->next = p1->next; free(p1); printf("A , :"); puts(a); for(i = 0;i < top;i++) // { if(a[i] == a[top]) // { for(j = top;j >= i;j--) // 1 { Queue *s = (Queue *)malloc(sizeof(Queue)); s->data = a[j]; r1->next = s; r1 = s; } r1->next = NULL; top = i-1; // a[top+1] = '\0'; printf("A :"); print(L1); printf("A , :"); puts(a); ok2 = 0; //2 。( ok1 ) break; } } } if(ok2 && L1->next != NULL) // B ,A { ok1 = 1; printf("B :"); print(L2); a[++top] = L2->next->data; // a[top+1] = '\0'; p2 = L2->next; if(p2->next == NULL) // r2 = L2; L2->next = p2->next; free(p2); printf("B , :"); puts(a); for(i = 0;i < top;i++) // { if(a[i] == a[top]) // { for(j = top;j >= i;j--) // 2 { Queue *s = (Queue *)malloc(sizeof(Queue)); s->data = a[j]; r2->next = s; r2 = s; } r2->next = NULL; top = i-1; // a[top+1] = '\0'; printf("B :"); print(L2); printf("B , :"); puts(a); ok1 = 0; //2 。( ok1 ) break; } } } } if(L1->next == NULL) { printf("B 。
"
); print(L2); } else if(L2->next == NULL) { printf("A 。
"
); print(L1); } else printf("
"
); return 0; }

아래 에 STL 로 쓴 AC 코드 는 queue 도 용기 어댑터 이기 때문에 옮 겨 다 닐 수 없 기 때문에 전체 디 테 일 을 인쇄 할 수 없습니다.
#include 
#include 
using namespace std;

int main()
{
	string a, b, pai;
	int N = 100010, t = -1, ok_A = 1, ok_B = 1, flag = 0;
	cin>>a>>b;
	queue<char> A, B;
	for(int i = 0;i < a.length();i++) A.push(a[i]);
	for(int i = 0;i < b.length();i++) B.push(b[i]);
	while(N--)	//    10w      ,           
	{
		if(ok_A)	//  ok_A ok_B             
		{
			ok_B = 1;
			int sign = -1;
			pai[++t] = A.front();	//A   
			A.pop();
			for(int i = 0;i < t;i++)//    
			{
				if(pai[i] == pai[t])
				{
					sign = i;
					break;
				}
			}
			if(sign != -1)	//A   
			{
				ok_B = 0;
				for(int i = t;i >= sign;i--) A.push(pai[i]);	//     
				t = sign-1;		//     
			}
			if(A.empty())	// A      , B  
			{
				flag = 2;
				break;
			}
		}
	
		if(ok_B)
		{
			ok_A = 1;
			int sign = -1;
			pai[++t] = B.front();
			B.pop();
			for(int i = 0;i < t;i++)
			{
				if(pai[i] == pai[t])
				{
					sign = i;
					break;
				}
			}
			if(sign != -1)	//B   
			{
				ok_A = 0;
				for(int i = t;i >= sign;i--) B.push(pai[i]);	//     
				t = sign-1;		//     
			}
			if(B.empty())	// B      , A  
			{
				flag = 1;
				break;
			}
		}
	}
	
	//     
	if(flag == 1)
	{
		while(!A.empty())
		{
			cout<<A.front();
			A.pop();
		} 
	}
	else if(flag == 2)
	{
		while(!B.empty())
		{
			cout<<B.front();
			B.pop();
		} 
	}
	else cout<<-1<<endl;
	return 0;
} 

좋은 웹페이지 즐겨찾기