Codeforces Round #194 Div1C Lucky Tickets

問題

チケットは８ケタの、０～９の数字で番号が振られています（leading zeroを含みます）。
k-luckyとは、その８ケタの番号に+-*やカッコをつけたりして、計算結果がkになるようにできるような数字です。
たとえば、
"224201016"は
( - 2 - (2 + 4)) * (2 + 0) + 1016 = 1000
なので、1000-luckyです。

k-luckyなチケット番号を、m個出力してください。

制約
0 ≤ k ≤ 10^4, 1 ≤ m ≤ 3·10^5

解法
正解者がDやEよりも少ない超地雷問だったっぽいです。
解法は極めてトリッキーで、こんなんコンテスト中に思いつくわけねーだろって感じです。

８ケタのチケット番号を、４ケタずつに区切って考えます。
ところでマイナスをいくらでもつけていいので、数字からNが作れる場合は-Nも作れます。
というわけで、上４ケタで作れる数字を片っ端から列挙していき（これをxとします）、
下４ケタを|x-k|とすれば、とりあえずk-luckyな番号が作れます。
（|x-k|の値が同じになるxが2つあるのと、|x-k|が４ケタに収まらない場合だけ注意が必要です）

４ケタの数字１つから平均して60以上の数字が作れるので、上４ケタから対応する下４ケタを当てていくスタイルだけで600000くらいの番号が作り出せる計算で、制約のmより十分大きくなっています。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

vector<li> search(li num, li keta){
	vector<li> res;
	res.pb(num);
	res.pb(-num);
	
	if(keta>1){
		li l=10;
		for(int i=1; i<keta; i++, l*=10){
			vector<li> v1=search(num%l, i);
			vector<li> v2=search(num/l, keta-i);
			rep(j,sz(v1)){
				rep(k,sz(v2)){
					res.pb(v1[j]+v2[k]);
					res.pb(v1[j]*v2[k]);
				}
			}
		}
	}
	
	sort(allof(res));
	vector<li>::iterator it=unique(allof(res));
	res.erase(it,res.end());
	
	return res;
}

int main(){
	li k,m;
	cin>>k>>m;
	
	rep(i,10000){
		vector<li> is=search(i,4);
		vector<li> exist;
		
		rep(j,sz(is)){
			if(is[j]>=0 && is[j]<10000 && find(allof(exist), abs(k-is[j]))==exist.end() && abs(k-is[j])<10000){
				printf("%04I64d%04I64d\n", i, abs(k-is[j]));
				exist.pb(abs(k-is[j]));
				m--;
				if(m<=0)return 0;
			}
		}
	}
	return 0;
}