2238. Кто получит “автомат”?

В Алтайском государственном техническом университете студенты получают оценки по стобалльной шкале, то есть от нуля до ста. Преподаватель Павел Иванович пообещал студентам, что те из них, у кого семестровый рейтинг будет выше среднего по группе, получит “автомат”. А староста группы Петька Петров еще пообещал каждому “автоматчику” по шоколадке (у Петьки папа занимается поставками шоколада в магазины, и Петька с ним договорился о спонсорской помощи).

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

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

Вход. Первая строка содержит количество студентов n (n ≤ 10000) в группе. Будем считать, что почин Петиного отца будет взят на вооружение всем прогрессивным человечеством, предприниматели будут сражаться за право дать приз студентам не только одной группы, но и всего университета, поэтому число студентов велико.

Следующие строки содержат n целых чисел – рейтинги студентов. Числа разделены пробелами и, может быть, символами перевода строки.

Выход. Выведите количество шоколадок, которое Петя должен принести в университет.

Пример входа	Пример выхода
4 10 20 30 40	2

РЕШЕНИЕ

линейный массив

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

Средний рейтинг по группе найдем как сумму s рейтингов студентов, деленную на их количество n. Далее находим количество студентов, у кого рейтинг будет выше среднего по группе s / n.

Пример

Сумма рейтингов студентов равна s = 10 + 20 + 30 + 40 = 100.

Средний рейтинг по группе равен s / n = 100 / 4 = 25.

Имеются два студента с рейтингом, выше среднего. Их рейтинги равны 30 и 40.

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

Объявим входной массив.

#define MAX 10010

int m[MAX];

Читаем входные данные. Количество студентов равно n.

scanf("%d", &n);

s = res = 0;

В переменной s находим сумму рейтингов студентов.

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

{

scanf("%d", &m[i]);

s += m[i];

}

Найдем количество студентов res, у кого рейтинг m[i] будет выше среднего по группе s / n. Неравенство s / n < m[i] перепишем в виде s < m[i] * n.

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

if (s < m[i] * n) res++; // s / n < m[i]

Выводим ответ.

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

Java реализация

import java.util.*;

class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

int s = 0, res = 0;

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

{

m[i] = con.nextInt();

s += m[i];

}

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

if (s < m[i] * n) res++; // s / n < m[i]

System.out.println(res);

con.close();

}

}

Python реализация

n = int(input())

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

s = res = 0

for i in range(n):

s = s + lst[i]

for i in range(n):

if s < lst[i] * n: res += 1 # s / n < m[i]

print(res)