iT邦幫忙

1

[C++] [ITSA競賽題目] 計算斜正方形個數 (Counting Tilt Squares)

題目出自ITSA競賽,解答僅供參考

題目連結: Counting Tilt Squares

解答:

#include <stdio.h>
#include <stdlib.h>

long long find(int r, int c);

int main(void)
{
	printf("r=%d, c=%d, ans=%d\n", 2, 2, find(2, 2));         
    //output n=2,    ans=0
	printf("r=%d, c=%d, ans=%d\n", 3, 3, find(3, 3));         
    //output n=3,    ans=1
	printf("r=%d, c=%d, ans=%d\n", 4, 4, find(4, 4));         
    //output n=4,    ans=6
	printf("r=%d, c=%d, ans=%d\n", 5, 5, find(5, 5));         
    //output n=5,    ans=20
	printf("r=%d, c=%d, ans=%d\n", 6, 6, find(6, 6));         
    //output n=6,    ans=50
	printf("r=%d, c=%d, ans=%d\n", 7, 7, find(7, 7));         
    //output n=7,    ans=105
	printf("r=%d, c=%d, ans=%d\n", 8, 8, find(8, 8));         
    //output n=8,    ans=196
	printf("r=%d, c=%d, ans=%d\n", 9, 9, find(9, 9));         
    //output n=9,    ans=336
	printf("r=%d, c=%d, ans=%d\n", 10, 10, find(10, 10));     
    //output n=10,   ans=540
	printf("r=%d, c=%d, ans=%d\n", 100, 100, find(100, 100)); 
    //output n=100,  ans=8004150

	system("pause");
	return 0;
}

long long find(int r, int c)
{
	long long sum = 0;
	int n = r < c ? r : c;

	for (int x = 1; x < n; x++)
	{
		for (int y = x + 1; y < n - x ; y++)
		{
			sum += (r - x - y) * (c - x - y) * 2;
		}
	}

	for (int x = 2; x <= n; x += 2)
	{
		sum += (r - x) * (c - x);
	}

	/*for (int x = 1; x < n; x++)
	{
		sum += (x + r - n) * (x + c - n);
	}*/

	return sum;
}

結語:
因為沒有正確解答可以比對,可以確定的只有前三個解,所以如果有錯誤或是有更好的解法都歡迎跟我說。


1 則留言

1
海綿寶寶
iT邦大神 1 級 ‧ 2017-09-29 08:52:47

今年的Google code jam Kickstart剛好也有類似這題的題目
提供您參考看看
改一下程式
去解 Google code jam kickstart
還可以用他驗證一下答案正確性
/images/emoticon/emoticon12.gif

fysh711426 iT邦研究生 2 級‧ 2017-09-29 12:46:26 檢舉

感謝您提供的資訊,發現解答有誤,驗證不過 XD

我要留言

立即登入留言