Baek Junアルゴリズム14660号:ピザ(Small)

リンク

( https://www.acmicpc.net/problem/14606 )

質問する

甲はアジア大学の学生です.甲は八達官の1階で学科の開講大会を準備している.甲はピザをN皿注文した.テーブルにはピザがN皿いっぱい積まれている.甲はこの高さNのピザタワーを、高さ1のピザタワーに分けるべきです.甲はこのことをしたくない.しかし、格言があります.
「避けられないなら、楽しもう!」ロバート・エリオット
格言に従って、甲は自分で游ぶことを决めて、楽しく事を解决します.だから次のゲームをすることにしました
ゲームが始まる前に、テーブルにはN枚のピザ板が塔に積まれていた.ゲームが始まると、甲はテーブルの上のピザタワーの中から一つを選ぶ.そして選んだピザタワーを二つのピザタワーに分けます.この時、甲は2つの別々のピザ塔の高さの平方のように楽しく感じた.すなわち、甲が選択したピザタワーの高さがAであり、甲がこのピザタワーを高さBのピザタワーと高さCのピザタワーに分離すれば、甲はこの時、B*Cと同じ楽しさを感じることになる.しかし、高さ1のピザタワーは分離されなくなった.甲はピザタワーを分離し続けた.このゲームをしている間にテーブルの上に分離可能なピザタワーがなければ、甲の開講大会の準備は終わります.
甲は突然知りたくて、一人で游ぶのがどんなに楽しいですか.甲に注文したピザの枚数Nの場合、甲が自分で遊ぶことで得た楽しみの合計の最低価格を見つけてください.

<高さ8のピザタワーを2つの高さ4のピザタワーに分離する過程>

入力

第1行は、ピザプレートの個数を表す正の整数N(1≦N≦10)を与える.

しゅつりょく

甲が得られる快楽総和の最値を1行に印刷する.

入力と出力の例

解法

...ああ...初めて解いた時はルールが見つからなかったので、どうせNの範囲も狭いので、1~10の間に包んで、答えを出しましたが...そうではないと思いますが、接着剤を見てみると、点火式はn*(n-1)/2...という結果になりました.
1~10を求めた時に何度かどこかで見たことがあるような…?考えてみたが、やはり点火式を導き出せなかった.
なんだ.どうすればいいの...ずっとほどいて

改善されたプールコード(C++)

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <algorithm> 
#include <math.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define max 11
#define INF 1e9
using namespace std;

int main(){
  int n;
  cin >> n;
  printf("%d",(n*(n - 1)) / 2);
  return 0;
}