iT邦幫忙

3

[Google Code Jam] C++ Saving The Universe Again 再次拯救宇宙

前言:

大家好,第一次發文往後請各位前輩多多指教,我文筆很糟,有手殘的地方請見諒。
首先先感謝朋友介紹Google Code Jam這活動,但錯過了沒機會參加到,還好Google還是開放讓人做題目,直接奉上題目網址了。
原題目

題目:

有個外星機器人使用指令來進行攻擊,預設攻擊為1,幸運的是我們知道他所擁有的指令為以下兩種:

  • C (for "charge"): 使光束攻擊加倍。
  • S (for "shoot"): 射擊光束,傷害等於目前"charge"的傷害。
    範例,假如目前機器人的指令是SCCSSC,則機器人在執行時的動作為:
  • 射擊光束,造成1點傷害。
  • 使光束傷害翻倍到2。
  • 使光束傷害翻倍到4。
  • 射擊光束,造成4點傷害。
  • 射擊光束,造成4點傷害。
  • 使光束傷害翻倍到8。
    所受的總傷害為9點傷害
    目前已經開發出一種可承受D傷害的盾牌,但機器人目前的程序運行會造成更大傷害。
    宇宙總統攻擊機器人程序,他唯一的攻擊方法就是交換兩個相鄰的指令。
    範例,總統可以交換第三個和第四個指令來破解上面指令SCSCSC,這樣傷害就變為7,然後第四個和第五個可以再交換變成SCSSCC,傷害就降到5,以此類推。
    為了防止機器人懷疑,總統不能破解太多次,請計算出最小破解次數,確保D總傷不大於盾牌。

輸入

輸入第一行T,為測試筆數,每筆包含整數D和一個字串P:盾牌所承受的最大總商和機器人指令。

輸出

輸出每筆資料,包含Case #x: y,其中x是測試筆數編號,y是目標所需最小數量,或是IMPOSSIBLE。

範圍

1 <= Ť <= 100 。
1 <= D <= pow(10,9)。
2 <= P的長度 <=30 。
P的字符是C或S。
時間限制:每個測試集20秒。
記憶體限制:1GB。

範例

輸入:
6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

輸出:
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5

解析:

  1. 只有C在S前才必須交換,也就是我們要找到"CS"。
  2. 因為次數要求最少,我們就必須從最後面開始找"CS"(後面的S必定大於等於前面效益最大)。
  3. 找到後交換(每交換一次次數 + 1)和將目前多餘的攻擊扣除S當時的攻擊除2(因為交換了,少了2被傷害),反覆直到攻擊小於等於0。

由上面三點我們得知,我們剛開始所需要的資料為,多餘的攻擊、S的位置和S當時的攻擊。

程式碼:

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

using namespace std;

// 交換。
template<class T>
void Swap(T& t1, T& t2)
{
	T save = t1;
	t1 = t2;
	t2 = save;
}

// 處理
// command: 指令。(因為會變動到資料所以直接拷貝)
// attakData: 攻擊的位置.目前位置的攻擊。
// needShield: 目前所需要的盾牌量(多出來的攻擊)。
int Process(string command, vector<vector<int>>& attakData, int needShield)
{

	int count = 0;
    
    // 直到我們不需要盾牌。
	while (needShield > 0)
	{
       for (int index = attakData.size() - 1; index > -1; index--)
		{
            // 得取"S"的索引位置。
			int offset = attakData[index][0];
            
            // 判斷上一個是不是"C"("CS"我們才交換)。
			if (command[offset - 1] == 'C')
			{
                // 交換.更新"S"位置和光束的攻擊大小。
				Swap(command[offset], command[offset - 1]);
				count++;
				attakData[index][0] = offset - 1;
				attakData[index][1] >>= 1;
				needShield -= attakData[index][1];
				break;
			}
		}
	}
	return count;
}

// 設定資料。
// command: 指令。
// attakData: 攻擊的位置.目前位置的攻擊。
// attak: 目前總攻擊。
void SetData(const string& command, vector<vector<int>>& attakData, int& attak)
{
	int base = 1;

	for (size_t index = 0; index < command.length(); index++)
	{
		if (command[index] == 'C')
		{
			base <<= 1;
		}
		else if (command[index] == 'S')
		{
			vector<int> data(2);
			data[0] = index;
			data[1] = base;
			attak += base;
			attakData.push_back(data);
		}
	}
}

// 檢查.初始化所需資料。
// command: 指令。
// shield: 盾牌。
int Compute(string& command, const int shield)
{
    // 等於0為IMPOSSIBLE。
	if (command.length() == 0)
	{
		return -1;
	}
    
    // 得取S的位置.S當下攻擊和目前的總攻擊。
	vector<vector<int>> attakData;
	int attak = 0;
	SetData(command, attakData, attak);
    
    // 攻擊次數大於盾牌為IMPOSSIBLE(都是1也無法抵擋)。
	if (attakData.size() > shield)
	{
		return -1;
	}
    
    // 計算最小需要幾次。
	return Process(command, attakData, attak - shield);
}

// 輸入和輸出。
void Input()
{
	int count = 0;
	int shield = 0;
	string command = "";

	while (cin >> count)
	{
		for (int index = 0; index < count; index++)
		{
			if (cin >> shield >> command)
			{
				int result = Compute(command, shield);
                
				if (result == -1)
				{
					cout << "Case #" << index + 1 << ": " << "IMPOSSIBLE" << endl;
				}
				else
				{
					cout << "Case #" << index + 1 << ": " << result << endl;
				}
			}
		}
	}
}

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

結果

https://ithelp.ithome.com.tw/upload/images/20180708/20110564Bog2JlK3gU.png
註:輸出部分要很注意Case #1 : N,N前面還有一個空格,測了一小時不過就是因為少了空格...。


0
神Q超人
iT邦新手 4 級 ‧ 2018-07-08 13:11:55

fysh711426C++好夥伴/images/emoticon/emoticon37.gif

MNGhost iT邦新手 5 級‧ 2018-07-08 13:14:14 檢舉

老大你好

小弟只是 C++ 初學者。 /images/emoticon/emoticon16.gif

2
fysh711426
iT邦新手 1 級 ‧ 2018-07-16 03:26:50

這題我終於把 Bug 解掉,大小 Case 都通過了。
/images/emoticon/emoticon37.gif

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

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

    while (testcase--)
    {
        int D;
        string P;

        scanf("%d", &D);
        cin >> P;

        int maxIndex = 0; //最大索引
        int index = 0;    //當前索引
        int sum = 0;      //總傷害
        int power = 1;    //能量強度
        int change = 0;   //交換次數

        //先計算總傷害
        for (int i = 0; i < P.size(); i++)
        {
            //充能
            if (P[i] == 'C')
            {
                power = power * 2;
            }
            //發射
            if (P[i] == 'S')
            {
                sum = sum + power;
            }
        }
        maxIndex = index = P.size() - 1;

        while (true)
        {
            //全部交換完畢
            if (index == 0)
            {
                break;
            }
            //損傷小於D
            if (sum <= D)
            {
                break;
            }
            //交換位置
            if (P[index] == 'S' && P[index - 1] == 'C')
            {
                P[index] = 'C';
                P[index - 1] = 'S';

                sum = sum - power + power / 2;

                //如果 index + 1 的位置是 S 可以再交換一次
                if (index + 1 <= maxIndex && P[index + 1] == 'S')
                {
                    index++;
                }

                change++;
                continue;
            }
            //由後往前退
            if (P[index] == 'C')
            {
                power = power / 2;
            }
            index--;
        }

        //印出結果
        if (sum > D)
        {
            printf("Case #%d: IMPOSSIBLE\n", c + 1);
        }
        else
        {
            printf("Case #%d: %d\n", c + 1, change);
        }

        c++;
    }

    //system("pause");
    return 0;
}
1
神Q超人
iT邦新手 4 級 ‧ 2018-07-16 19:30:41

我也分享一下解法XD
第一次解的時候是每次都去找“CS”去交換,
但是後來想一下,傷害最小的情況下是把S都換到最前面,
也就是每次攻擊傷害都是1的時候,
所以我把一開始指令每一次的傷害都記錄下來,
然後從最高的開始除上2,一直到盾牌擋得了傷害為止,
程式碼如下:

#接收到幾個指令
commandCount = int(input())

#跑迴圈一次接收一個指令
for case in range(1, commandCount+1):
    #接收這次的指令
    data = input()
    #把血量和指令分別取出來
    hp = int(data.split(" ")[0])
    command = data.split(" ")[1]
    
    #用來印出結果的地方
    def printStatus(status):
        print("Case #" + str(case) + ": " + str(status))
    
    #在做處理前先判斷出現的S數目有沒有大於血量,有的話怎麼換都不可能守護地球了
    if(command.count("S")>hp):
        printStatus("IMPOSSIBLE")
        continue
    
    #用一個陣列,等等拿來放指令中每次的S傷害值
    killArr = []
    #設定初始傷害值1
    basedKill = 1
    
    #去取指令中的每個動作
    for indexStr in command:
        #如果是S就把這一次的傷害放進陣列中
        if (indexStr=="S"):
            killArr.append(basedKill)
        #如果是C就把這一次目前傷害*2
        elif (indexStr=="C"):
            basedKill = basedKill*2
    
    #設定變換的次數
    changeCount = 0;
    '''
    去跑迴圈,一直到目前的盾牌可以扛下總傷害量為止
    '''
    while(sum(killArr)>hp):
        #把最後一次的傷害除於2,這樣就等於把最後的C和S換位置
        killArr[-1] = killArr[-1]/2
        #重新排序,讓傷害維持由小到大
        killArr.sort()
        #變換次數+1
        changeCount+=1
    
    #印出變換次數
    printStatus(changeCount)

我要留言

立即登入留言