Guest User

Untitled

a guest
Oct 18th, 2017
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. // It's like a BFS algorithm, where you have 9 roots for 9 trees (1, 2, ..., 9).
  7. // For each tree, you scan it level by level,
  8. // and you generate the two children of every number,
  9. // add them to the queue, and remove the current number at q.front().
  10.  
  11. // When you generate a children, make sure that the digit is >= 0 and <= 9.
  12. // So, If currNum = 9, therefore, two possible children 9[8] (valid) and 9[10] (invalid).
  13.  
  14. // This algorithm will take O(10 * LogN), where Log is to the base 10. Because in every tree level we multiply by 10.
  15.  
  16. int main() {
  17. int t;
  18. scanf("%d",&t);
  19. while(t--) {
  20. long long n;
  21. scanf("%lld",&n);
  22.  
  23. if(n <= 9) {
  24. printf("%d\n", -1); continue;
  25. }
  26.  
  27. queue<long long> q;
  28. for(int i = 1; i <= 9; i++)
  29. q.push(i);
  30.  
  31. while(true) {
  32. long long currNum = q.front();
  33. int lastDigit = currNum % 10;
  34.  
  35. if(currNum > n)
  36. break;
  37. else if(currNum > 9 && currNum <= n)
  38. printf("%lld ", currNum);
  39.  
  40. if(lastDigit - 1 >= 0){
  41. q.push(currNum * 10 + (lastDigit - 1));
  42. }
  43. if(lastDigit + 1 <= 9){
  44. q.push(currNum * 10 + (lastDigit + 1));
  45. }
  46. q.pop();
  47. }
  48.  
  49. printf("\n");
  50. }
  51. return 0;
  52. }
Add Comment
Please, Sign In to add comment