此文章可以使用目录功能哟↑(点击上方[+])
Kattis <Zamka>
Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 1024 MB
Problem Description
The impossible has happened. Bear G. has fallen into his own trap. Lured by a delicious box of Doma?ica, without even thinking, he rushed and fell into his trap. In order to get out of the trap, he must solve the following task with your help. You are given three integers L, D and X.
- determine the minimal integer N such that L≤N≤D and the sum of its digits is X
- determine the maximal integer M such that L≤M≤D and the sum of its digits is X
Bear will be able to escape from the trap if he correctly determines numbers N and M. The numbers N and M will always exist.
Input
The first line of input contains the integer L (1≤L≤10000), the number from the task. The second line of input contains the integer D(1≤D≤10000, L≤D), the number from the task. The third line of input contains the integer X (1≤X≤36), the number from the task.
Output
The first line of output must contain the integer N from the task. The second line of output must contain the integer M from the task.
Sample Input
100
4
100
500
12
1
10000
1
Sample Output
40
129
480
1
10000
Problem Idea
解题思路:
【题意】
问题一:在区间[L,D]内找到一个最小整数N,使得其各位数字之和为X
问题二:在区间[L,D]内找到一个最大整数M,使得其各位数字之和为X
【类型】
暴力
【分析】
想要根据各位数字之和是X在区间[L,D]内直接确定出N和M还是有难度的
但考虑到区间[L,D]的最大区间长度为10000
所以可以采用暴力枚举法
从L开始向D枚举(从小到大枚举),直到出现第一个[各位数字之和是X的]数,则该数即为N
再从D开始向L枚举(从大到小枚举),直到出现第一个[各位数字之和是X的]数,则该数即为M
【时间复杂度&&优化】
O((D-L+1)×digit(i))
题目链接→Kattis <Zamka>
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 6;
const int M = 100005;
const int inf = 1000000007;
const int mod = 10007;
int judge(int x)
{int sum=0;while(x){sum+=x%10;x/=10;}return sum;
}
int main()
{int L,D,X,i;scanf("%d",&L);scanf("%d",&D);scanf("%d",&X);for(i=L;i<=D;i++)if(judge(i)==X){printf("%d\n",i);break;}for(i=D;i>=L;i--)if(judge(i)==X){printf("%d\n",i);break;}return 0;
}