AOJ 0057 The Number of Area

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0057

概要

領域をn本の線で分割する。
このとき、最大の領域の数を求めよ。

解法

n = 1のとき
どこに線を引いても領域は2つになります。

n = 2のとき
先ほど引いた線と交差させることで、4つの領域を作ることができます。

n = 3のとき
図のように線を引くと、3つの領域を二分割できるため、合計7

n = 4のとき
図のように線を引くことで、4つの領域を二分割できるため、合計11
7

このように、nのとき、領域を新たにnだけ増やすことができることが分かります。
つまり、n本のとき、2+3+4+・・・・+n 個の領域が作れることになります。
なのでΣn + 1で求めることができそうです。
Σnは、公式を用いて、Σn = n * (n + 1) / 2 で計算できます。

コード

#include <iostream>
using namespace std;

int main()
{
    while (1) {
        int n;
        cin >> n;
        if (cin.eof()) break;
        cout << 1 + n * (n + 1) / 2 << endl;
    }
    return 0;
}