подсчитать количество шестерок в числе...

[TGX]

Даны числа от 1 до 1000000. Числа целые. И они записаны в строку один за другим - вплотную, вот так: 123456789101112 и т.д. И необходимо подсчитать какое количество 6-ок находится в первых 5000 цифрах (символах).

Пробовал в лоб: рассчитал сколько символов в диапазонах от 1-99, 100-999, 1000 - .... И сколько шестёрок приходится на диапазоны... Как-то не оптимально! Подскажите, возможно есть метод лучше?

[venco]

Сомневаюсь, что есть что-то лучше.

[TGX]

venco в сообщении #352844 писал(а):

Сомневаюсь, что есть что-то лучше.

ну когда перебирал.. там видно закономерности, которые прослеживаются от диапазона к диапазону... всё-таки может есть?

[ИСН]

$_=substr(join("",(1..2000)),0,5000); s/[0-5,7-9]+//g; print length;

(подозреваю, что можно ещё сократить, но у меня не хватает скиллов.)
Закономерности-то есть. Но они бы хорошо пошли с условием типа "среди первого миллиона чисел", а не "среди стольких-то цифр".

[EtCetera]

Не знаю, насколько следующий алгоритм лучше "лобового", но все же...

Будем обозначать основание системы счисления $a$, цифру, количество которой необходимо подсчитать $b$, количество цифр - $N$.
1. Найдем наибольшее $n$, при котором все еще справедливо неравенство $S_n\le N$ (здесь $S_n=na^n-\dfrac{a^n-1}{a-1}$).
2. Найдем
$P=\sum\limits_{\left\lfloor\frac{M}{a^k}\right\rfloor>0,\atop k\in\mathbb{N}}\left\lfloor\frac{M}{a^k}\right\rfloor$
где $M=N-S_n$.
3. Найдем количество цифр в записи $M$ в $a$-ричной системе счисления, не меньших по значению $b$ (обозначим это число $R$).
Искомое количество цифр $b$ среди первых $N$ символов равно $Q=n_{max}a^{n_{max}-1}+P+R$.

Пример.
По условию $a=10$, $b=6$, $N=2000$.
1. $n_{max}=2$, т.к. $2\cdot 10^2-\dfrac{10^2-1}{10-1}=189<2000<2889=3\cdot 10^3-\dfrac{10^3-1}{10-1}$
2. $M=2000-189=1811$, $P=181+18+1=200$
3. $R=1$ (т.к. $1<6$, $8>6$)
Итого: $Q=2\cdot 10^{2-1}+200+1=221$.
Вроде бы, нигде не ошибся... Но для контроля неплохо бы свериться...

[VAL]

EtCetera в сообщении #352895 писал(а):

Не знаю, насколько следующий алгоритм лучше "лобового", но все же...
[..]
Итого: $Q=2\cdot 10^{2-1}+200+1=221$.
Вроде бы, нигде не ошибся... Но для контроля неплохо бы свериться...

А Вас не смутило, что шестерок оказалось меньше, чем $\frac1{20}$ от общего количества цифр?
У меня получилось 403.

[EtCetera]

VAL

VAL в сообщении #352956 писал(а):

А Вас не смутило, что шестерок оказалось меньше, чем $\frac1{20}$ от общего количества цифр?

Да, я слегка ошибся (правда, не в вычислениях). Сослепу взял $N=2000$, а не $N=5000$.
Исправляюсь.

Пример 2.
По условию $a=10$, $b=6$, $N=5000$.
1. $n_{max}=3$, т.к. $3\cdot 10^3-\dfrac{10^3-1}{10-1}=2889<5000<38889=4\cdot 10^4-\dfrac{10^4-1}{10-1}$
2. $M=5000-2889=2111$, $P=211+21+2=234$
3. $R=0$ (т.к. $1<2<6$)
Итого: $Q=3\cdot 10^{3-1}+234+0=534$.
Конечно, не 403, но уже ближе.

[VAL]

EtCetera в сообщении #352961 писал(а):

VAL

VAL в сообщении #352956 писал(а):

А Вас не смутило, что шестерок оказалось меньше, чем $\frac1{20}$ от общего количества цифр?

Да, я слегка ошибся (правда, не в вычислениях). Сослепу взял $N=2000$, а не $N=5000$.
Исправляюсь.
[..]
Итого: $Q=3\cdot 10^{3-1}+234+0=534$.
Конечно, не 403, но уже ближе.

Вновь пропускаю выкладки (некогда, я занятие веду ). Но теперь многовато получается. 5000 цифр заканчиваются в районе полутора тысяч. Поэтому перекос должен быть в сторону единиц (их там 1041). А шестерок ожидается менее 10%.

[TOTAL]

У меня тоже $1 \cdot 100+15 \cdot 10+153 \cdot 1$

[VAL]

TOTAL в сообщении #352974 писал(а):

У меня тоже $1 \cdot 100+15 \cdot 10+153 \cdot 1$

Угу.
Эти "выкладки" мне больше нравятся :)
Единственный нюанс - найти, чем обрывается интересующий нас кусок записи.
Но это тоже просто: 5000-(9+2*90+3*900)=2111=4*527+3.
Значит. с 1000 по 1526 умещаются полностью, а от 1527 - три первых цифры.

[EtCetera]

Понял, где ошибался.

Итак, более правильный вариант алгоритма (обозначения те же):
1. Найдем наибольшее $n$, при котором все еще справедливо неравенство $S_n\le N$ (здесь $S_n=na^n-\dfrac{a^n-1}{a-1}$).
2. Найдем
$K=\left\lfloor\dfrac{M}{n_{max}+1}\right\rfloor+a^{n_{max}}-1$,
где $M=N-S_n$.
$K$ - наибольшее число, которое целиком присутствует в строке.
3. Найдем
$P=\sum\limits_{\left\lfloor\frac{M}{a^k}\right\rfloor>0,\atop k\in\mathbb{N}}\left\lfloor\frac{M}{a^k}\right\rfloor a^{k-1}$
4. Найдем $R=\overline{\alpha_{n_{max}}\alpha_{n_{max}-1}\dots\alpha_1\alpha_0}$, где
$\alpha_k=\left\{\begin{array}{l}0, a_k\le b \\ 1, a_k>b\end{array}\right.$
$a_k$ - цифры в записи $K$ в $a$-ричной системе счисления: $K=\overline{a_{n_{max}}a_{n_{max}-1}\dots a_1 a_0}$
5. Найдем $T=\beta_0+\sum\limits_{k=1}^{n_{max}}\beta_k\left(\overline{a_{k-1}\dots a_1 a_0}+1\right)$, где
$\beta_k=\left\{\begin{array}{l}0, a_k\ne b \\ 1, a_k=b\end{array}\right.$
6. Найдем $U$ - количество цифр $b$ в первых $r$ символах записи числа $K+1$ в $a$-ричной системе счисления ($r$ - остаток от деления $M$ на $n_{max}+1$).
Искомое количество цифр $b$ среди первых $N$ символов равно $Q=P+R+T+U$.

Пример <надеюсь, что наконец-то правильный>.
По условию $a=10$, $b=6$, $N=5000$.
1. $n_{max}=3$, т.к. $3\cdot 10^3-\dfrac{10^3-1}{10-1}=2889<5000<38889=4\cdot 10^4-\dfrac{10^4-1}{10-1}$
2. $M=5000-2889=2111$, $K=\left\lfloor\dfrac{2111}{3+1}\right\rfloor+10^3-1=1526$
3. $P=152\cdot 10^0+15\cdot 10^1+1\cdot 10^2=402$
4. $R=0$
5. $T=1$
6. $U=0$ ($r=3$, 152 не содержит 6)
Итого: $Q=402+1=403$.

P.S. Кстати, более интересно найти количество цифр 6 среди первых 1890 символов.

[Zealint]

Цитата:

P.S. Кстати, более интересно найти количество цифр 6 среди первых 1890 символов.

Шутку понял ($n=666$?). Ответ (для каждой цифры):

"0" - 126
"1" - 237
"2" - 237
"3" - 237
"4" - 237
"5" - 237
"6" - 201
"7" - 126
"8" - 126
"9" - 126

В школе (на олимпиаде попалась) писал программу, которая считает количество повторений каждой цифры в числах о 1 до $n$. Число $n$ может быть большим. Программа работает по принципу динамического программирования со сложностью $O(\log n)$. Код без комментариев нужен кому?

Только я не понял, зачем в условиях сказано:

Цитата:

Даны числа от 1 до 1000000.

[TGX]

я сам не знаю для чего в задание указано "Даны числа от 1 до 1000000." =)

Господа, я написал скрипт на JS:

var k = 0; //количество шестёрок в числе
function f(a) //функция, рассчитывающая количество шестёрок в числе
{
   if((a%10)==6){k++;} //если в младшем разряде шестёрка - увеличиваем
         else{
         if((a/10)!=0){f(a/10);}    //если есть старшие разряды, то убираем младший 
                                                                                       //и рекурентно запускаем снова уже для него
         }
   return k; //возвращает колличество
}

$(document).ready(function() { //при запуске браузера проводить расчёт =)
      var n=0; // количество шестёрок всего
      var str = ""; //буферная строковая переменная
                             var i = 1; //начальное число для расчёта
      var sum = 0; //сумма символов
       while(sum<=50000)// пока не прошли 5000 символов - выполнять...
         {       
                       n=f(i); //берём число шестёрок в числе 
            str=""+i; // загоняем число текущее в буферную переменную
            sum+=str.length;//берём длину строки буф. переменной(количество символов)
            i++; //переходим к следующему числу
         }
alert(n); // выводим число =)
   });

Вот что показал алгоритм:

• для 7 первых символов: 1 шестёрка
• для 59 первых символов : 3 шестёрки
• для 100 первых символов : 5 шестёрок
• для 189 первых символов : 11 шестёрок (до 1 до 99 числа)
• для 666 первых символов : 28 шестёрок
• для 5000 первых символов : 169 шестёрок
• для 10000 первых символов : 309 шестёрок

[VAL]

TGX в сообщении #353123 писал(а):

я сам не знаю для чего в задание указано "Даны числа от 1 до 1000000." =)

Господа, я написал скрипт на JS:
[..]
[*] для 7 первых символов: 1 шестёрка
[*] для 59 первых символов : 3 шестёрки
[*] для 100 первых символов : 5 шестёрок
[*] для 189 первых символов : 11 шестёрок (до 1 до 99 числа)
[*] для 666 первых символов : 28 шестёрок
[*] для 5000 первых символов : 169 шестёрок
[*] для 10000 первых символов : 309 шестёрок[/list]

То, что написал TOTAL (без JS) явно проще. И что самое главное - правильнее.

Среди 5000 первых символов - 403 шестерки: 153 в позиции единиц, 150 в позиции десятков и 100 в позиции сотен.

PS: Разве Вам без скрипта не очевидно, что при приписывании чисел от 1 до 99 получается не 11, а 20 шестерок?

[ИСН]

Это просто парад ужаса какой-то. TGX, послушайте: не надо, не надо проверять ручные математические задачи софтовым путём. В софте ошибиться легче, а результаты ошибки - страшнее. Я грешен, каюсь: сам же в этой теме первым вызвал этого дьявола. Но меня хотя бы частично оправдывает то, что во-первых, моя программа короче (стало быть, легче проверить), а во-вторых, выдаёт правильный результат.

(Оффтоп)

По ветке, где a/10, Вы идёте только в случае "else". То есть, если крайняя - шестёрка, то дальше проверять кагбе не надо. Это первое. Второе хуже. Сделайте выдачу промежуточных значений a куда-нибудь. Сделайте её. да.