Разбор задачи «Дуэль табло»

Идея задачи

После каждого раунда в строку записывается один символ:

• A — победил Anton;
• D — победил Danik.

Нужно определить, у кого по итогам всех раундов побед больше.

Если побед у Anton больше, выводим Anton. Если побед у Danik больше, выводим Danik. Если побед поровну, выводим Friendship.

Что на самом деле требуется

Нам дана строка длины n, состоящая только из символов A и D.

Значит, задача сводится к очень простой идее:

• посчитать количество символов A;
• посчитать количество символов D;
• сравнить эти два количества.

Других действий не требуется.

Пошаговое решение

Пусть:

• anton — количество побед Anton;
• danik — количество побед Danik.

Тогда мы просто идём по строке слева направо.

Для каждого символа:

• если это A, увеличиваем anton;
• иначе увеличиваем danik.

После этого:

• если anton > danik, ответ Anton;
• если danik > anton, ответ Danik;
• иначе ответ Friendship.

Почему это корректно

Каждый символ строки соответствует ровно одному сыгранному раунду.

• Все символы A — это победы Anton.
• Все символы D — это победы Danik.

Если мы правильно подсчитали количество A и D, то мы точно знаем итоговое число побед каждого игрока.

После этого сравнение этих двух чисел напрямую даёт правильный ответ:

• больше побед у Anton — выигрывает Anton;
• больше побед у Danik — выигрывает Danik;
• побед одинаково — ничья, то есть Friendship.

Следовательно, алгоритм всегда работает правильно.

Оценка сложности

Пусть длина строки равна n.

Мы совершаем один проход по строке.

Время

O(n)

Память

O(1)

Мы используем только несколько переменных-счётчиков.

Эталонное решение на C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    int anton = 0;
    int danik = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == 'A') {
            anton++;
        } else {
            danik++;
        }
    }

    if (anton > danik) {
        cout << "Anton";
    } else if (danik > anton) {
        cout << "Danik";
    } else {
        cout << "Friendship";
    }

    return 0;
}

Эталонное решение на Python

n = int(input())
s = input()

anton = 0
danik = 0

for ch in s:
    if ch == 'A':
        anton += 1
    else:
        danik += 1

if anton > danik:
    print("Anton")
elif danik > anton:
    print("Danik")
else:
    print("Friendship")

Разбор примера

Рассмотрим строку:

ADAAAA

Подсчитаем:

• A встречается 5 раз;
• D встречается 1 раз.

Значит, Anton выиграл больше раундов, поэтому ответ:

Anton

Частые ошибки

1. Не сравнить количества после подсчёта

Иногда участник правильно считает число A и D, но забывает отдельно обработать случай равенства.

Например, если побед поровну, нужно вывести именно Friendship.

2. Считать только одного игрока и забыть про второго

Так тоже можно решить задачу, ведь число побед Danik можно получить как n - anton, но в таком случае важно не ошибиться в логике сравнения.

Для новичка безопаснее и понятнее считать оба значения отдельно.

3. Игнорировать длину строки

По условию строка имеет длину n, и обычно вход корректен. Но при написании решения важно не выходить за границы строки.

Более компактная идея

Можно считать только количество A. Тогда количество D будет равно n - anton.