e-olymp 7258. Числовые операции

Условие

На доске записано число $1$. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу $1$, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.

Задание
Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.

Входные данные

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4),$ которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих $T$ строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

Выходные данные

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

Ввод Вывод
1 3

3

955

21

1

48

12

2 4

137

318

3028

300
39

40

71

50

Код

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и так далее, пока количество цифр в числе не будет таким, какое требуется.
Наименьшее количество операций, необходимое для того, чтобы перейти от числа $10^{n-1}$ до заданного $n$ -значного числа $N$ можно посчитать следующим образом:
1. Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то количество операций можно посчитать по формуле summa(N) + nonzero(N) edinica(N) - 1, где summa(N) — сумма цифр числа, nonzero(N) — количество цифр, отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N) — число, которое равно единице, если хотя бы на одной позиции числа $N$, кроме последней, есть единица, или равна нулю, если единиц на этих позициях нет.
2. Если все цифры числа $N$, кроме первой, нулевые, а первая цифра больше единицы, то количество операций можно посчитать по формуле summa(N-1)+nonzero(N-1) edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$ -заданное число, число $n$ -количество цифр числа $N$. Если $n=1$, $N=7$, то для того, чтобы дойти от единицы до заданного числа, потребуется $N-1$ операций. В нашем случае $6$ операций
($1+1=2,
2+1=3,

6+1=7$)
Если $n\geq2$, то для этого достаточно привести пример цепочки, подсчитывающая количество операций, которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. $N \Rightarrow 10^{n-1}$. За одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так, чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1. Если $N=10^{n-1}$, то количество операций равно summa(N) + nonzero(N) - edinica(N) - 1 $= $ $0$.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2. Если $N!=10^{n-1}$ и первая цифра числа $N$ равна единице, то проводим следующие операции:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем, далее переставим местами последнюю цифру с какой-нибудь другой, отличной от нуля, кроме первой, и опять отнимем количество единиц, чтобы последняя цифра стала нулевой. Повторять будем до тех пор, пока все цифры, кроме первой, не станут нулями.
Например, возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Количество операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3. Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа, кроме последней, есть единица, то проводим следующие операции:
Сначала уменьшаем последнюю цифру, пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой цифры. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4. Если ни на одной из позиций числа $N$, кроме, возможно, последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра, кроме первой, то проводим следующие операции:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой, кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5. Если первая цифра числа $N$ больше единицы, а все другие цифры — нулевые, то проводим следующие операции:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее написанных алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6. Подсчет операций от $1$ до $10^{n-1}$.
Для того, чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) edinica(k) - 1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где $n > 1$.
Если $n=1$, то количество операций $= 10 \cdot n – 2 =8$.

Количество операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- количество цифр заданного числа.

Ссылки

2 thoughts on “e-olymp 7258. Числовые операции

  1. По оформлению много замечаний. От мелких, вроде пропущенных пробелов и всяких «кол-во», до незавершенных фраз «Наименьшее кол-во операций…»
    Ждал, когда вы догадаетесь сами перечитать свою работу. Так и не дождался.

Добавить комментарий