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

n-th number in given list
Автор 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.

→ Ответить