sdryapko's blog

SRM 510
By sdryapko, 13 years ago, In Russian
Здравствуйте, сегодня в 5:00 по московскому времени начался очередной SRM, предлагаю после окончания соревнования вести его обсуждение здесь.
  • Vote: I like it
  • +26
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve the problem 500 (Div 2) ?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    1 . pre calculate the amount of lucky numbers on segment [0,N]. (you can do this using dp approach). Code will look like this
    int cnt[4747+1] = {0};
    for(int x = 1; x <= 4747; ++x) cnt[x] = cnt[x-1] + isLucky(x);

    2.  in order to obtain the amount of lucky numbers on arbitrary segment you can use cnt array. number of lucky numbers on segment[M,N] equals to cnt[N] - cnt[N-1].

    3. to solve problem just simulate the game

    int ans = 0;

    for(int aa = a; aa + jLen - 1 <= b; ++aa) 
        { 
            int brus = bLen; 

            for(int bb = aa; bb + bLen - 1<= aa + jLen - 1; ++bb) 
            { 
                    brus = min(brus, cnt[bb + bLen - 1] - cnt[bb-1] ); 
            } 

            ans = max(ans, brus); 
        } 

    return ans;
    → Reply