2018 code jam Qualification Round

一年一度的google code jam!

所有參賽者需要在Qual Round中獲得25 pt，始能晉級下一個Round

PA   5 pt; 10 pt

PB   8 pt; 15 pt

PC 10 pt; 20 pt

PD 11 pt; 21 pt

我只有寫PA%PB，於是這裡就附上PA&PB的題解

連結：2018 code jam Qualification Round

PA：

一由S, C組成的字串

其中

• C (for "charge"): Double the beam's strength.
• S (for "shoot"): Shoot the beam, doing damage equal to the beam's current strength.

預設的damage為1

然後你可以對他做操作，每次操作可以任意調換兩個"相鄰字元"

請輸出最少操作幾次能使damage <= D

做法：

操作愈少次愈好，也就是調換後能減少的傷害愈多愈好

而每次charge都會加倍，那當然是調換最右邊的!

於是每次對字串中最右邊的"CS"做操作，直到傷害 <= D為止，算是一種貪心的想法

PB：

Bubble Sort的改編版——Trouble Sort

運作方式

 TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

然而，這個方法並不能正確的排序陣列，例如897即是一例

現在給你一個陣列，請問他能否用Trouble Sort成功排序

否則，輸出index其a[index]為第一個>a[index+1]的位置

做法：

觀察Trouble Sort，發現他只是將index為奇數的排序一遍、index為偶數的排序一邊

於是不需要O(N^2)實作，分成奇數與偶數用STL裡的Sort()，即可O(NlogN)完成

code for PA:

code for PB: