Задача на признак делимости на 11. C++

Question

Для делимости числа на 11 необходимо, чтобы разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, делилась на 11.

Требуется написать программу, которая проверит делимость заданного числа на 11.

Входные данные

Входной файл INPUT.TXT содержит одно натуральное число N, делимость которого надо проверить (1 ≤ N ≤ 10^10000).

Выходные данные

В выходной файл OUTPUT.TXT выведите “YES”, если число делится на 11, или “NO” иначе.

Сразу оговорюсь. Сайт позволяет делать обычный ввод и вывод без использования файловых потоков.

Решение:

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

int main()
{
    long long even = 0, odd = 0;
    string inp;
    cin >> inp;
    int size = inp.size();
    for (size_t i = 0; i < size; i += 2)
        even += inp[i] - '0';
    for (size_t i = 1; i < size; i += 2)
        odd += inp[i] - '0';
    cout << (even - odd % 11 ? "NO" : "YES");
}

На одном из тестов программа проваливается (тесты мне не видны). И в действительности мне даже не понятно, почему моя программа проваливается.

Переполнение?

хорошо рассмотрим число 10^1000 - 1, это число состоит из 9999 девяток. на каждую переменную odd и even идет примерно поровну распределение девяток. но в случае нечетности количества цифр odd перевешивает. значит в крайнем случае odd = 9*(9998/2 + 1) = 45000. Я от страха поставил long long, но очевидно мне это не помогло.

Переполнение переменных цикла?

size_t range = 2^16 - 1, а по факту мне 1000 уже достаточно, потому что длина строки до 10^1000

Может надо было условие odd - even, а не even - odd?

Мое условие требует ненулевой остаток и в этом случае мое условие верно. Даже если остаток и будет отрицателен это никак не повлияет на работу.

И вообще я полностью убежден в верности своего решения. От отчаяния я решил проверить ее работоспособность на числах до 10e7. И все срабатывало вполне адекватно.

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

Второе решение:

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

int main()
{
    long long even = 0, odd = 0;
    char x, i = 0;
    while ((x = cin.get()) != EOF)
    {
        if (i % 2 == 0)
            even += x - '0';
        else
            odd += x - '0';
        i++;
    }
    cout << (even - odd % 11 == 0 ? "YES" : "NO");
}

Вероятно я упускаю какой-то частный случай. Но вторая программа точно работает как-то криво. Объясните мне пожалуйста, что я упускаю и что я сделал не так в своих программах.

Answer 1

Если даже не смотреть внимательно, то:

Ваша программа вводит символы, а эти символы могут быть любыми, в том числе в начале могут быть нули или может быть введен не цифра. Поэтому придется проверять является ли первый символ больше или равно символа '1' и меньше или равно '9' или знаком числа '+'(тогда его нужно пропускать) а другие цифры могут быть еще и нулем.

Второе: Вы используете консольное приложение, где на одной строке могут не вмещаться столько символов (например если хотим ввести число больше чем 10^100 ), а вы практически читаете только первую строку(до символа '\n'), а значит не всю цифру, а во втором примере читаете '\n' тоже, а это еще хуже.

Третье:

Вы два раза проходите по всем символам строки, когда за один раз можно все делать:

Answer 2

Все гораздо проще. Вам дают строку с завершающим переводом строки... cin.get() его читает.

Вот решение которое проходит тесты:

#include <iostream>
int s;
char a;

int main(){
    while(std::cin>>a)
    {
        s+=a;
        s-=std::cin>>a?a:'0';
    }
    std::cout << (s%11 ? "NO":"YES");
}

Кстати, как видите, хранить отдельно две суммы ни к чему.

БЛОГ НА HUSL

Задача на признак делимости на 11. C++

Ответы (2 шт):