Как решить олимпиадную задачу по информатике

Question

Текст задания (он ужасно длинный, ивиняюсь):
Завтра студенты первого курса пойдут сдавать математический анализ. Экзамен будет принимать профессор Ильдар.

Экзамен будет проходить по старинке: студенты по одному подходят к профессору, отвечают на заданные им вопросы и получают свои оценки. Результат экзамена сильно зависит от настроения профессора Ильдара: если у него плохое настроение, то не важно, насколько хорошо вы подготовились, – он отправит вас на пересдачу.

Пусть настроение профессора в некоторый момент времени равно x. После ответов отличника настроение профессора повышается и становится равно x+1. После ответов хорошиста настроение профессора не меняется. А если ответы явно не тянут на оценку 4, то профессор ставит 3 и его настроение падает до x-1.

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

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

Вы можете купить шоколадку (а лучше не одну) и подарить её профессору сегодня вечером. Каждая подаренная профессору шоколадка повышает его настроение на 1. Что профессор делает с шоколадками, никому не известно.

Какое минимальное количество шоколадок вам надо сегодня подарить профессору, чтобы завтра все студенты сдали экзамен?

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

В первой строке вводятся два целых числа n и k (1≤n≤1000,−10⁹≤k≤10⁹) – количество студентов в вашей группе и настроение профессора сегодня вечером (настроение профессора до начала экзамена может измениться только благодаря вам).

Во второй строке вводится строка из символов a_i (a_i ∈{A,B,C}). Эта строка описывает порядок, в котором студенты будут подходить к профессору. Каждый студент описывается одним символом. Символом A обозначается отличник, символом B – хорошист, символом C – троечник или неподготовившийся к экзамену студент.

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

n, k = [int(i) for i in input().split()]

S = input()

mood = k
worse_mood = mood
for i in range(len(S)):
    if S[i] == 'C':
        mood -= 1
    elif S[i] == 'A':
        mood += 1

    if mood < worse_mood:
        worse_mood = mood


if worse_mood < 0:
    print(abs(worse_mood))
else:
    print(0)

Answer 1

Вообще в целом, похоже, что код делает именно то, что нужно, но ответ дает не на тот вопрос. Ведь вопрос в том, сколько нужно шоколадок дать профессору, а не ответить какое будет минимальное плохое настроение. в ответе вместо вывода abs(worse_mood) Вам нужно вывести сколько шоколадок потребуется, что бы превысить это значение(в тексте задания сказано, что на 11, а не на 1). Так же подправил бы, что worse_mood = mood на старте, а не какой то большой константе

Answer 2

Вы не рассматриваете граничный случай.
Последний студент может получить свою тройку, если настроение 0.
Минимальное настроение = -1, но и студентов больше не осталось.
Т.е. solve(k=-1, S='C') -> 1, а не 2

Для обработки этого кейса достаточно добавить проверку:

  if S[i] == 'C':
    if i < len(S)-1: # последний плохиш не ухудшает настроение)
      mood -= 1

Или предварительно уменьшить range:

for i in range(n-1):
# for i in range(len(S)-1):

Answer 3

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

Дальше каждый отличник улучшает настроение, каждый троечник ухудшает. Если настроение упало ниже нуля, добавляем одну шоколадку.

Последнего студента не рассматриваем, он сдал в любом случае, а после него хоть потоп.

n, k = map(int, input().split())

choco = -1 * min(k, 0)
k = max(k, 0)

for s in input()[:-1]:
    k += s == "A" or s == "C" and -1
    choco += k < 0
    k = max(k, 0)

print(choco)

БЛОГ НА HUSL

Как решить олимпиадную задачу по информатике

Ответы (3 шт):