Разбор олимпиадной задачи — Пицца

[@admin]

Условие задачи взято с сайта acmp.ru:

Пицца – любимое лакомство Васи, он постоянно покупает и с удовольствием употребляет различные сорта этого великолепного блюда. Однажды, в очередной раз, разрезая круглую пиццу на несколько частей, Вася задумался: на какое максимальное количество частей можно разрезать пиццу за N прямых разрезов?

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

Входные данные
Входной файл INPUT.TXT содержит натуральное число N – число прямых разрезов пиццы (N <= 1000).

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры:

table class=main cellpadding=2 cellspacing=1>

№INPUT.TXTOUTPUT.TXT124237

Разбор решения задачи

Опытным путем определено, что при одном разрезе пиццы максимальное число кусков равно двум, при двух разрезах – 4, при трех разрезах – 7, при четырех разрезах – 11 (смотри рисунок). Для получения максимального числа кусков пиццы, делая новый разрез, необходимо что бы он проходил через каждый предыдущий.

Под динамическим программированием понимают сведение задачи к подзадачам. Первым делом для решения задачи заполняются известные значения. В данном примере взяты число кусков при одном и двух разрезах (array [1] = 2; array [2] = 4;). Так, например, при если N равно 1 или 2, то в выходной файл записывается уже ранее известное (присвоенное) значение элемента, иначе, например, если N = 5, то (с помощью цикла for) находим первое неизвестное значение array [3], затем следующее array [4], и т.д., пока не дойдем до нужного. Неизвестные значения находятся по формуле — сумма значения предыдущего элемента и порядкового номера текущего элемента. Формула получена опытным путем. Описанный алгоритм можно изобразить в виде блок-схемы:

Исходный код реализации алгоритма на языке C#:

using System;
using System.IO;

namespace Lab2 {
  class Program {
    static void Main(string[] args) {
      var file = File.ReadAllText("input.txt");

      var n = Convert.ToInt32(file);
      var array = new int[n+1];
      array[1] = 2;
      array[2] = 4;

      if (n == 1 || n == 2) {
        File.WriteAllText("output.txt", array[n].ToString());
      }
      else {
        for (int i = 3; i < n+1; i++) {
          array[i] = array[i - 1] + i;
        }
        File.WriteAllText("output.txt", array[n].ToString());
      }
    }
  }
}

[Автор]

Сообщения