Комбинаторная задача с подсчетом посещаемости студентов

Как я могу решить эту проблему?

Вход: s - строка (n <= 100 000), в которую входят следующие буквы:

a для отсутствующего
л для позднего
p для подарка

если идущие подряд буквы «ааа», то вывод: студент не допущен к экзамену если в строке больше 4 'L', то вывод: студент не допущен к экзамену

else - студент допущен к экзамену.

ПРИМЕР:

Input: PPPPPLLLL
Output: student is not allowed to the exam

Input: PLPLPPPAAA
Output: student is not allowed to the exam

Input: APLPLLPPAP
Output: student is allowed to the exam

мне нужна комбинаторная формула. но как его применить и какой?

Re: «Мне нужна комбинаторная формула»: Почему вы так говорите?

ruakh 13.09.2018 21:49
6
1
93
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Самое простое и наивное решение - перебрать все символы в наихудшей сложности O(n) - на самом деле я не знаю лучшего решения. Итерации 100'000 - это ничто, с чем Java не может справиться.

int consecutiveA = 0;                                          // Absent counter
int consecutiveL = 0;                                          // Late counter

boolean flag = true;

for (char ch: s.toLowerCase().toCharArray()) {                 // Iterate through the chars
    if (ch == 'a') {                                           // Checks the absent
        consecutiveL = 0;
        consecutiveA++;
    } else if (ch == 'l') {                                    // Checks the late
        consecutiveA = 0;
        consecutiveL++;
    } else {                                                   // Or else reset counters
        consecutiveA = 0;
        consecutiveL = 0;
    }
    if (consecutiveA == 3 || consecutiveL == 4) {              // If the condition is met
        System.out.println("Student is not allowed to exam."); // Print it out
        flag = false;                                          // Sets the flag
        break;                                                 // And leave the cycle
    }
}

if (flag) {                                                   
    System.out.println("Student is allowed to exam.");
}

Обратите внимание, что ключевой частью также является использование ключевого слова break, которое останавливает цикл и оставляет for-cycle. Это может сэкономить время на проверке большого количества символов и избежать повторной печати "Student is not allowed to exam.".

Проблема может быть в том, что буквы будут сочетанием верхнего и нижнего регистра (мой фрагмент). Если вы уверены, что появится только один случай, String::toLowerCase() можно не указывать.

Я считаю, что здесь ошибка. Если моя запись о посещаемости - ALALA или LLALL, меня исключают из экзамена. Я не думаю, что это соответствует спецификации.

Dawood ibn Kareem 13.09.2018 22:06

@DawoodibnKareem: Хороший вопрос! Не могу поверить, что я это пропустил. Большое спасибо, исправил.

Nikolas Charalambidis 13.09.2018 22:09

Не думаю, что вы исправили ошибку. Я думаю, вы только что ввели новую ошибку.

Dawood ibn Kareem 13.09.2018 22:12

@DawoodibnKareem: Хмпф, еще одна попытка? Думаю, теперь это должно сработать.

Nikolas Charalambidis 13.09.2018 22:17

Да, так выглядит лучше. Здесь, проголосуйте за.

Dawood ibn Kareem 13.09.2018 22:18
Ответ принят как подходящий

Я читаю требование о том, чтобы более 4 Ls в любом месте строки мешали студенту сдать экзамен - они не должны быть последовательными. Кроме того, я предполагаю, что все символы в верхнем регистре.

Я думаю, что самым коротким решением для Java было бы следующее:

static boolean canTakeExam(String s)
{
    return !s.contains("AAA") && s.replaceAll("[^L]", "").length() < 4;
}

Но более эффективная реализация была бы такой:

static boolean canTakeExam(String s)
{
    for(int i=0, ca=0, cl=0; i<s.length(); i++)
    {
        char c = s.charAt(i);
        if(c == 'A')
        {
            if(++ca == 3) return false;
        }
        else
        {
            if(c == 'L' && ++cl == 4) return false;
            ca = 0;
        }
    }
    return true;
}

Другие вопросы по теме