ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования
вернуться в форум

Обсуждение задачи 1044. Счастливые билеты. Easy!

Ruby non, C++ oui
Послано Donald Cameron 14 мар 2015 08:08
For my first try I wrote this:

def sum_of_digits(n)
  sum = 0
  while (n > 0)
    sum += n % 10
    n /= 10

num_digits = gets.chomp.to_i

exponent = num_digits/2
divisor = 10**exponent

limit = (10**num_digits) - 1
total = 0

0.upto(limit) do |cur|
  upper = cur / divisor
  lower = cur % divisor
  total += 1 if sum_of_digits(upper) == sum_of_digits(lower)

puts total

# eof

For 2, 4 and 6 digits it got the requisite answers of 10, 670, and 55252.  There was a bit of a pause while it crunched away at the 6-digit case, though.

For 8 digits it … well, I let it run and went to do something else.  Then I had the bright idea to time it (on mac OS X, using the time command):


real    1m42.596s
user    1m34.222s
sys    0m1.837s

The right answer, but the last time I checked, one minute anything was greater than two seconds.  What to do?

It’s pretty clear that calling sum_of_digits a bunch more times than necessary is the biggest problem. For try #2, I precomputed the sums and stuffed them into an array, and indexed the array in place
of calling sum_of_digits in the main loop.  Here’s the result:

time ruby lucky.rb < t8.txt

real    0m19.176s
user    0m18.017s
sys    0m0.313s

A better than 80% speedup.  Most times I would kill for that, but I still need to lose 95% of the remaining run time.  How to do it?

I checked … initializing the array of sums takes virtually no time, even if I write out the entire array contents to a file.

So the main loop is killing me, and unfortunately I need a dramatic change of algorithm but I
don’t see one. So …

1. Recode in C or C++
2. Hell if I know

Taking option 1, I got Accepted, with run times around 1.1 seconds or so for 8 digits.  It's a straightforward translation to C++, very brute force.