记录编号	397523	评测结果	AAAAATATAATTTA
题目名称	575.猴子和香蕉	最终得分	64
用户昵称	confoo	是否通过	未通过
代码语言	C++	运行时间	7.002 s
提交时间	2017-04-20 16:56:34	内存使用	38.43 MiB

#include <cstdio>
#include <cstring>
const int C = 25;
int n, m, k, x[C], y[C], vis[int(1e7)];
bool check(int a, int dep) {
	if (dep == n) return !a;
	if (!a) return 1;
	if (dep < vis[a]) return vis[a];
	for (int i = 1; i <= m; i++) if (a >= y[i] && (a - y[i])%x[i] == 0) {
		if (check(a - y[i] - (a - y[i])/x[i], dep + 1)) return (vis[a] = dep);
	}
	return 0;
}
int main() {
	freopen("monkeys.in", "r", stdin);
	freopen("monkeys.out", "w", stdout);
	memset(vis, -1, sizeof vis);
	scanf("%d%d", &n, &m);
	n++;
	for (int i= 1; i <= m; i++) scanf("%d%d", x + i, y + i);
	scanf("%d", &k);
	int i, tot;
	for (i = 1, tot = 0; tot < k && i < int(1e7); i++)
		if (check(i, 1)) tot++;
//	for (int i = 1; i <= 15 ;i++) if (check(i, 1)) printf("%d\n", i);
	printf("%d\n", tot == k ? i - 1 : -1);
}