fork download 
  1. #include<iostream>
  2.  
  3. const int MAX_N = 1000;
  4. int N;
  5. std::string dp[MAX_N+10][MAX_N+10];
  6.  
  7. /*
  8.  * compares two integers represented as strings
  9.  * if what>competitor, 'what' value copies 'competitor' value
  10.  * returns true if value was copied, false otherwise
  11.  */
  12. bool reduce(std::string& what, const std::string& competitor)
  13. {
  14.     int wlen = what.length(), clen = competitor.length();
  15.     if (!wlen)
  16.     {
  17.         what = competitor;
  18.         return true;
  19.     }
  20.  
  21.     bool competitorIsLesser = false;
  22.     if (wlen != clen)
  23.         competitorIsLesser = wlen>clen;
  24.     else
  25.     {
  26.         for (int i = 0; i < wlen; ++i)
  27.             if (what[i] != competitor[i])
  28.             {
  29.                 competitorIsLesser = what[i]>competitor[i];
  30.                 break;
  31.             }
  32.     }
  33.  
  34.     if (competitorIsLesser)
  35.     {
  36.         what = competitor;
  37.         return true;
  38.     }
  39.  
  40.     return false;
  41. }
  42.  
  43. /*
  44.  * iterate through all possible last digits and adds them to end
  45.  * tries to improve dp values with obtained integer
  46.  * 
  47.  * tricky case: when adding '0', we can refer to previous dp values
  48.  * in this case, function calls recursively on that previous cell if it was improved
  49.  */
  50. void proceed(int sum, int rem)
  51. {
  52.     for (int lastDigit = 9; lastDigit; --lastDigit)
  53.         reduce(dp[sum+lastDigit][(rem*10+lastDigit)%N], dp[sum][rem]+char('0'+lastDigit));
  54.  
  55.     if (reduce(dp[sum][rem*10%N], dp[sum][rem]+'0') && rem*10%N<rem)
  56.         proceed(sum, rem*10%N);
  57. }
  58.  
  59. int main()
  60. {
  61.     std::ios_base::sync_with_stdio(false);
  62.     std::cin.tie(0);
  63.     std::cout.tie(0);
  64.  
  65.     std::cin>>N;
  66.  
  67.     //starting conditions
  68.     for (int lastDigit = 9; lastDigit >= 0; --lastDigit)
  69.         dp[lastDigit][lastDigit%N] = char('0'+lastDigit);
  70.  
  71.     //dp itself
  72.     for (int sum = 1; sum <= N; ++sum)
  73.         for (int rem = 0; rem < N; ++rem)
  74.             if (dp[sum][rem].length())
  75.                 proceed(sum, rem);
  76.  
  77.     std::cout<<dp[N][0];
  78. }
Success #stdin #stdout 4.43s 29808KB
comments (?)
stdin 
1000
stdout 
1999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999000
https://ideone.com/UqKJfn
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!