| Submit | All submissions | Best solutions | Back to list |
INUMBER - Interesting number |
For the given number n find the minimal positive integer divisable by n, with the sum of digits equal to n.
Input
t – the number of test cases, then t test cases follow. (t <= 50)
Test case description:
n - integer such that 0 < n <= 1000
Output
For each test case output the required number (without leading zeros).
Example
Input: 2 1 10 Output: 1 190
| Added by: | Roman Sol |
| Date: | 2005-01-13 |
| Time limit: | 7s |
| Source limit: | 4096B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | XII team championship of St.-Petersburg in programming |
hide comments
|
||||||
|
2019-02-19 12:09:44
after 1 hours, AC in one go. |
||||||
|
2018-09-01 00:50:38
Really good one iterative DP + BFS + backtracking for printing the solution |
||||||
|
2017-12-19 23:31:49
Challenging one...!! Important Lesson learnt: For solving bfs, using "array" instead of "map" for storing visit state reduces complexity by large fraction. |
||||||
|
2016-09-05 22:15:57 Sarthak Munshi
Using STL gives WA while simulating using an array gives AC . Weird . Spent 2 full days on getting this passed . |
||||||
|
2016-06-21 21:24:01 kartikay singh
dp + bfs + backtracking = AC :-B |
||||||
|
2016-06-21 02:21:06
if using bfs don't use string to store no from starting use backtracking ie maintain the parent's address in some form and calculate the number in the end |
||||||
|
2016-04-08 07:10:46 Navneet Kumar Srivastava
Can someone explain why the output is 1 when input is 1? |
||||||
|
2016-01-21 01:26:46
19 sums up to 10, but it is not divisible by 10. thats y. |
||||||
|
2016-01-16 10:46:46 kejriwal
why is the answer of 2nd case 190.. ? 19 also sums upto 10 !! ? |
||||||
|
2015-09-07 22:06:56 Rohit Agarwal
Very challenging problem. Was fun to implement it. The hardest part was to print the number. Finally AC ;) :D STL and w/o STL both. :) |
||||||
RSS