ЕГЭ. Информатика. Поляков. Решение. C4-35

Ещё одна задача, подобную решал ранее. Добавил комментариев в код, для понятности.

Условие

В командных олимпиадах по программированию для решения предлагается не более 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систем соревнований. Вам предлагается написать эффективную, в том числе и по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы на проверку, чтобы определить популярность той или иной задачи. Следует учитывать, что количество запросов в списке может быть очень велико, например, когда олимпиада проводится через Интернет. перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строчке подается количество пришедших запросов N. В каждой из последующих N строк записан номер задачи от 1 до 12. Пример входных данных:

6
1
2
1
1
5
2

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

5 1
2 2
1 3

Решение

#include <stdio.h>
#include <iostream>
#include <string.h>
 
struct info {
    int id, count;
} array[12];
 
int main()
{
    memset(array, 0, 12 * sizeof(info)); // обнуляем массив array
    int N, tmp, found = 0;
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &tmp);
        // если число есть в массиве, то мы увеличиваем его count на 1, а не добавляем новый элемент
        for (int j = 0; j < N; j++)
        {
            if (array[j].id == tmp)
            {
                array[j]. count++;
                found = 1;
            }
        }
        // если числа нет в массиве, то добавим его
        if (found == 0)
        {
            array[i].id = tmp;
            array[i].count = 1;
        }
        found = 0;
    }
    // сортируем массив методом пузырька
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N-1; j++)
        {
            if (array[j].count > array[j+1].count)
            {
                std::swap(array[j], array[j+1]);
            }
        }
    }
    // выводим
    for (int i = 0; i < N; i++)
    {
        if (array[i].count != 0)
        {
            printf("%d %d\n", array[i].id, array[i].count);
        }
    }
    return 0;
}
Перейти к верхней панели