Замок

Решить данную задачу можно следующим образом: на каждом шаге вычислять количество новых комнат на каждом уровне и добавлять это значение к некоторой переменной S. В начале положим, что S=1 (на нулевом уровне всего одна комната) и пройдем с первого уровня до K-го. На каждом шаге нас не будут интересовать все комнаты, мы будем рассматривать только те, которые не посчитали ранее, т.е. комнаты, лежащие на N-2 сторонах N-угольника. Всего комнат на i-м уровне N*i, но нас интересуют (N-2)*i+1 комнаты, их мы и будем суммировать. Таким образом, реализация решения этой задачи может выглядеть так:

  int n,k,i,s=0;

  read(n,k);

  for i=0..k{
    s = s + (n-2)*i + 1
  }  

  write(s);

Следует обратить внимание на ограничения в этой задаче. Несмотря на то, что вышеописанный алгоритм укладывается по времени, здесь могут возникнуть проблемы с переполением, если используется 4-байтовое целое для накопления суммы комнат. Поэтому рекомендуется использовать либо 8-байтовое целое, либо достаточно большой вещественный тип. Так же заметим, что здесь можно обойтись без использования цикла, т.к. несложно выделить в последовательности добавляемых новых комнат арифметическую прогрессию. Это значительно может ускорить работу программы при больших значениях.

[Обсуждение] [Все попытки] [Задача]