3937. Цифровой корень

 

Цифровым корнем (digital root) числа n называется следующее число: берётся сумма цифр числа n, затем сумма цифр у получившегося числа и так далее, пока не получится однозначное число.

Ваша задача – отсортировать данный массив по возрастанию цифровых корней его элементов. Если цифровые корни двух чисел равны, то раньше должно идти меньшее число.

 

Вход. В одной строке заданы элементы массива. Длина массива не превосходит 200, каждое число положительно и не превышает 109.

 

Выход.  Вывести массив, отсортированный в порядке возрастания цифрового корня.

 

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

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

15 14 13 12 11 10 9 8 7

10 11 12 13 14 15 7 8 9

 

 

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

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

80 61 51 41 22 1

1 22 41 51 61 80

 

 

РЕШЕНИЕ

сортировка

 

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

Реализуем компаратор, сортирующий элементы массива по возрастанию их цифрового корня. Если цифровые корни чисел равны, то сортируем их по возрастанию.

 

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

Объявим массив для хранения чисел.

 

#define MAX 200

int m[MAX];

 

Функция sum вычисляет сумму цифр числа n.

 

int sum(int n)

{

  return (n < 10) ? n : sum(n/10) + n % 10;

}

 

Функция digSum вычисляет цифровой корень числа n.

 

int digSum(int n)

{

  while (n > 9) n = sum(n);

  return n;

}

 

Функция f является компаратором (функцией сравнения).

 

int f(int a, int b)

{

  if (digSum(a) == digSum(b)) return a < b;

  return digSum(a) < digSum(b);

}

 

Основная часть программы. Читаем массив чисел.

 

n = 0;

while (scanf("%d",&m[n]) == 1) n++;

 

Сортируем массив.

 

sort(m, m + n, f);

 

Вывод элементов массива.

 

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

  printf("%d ",m[i]);

printf("\n");

 

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

 

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

int i, x;

vector<int> v;

 

int sum(int n)

{

  return (n < 10) ? n : sum(n / 10) + n % 10;

}

 

int digSum(int n)

{

  while (n > 9) n = sum(n);

  return n;

}

 

int f(int a, int b)

{

  if (digSum(a) == digSum(b)) return a < b;

  return digSum(a) < digSum(b);

}

 

void merge(vector<int>& a, int bleft, int bright, int cleft, int cright)

{

  // a[bleft..bright] and a[cleft..cright] are merged into a[bleft..cright]

  int i, left = bleft, len = cright - bleft + 1;

 

  int* res = new int[len];

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

  {

    if ((bleft > bright) || (cleft > cright)) break;

    if (f(a[bleft], a[cleft])) res[i] = a[bleft], bleft++;

    else res[i] = a[cleft], cleft++;

  }

 

  while (bleft <= bright) res[i++] = a[bleft++];

  while (cleft <= cright) res[i++] = a[cleft++];

 

  for (i = left; i < left + len; i++) a[i] = res[i - left];

  delete[] res;

}

 

void mergeSort(vector<int>& a, int left, int right)

{

  if (left >= right) return;

  int middle = (left + right) / 2;

  mergeSort(a, left, middle);

  mergeSort(a, middle + 1, right);

  merge(a, left, middle, middle + 1, right);

}

 

int main(void)

{

  while (scanf("%d", &x) == 1)

    v.push_back(x);

 

  mergeSort(v, 0, v.size() - 1);

 

  for (i = 0; i < v.size(); i++)

    printf("%d ", v[i]);

  printf("\n");

  return 0;

}

 

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

 

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

int i, x;

vector<int> v;

 

int sum(int n)

{

  return (n < 10) ? n : sum(n / 10) + n % 10;

}

 

int digSum(int n)

{

  while (n > 9) n = sum(n);

  return n;

}

 

int f(int a, int b)

{

  if (digSum(a) == digSum(b)) return a < b;

  return digSum(a) < digSum(b);

}

 

void swap(int &i, int &j)

{

  int temp = i; i = j; j = temp;

}

 

int Partition(vector<int>& m, int L, int R)

{

  int x = m[L];

  int i = L - 1, j = R + 1;

  while (1)

  {

    do j--; while (f(x, m[j]));

    do i++; while (f(m[i], x));

    if (i < j) swap(m[i], m[j]); else return j;

  }

}

 

void QuickSort(vector<int>& m, int L, int R)

{

  if (L < R)

  {

    int q = Partition(m, L, R);

    QuickSort(m, L, q); QuickSort(m, q + 1, R);

  }

}

 

int main(void)

{

  while (scanf("%d", &x) == 1)

    v.push_back(x);

 

  QuickSort(v, 0, v.size() - 1);

 

  for (i = 0; i < v.size(); i++)

    printf("%d ", v[i]);

  printf("\n");

  return 0;

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static int sum(int n)

  {

    return (n < 10) ? n : sum(n/10) + n % 10;

  }

 

  public static int digSum(int n)

  {

    while (n > 9) n = sum(n);

    return n;

  }

  public static class MyFun implements Comparator<Integer>

  {

    public int compare(Integer a, Integer b)

    {

      if (digSum(a) == digSum(b)) return a - b;

      return digSum(a) - digSum(b);

    }

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    ArrayList<Integer> m = new ArrayList<Integer>();

    while(con.hasNext()) m.add(con.nextInt());

 

    Collections.sort(m, new MyFun());

   

    for(int i = 0; i < m.size(); i++)

      System.out.print(m.get(i) + " ");

    System.out.println();

    con.close();

  }

}

 

Python реализация

Функция sum_digits вычисляет сумму цифр числа n.

 

def sum_digits(n):

  if n < 10: return n

  return sum_digits(n // 10) + n % 10

 

Функция dig_sum вычисляет цифровой корень числа n.

 

def dig_sum(n):

  while n > 9:

    n = sum_digits(n)

  return n

 

Основная часть программы. Читаем входные данные.

 

lst = list(map(int, input().split()))

 

Сортируем и выводим список.

 

lst.sort(key = lambda x: (dig_sum(x), x))

print(*lst)