TÓPICO

Tempo de execução.

Wellerson Salvatore perguntou 10 months ago

Alguém sabe como diminuir o tempo de execução para esse problema? a unica forma que eu pensei vai levar muito tempo, nem testei enviar porquê sei que vai dar TLE pra casos como 10^12... segue o codigo:

n = int(input())
cont = 0
for i in range(1, n + 1):
    a = str(i)
    cont += a.count("1")
    cont += a.count("7")
print(cont)

foi a unica forma que consegui pensar, se alguém tiver uma dica fico grato.

Lembre de não publicar soluções. Sua publicação pode ser revisada por nossos moderadores.

  • feodorv respondido 10 months ago

    Hm. That was a hint, that was not a solution. Let's consider the input number 15725. We can count offhand the answer for the interval [1...9999]: x is 4 (x is the number of digits of 9999) and the answer for the interval [1...9999] is 8000. Now we should consider the interval [10000...15725]. We can see that it consists of numbers 1#[0...5725] and contains 5726 times the number '1' and the interval [0...5725] (the answers for intervals [0...5725] and [1...5725] are the same ones). So you can reduce the task to smaller interval. Now you can consider the intervals [0...999], [1000...1999], [2000...2999], [3000...3999], [4000...4999], [5000...5725]. The answer for first five intervals are calculated by means of the given formula (here x = 3): 600 + (1000+600) + 600 + 600 + 600. Now you have 17726 in total and the interval [0...725] for further counting . You can continue this algorithm till zero interval.

    This algorithm is not the only approach to the problem. Please, see the following sites:

    https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property
    https://codeforces.com/blog/entry/53960
    https://www.geeksforgeeks.org/digit-dp-introduction/
    
  • feodorv respondido 10 months ago

    It's a Digit DP problem. Hint: you can offhand count the number of 1 and 7 for N = (10^x)-1. It's

    2 * x * 10^(x-1) 

    For example:

    40 for N = 99 (x=2)
    14000000 for N = 9999999 (x=7)
    2400000000000 for N = 999999999999 (x=12)
  • Wellerson Salvatore respondido 10 months ago

    I didn't understand it. How did you get the value of ' x '?

    #

    Eu não entendi... Como você obteve o valor de ' x '?