BOJ 13482 Java2016

25.09.14 현재 스페셜 저지가 문제 의도와 다르게 작동하고 있는 것으로 추정됩니다. 그래서… 잘못 짜도 AC를 받을 수 있습니다.

문제 링크입니다.

문제 요약

랜덤으로 값이 정해지는 8비트 부호 없는 정수들과 사칙연산, min, max 연산을 이용해, 50% 이상의 확률로 0~255 사이의 원하는 값이 나오게끔 하는 식을 만드세요. 최대 26개의 매크로 식을 선언할 수 있으며, 매크로를 포함해 전체 식의 길이는 256글자를 넘을 수 없습니다.

풀이

0은 예제에서 만드는 방법을 알려줬습니다. 그대로 이용합시다.

1 이상의 수를 만들기 위해 2진법을 이용합시다. 1, 2, 4, 8, 16, 32, 64, 128을 나타내는 8개의 매크로 식을 선언해준다면, 실제로 값을 얻어내는 코드는 최대 15글자(8개의 매크로, 7개의 합 기호)로 구성됩니다.

2부터 128까지는 이전 매크로를 더하는 것으로 5글자를 써서 만들 수 있습니다. 현재까지 총 50글자가 사용되었습니다.

예제를 확인해보면, 1을 a = ? max ?; (a max a)/a 의 꼴로 만들고 있습니다. 분자가 분모 이상이면서 2배를 넘지 않으면 되므로 꽤 괜찮은 전략입니다. 이 전략을 강화합시다.

분수의 값이 1을 넘지 않으려면 분모가 충분히 커야 하고, 0이 되지 않으려면 분자가 훨씬 더 충분히 커야 합니다. max를 최대한 많이 결합하기 위해 여러 개의 매크로를 이용해 max로 연결된 ?의 개수를 2배씩 늘립시다. 그렇게 만들어진 매크로들 중 적당히 두 개(제일 큰 것과 그보다 몇 스텝 작은 것)을 골라 1을 정의해주고, 이를 바탕으로 $2^k$를 만들어 주면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; if(n==0) return !(cout << "?/?/?");
	cout << "a=?max?\n";
	cout << "j=amaxa\n";
	for(char c = 'k'; c <= 'y'; c++) cout << c << '=' << char(c-1) << "max" << char(c-1) << '\n';
	cout << "z=ymaxymaxymaxymaxymaxymaxymaxymaxymaxymaxy\nb=z/p\n";
	for(char c = 'c'; c <= 'i'; c++) cout << c << '=' << char(c-1) << '+' << char(c-1) << '\n';
	vector<char> ans;
	for(int i=0; i<8; i++) if(n&(1<<i)) ans.push_back('b'+i);
	cout << ans.back(); ans.pop_back();
	for(auto c:ans) cout <<'+'<<c;
}