20120104

ACM 11044 Searching for Nessy

很有趣的題目,
之前玩解謎遊戲有解到。
其實直接去填圖就是最佳解。
正規的解法:ceil(長 / 3) * ceil(寬 / 3)。
所以此題的解應該是ceil((h - 2) / 3) * ceil((w - 2) / 3),
不過x / 3與ceil((x - 2) / 3)的解相同。
所以(h / 3) * (w / 3)就是答案。

/* ACM 11044 Searching for Nessy
 * mythnc
 * 2012/01/04 16:59:37   
 * version2: optimization v1
 * run time: 0.008
 */
#include <stdio.h>

int main(void)
{
    int m, n;

    scanf("%*d");
    while (scanf("%d %d", &m, &n) == 2)
        printf("%d\n", (m / 3) * (n / 3));

    return 0;
}

沒有留言: