Понять условие задачи на вечную зиму

Сначала немного упростим. Дана последовательность измерений снега каждый день - нужно по ней определить, сколько снега выпало за каждый день. Очевидно, что это разность двух соседних элементов последовательности. Ну и за первый день - её первый элемент, поскольку сказано, что до этого снега не было.

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

А теперь добавляем то, что некоторые элементы неизвестны. Рассмотрим часть последовательности, которую мы уже восстановили и сейчас смотрим на -1: она возрастающая (иначе мы бы уже раньше сказали NO) и мы хотим продолжить её так, чтобы она осталась возрастающей, причём, чтобы не испортить хвост (добавление оставшейся части последовательности), если это вообще возможно. Числа целые, а значит минимальное, что мы можем добавить - это 1. С одной стороны оно обеспечивает возрастающую последовательность, а с другой стороны у нас нет никакой возможности ужаться, если потом из-за этой единицы что-то пойдёт не так. Она может быть не единственным решением, но если есть другое решение, то она - тоже. Так что заменяем все -1 на предыдущий плюс 1 (если нет первого, то предыдущий 0 и получаем 1) и получаем последовательность замеров. Единственное требование, которое мы проверяем, - она возрастает на каждом шаге.

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

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

tio.run

a = [1, 3, -1, 10, -1]

if a[0] == -1:
  a[0] = 1

for i in range(1, len(a)):
  if a[i] == -1:
    a[i] = a[i-1] + 1
  elif a[i] <= a[i-1]:
    print("No")
    exit(0)

for i in range(1, len(a)):
  a[i] -= a[i-1]

print("Yes")
print(" ".join(map(str, a)))

Давайте я попробую «разложить всё по полочкам».

По поводу объяснения задачи

На планете началась вечная зима, теперь выпавший снег совсем перестал таять. Каждый день выпадает несколько миллиметров снега…

Очевидно, что последовательность чисел не может быть уменьшающейся, а также «стагнирующей».

Это значит, что следующее число в последовательности должно быть больше предыдущего. Но это, как мне кажется, очевидно.

2.

Достоверно известно, что перед первым днем замеров снега не было вовсе...

Последовательность не может начинаться с «0». А, следовательно, сама последовательность не может содержать «0».

3.

Среди всех вариантов ответа вас устроит любой, главное, чтобы он согласовывался с сохранившимися данными из испорченного журнала.

Это значит, что достоверность данных не интересует «заказчиков», а интересует согласованность с «планом»! (В данном случае «план» — условия задачи: постоянный рост уровня снега).

Обновлено: по поводу противоречивости примера № 1

Важно обратить внимание на то, что итоговая версия алгоритма не будет соответствовать примеру 1: мы поговорили с @Qwertiy (и другими людьми в комментариях под моим ответом), и пришли к выводу, что этот пример дан как просто пример (он не будет соответствовать итоговому алгоритму).

Моё мнение:

Пример 1 не должен был даваться авторами задания, потому что по нему видно, что растёт не только уровень снега в мм, но и сама динамика выпадения снега (с каждым днём снега выпадает всё больше).

По-другому объяснить эту последовательность в выходных данных:

1 2 3 4 5

Я не могу, потому что по ней подходят только следующие данные по дням:

1 (+1) 3 (+2) 6 (+3) 10 (+4) 15 (+5)

Которые не воспроизводятся по логичному алгоритму (+1 к предыдущему числу для неизвестного числа).

Пример 1 — ломает принцип работы изначального алгоритма.

Зачем это было сделано — непонятно. Для того, чтобы запутать? Для того, чтобы нельзя было изначально догадаться о том, что неизвестное число — это предыдущее число +1? А может быть этот пример просто был составлен «на бум», и в этом нет особого смысла (скорее всего этот вариант)? Оставлю эти догадки на ваше усмотрение...

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

Он не соответствует примеру 1 задачи, но я исхожу из того, что было обусловлено, что подойдёт любой алгоритм (пункт 3).

По поводу примера № 1 — почему именно так

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

День 1: 1 — ОК

День 2: 3 — ОК

День 3: -1 — Найдём и проверим

День 4: 10 — ОК

День 5: -1 — Найдём и проверим

Спрашиваем себя логически: «Могло ли за третий день выпасть столько снега, чтобы с 3 мм уровень снега повысился до 10 мм»? Отвечаем: «Да, разумеется»!

Вы можете задаться вопросом: «Что это за число»? А я отвечу: «А это важно с точки зрения логики, а не алгоритма? Не думаю». Я напоминаю, нас не интересует достоверность, нас интересует верность плану!

Но поскольку нам нужно конкретное правило для составления алгоритма, то самым простым решением будет прибавить «1» к предыдущему числу»:

(3 + 1 = 4)

И это не противоречит никакому из пунктов условия задачи, которые нам поставили вначале!

На финальный день проверки нам не нужно вычислять само число (с точки зрения логики), нам нужно лишь понять, чему оно не может быть. А оно не может быть меньше или равно 10 (значит, оно > 10). Но вычисление нам всё равно понадобится: значит, как и ранее прибавляем «1» к предыдущему значению.

Тогда восстановленный отчёт будет таким:

День 1: 1 — ОК [= 0 + 1]

День 2: 3 — ОК [= 1 + 2]

День 3: 4 — ОК (восстановили по алгоритму) [= 3 + 1]

День 4: 10 — ОК [= 6 + 4]

День 5: 11 — ОК (восстановили по алгоритму) [= 10 + 1]

А по выводу от нас требуется вывести динамику выпадения снега по дням:

День 1: 1

День 2: 2

День 3: 1

День 4: 6

День 5: 1

То есть проверку мы осуществляем пошагово.

По поводу примера № 2 и почему именно так

Позволю себе краткость. Записи в журнале неверны, ведь кол-во осадков в третий день снизилось (как же оно снизится, если снег не тает ?). Значит, нам врут (ах они @#!%$).

Алгоритм по задаче

Я написал его на C#:

class Program
{
    private static void Main()
    {
        while (true)
        {
            CheckReport();

            Console.WriteLine("\nНажмите любую клавишу для продолжения работы. Нажмите \"ESC\" для выхода из программы.");

            if (Console.ReadKey(true).Key == ConsoleKey.Escape)
            {
                break;
            }

            else
            {
                Console.WriteLine("Подготовка работы с новым журналом...\n");
            }
        }
    }

    /// <summary>
    /// Основной метод проверки журнала
    /// </summary>
    private static void CheckReport()
    {
        try
        {
            Console.WriteLine("Введите количество замеряемых дней:");
            int Days = int.Parse(Console.ReadLine());

            // не может быть 0 дней отчёта
            if (Days <= 0)
            {
                Console.WriteLine("\nNO");

                return;
            }

            Console.WriteLine($"\nВведите данные журнала за {Days} дней:");
            int[] OriginalJournal = Console.ReadLine().Split().Select(int.Parse).ToArray();

            // кол-во измерений не может отличаться
            // от кол-ва дней
            if (OriginalJournal.Length != Days)
            {
                Console.WriteLine("\nNO");

                return;
            }

            // в отчёте не могут содержаться
            // негативные числа (кроме "-1") и число "0"
            // (пункт "2" задачи)
            if (OriginalJournal.Any(x => x < 0 && x != -1 || x == 0))
            {
                Console.WriteLine("\nNO");

                return;
            }

            RecoverJournal(in OriginalJournal, out int[] RecoveryJournal);

            bool IsJournalValid = IsJournalCorrect(RecoveryJournal);

            if (IsJournalValid)
            {
                Console.WriteLine("\nYES");
                DetailRecord(RecoveryJournal);
            }

            else
            {
                Console.WriteLine("\nNO");
            }
        }

        catch
        {
            Console.WriteLine("\nПохоже, что были данные были введены в неверном формате. Попробуйте загрузить отчёт ещё раз.");
        }
    }

    /// <summary>
    /// Метод восстановления журнала
    /// </summary>
    /// <param name="OriginalJournal">Оригинальный журнал с данными</param>
    /// <param name="RecoveryJournal">Восстановленный журнал с данными</param>
    private static void RecoverJournal(in int[] OriginalJournal, out int[] RecoveryJournal)
    {
        RecoveryJournal = new int[OriginalJournal.Length];

        for (int i = 0; i < OriginalJournal.Length; i++)
        {
            if (OriginalJournal[i] != -1)
            {
                RecoveryJournal[i] = OriginalJournal[i]; // данные не повреждены — оставляем
            }

            else
            {
                // если день первый, то лучше начать с минимума,
                // т. к. будет больше манёвров для "правдивых" данных
                // (если мы на стороне метеорологов, конечно)
                if (i == 0)
                {
                    RecoveryJournal[i] = 1;
                }

                // иначе прибавляем единицу к значению
                // выпавшего снега за предыдущий день
                else
                {
                    RecoveryJournal[i] = RecoveryJournal[i - 1] + 1;
                }
            }
        }
    }

    /// <summary>
    /// Проверка корректности восстановленного журнала
    /// </summary>
    /// <param name="RecoveryJournal">Проверяемый восстановленный журнал</param>
    /// <returns>Правдивость данных восстановленного журнала</returns>
    private static bool IsJournalCorrect(in int[] RecoveryJournal)
    {
        bool IsValid = true;

        for (int i = 1; i < RecoveryJournal.Length; i++)
        {
            // основная магия проверки тут :)
            // (сверяем с пунктом "1" задачи)
            if (RecoveryJournal[i] <= RecoveryJournal[i - 1])
            {
                IsValid = false;

                break;
            }
        }

        return IsValid;
    }

    /// <summary>
    /// Метод вывода данных о динамике выпадения снега по дням
    /// </summary>
    /// <param name="RecoveryJournal">Восстановленный журнал с данными</param>
    private static void DetailRecord(in int[] RecoveryJournal)
    {
        int[] DetailJournal = new int[RecoveryJournal.Length];

        for (int i = 0; i < RecoveryJournal.Length; i++)
        {
            if (i == 0)
            {
                DetailJournal[i] = RecoveryJournal[i];
            }

            else
            {
                DetailJournal[i] = RecoveryJournal[i] - RecoveryJournal[i - 1];
            }
        }

        Console.WriteLine(string.Join(" ", DetailJournal));
    }
}

Надеюсь, что я объяснил всё максимально доступно ?