Разбор задачи «Сигнальная вывеска»

Идея задачи

Дано слово, состоящее из английских букв в верхнем и нижнем регистре.

Нужно привести всё слово к одному регистру:

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

Выбор делается по простому правилу:

• если заглавных букв строго больше, чем строчных, то всё слово переводим в верхний регистр;
• иначе переводим всё слово в нижний регистр.

Иными словами, нам нужно понять, каких букв в слове больше.

Как наблюдать за задачей

Нас не просят минимизировать число операций напрямую, но правило фактически именно это и делает:

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

Значит, задача сводится к двум действиям:

1. Посчитать количество заглавных и строчных букв.
2. В зависимости от сравнения перевести всю строку в нужный регистр.

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

Пусть дана строка s.

Шаг 1. Считаем буквы двух типов

Проходим по всем символам строки:

• если буква заглавная, увеличиваем upper;
• иначе увеличиваем lower.

Так как по условию строка состоит только из английских букв, других вариантов нет.

Шаг 2. Выбираем итоговый регистр

• если upper > lower, делаем всю строку заглавной;
• иначе делаем всю строку строчной.

Обрати внимание на случай равенства:

• если upper == lower, по условию нужно выбрать нижний регистр.

Разберём на примерах

Пример 1

Строка: HoUse

Подсчитаем:

• заглавные: H, U — 2;
• строчные: o, s, e — 3.

Строчных больше, значит ответ:

house

Пример 2

Строка: ViP

Подсчитаем:

• заглавные: V, P — 2;
• строчные: i — 1.

Заглавных больше, значит ответ:

VIP

Пример 3

Строка: maTRIx

Подсчитаем:

• заглавные: T, R, I — 3;
• строчные: m, a, x — 3.

Количество одинаковое, а значит по условию нужно перевести всё в нижний регистр:

matrix

Почему решение верное

Докажем, что описанный алгоритм всегда даёт правильный ответ.

Рассмотрим слово длины n.

Пусть:

• upper — число заглавных букв,
• lower — число строчных букв.

Очевидно, что upper + lower = n.

Есть только два допустимых итоговых варианта:

1. сделать все буквы заглавными;
2. сделать все буквы строчными.

Если делать все буквы заглавными, то нужно изменить все строчные буквы, то есть lower штук.

Если делать все буквы строчными, то нужно изменить все заглавные буквы, то есть upper штук.

Тогда:

• если upper > lower, то изменений меньше при переводе в верхний регистр;
• если upper < lower, то изменений меньше при переводе в нижний регистр;
• если upper == lower, оба варианта требуют одинаковое число изменений, и по условию нужно выбрать нижний регистр.

Именно это и делает наш алгоритм.

Следовательно, он всегда выдаёт правильный ответ.

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

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

Мы один раз проходим по строке, чтобы посчитать количество букв каждого регистра, и ещё один раз — чтобы при необходимости преобразовать строку.

Итого:

• время: O(n);
• память: O(1), если не считать хранение самой строки.

Возможные ошибки

1. Неправильно обработать равенство

Некоторые по привычке пишут:

• если заглавных не меньше, то сделать всё заглавным.

Это ошибка. По условию при равенстве нужно делать всё строчным.

То есть сравнение должно быть именно таким:

• если upper > lower, то верхний регистр;
• иначе нижний.

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

Можно считать только заглавные, а строчные получать как n - upper, это тоже корректно. Но для новичка чаще понятнее держать два отдельных счётчика.

3. Забыть, что строка состоит только из букв

В этой задаче нет цифр, пробелов и других символов, поэтому ветка else спокойно означает, что символ — строчная буква.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

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

    int upper = 0;
    int lower = 0;

    for (char c : s) {
        if (isupper(c)) {
            upper++;
        } else {
            lower++;
        }
    }

    if (upper > lower) {
        for (char &c : s) {
            c = toupper(c);
        }
    } else {
        for (char &c : s) {
            c = tolower(c);
        }
    }

    cout << s << '\n';
    return 0;
}

Пояснение к коду на C++

• isupper(c) проверяет, является ли символ заглавной буквой.
• toupper(c) переводит символ в верхний регистр.
• tolower(c) переводит символ в нижний регистр.
• Во втором проходе мы изменяем саму строку s, а затем выводим её.

Решение на Python

s = input()

upper = 0
lower = 0

for c in s:
    if c.isupper():
        upper += 1
    else:
        lower += 1

if upper > lower:
    print(s.upper())
else:
    print(s.lower())

Пояснение к коду на Python

• c.isupper() проверяет, заглавная ли буква.
• s.upper() возвращает новую строку, где все буквы заглавные.
• s.lower() возвращает новую строку, где все буквы строчные.

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

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

Можно считать только число заглавных букв, а число строчных находить как:

lower = len(s) - upper

Это тоже полностью корректно.

Например, на Python:

s = input()
upper = 0

for c in s:
    if c.isupper():
        upper += 1

if upper > len(s) - upper:
    print(s.upper())
else:
    print(s.lower())