Последняя задача перед сдачей экзамена…

Условие

Дан список результатов сдачи экзамена учащимися школ некоторого района, с указанием фамилии и имени учащегося, номера школы и итогового балла. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая определяет номера школ, в которых больше всего учащихся получило за экзамен максимальный балл среди всех учащихся района.
На вход программе в первой строке подается количество учащихся во всех школах района N. В каждой из последующих N строк находится информация в следующем формате:
<Фамилия> <Имя> <Номер школы> <Балл>
где < Фамилия > — строка, состоящая не более, чем из 20 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — число от 1 до 99, <Балл> – число от 0 до 100. Порядок следования строк — произвольный.
Пример входных данных:

6
Иванов Сергей 7 74
Сергеев Петр 3 82
Петров Кирилл 7 85
Кириллов Егор 3 82
Егоров Николай 7 85
Николаев Иван 19 85

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

7

Примечание. В данном примере максимальный балл по району равен 85, его набрало 2 учащихся из школы 7 и 1 учащийся из школы 19, поэтому выводится только номер школы 7.
При выполнении задания следует учитывать, что значение N может быть велико (до 10.000).

Решение

#include <stdio.h>
#include <string.h>
 
const int MAX_SCHOOL = 100;
 
struct info {
    int ppls, balls;
};
 
int main()
{
    int N;
    scanf("%d", &N);
 
    int school, balls, max_ball = 0, max_ppl = 0;
    info arr[MAX_SCHOOL];
    memset(arr, 0, MAX_SCHOOL * sizeof(info));
 
    for (int i = 0; i < N; i++)
    {
        scanf("%*s %*s %d %d", &school, &balls);
        // записываем в массив макимальное количество баллов в школе
        // и количество человек, получившее их
        if (balls == arr[school].balls)
        {
            arr[school].ppls++;
        }
        if (balls > arr[school].balls)
        {
            arr[school].balls = balls;
            arr[school].ppls = 1;
        }
        // определяем максимальное количество людей и баллов
        if (max_ppl < arr[school].ppls)
        {
            max_ppl = arr[school].ppls;
        }
        if (max_ball < balls)
        {
            max_ball = balls;
        }
    }
 
    // выводим
    for (int i = 0; i < MAX_SCHOOL; i++)
    {
        if (arr[i].ppls == max_ppl && arr[i].balls == max_ball)
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

Особенность задачи — даты(сортировка и вывод).

Условие

На вход программе подаются сведения о ячейках камеры хранения багажа. В первой строке – текущая дата – день (ровно две цифры, от 01 до 31), затем через точку – месяц (ровно две цифры, от 01 до 12). Во второй строке сообщается количество занятых ячеек N (не меньше 3, но не больше 1000). Каждая из следующих строк имеет формат:
<номер ячейки> <дата сдачи багажа>
Номер ячейки – это целое число, дата – 5 символов: день (ровно две цифры, от 01 до 31), затем через точку – месяц (ровно две цифры, от 01 до 12). Сведения отсортированы по номерам ячеек. Все даты относятся к одному календарному году. Считать, что в феврале 28 дней.
Нужно вывести номера тех ячеек, в которых багаж хранится более 3 дней в хронологическом порядке сдачи багажа. Например, если исходные данные были такие:

04.06
3
1000 01.06
1001 31.05
2007 21.05

то результат должен быть следующий:

2007
1001

Решение

#include <stdio.h>
#include <iostream>
#include <string.h>
 
struct info {
    int cell, day, month;
};
 
// возвращает количество дней месяца
int get_day(int month)
{
    int months[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    return months[month-1];
}
 
int main()
{
    int curr_day, curr_month;
    scanf("%d.%d", &curr_day, &curr_month);
 
    int N;
    scanf("%d", &N);
 
    info arr[1000];
    memset(arr, 0, 1000 * sizeof(info)); // обнуляем массив
 
    // ввод значений
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d.%d", &arr[i].cell, &arr[i].day, &arr[i].month);
    }
 
    // сортируем массив в порядке убывания, месяц в приоритете
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N-1; j++)
        {
            if (arr[j].month > arr[j+1].month || (arr[j].month == arr[j+1].month && arr[j].day > arr[j+1].day))
            {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        if (   (curr_month - arr[i].month == 1 && get_day(arr[i].month) - arr[i].day + curr_day > 3)
            || (curr_month - arr[i].month > 1)
            || (curr_month == arr[i].month && curr_day - arr[i].day > 3))
        {
            printf("%d\n", arr[i].cell);
        }
    }
    return 0;
}

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

Условие

В командных олимпиадах по программированию для решения предлагается не более 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;
}

Продолжаю готовиться к ЕГЭ решая задачки из задач Полякова, делюсь решением на C.

Условие

По каналу связи передается последовательность положительных целых чисел X1, X2, …; все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0.
Участок последовательности от элемента XT до элемента XT+N называется подъемом, если на этом участке каждое следующее число больше предыдущего. Высотой подъема называется разность
XT+N — XT.
Напишите эффективную программу, которая вычисляет наибольшую высоту среди всех подъемов последовательности. Если в последовательности нет ни одного подъема, программа выдает 0. Программа должна напечатать отчет по следующей форме:

Получено … чисел
Наибольшая высота подъема: …

Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел.

Решение

#include 
 
int main()
{
    int input = 0, start = 0, before = 0, k = 0;
    do
    {
        scanf("%d", &input);
        if (input == 0)
        {
            printf("Получено %d чисел\nНаибольшая высота подъёма: %d", k, before-start);
            break;
        }
        k++;
        if (input > before)
        {
            before = input;
        }
        else
        {
            start = input;
            before = input;
        }
    }
    while (true);
    return 0;
}

Условие

В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему сорвенований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запростов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6
А+В
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель

Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трёх задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1

Моё решение

#include <iostream>
#include <string.h>
#include <stdio.h>
 
struct info {
    int count;
    std::string name;
};
 
int main()
{
    int N;
    scanf("%d%*c", &N);
 
    info arr[11];
    std::string bufer;
    int found = 0,
        arr_count = 0;
 
    for (int i = 0; i < N; i++)
    {
        std::getline(std::cin, bufer);
 
        for (int j = 0; j < N; j++)
        {
            if (arr[j].name == bufer)
            {
                arr[j].count++;
                found = 1;
                break;
            }
        }
        if (found == 0)
        {
            arr[i].name = bufer;
            arr[i].count = 1;
 
            arr_count++;
        }
        found = 0;
    }
 
    for (int i = 0; i < arr_count; i++)
    {
        for (int j = 0; j < arr_count-1; j++)
        {
            if (arr[j].count < arr[j+1].count)
            {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
 
    for (int i = 0; i < arr_count; i++)
    {
        std::cout << arr[i].name << " " << arr[i].count << std::endl;
        if (i == 2)
        {
            while (arr[2].count == arr[++i].count)
            {
                std::cout << arr[i].name << " " << arr[i].count << std::endl;
            }
            break;
        }
    }
    return 0;
}