Условие
На доске записано число $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 |
Код
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> using namespace std; int nonzero(int number) //функция,которая считает количество цифр,не равных нулю,кроме последней { int count = 0; number /= 10; while (number != 0) { if (number % 10 != 0) count++; number /= 10; } return count; } int summa(int number) //функция,которая возвращает сумму цифр числа { int sum = 0; while (number != 0) { sum += number % 10; number /= 10; } return sum; } bool edinica(int number) //функция,которая проверяет есть ли среди цифр числа,кроме последней, единица { number /= 10; bool ok = false; while (number != 0) { if (number % 10 == 1) ok = true; number /= 10; } return ok; } int kol_vo(int number) //функция,вычисляющая кол-во цифр числа { int count = 0; while (number != 0) { count++; number /= 10; } return count; } int formula(int number) //формула,по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа { int a = kol_vo(number); return (5 * a - 1) * (a - 1); } int main() { //инииализируем переменную t и считываем ее с клавиатуры int t; cin >> t; //инициализируем переменную ni и задаем цикл,который будет работать пока мы вводим значения ni и t>0 int ni; while (cin >> ni and t > 0) { //кладем в переменную kol_vo1 значение функции kol_vo от значения ni int kol_vo1 = kol_vo(ni); //появляется необходимость создать переменную,которая будет равна значению ni,так как с этим значением //в дальнейшем будут проводится операции,а в конце программы нам нужно будет обратиться к исходному значению ni int a = ni; //задаем массив,размерность которого равна кол-ву цифр числа int b[kol_vo1]; for (int i = 0; i < kol_vo1; i++) { b[i] = a % 10; a /= 10; } //далее производим проверку условия №2,которое описано в решении. Если число проходит условие,то //выводим соответствующую формулу,указанную в условии №2 bool ok = false; for (int i = 0; i < kol_vo1 - 1; i++) { if (b[i] == 0) ok = true; else { ok = false; break; } } if (b[kol_vo1 - 1] > 1 and ok == true) { cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl; } //далее производим проверку условия №1,которое описано в решении. Если число проходит условие,то //выводим соответствующую формулу,указанную в условии №1 bool ok2 = false; for (int i = 0; i < kol_vo1 - 1; i++) { if (b[i] != 0) ok2 = true; } if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl; //остались крайние случаи,когда число однозначное или кратное 10^n.Проверяем число на эти условия //и если оно является таковым,выводим соответствующие значения if (kol_vo1 == 1) cout << ni - 1 << endl; if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl; //декрементируем переменную t t--; } } |
Решение
Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $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$ операций, где b $>$ 1.
Если $n=1$, то кол-во операций $= 10 \cdot n – 2 =8$.
Кол-во операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- кол-во цифр заданного числа.
Ссылки
