3744. Снова факториал!

 

Матвей, начинающий инженер, разрабатывает оригинальную позиционную нотацию для представления целых чисел. Он назвал ее "A Curious Method" (ACM вкратце). Нотация ACM использует те же цифры что и десятичная, то есть цифры от 0 до 9.

Для перевода числа A из нотации ACM в десятичную необходимо найти сумму k слагаемых, где k – количество цифр A (в ACM нотации). Значение i-го слагаемого, соответствующего i-ой цифре ai считая справа налево, равно ai × i!. Например 719[ACM] эквивалентно 53[10], так как 7 × 3! + 1 × 2! + 9 × 1! = 53.

Матвей только недавно начал изучать теорию чисел, и он еще не знает свойств разрабатываемой числовой системы, однако на данный момент он интересуется в преобразовании чисел из системы ACM в десятичную. Можете ли Вы ему помочь?

 

Вход. Каждая строка содержит непустую последовательность из не более чем 5 цифр, задающих число в ACM нотации. Строка не имеет ведущих нулей.

Последний тест содержит ноль и не обрабатывается.

 

Выход. Для каждого теста в отдельной строке вывести десятичное представление числа.

 

Пример входа

Пример выхода

719

1

15

110

102

0

53

1

7

8

8

 

 

РЕШЕНИЕ

вычисления

 

Анализ алгоритма

В задаче следует преобразовать число из АСМ нотации в десятичную систему счисления.

 

Реализация алгоритма

Числа в ACM нотации будем читать в строку s. В массиве fact вычислим факториалы чисел от 1 до MAX – 1.

 

#define MAX 7

char s[MAX+1];

int fact[MAX];

 

Вычисляем факториалы.

 

fact[0] = 1;

for(i = 1; i < MAX; i++)

  fact[i] = fact[i-1] * i;

 

Читаем входную строку – число в АСМ нотации.

 

while(gets(s),s[0] != '0')

{

  len = strlen(s);

 

Преобразовываем число в десятичную систему счисления.

 

  res = 0;

  for(i = 0; i < len; i++)

    res += (s[i] - '0') * fact[len - i];

 

Выводим десятичное представление числа.

 

  printf("%d\n",res);

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int fact[] = new int[10];

    fact[0] = 1;

    for(int i = 1; i < 10; i++)

      fact[i] = fact[i-1] * i;

   

    while(true)

    {

      String s = con.nextLine();

      if (s.equals("0")) break;

      int res = 0, len = s.length();

      for(int i = 0; i < len; i++)

        res += (s.charAt(i) - '0') * fact[len - i];

     System.out.println(res);     

    }

    con.close();

  }

}