Сортировка по сумме цифр - Сириус

@Eisenstein · Регистрация: 28.06.2021

Студворк — интернет-сервис помощи студентам

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

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N чисел — элементы массива. Гарантируется, что 0 <N≤ 1000 .

Выходные данные
Программа должна вывести в одной строке элементы массива, отсортированного в порядке убывания суммы цифр десятичной записи числа, разделив их пробелами.

Примеры
Ввод
6
9 21 32 55 81 11
Вывод
55 9 81 32 21 11

На проверке пишет, что программа выдаёт неверный ответ. Не понимаю, что не так, помогите, пожалуйста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool cmp(int x, int y)
{
    return x % 10 + x / 10
    < y % 10 + y / 10;
    
}
 
int main()
{ 
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.rbegin(), a.rend(), cmp);
    for (int i = 0; i < a.size(); ++i)
        cout << a[i] << " ";
    return 0;
}

@alexu_007 · 08.07.2021, 22:36

Массив массивов это круто.

А я бы создал структуру, в которой будет 2 элемента - само число и сумма его цифр. А потом отсортировал массив структур по сумме цифр.

Если есть ограничения по памяти, можно не создавать дополнительных массивов, а каждый раз считать сумму цифр для числа "на лету" и сортировать по этой сумме. Это будет медленнее и больше бесполезных расчётов.

Только неинтересно решать такую примитивную задачу.

@Obivashka · 14.03.2023, 21:54

Вот код несколько попроще, чем данный ранее. Надеюсь будет попонятнее.
P.S. У меня тоже возникала такая проблема: несмотря на то, что ответ выводился правильный, тестировщик писал, что ответ неверный. Насколько я понял, проблема заключается в том, что от нас хотят использования именно функции stable_sort, а не sort.

C++ (Qt)
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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int sum_chi(int  a)        // Программа для поиска суммы цифр в числе. Число может быть больше 100
{
    int  suma = 0;        // Переменная, в которую записывается сумма цифр
    int  i = 1;
    while (a/i != 0) {               // Проверяем не больше ли наше число чем 10^n, где n принадлежит целым неотрицательным
        suma += (a/i)%10;       // С помощью кода в этой строке можно извлечь n-ный разряд из числа a : razrad = (a/10**n)%10
        i*=10;                          // Изменяем переменную для поиска следующего разряда
    }
    return suma;
}
 
bool sumcif(int  a, int  b)       // Ключ сортировки
{ 
    return sum_chi(a)<sum_chi(b);         // Сравнения суммы цифр в числе
}
 
int main()
{
    int  n;
    cin >> n;
    vector<int > sp(n);
    for(int  i = 0; i < n; ++i) {
        cin >> sp[i];                 
    }
    stable_sort(sp.rbegin(), sp.rend(), sumcif);
    for (int  i : sp) {
        cout << i << " ";
    }
}

@Compoter25120 · 24.05.2023, 14:22

C++
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
 
#include <iostream>
using namespace std;
unsigned DigitSum( unsigned x ) {
   unsigned sum = 0;
   while ( x != 0 ) {
       sum += x % 10;
       x /= 10;
   }
   return sum;
}
bool Comparison( const unsigned a, const unsigned b ) {
   return DigitSum( a ) < DigitSum( b );
}
void InsertionSort( unsigned long *arr, size_t size, bool (*compareFunc)( const unsigned, const unsigned ) ) {
   for ( size_t i = 1; i < size; ++i )
       for ( size_t j = i; j > 0 && Comparison( arr[ j - 1 ], arr[ j ] ); --j )
           swap( arr[ j - 1 ], arr[ j ] );
}
int main() {
   const size_t maxCount = 10000;
   unsigned long* arr = new unsigned long[ maxCount ];
   size_t count = 0;
   cin >> count;
   for ( size_t i = 0; i < count; ++i ) {
       cin >> arr[ i ];
   }
   InsertionSort( arr, count, Comparison );
   for ( size_t i = 0; i < count; ++i )
       cout << arr[ i ] << " ";
   delete[] arr;
   return 0;
}

@Pythonist213 · 20.06.2023, 12:15

Да, да, прошло 2 года, не скажешь, пожалуйста, так в чем был подвох??

@AK-rasava · 01.08.2024, 19:51

Проблема в том, что stable_sort сохраняет порядок при сортировке. Странно только, что в Сириус это не сказали -_-

C++
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
unsigned summ_digits(int x)
{
    unsigned summ = 0;
    while (x)
    {
        summ += x % 10;
        x = x / 10;
    }
    return summ;
}
 
bool mp(int x, int y)
{
    return summ_digits(x) < summ_digits(y);
}
 
int main()
{
    int n;
    cin >> n;
    vector <int> num(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> num[i];
    }
    
    stable_sort(num.rbegin(), num.rend(), mp);
    
    for (int i = 0; i < n; ++i)
    {
        cout << num[i] << " ";
    }
    
    return 0;
}

@SmallEvil · 01.08.2024, 21:18

C++
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
#include <iostream>
#include <map>
#include <deque>
#include <functional>
 
int main(){
   using list_t = std::deque<unsigned>;
   using voc_t  = std::map<std::uint8_t, list_t, std::greater<>>;
   
   auto digits_sum = [](unsigned num){
      unsigned sum = 0;
      while(num)
         sum += num%10, num /= 10;
      return sum;
   };
   
   unsigned n, num;
   voc_t voc;
   
   std::cin >> n;
   while(n--){
      std::cin >> num;
      voc[digits_sum(num)].push_back(num);
   }
   
   for(const auto &p : voc){
      for(const auto &num : p.second)
         std::cout << num << ' ';
   }
   std::cout << std::endl;
}

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов и табличных частей документа при копировании Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .	сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,316
	08.07.2021, 22:36
	Массив массивов это круто. А я бы создал структуру, в которой будет 2 элемента - само число и сумма его цифр. А потом отсортировал массив структур по сумме цифр. Если есть ограничения по памяти, можно не создавать дополнительных массивов, а каждый раз считать сумму цифр для числа "на лету" и сортировать по этой сумме. Это будет медленнее и больше бесполезных расчётов. Только неинтересно решать такую примитивную задачу. 2

@Pythonist213 1 / 1 / 0 Регистрация: 29.10.2021 Сообщений: 8
	20.06.2023, 12:15
	Да, да, прошло 2 года, не скажешь, пожалуйста, так в чем был подвох?? 0