Дано число. в этом числе необходимо изменить одну цифру таким образом, чтобы новое число делилось на 3 и было бы максимально возможным. в исходном числе нужно обязательно изменить одну цифру, даже если исходное число уже делилось на 3. программа получает на вход одно длинное натуральное число. длина числа может достигать 100 цифр. программа должна вывести другое натуральное число, удовлетворяющее условиям: 1. новое число должно отличаться от данного ровно одной цифрой. 2. новое число должно делиться на 3. 3. новое число должно быть максимально возможным из всех таких чисел.

Почему-то мой ответ удалили, попробую еще раз.
1) Вводим число, как массив A[n] ; n - количество цифр в числе.
2) S = 0 ; S - сумма цифр. Если S делится на 3, то и число делится на 3.
3) Цикл по i от 1 до n
3.1) S = S + A[i]
3.2) Конец цикла по i
4) Ost = S Mod 3 ; находим остаток от деления S на 3.
4.1) Если Ost = 0, то прибавляем A[1] = A[1] + 3 до тех пор, пока A[1] <= 9
4.2) Если Ost = 1, то A[1] = A[1] + 2
4.2.1) Прибавляем A[1] = A[1] + 3 до тех пор, пока A[1] <= 9
4.3) Если Ost = 2, то A[1] = A[1] + 1
4.3.1) Прибавляем A[1] = A[1] + 3 до тех пор, пока A[1] <= 9
5) Выводим массив A[n]
6) Конец.

Модераторы, не удаляйте ответ, я его ниоткуда не списал, а сам
придумал! Если он один в один совпадает с алгоритмом на каком-то сайте, то я не виноват!