iT邦幫忙

3

[Google Code Jam] C++ Go, Gopher! 互動題目

前言

這題題目實在有夠長,光題目我就看了非常久,題目看不懂真的很慘連做都沒辦法做(翻譯我也看不懂,中英文都很差真的很慘..),還好最後多虧這位大大的文章和測試工具的幫忙才了解題目....。
原題目

題目

Code Jam團隊買了一個果園,他剛好是一個二維矩陣1000行和1000列,計畫用來種植各種樹木。

  • 我們至少要有一個準備好的位置。
  • 所有準備好的位置都必須組成一個對齊的矩形,矩形中每個位置也必須準備好。

注意,上述還包括已準備好的位置不能超過該矩形之外。
例如(*為準備好位置, .為未準備好位置):

當A = 11,如圖一雖然他面積是11但矩形內有一個未準備,那這個果園就不算是準備好,必須和圖二一樣整個矩形都準備好。

*****
*.***
*****
圖一
*****
*****
*****
圖二

當A = 6,如圖三很明顯未準備好,圖四雖然有6塊但它不是一個完整的矩形,圖五雖然有一個完整矩形但它周圍多出一塊已準備好,所以這些果園都未準備好。

**
.*
**
圖三
.**
*.*
.**
圖四
.**
***
.**
圖五

我們借用了Go gopher,指定位置來幫助我們,但我們還沒有完善的開發,目前只可以在指定位置為中心3X3區塊中隨機準備好一個位置。
我們只能使用1000次來完成我們的果園。

輸入輸出

這題是互動式題目,官方提供了下載Python腳本來進行測試,輸入整數T表示測試數量,A為矩形面積,最多只能互動1000次。
你的程式必須輸出i和j位置(中心位置),並介於2~999之間,如果格式錯誤將會讀取到-1 -1已準備好位置。為了要回應請將程式使用標準輸入讀取回傳已準備好數值。
當你完成矩形則會接收到0 0位置,然後就停止輸入輸出,若程式還在等待則會判斷為超時。

範圍

1 ≤ T ≤ 20.
記憶體: 1 GB.

測試1:
A = 20.
時間限制: 20 秒.

測試2:
A = 200.
時間限制: 60 秒.

範例

t = readline_int() // 讀取T測資數量
a = readline_int() // 讀取A面積
printline 10 10 to stdout // 輸出10 10位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置10 11
printline 10 10 to stdout // 輸出10 10位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置10 10
printline 10 12 to stdout // 輸出10 12位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置10 11
printline 10 10 to stdout // 輸出10 10位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置11 10
printline 11 10 to stdout // 輸出11 10位置
flush stdout
x, y = readline_two_int() // 讀取到0 0,已完成面積矩形

解析

當下看到題目非常之長,最後才發現其實就只是要你在1000次內把指定面積矩形做出來就好,測試固定20和200那問題就簡單許多了。

  1. Go Gopher是隨機我們輸出的位置當中心來回傳的,那我們就可以先把固定一塊Block(3X3)填滿再去填滿下一塊,因為最大200塊也不用擔心會超出範圍。

測試工具

Windows cmd:testing_tool.py ./Console.exe
如果運行過會這樣
https://ithelp.ithome.com.tw/upload/images/20180713/20110564jQZr0GAxhy.png

完整程式碼

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MAX = 1000;

void Process(const int& blockSize)
{
	vector<int> blockUsed(blockSize, 0);
	vector<vector<vector<bool>>> check(blockSize, vector<vector<bool>>(3, vector<bool>(3, true)));

	int index = 0;
	int count = 0;
	int centerX = 3;
	int centerY = 3;
	int x = 0;
	int y = 0;

	while (count < MAX) {
		cout << centerX << " " << centerY << endl;
		cin >> x >> y;

		if ((x == 0 && y == 0))
		{
			return;
		}

		const int offsetX = x - centerX + 1;
		const int offsetY = y - centerY + 1;

		if (check[index][offsetX][offsetY])
		{
			blockUsed[index] += 1;
			check[index][offsetX][offsetY] = false;
		}

		if (blockUsed[index] == 9)
		{
			index++;
			centerX += 3;
		}

		count++;
	}
}

void Input()
{
	int count = 0;

	if (cin >> count)
	{
		for (int index = 0; index < count; index++)
		{
			int area = 0;
			cin >> area;

			const int blockSize = (area / 9) + ((area % 9) == 0 ? 0 : 1);
			Process(blockSize);
		}
	}
}

int main()
{
	Input();
	return 0;
}

程式碼解析

輸入

1.count 測資數量。
2.area 面積。
3.blockSize 3X3的Block數量。
4.Process 運行交互式函數。
5.開始交換訊息。

void Input()
{
	int count = 0;

	if (cin >> count)
	{
		for (int index = 0; index < count; index++)
		{
			int area = 0;
			cin >> area;

			const int blockSize = (area / 9) + ((area % 9) == 0 ? 0 : 1);
			Process(blockSize);
		}
	}
}

運行

1.我們先宣告一個容器blockUsed來記錄準備好的數量,和一個容器check來紀錄已準備好的位置(都是3X3當作一個index)。
2.index記錄目前Block位置,count來記錄交換次數(最大1000)。
3.我選擇從centerX = 3,centerY = 3當第一個Block的中心。
4.x和y則是要接收Go Gopher回傳已準備好的位置。

void Process(const int& blockSize)
{
	vector<int> blockUsed(blockSize, 0);
	vector<vector<vector<bool>>> check(blockSize, vector<vector<bool>>(3, vector<bool>(3, true)));

	int index = 0;
	int count = 0;
	int centerX = 3;
	int centerY = 3;
	int x = 0;
	int y = 0;

	while (count < MAX) {
		cout << centerX << " " << centerY << endl;
		cin >> x >> y;
        
        // 如果已完成則退出
		if ((x == 0 && y == 0))
		{
			return;
		}
        
        // 計算容器位置(可改為宣告1000 * 1000則不用計算)
		const int offsetX = x - centerX + 1;
		const int offsetY = y - centerY + 1;
        
        // 如果未使用,Block數量加一和設定已使用
		if (check[index][offsetX][offsetY])
		{
			blockUsed[index] += 1;
			check[index][offsetX][offsetY] = false;
		}
         
        // 當下Block已準備好,換下一塊
		if (blockUsed[index] == 9)
		{
			index++;
			centerX += 3;
		}

		count++;
	}
}

結語

這次改了一下解釋風格,但還是有部分式寫在裡面,會慢慢改善排版模式讓人輕鬆觀看。


2 則留言

2
fysh711426
iT邦研究生 5 級 ‧ 2018-07-14 00:05:20

感謝大大分享,比賽完 Google 就關閉上傳功能,所以一直沒有機會測試大 Case,看到您第一篇文章後就想趁假日來重寫看看。

哈哈哈,這題我也看很久,第一次遇到互動式的題目,
我那篇文章內容不多,而且程式跑大 Case 都沒過,太丟臉了。
/images/emoticon/emoticon16.gif

MNGhost iT邦新手 5 級‧ 2018-07-14 09:53:06 檢舉

但似乎只開放4個月有看到時間倒數現在剩下27天

fysh711426 iT邦研究生 5 級‧ 2018-07-16 07:38:38 檢舉

竟然剩下 27 天。 /images/emoticon/emoticon16.gif

0
fysh711426
iT邦研究生 5 級 ‧ 2018-07-16 07:30:09

這題我是偷看官方分析才知道,原來要以3X3區塊去整理 Go Gopher 才不會給出太多重複的座標,導致交換次數超過 1000 次的限制。
/images/emoticon/emoticon37.gif

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

using namespace std;

int main(void)
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        int a;
        scanf("%d", &a);

        int record[3][3] = {0}; //記錄3X3區塊完成的部分
        int count = 9;          //剩餘的數量
        int num = 1;            //區塊編號

        int x, y;               //GoGopher回傳的座標
        int centet_x, centet_y; //3X3區塊中心座標

        //隨便選一個座標開始
        centet_x = centet_y = 6;

        while (true)
        {
            //該3X3區塊已整理完
            if (count == 0)
            {
                centet_y += 3;
                count = 9;
                num++;
                continue;
            }

            printf("%d %d\n", centet_x, centet_y);
            fflush(stdout);

            scanf("%d %d", &x, &y);

            //程式失敗
            if (x == -1 && y == -1)
            {
                return 0;
            }
            //完成果園整理
            if (x == 0 && y == 0)
            {
                break;
            }
            //x,y超出範圍
            if (x < 2 || x > 999 || y < 2 || y > 999)
            {
                continue;
            }
            //紀錄完成的部分,以區塊編號當標記
            if (record[x - centet_x + 1][y - centet_y + 1] != num)
            {
                record[x - centet_x + 1][y - centet_y + 1] = num;
                count--;
            }
        }

        c++;
    }

    //system("pause");
    return 0;
}
MNGhost iT邦新手 5 級‧ 2018-07-16 08:40:33 檢舉

其實-1 -1可以偷懶不用判斷哈哈,官方寫的我還真的看不懂/images/emoticon/emoticon16.gif

我要留言

立即登入留言