Блог пользователя Vasiljko

Автор Vasiljko, история, 7 лет назад, По-английски

List of integers is formed such that all integers that can be written in form 2x3y5z are sorted in increasing order. So, list look like this: 1, 2, 3, 4, 5, 6, 8, 9, ... What is n-th element (0-indexed) in list?
0 <  = n <  = 105

Input
500
Output
944784

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Am I missing anything, or answer for 500 is 937500?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is 0-indexed. for n=0 answer is 1, for n=1 answer is 2... Maybe this?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Yep, you are right. There is simple O(n) algorithm:

          intt n; cin >> n; n++;
          intt pw2 = 0, pw3 = 0, pw5 = 0, next2 = 2, next3 = 3, next5 = 5, res = 1;
          dp[0] = 1;
          for (intt i = 1; i < n; i++) {
              dp[i] = res = min (next2, min (next3, next5));
              if (next2 == res) {
                  next2 = 2 * dp[pw2 + 1];
                  pw2++;
              }
              if (next3 == res) {
                  next3 = 3 * dp[pw3 + 1];
                  pw3++;
              }
              if (next5 == res) {
                  next5 = 5 * dp[pw5 + 1];
                  pw5++;
              }
          }
          cout << res << endl;
      
      

      Idea is same with fofao_funk's.

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

Disregarding the overflow, I think this should work: create an ordered set which contains the element 1 initially. Now, you will do the following n + 1 times: pop out the smallest element X in the set (and delete it) and then put the elements 2X, 3X and 5X in the set. The n + 1-th popped element is the answer.