SRM 146 DIV2 500

問題を読む為の英単語

単語 意味
rectangular 長方形の

問題概要

入力:width, height
出力:長方形の個数

以下のような四角形が与えられる。

 __ __ __
|__|__|__|
|__|__|__|
|__|__|__|

(width:3 height:3)

与えられた四角形に存在する長方形の数を出力せよ。
ただし、正方形は除外すること。

例示

width:3 height:3
return 22

回答案

すべての長方形パターンの数を合計する。

3x3の長方形では。。。
W:入力width H:入力heightとし、例示より以下のパターンが導かれる。

width height 個数
1 2 6
1 3 3
2 1 6
2 3 2
3 1 3
3 2 2

widthとheightから個数を得る一般式
(W - width + 1) * ( H - h + 1)

回答コード(C#)

class RectangularGrid
	{
		public long countRectangles(int width, int height)
		{
			long rect_num = 0;

			for (int i = 1; i <= height; i++) {
				for (int j = 1; j <= width; j++) {
					if (i != j)
						rect_num += (width - j + 1) * (height - i + 1);
				}
			}

			return rect_num;
		}
	}
広告を非表示にする