В кафе мороженое продают по три шарика и по пять шариков. Можно ли купить ровно k

шариков мороженого?

Формат входных данных
На вход программе дается одно целое число k (0≤k≤109).

Формат выходных данных
Программа должна вывести «YES», если в кафе можно купить ровно k шариков, или «NO», если нет.

ОБЯЗАТЕЛЬНО НА C++

Для решения этой задачи можно воспользоваться идеей проверки, можно ли представить число $k$ в виде суммы только множителей 3 и 5. Задача сводится к нахождению таких неотрицательных целых чисел $x$ и $y$, чтобы $3x + 5y = k$.

Подход к решению

1. Если $k$ делится на 3 или 5, то его можно легко набрать комбинацией этих шариков.
2. Если $k$ больше 5, можно попробовать перебором проверить, можно ли выбрать такое количество шариков по 3 и по 5, чтобы в сумме получилось ровно $k$.
3. Основная идея заключается в том, что мы будем вычитать по 5 из $k$ до тех пор, пока оно не станет кратным 3 (или пока не станет меньше 0, тогда решения нет).

Алгоритм

1. Начнем с $k$ и будем проверять, является ли $k$ кратным 3. Если да — выводим "YES".
2. Если нет, вычитаем из $k$ по 5 до тех пор, пока $k$ не станет кратным 3 или не станет отрицательным.
3. Если $k$ в процессе стал кратным 3 — выводим "YES". Если $k$ стал отрицательным — выводим "NO".

Пример кода на C++

cpp
#include 
using namespace std;
int main() {
    int k;
    cin >> k;
    while (k >= 0) {
        if (k % 3 == 0) {
            cout << "YES" << endl;
            return 0;
        }
        k -= 5;
    }
    cout << "NO" << endl;
    return 0;
}

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

1. Сначала считываем число $k$.
2. Далее в цикле while (k >= 0) проверяем, делится ли $k$ на 3. Если делится, то можно собрать ровно $k$ шариков, и мы выводим "YES".
3. Если $k$ не делится на 3, уменьшаем $k$ на 5 и повторяем проверку.
4. Если $k$ стал меньше нуля, значит, собрать ровно $k$ шариков невозможно, и мы выводим "NO".

Примеры работы

Вход:

7

Выход:

objectivec
NO

Вход:

10

Выход:

objectivec
YES

Вход:

12

Выход:

objectivec
YES

Обоснование правильности

Мы постепенно проверяем все возможные комбинации чисел 3 и 5 для заданного $k$. Так как $k$ ограничено, алгоритм всегда завершается за приемлемое время.