#P4467. [Jsoi2013]数字理论

    ID: 3701 传统题 1000ms 512MiB 尝试: 67 已通过: 23 难度: 8 上传者: 标签>CF2400提高+/省选-数位 DP记忆化搜索状态编码同余的加减乘运算可行性剪枝搜索顺序优化By

[Jsoi2013]数字理论

[JSOI2013] 数字理论

题目描述

给定 44 个正整数 K, S, P, DK,~S,~P,~D,要求在十进制数中,寻找一个最小的 KK 位自然数 xx,满足 xx 的各个数位之和为 SS,并且 xx 乘以 DD 之后各个数位之和为 PP。

输入格式

输入数据中包含一行四个整数,分别为 K, S, P, DK,~S,~P,~D。

输出格式

输出一行一个整数,表示满足条件的最小自然数 xx。如果不存在则输出−1-1。

样例 #1

样例输入 #1

2 9 9 5

样例输出 #1

18

提示

$1~\leq~K~\leq~100,~1~\leq~S,~P~\leq~1000,~1~\leq~D~\leq~9$