Редакция для Значок удачи

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Автор: montes332

Разбор задачи «Значок удачи»

Ключевая идея

Нам дано число n в виде строки. Нужно:

  1. Посчитать, сколько раз в записи числа встречаются цифры 4 и 7.
  2. Проверить, является ли полученное количество счастливым числом.

В этой задаче счастливым считается число, запись которого состоит только из цифр 4 и 7.

Если количество цифр 4 и 7 в исходном числе само является счастливым числом, нужно вывести YES, иначе NO.

Как понять задачу на примере

Пусть дано число:

40047

В нём цифры 4 и 7 встречаются 3 раза:

  • 4
  • 4
  • 7

Получаем число 3.

Но 3 не является счастливым числом, потому что его запись не состоит из цифр 4 и 7.

Ответ: NO.

Другой пример:

7747774

Все 7 цифр здесь — это 4 или 7, значит количество равно 7.

Число 7 является счастливым.

Ответ: YES.

Почему удобно читать число как строку

Число может быть очень длинным. Нам не нужны арифметические операции над самим числом. Нужно فقط пройти по его цифрам и проверить каждую.

Поэтому удобнее всего:

  • считать число как строку,
  • пройтись по всем символам,
  • увеличить счётчик, если символ равен 4 или 7.

Шаг 1. Считаем количество цифр 4 и 7

Пусть cnt — число таких цифр.

Алгоритм:

  • изначально cnt = 0,

  • для каждого символа c в строке:

    • если c == '4' или c == '7', то увеличиваем cnt на 1.

Например, для строки 4471237 получим cnt = 4.

Шаг 2. Проверяем, счастливое ли число cnt

Теперь нужно проверить само число cnt.

Когда число является счастливым

Число счастливое, если каждая его цифра — либо 4, либо 7.

Например:

  • 4 — счастливое,
  • 7 — счастливое,
  • 47 — счастливое,
  • 74 — счастливое,
  • 44 — счастливое,
  • 13 — не счастливое,
  • 0 — не счастливое.
Как это проверить

Можно брать последнюю цифру числа:

  • d = cnt % 10,
  • если d не равна 4 и не равна 7, то ответ сразу NO,
  • иначе убираем последнюю цифру: cnt /= 10.

И так продолжаем, пока число не закончится.

Важный частный случай: cnt = 0

Если в исходном числе вообще нет цифр 4 и 7, то cnt = 0.

Число 0 не является счастливым, потому что его запись не состоит из цифр 4 и 7.

Значит в этом случае нужно вывести NO.

Полный алгоритм

  1. Считать число как строку s.
  2. Посчитать количество символов 4 и 7. Сохранить в cnt.
  3. Если cnt == 0, вывести NO.

  4. Иначе проверить все цифры числа cnt:

    • пока cnt > 0:

      • взять cnt % 10,
      • если цифра не 4 и не 7, вывести NO,
      • иначе отбросить последнюю цифру.
  5. Если все цифры подошли, вывести YES.

Почему алгоритм корректен

Докажем это по шагам.

1. После первого прохода cnt равно количеству цифр 4 и 7 в числе

Мы просматриваем каждый символ строки ровно один раз.

  • Если символ равен 4 или 7, увеличиваем счётчик.
  • Иначе не изменяем его.

Значит в конце cnt действительно равно числу всех цифр 4 и 7 во входном числе.

2. Второй этап правильно проверяет, является ли cnt счастливым числом

На каждом шаге мы смотрим на последнюю цифру числа cnt.

  • Если последняя цифра не равна 4 и не равна 7, то число уже не может быть счастливым.
  • Если равна, то можно удалить её и продолжить проверку оставшейся части.

Так как мы последовательно проверяем все цифры числа cnt, то:

  • если все цифры — только 4 и 7, мы получим YES,
  • если встретится хотя бы одна другая цифра, получим NO.

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

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

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

По времени
  • Подсчёт цифр 4 и 7: O(n).
  • Проверка числа cnt: O(log cnt).

Но cnt <= n, поэтому вторая часть очень маленькая по сравнению с первой.

Итоговая сложность:

O(n).

По памяти

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

Итог:

O(1) дополнительной памяти, если не считать входную строку.

Типичные ошибки

Ошибка 1. Считать счастливым число 0

Это неверно. Если цифр 4 и 7 нет совсем, то cnt = 0, а 0 не является счастливым числом.

Ошибка 2. Проверять исходное число вместо количества

По условию нужно проверить не само число n, а количество цифр 4 и 7 в нём.

Ошибка 3. Считывать число в тип int или long long

В задаче удобнее и надёжнее читать вход как строку, потому что нас интересуют именно цифры.

Ошибка 4. Забыть, что число может быть длинным

Если работать со строкой, эта проблема исчезает.

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

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

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

    int cnt = 0;
    for (char c : s) {
        if (c == '4' || c == '7') {
            cnt++;
        }
    }

    if (cnt == 0) {
        cout << "NO\n";
        return 0;
    }

    while (cnt > 0) {
        int d = cnt % 10;
        if (d != 4 && d != 7) {
            cout << "NO\n";
            return 0;
        }
        cnt /= 10;
    }

    cout << "YES\n";
    return 0;
}

Разбор решения на C++

Считывание
string s;
cin >> s;

Считываем число как строку.

Подсчёт нужных цифр
int cnt = 0;
for (char c : s) {
    if (c == '4' || c == '7') {
        cnt++;
    }
}

Если очередной символ равен 4 или 7, увеличиваем счётчик.

Обработка случая cnt = 0
if (cnt == 0) {
    cout << "NO\n";
    return 0;
}

Если нужных цифр нет совсем, ответ сразу NO.

Проверка числа cnt
while (cnt > 0) {
    int d = cnt % 10;
    if (d != 4 && d != 7) {
        cout << "NO\n";
        return 0;
    }
    cnt /= 10;
}

По одной проверяем все цифры числа cnt.

Если встретилась цифра, отличная от 4 и 7, сразу выводим NO.

Если цикл закончился, значит все цифры подходят.

Решение на Python

s = input().strip()

cnt = 0
for c in s:
    if c == '4' or c == '7':
        cnt += 1

if cnt == 0:
    print("NO")
else:
    ok = True
    while cnt > 0:
        d = cnt % 10
        if d != 4 and d != 7:
            ok = False
            break
        cnt //= 10

    if ok:
        print("YES")
    else:
        print("NO")

Разбор решения на Python

Подсчёт количества
cnt = 0
for c in s:
    if c == '4' or c == '7':
        cnt += 1

Это полностью повторяет идею решения на C++.

Проверка счастливости числа cnt
while cnt > 0:
    d = cnt % 10
    if d != 4 and d != 7:
        ok = False
        break
    cnt //= 10

Берём последнюю цифру числа и проверяем её.

Более короткая идея проверки в Python

В Python можно было бы преобразовать cnt в строку и проверить её символы. Но для учебного разбора полезнее показать именно арифметическую проверку цифр, потому что она универсальна и часто встречается в задачах.

Небольшие тесты для самопроверки

Тест 1

Вход:

40047

Цифры 4 и 7 встречаются 3 раза.

3 — не счастливое число.

Ответ:

NO
Тест 2

Вход:

7747774

Цифры 4 и 7 встречаются 7 раз.

7 — счастливое число.

Ответ:

YES
Тест 3

Вход:

123456

Цифры 4 и 7 встречаются 1 раз.

1 — не счастливое число.

Ответ:

NO
Тест 4

Вход:

4477

Цифры 4 и 7 встречаются 4 раза.

4 — счастливое число.

Ответ:

YES

Итог

В задаче используется очень простая, но важная идея из базового программирования:

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

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

Главная мысль решения:

  • считаем, сколько в числе цифр 4 и 7,
  • проверяем, состоит ли это количество только из цифр 4 и 7.

Если да — YES, иначе — NO.

Комментарии

Еще нет ни одного комментария.