e-olymp 2691. Проходной балл

Задача

Дан список учащихся с указанием годовых оценок по всем предметам. Для поступления в Школу Одаренных Детей необходимо, чтобы средний балл по всем предметам был не ниже, чем $K$. Определите, кого из перечисленных ребят могут зачислить в эту школу.

Формат входных данных

В первой строке дано число $N$ ($1 \leqslant N \leqslant 10000$), количество учащихся в списке. Каждая из следующих $N$ строк имеет вид: фамилия и имя, затем число $M_i$ ($1 \leqslant M_i \leqslant 50$) — количество предметов, которые изучал ученик, а затем годовые оценки по каждому из этих предметов.
В последней строке дано единственное число $K$ — проходной балл. Фамилия и имя — строки, состоящие не более чем из $20$ латинских букв. Все числа во входном файле натуральные и не превышают $10^9$.

Формат выходных данных

Требуется вывести список ребят, которые могут быть зачислены.

Тесты

Входные данные Выходные данные
1 3
Ivanov Ivan 2 7 9
Petrov Petr 1 7
Sidorov Sidor 2 10 8
4
Ivanov Ivan
Petrov Petr
Sidorov Sidor
2 1
Ivanov Ivan 1 6
5
Ivanov Ivan
3 4
Petrov Petr 10 1 2 3 4 5 6 7 8 9 10
Sidorov Sidor 5 8 8 8 4 4
Ivanov Ivan 0
Darienko Dasha 3 10 3 9
6
Sidorov Sidor
Darienko Dasha
4 2
Petrov Petr 10 1 2 3 4 5 6 7 8 9 10
Darienko Dasha 3 10 3 9
11
5 5
Petrov Petr 10 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000
Darienko Dasha 5 500000000 500000000 500000000 700000000 800000000
Sidorov Sidor 20 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 500000000 500000000 500000000 700000000 800000000 500000000 500000000 500000000 700000000 800000000
Ivanov Ivan 8 600000000 600000000 600000000 800000000 200000000 1000000000 300000000 300000000
Sergeev Alexandr 1 700000000
600000000
Darienko Dasha
Sergeev Alexandr

Код

Оптимальное решение:

Более структурированное решение:

Решение

Введем данные в соответствующие структуры (см. комментарии в коде), вычислим средние баллы для каждого ученика и выведем фамилии и имена всех тех и только тех, чей средний балл выше проходного.
Т. к. все исходные данные натуральные и не превышают $10^9$ используем для их ввода тип int. При этом сумма оценок может выйти за пределы типа int ($50\cdot10^9 > 2 147 483 647$), поэтому для переменной sum используем тип long. Также заметим, что среднее арифметическое натуральных чисел может быть дробным числом, но в данном случаи средний проходной балл $K$ по условию являет натуральным числом, поэтому будет уместно отбросить дробную часть при сравнении, т. е. использовать целочисленных тип данных в вычислениях.

Ссылки

  • Задача на e-olymp
  • Код оптимального решения на ideone
  • Код решения со структурами на решения со структурами на ideone
  • Засчитанное оптимальное решение на e-olymp
  • Засчитанное структурированное решение на e-olymp
  • e-olymp 8361. Робот

    Задача взята с сайта e-olymp

    Условие

    Движение робота управляется программой. Программа состоит из следующих команд:

    • [latex]S[/latex] — сделать шаг вперед
    • [latex]L[/latex] — повернуться на [latex]90°[/latex] влево
    • [latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

    Входные данные

    Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

    Выходные данные

    Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].

    Тесты

    Inputs Outputs
    1 SSLSLSLSSRSRS 5
    2 LSSSS -1
    3 LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS 15
    4 LLLLLLLL -1
    5 SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL 7

    Код

    Решение

    Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

    Ссылки

    А273. Центр тяжести системы

    Задача. Задача из сборника задач по программированию С.А.Абрамова за 2000 год.
    Система из 25 материальных точек в пространстве задана с помощью последовательности действительных чисел [latex]x_{1}, y_{1}, z_{1}, p_{1}, x_{2}, y_{2}, z_{2}, p_{2},\ldots,x_{25}, y_{25}, z_{25}, p_{25}[/latex], где [latex]x_{i}, y_{i}, z_{i}[/latex] — координаты [latex]i[/latex]-ой точки, а [latex]p_{i}[/latex] — ее вес ([latex]i=1,2,\ldots,25[/latex]). Получить координаты центра тяжести системы, а также расстояние от центра тяжести до всех точек системы.

    Входные данные:
    [latex]x, y, z, p[/latex] — координаты и вес точки.

    Выходные данные:
    [latex]sum(x,y,z)[/latex] — координаты центра тяжести системы, [latex]l[/latex] — расстояние от центра тяжести до одной из точек.

    Тесты:

    Входные данные Выходные данные
    [latex]x[/latex] [latex]y[/latex] [latex]z[/latex] [latex]p[/latex] [latex]sum[/latex] [latex](x[/latex] [latex]y[/latex] [latex]z)[/latex] [latex]l[/latex]
    2 2 1 2
    3 1 2 1
    2.33333 1.66667 1.33333 0.57735
    1.1547
    7 10 5 20
    1 0 3 1
    43 50 6 3
    0 9 0 200
    4 8 15 66
    1.84138 9.23448 3.83103 5.34452
    9.3099
    57.9704
    4.25705
    11.4424

    Код программы на С++

    Код программы на Java

    Решение
    В цикле «[latex]while[/latex]» читаем числа из входного потока и запоминаем координаты точек в векторе [latex]а[/latex], к переменной [latex]sum[/latex] прибавляем эти координаты, умноженные на [latex]p[/latex].
    Потом подсчитываем координаты центра тяжести системы и выводим эти координаты.
    В цикле «[latex]for[/latex]» берем из вектора координаты одной из точек системы, считаем расстояние от центра тяжести до одной из точек системы и выводим это расстояние.

    Ссылки
    Код в ideone.com (C++)
    Код в ideone.com (Java)
    Условие задачи (с.117)