백준17297 Messi Gimossi

작성일 | In

문제 링크

  • http://icpc.me/17297

문제 출처

  • 제3회 천하제일 코딩대회 예선 E번

풀이

대회 중에 계속 MLE가 나오길래 꼼수를 썼던 문제입니다.
출제자가 제시하는 정해는 여기에서 볼 수 있고, 이 글에서는 제가 작성한 풀이를 소개하겠습니다.

40번째 항까지 구하면 (230-1)번째 글자까지 모두 구할 수 있다는 것은 컴퓨터를 이용한 완전탐색을 통해 알 수 있습니다.
정답이 반복되는 사이클을 찾으려고 했지만 실패해서 Naive한 풀이를 작성했습니다.

Messi는 “0”, Gimossi는 “1”로 한 뒤, 토글링을 하면서 40번째 항을 구했습니다. 약 1억 6000만 글자입니다.
40번째 항까지 구했더니 MLE가 발생해서 한 가지 트릭을 생각했습니다. 40번째 항은 38번째 항과 39번째 항으로 구성이 되기 때문에 39번째 항까지 구하는 방법을 사용했습니다. 이 방법을 사용하면 통과가 되긴 합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#pragma GCC optimize('Ofast')
using namespace std;

string a, b, c;

int solve(int x){
	string aa = "Messi ";
	string bb = "Gimossi ";
	x--;

	for(int k=0; k<c.size(); k++){
		char i = c[k];
		if(i == '0'){
			if(x == 5){
				cout << "Messi Messi Gimossi";
				return 0;
			}else if(x < 5){
				cout << aa[x];
				return 0;
			}else{
				x -= aa.size();
			}
		}else{
			if(x == 7){
				cout << "Messi Messi Gimossi";
				return 0;
			}else if(x < 7){
				cout << bb[x];
				return 0;
			}else{
				x -= bb.size();
			}
		}
	}
	for(int k=0; k<b.size(); k++){
		char i = b[k];
		if(i == '0'){
			if(x == 5){
				cout << "Messi Messi Gimossi";
				return 0;
			}else if(x < 5){
				cout << aa[x];
				return 0;
			}else{
				x -= aa.size();
			}
		}else{
			if(x == 7){
				cout << "Messi Messi Gimossi";
				return 0;
			}else if(x < 7){
				cout << bb[x];
				return 0;
			}else{
				x -= bb.size();
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	a = "0"; b = "01";
	for(int i=3; i<=39; i++){
		c = b + a;
		if(i != 40) a = b; b = c;
	}

	int x; cin >> x;
	solve(x); return 0;
}