Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Assistance for Timus 2052: Physical Education

Правка en2, от minimario, 2016-02-06 05:02:14

Hello all,

Today I will bring you some interesting problem: Oh, I forgot to mention I cannot solve it...Dx

So here is the problem. Well, the first observation I have is that we can divide the numbers 1 to n into groups based on digit sum. Since two numbers with same digit sum have to differ by 9 or more, there can only be at most one number that does not change position after the sorting. So there are at most 81 different digit sum. (1 to 9 x 9)

So now there is new idea. This is part I am quite fuzzy with. It is not too bad to find the number of integers in the range 1...n with some digit sum k. (Some classical digit DP) But how this will help us? In particular, maybe there is a way to find the position of a number in a sorting in some good complexity, then apply some binary search method? I'm not sure, I have been working this problem for a while.

So if anyone has any ideas or can provide some hints, I would really appreciate!

Thanks,

minimario

Теги dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский minimario 2016-02-06 05:02:14 15
en1 Английский minimario 2016-02-06 05:01:56 1067 Initial revision (published)