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

Автор Eternity, 14 лет назад, По-русски
Вводится число n. Нужно определить сколько "единичек" в отрезке [1..n]
Например для 10 это 2, для 50 - 14.
Похоже на довольно стандартную задачу, но как сделать не пойму...
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ограничения на N?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно придумать формулу для ответа в диапазоне [a * 10p..b * 10p - 1] за O(b - a + p) и разбить искомый промежуток на такие части.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересная задача!=)
кол-во 1 будет равно общему кол-ву цифр минус количество нулей,2,..,9 ок
а количество цифр равно (n + 1)*n/2
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а соотношение количества разных цифр можно попробовать найти экспериментальным путем до какого то значение пока не станет ясно.
    Интересно будет узнать формулу)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как-то неправдоподобно. Общее количество цифр должно быть порядка Nlog_{10}N
    • 14 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
      точно, просто туплю после SRM'а=))

      P.S.
      короче цифр длинной 1 будет 9
      цифр длиной 2 будет 10 .. 99 =  90
      длиной 3 100 .. 999 = 900
      ...
      уже видна закономерность.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Динамикой предподсчитываешь сколько единичек от 1 до 10^k. Делается это просто-считаешь сколько получилось на 10^(k-1), для 10^k очевидно ответ 10^(k-1)+то что было раньше(берется из соображения что мы можем после каждого числа поставить 0,1,2,3,4,5,6,7,8,9) Далее разбиваешь свой отрезок от L до R на 2 части-от 1 до L и от 1 до R. Далее у тебя сохранена динамика, допустим у тебя число L... дай подумать... 212344587. Берешь и считаешь ответ от 1 до 200000000, потом от 200000000 до 210000000 и тд
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Может есть просто тупая формулка но думать лень:)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот как раз интересует формула)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    А нафига о_0? Решение и так за логарифм(при том десятичный) от времени и чуть побольше от памяти:)
14 лет назад, # |
Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится
Придумал такое решение.
От каждой цифры числа, кроме числа единиц, которая больше 1 отнимаем 1. Умножаем это число на 9. Складываем все + число единиц числа. Теперь от n+1 отнимем это число. Вуаля.
n=29 таким образом 1*9 + 9 = 18. Вычтите из n+1, и получаем 12
5394=9*9*9*4+2*9*9+8*9+4=5395-3154=2241
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    и какой же для 100 ответ?
    9+0+0 ?

    upd: теперь кажется понял, что делается..
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне кажется не будет работать на больших тестах, где много единиц в числе(но не все). Хотя хз, я невнимательно читал. И тем не менее не понимаю, зачем тебе формула(да еще такая)
  • 14 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится
    Итак. Окончательная формула такова: Пробегаемся по разрядам числа. Если число больше 1 то вычитаем из него 1 и умножаем это число на 9^разряд числа. Так бежим либо до конца, либо пока не встретим единичку. Встретили - значит это последнее число. Складываем все эти цифры. Теперь из n+1 вычитаем эту сумму. Все.

    Относительно последней цифры: Если были цифры 1 до сих пор, мы включаем последнюю цифру, и добавляем 1, если это 0. Таким образом добавляем 4 для 5394, 1 для 5390, ничего для 5216,но добавляем 1 для 5391.

    Пусть n=31874, тогда 2*9^4+1*9^3=13851, 31874+1-13851=18024.
    Это подтверждает решение в лоб

    #include <iostream>
    inline bool valueContainsOne(int n)
    {
        do {
            if (n % 10 == 1) {
                return true;
            }
        } while (n /= 10);
        return false;
    }

    int main()
    {
        int x;
        do {
            std::cin >> x;
        } while (x < 1);
        int result = 0;
        for (; x >= 1; --x) {
            if (valueContainsOne(x)) {
                ++result;
            }
        }
        std::cout << result ;
    }
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Осталось закодить...
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ты молодец елы-палы. Это линейное решение. Посмотри повыше на свои ограничения. Лярд. Хочешь 10^9*9 в ТЛ запихать? Удачи тебе. Решение должно быть за логарифм. Я его написал выше
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Оно не линейное оно за n log(10) n
          ))
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Тут и линейного хватит чтобы в ТЛ ушло:) В принципе можно-то ведь по маске пройти...
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          "Это подтверждает решение в лоб"

          Я так понимаю, это код перебора для проверки
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Не знаю, поможет ли тебе это, но на 50-ом бета-раунде, нужно было написать функцию, которая считает кол-во чисел с единицами от l до r. Я тогда написал функцию, которая считает кол-во таких чисел от 1 до n за log10(n). Вот код, можешь юзать:

      long long f (long long num) {
          if (num==0) return 0;
          int len=0,first=0;
          long long tmp=num;
          while (tmp>0) {
              if (tmp<10) first=tmp;
              len++; tmp/=10;
          }
          long long res=0,md=1;
          for (int i=0;i<len-1;i++) {
              res+=md;
              md*=10;
          }
          if (first==1) {
              res+=(num-md+1);
          } else {
              res+=md;
          }
          return res;
      }
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Разве код корректно работает? 100 к примеру
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Ой, извиняюсь. Там в задаче, кол-во чисел у которых только первая цифра - 1.