[Medium] 重新開始文章張貼XD

目前新的文章會開始在Medium這個平台上發布，
如果想看一些關於LeetCode以及演算法的探討的話，
歡迎移駕前往觀看~

https://medium.com/@desolution

如果看到什麼錯字或有問題的地方也歡迎留言告訴我歐!

HackerRank Bon Appétit(Algorithms>Implementation)

題目:
Anna和Brian在一個餐廳點了n道菜，
但Anna拒絕吃第k道菜(0<= k < n, 菜的編號從0開始)
因為她會過敏。
所以他們決定要分攤所有他們有共食的菜的花費；
但是Brian有可能會忘記他們並沒有分攤第k道菜，
並且不小心向Anna收了這筆錢。

給定n, k，和這n道菜的各自價格以及Brian像Anna收她那部分的錢。
如果分帳公平，就印出Bon Appetit，
否則就印出Brian應該退給Anna的錢。

輸入:
第一行以空格隔開2個數，分別為n(總菜數), k(從0起算Anna沒吃的那道菜的編號)
第二行以空格隔開n個數，分別代表每道菜的價格。
第三行輸入的是Brian向Anna收取的分帳費用。

輸入限制:
2<=n<=10的5次方 (會不會點太多菜了!)
0<=k<n
0<=c[i]<=10的4次方(c[i]指第i道菜的價格)
0<=b<=(c[i]的總和)

輸出:
Brian沒有超收Anna錢的話，就印出Bon Appetit，
否則就印出差值以表示Brian必須退還給Anna的錢(這邊保證這會是整數)。

解題:
這題其實並不難，
問題在於輸入限制條件n最大可以到10的5次方，
這兩個人的食量也是太扯了一點......
言歸正傳，這題仔細一看，我們並不需要記錄每道菜到底多少錢，
只需要算出拆帳金額，也就是把第k道菜以外的錢相加再除以2就行了!
故不需要額外開出每道菜金額的陣列，
只要讀進來相加除以2，
最後和charge比較，來決定印出的值。


Code：

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

int main() {
    int n, k, charge, actual = 0;
    scanf("%d %d\n", &n, &k);
    for(int i = 0; i < n; i++){
        int c;
        scanf("%d ", &c);
        if(i != k){
            actual += c;
        }
    }
    actual /= 2;
    scanf("%d", &charge);
    if(charge > actual)
        printf("%d", charge - actual);
    else
        printf("Bon Appetit");
    return 0;
}

HackerRank The Bomberman Game(Algorithms>Implementation)

題目:
炸彈超人存在在一個矩形的區塊，
這個區塊有R行C列(R rows and C columns)。
每一個區塊內的方格(cell)要嘛有一個炸彈，
要嘛就是空的。

每個炸彈可以被放在區塊內的任意方格中，
一旦放置，在倒數3秒後會爆炸，
並且摧毀連同周邊的四個方格。
也就是說在i, j座標的方格裡的炸彈引爆，
會讓(i+-1, j)和(i, j+-1)的方格被清空。
(注意在邊緣的格子可能周邊少於4個方格)
如果周邊的格子在被清空時有炸彈的話，
該炸彈會被摧毀，但不會再被引爆。
(也就是不會有連鎖反應)

炸彈超人對炸彈是免疫的(最好啦!怎麼跟我小時候玩的不一樣)，
所以他可以在區塊內任意移動。
下面是他所做的:
1. 最初炸彈超人任意在區塊內的一些格子放置炸彈。
2. 1秒後，炸彈超人不做任何事情。
3. 再多1秒後，炸彈超人將剩下沒被放炸彈的格子放滿炸彈，
也就是保證現在所有格子都有炸彈，且這一秒還沒有炸彈會爆炸。
4. 再多1秒後，3秒前被放的炸彈會爆炸，這裡，炸彈超人退後並觀測。
5. 然後炸彈超人不停反覆進行步驟3和步驟4。

注意每次炸彈超人放的炸彈都視為同時放，
所以同時放的炸彈也會同時爆炸(一個光速的概念就對了)

給定初始放炸彈的格子，
決定N秒後區塊的狀態。

輸入:
第一行包含了3個用空格隔開的整數，
分別代表R,C,N，
R條連續的線(line)i代表行(row)i在區塊內的起始狀態，
以'.'表示空方格，O(ascii 79)表示炸彈。

限制:
1<=R, C<=200
1<=N<=10的9次方

輸出:
印出區塊的最終狀態，
也就是要印出R行C列的字母，
當中每個字母會是'.'(沒炸彈)或'O'(有炸彈)，
用以表示N秒後的區塊狀態。

範例輸入:

6 7 3
.......
...O...
....O..
.......
OO.....
OO.....

範例輸出:

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

解題:
這題有相當程度的麻煩，在實作時也要考慮到一些東西。
首先考慮如何計算狀態變化，
我們以B1表示最初放的炸彈，
B2表示2秒後填滿的那次，
以此類推，那麼我們大概可以藉由下面列出的時間軸看出一些端倪。
0----->1----->2----->3--------->4------->5----------->6------>7
B1      X        B2      X(B1炸)   B3        X(B2炸)     B4       X(B3炸)

t=0時，放下B1
t=1時，不變(也就是說N=1的話就可以直接按照原輸入的陣列輸出。)
t=2時，放下B2(這時候填滿了)
t=3時，B1炸開來
t=4時，放下B3(這時候又填滿了)
......
所以，我們可以知道:
1. N=1 => 直接輸出原陣列
2. N%2 = 0 => 輸出全填滿'O'(因為這時候炸彈全填滿)
3. 其他
考慮B1炸開來的時候，炸開的範圍是B1加上其前後左右。
(注意不會連鎖引爆，會的話又不一樣了)
由於這時候t=3，我們先叫它t3 state。

t3 state在t=4的時候補下B3，跟著t=5時又爆炸，
炸開的範圍是t3加上其前後左右，
會留下除了(t3及其前後左右)以外的格子，
我們叫它t5 state。

t5到t7又炸一次，不難得知t7=t3 state(因為剛好互補)。
所以可知t3=t7=t11=...=t(4r+3), r = 0,1,2, ...
同樣的，t5=t9=t13=...=t(4k+1), k= 0,1,2, ...

所以t1到t3作的事情，
就是先expand(延展)以後，再reverse(取互補)。
t3到t5只是做同樣的事情一次，
但t1不等同於t5就是了。

下面在宣告時，由於二階陣列不宜動態宣告(記憶體配置容易管理不好)，
我們可以藉由限定的行列數在200以下，直接宣告grid[201][201]。
(剛好200會出錯，不清楚為什麼，如果有看出我寫法問題的還請不吝賜教，感謝~)

讀入時記得先讀入R,C,N，
然後每一行由於是讀字元，不要忘記多讀一次將LF換行字元讀走。
剩下的重點就是expAndRev的部分了:
首先傳入二維以上的陣列時，第二個維度以後要先給值，
故使用的是grid[][201]傳入。
再來，在expand的部分，
要注意的是先檢查該格是否是炸彈('O')，
再作延展的動作，而且不能同樣標記為'O'，
否則在另一輪迴圈裡可能會當作是新的炸彈，
這樣就變成連鎖反應了。
這邊用'E'來表示延展的格子。

最後reverse時，檢查是否為有炸彈或被延展(!= '.' )，
有的話就回歸為空格，不然就反轉為炸彈格('O')。

其他要留意的部分，
如expand時兩個if是不能寫到一起的，
因為有可能發生超過界線的狀態。


Code：

/* 
 Solve by Desolve Lin, 2016/09/15
 Please help yourself take it for reference,
 but kindly have a link to my blog if you use it at other website,
 thanks a lot!
*/

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

void printAns(int r, int c, char grid[][201]){
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            printf("%c", grid[i][j]);
        }
        printf("\n");
    }
}

void printFull(int row, int column){
    for(int i = 0; i < row; i++){
        for(int j = 0; j < column; j++){
                printf("O");
        }
        printf("\n");
    }
}

// t3 result
void expAndRev(int row, int column, char grid[][201]){
    // Expand to find detonate area
    for(int i = 0; i < row; i++){
        for(int j = 0; j < column; j++){
            if(grid[i][j] == 'O'){
                // Those who are detonated areas are not real bomb and can't be expanded again.
                if(i - 1 >= 0)
                    if(grid[i-1][j] == '.')
                        grid[i-1][j] = 'E';
                if(j - 1 >= 0)
                    if(grid[i][j-1] == '.')
                        grid[i][j-1] = 'E';
                if(i + 1 < row) 
                    if(grid[i+1][j] == '.')
                        grid[i+1][j] = 'E';
                if(j + 1 < column) 
                    if(grid[i][j+1] == '.')
                        grid[i][j+1] = 'E';
            }
        }
    }
    // Reverse to find t3 bomb state        
    for(int i = 0; i < row; i++){
        for(int j = 0; j < column; j++){
            if(grid[i][j] != '.'){
                grid[i][j] = '.';
            }else{
                grid[i][j] = 'O';
            }    
        }
    }   
}

int main() {
    int row, column, n;
    scanf("%d %d %d\n", &row, &column, &n);
    char grid[201][201];
    
    for(int i = 0; i < row; i++){
        char tmp;
        for(int j = 0; j < column; j++){            
            scanf("%c", &grid[i][j]);
        }
        scanf("%c", &tmp); // remove linefeed
    }
    if(n == 1)
        printAns(row, column, grid);
    else if(n % 2 == 0)
        printFull(row, column);
    else{
        // t3 state => expand and reverse once : t3, 7, 11, 15
        // t5 state => expand and reverse twice: t5, 9, 13, 17
        expAndRev(row, column, grid);
        if(n % 4 == 1)
            expAndRev(row, column, grid);
        printAns(row, column, grid);
    }    
    return 0;
}

HackerRank Minimum Distances(Algorithms>Implementation)

題目:
考慮一個陣列A=[a0, a1, ..., an-1]。
當中兩個索引值i, j的距離使用di,j = |i-j|來表示。
給定A，找出最小的di,j，當中ai=aj且i不等於j。
換句話說，找出裡面元素值相等的元素對(pair)，
且找到符合這個條件的元素對的最小的距離。
如果沒有任何元素對符合的話，印出-1。

輸入:
第一行輸入A的陣列大小n。
第二行輸入n個以空白隔開的整數，用以代表A的所有元素。

限制:
1<=n<=10的3次方
1<=ai<=10的5次方

輸出:
印出一個整數用以代表A裡面最小的di,j，
如果不存在這樣的數的話，印出-1。

解題:
用簡單的雙層迴圈來解該題，
我們只要沿著每一對都比較過一次，
先確認A[i]是否等於A[j]，
再來看新的距離是否小於原本已記錄的最小距離，
是的話就取而代之。
這邊別忘記一開始設定d=-1，
故如果找到第一個距離的話，
必須直接將d覆寫過去。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n; 
    scanf("%d",&n);
    int *A = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++){
       scanf("%d",&A[i]);
    }
    int d = -1;
    for(int i = 0; i < n-1; i++)
        for(int j = i + 1; j < n; j++){
            if(A[i] == A[j])
                if(d < 0) d = j - i;
                else if(j - i < d) d = j - i;
        }
    printf("%d", d);
    
    return 0;
}

HackerRank Absolute Permutation(Algorithms>Implementation)

題目:
我們定義P是前N個自然數的其中一種排列，也就是[1, N]裡面的正整數的排列。
定義posi是i在這個排列裡面所在的位置。
如果abs(posi-i) = K對每個[1, N]裡面的i都成立的話，
我們叫這個排列為絕對排列(Absolute Permutation)
給定N和K，印出字典順序最小的絕對排列P；
若不存在絕對排列，印出-1。

輸入:
第一行為T，代表總測資項數。
每個接下來的T行都有2個以空格分開的整數，
為該次測項的N和K。

限制:
1<=T<=10
1<=N<=10的5次方
0<=K<N

輸出:
在新的一行印出對該測項字典順序排列最小的絕對排列，
沒有絕對排列的話就印出-1。

範例輸入:

3
2 1
3 0
3 2

範例輸出:

2 1
1 2 3
-1

解題:
請同步參閱code內的註解。
在主函式內首先將arr填滿，
留意當k為0時，直接印出陣列即為解。

當k不等於0呢?
我們先假設絕對排列存在，
那麼i就必須跟i+k換(這樣才會有k的絕對差)，
那麼這樣思考的話，我們就可以用2k為一個區間來計算。
0, 1, ..., k-1 -> k+0, k+1, ... k+k-1這樣子做對照，
然後下一組區間從0+2k開始。
那麼接下來就是每次跳2k來看每個j能不能跟j+k交換。
也就是
i=0 : 0, k -> 2k, 3k -> 4k, 5k ...(if still < n)
i=1 : 1, k+1-> ......
以此類推，當中間碰到某次無法交換，就代表不存在這樣的絕對排列，

由於k被固定的狀況，0必須要跟k換，1必須要跟k+1換，
(因為沒得往前換，只能往後換)
所以前2k個數(0~2k-1)的換法都被固定了，
其後的數也無法跟前面的交換，
從而，2k~4k-1的換法也被固定了，
以此類推，此絕對排列要嘛不存在，
不然存在的話就是唯一解，那麼唯一解當然是最小囉XD!

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

// swap: make element i, j of the array arr[] swap with each other.
void swap(int *arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
/* permute: calculate absolute permutation of k, if NOT possible then return -1.
/  case: k==0
        Array itself is the answer, no need to swap anything.
  case: other
        Suppose there's an absolute permutation of the array, then element i must swap with element i+k,
        then the difference will be -k, +k.
        Since then, a section will be 2*k. 
        Ex: 0, 1, ..., k-1 -> k+0, k+1, ... k+k-1, and next round should start from 0+2k.
        We could start from i=0, each time adding 2*k to find if there's a pair to swap,
        that is, from 0, k -> 2k, 3k -> 4k, 5k ...(if still < n)
        (Notice that if we find a single num that can't be paired, we have to return -1.)
        
        Then i=1, i=2, i=3 ... ...
        And we could get the array done with absolute permutation of k.
*/
int permute(int *arr, int k, int n){
    for(int i = 0; i < k; i++){
        for(int j = i; j < n; j += k*2){
            if(j + k >= n)                        
                return -1;
            else
                swap(arr, j, j+k);        
        }         
    }
    return 0;
}
int main(){
    int t; 
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        int n, k;
        scanf("%d %d",&n,&k);
        int arr[n];
        
        for(int i = 0; i < n; i++)
            arr[i] = i + 1;
        
        if(k == 0){
            for(int i = 0; i < n; i++)
                printf("%d ", arr[i]);
        }else{
            if(permute(arr, k, n) == -1)
                printf("-1");
            else
                for(int i = 0; i < n; i++)
                    printf("%d ", arr[i]);            
        }
        printf("\n");
    }
    return 0;
}

HackerRank Lisa's Workbook(Algorithms>Implementation)

題目:
Lisa剛拿到一本新的數學習題本。
這本習題本包含了以章節來分組的練習題。
1. 習題本共有1到n的章節。
2. 第i章有ti個問題，編號從1到ti。
3. 每頁最多可以放下k道問題，這本書沒有空頁或不必要的空白，
所以只有在每章最後一頁才可能會有少於k到問題的狀況。
4. 每逢新的一章，就要從新的一頁開始，
所以一頁當中不可能會有不同章節的題目。
5. 頁數從1開始起算。

Lisa相信如果一個問題的編號和它所在的頁數是一樣的時候，
它會是"特別的"。(啥鬼!)
給定這本習題本的細節，你能計算出有多少問題是"特別的"嗎?

輸入:
第一行為n和k，分別代表章節的數量和單頁最大習題數。
第二行為n個整數t1, t2, t3, ..., tn，
代表每個章節分別有多少個習題。

限制:
1<= n, k, ti <=100

輸出:
印出"特別的"習題的總數。
例如輸入:

5 3  
4 2 6 1 10

輸出

4

因共有5章，每頁最多3題，
那麼題目排列的狀況為:Page 1
Page   1: 1 2 3
Page   2: 4
Page   3: 1 2
Page   4: 1 2 3
Page   5: 4 5 6
Page   6: 1
Page   7: 1 2 3
Page   8: 4 5 6
Page   9: 7 8 9
Page 10: 10
故答案為4。

解題:
我們用2層的迴圈來解此題。
pb_cnt為問題編號的計數，
在每一章之中我們遍歷過每個問題的編號，
如果問題的編號和現在頁數相同，
special_num就加1。
且問題數每經k道題，就該換頁(page++)，
並在換章節時也要換頁(page++)。
注意到為了避免剛好問題數是k的整數倍，
故加入pb_cnt < t[chap-1]的判斷，
如果這次的換頁已經是這章的最後了，
就取消換頁，避免和換章節的換頁重複到。

最後印出special_num即為解答。

Code：

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

int main() {

    int n, k;
    scanf("%d %d\n", &n, &k);
    int t[n];
    for(int i=0; i<n; i++)
        scanf("%d ", &t[i]);
    int special_num = 0, page = 1;
    
    for(int chap=1; chap<=n; chap++)
    {
        for(int pb_cnt=1; pb_cnt<=t[chap-1]; pb_cnt++)
        {
            if(pb_cnt == page) special_num++;
            if(pb_cnt % k == 0 && pb_cnt < t[chap-1]) page++;
        }
        page++;
    }    
    printf("%d", special_num);
    
    return 0;
}

HackerRank Repeated String(Algorithms>Implementation)

題目:
Lilah有一個字串s, s由小寫的英文字母組成，她會一直不斷地重複它。

給定一個整數n，找到並印出前n個字母中，字母'a'所出現的次數。

輸入:
第一行包含一個字串s，
第二行是整數n。

限制:
1<=|s|<=100
1<=n<=10的12次方
這當中有25%的測資是n<=10的6次方

輸出:
印出一個整數，用以代表在前n個字母裡面a出現幾次。

解題:
我們分成2種case:
case 1: s的長度為1
這種情況下要是s剛好是a的話，
那答案就是n，否則就是0。

case 2: s的長度大於1
我們可以計算在計到n時，總共經過了幾次s，
答案=(經過次數)*(s所含a的個數)+(最後餘數所含的a的個數)
請留意code內的方法，可以讓我們只遍歷一遍s就算完全部。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    char* s = (char *)malloc(512000 * sizeof(char));
    scanf("%s",s);
    long n; 
    scanf("%ld",&n);
    if(strlen(s) == 1)
    {
        if(s[0] == 'a')
            printf("%ld", n);
        else
            printf("0");
    }else {
        int leng = strlen(s);
        long quotient = n / leng, remainder = n % leng;
        int a_total = 0, a_remain = 0, i = 0;
        while(i < remainder){
            if(s[i] == 'a'){
                a_total++;
                a_remain++;
            }
            i++;
        }
        while(i < leng){
            if(s[i] == 'a'){
                a_total++;
            }
            i++;
        }
        printf("%ld", quotient * a_total + a_remain);        
    }    
    return 0;
}

HackerRank Strange Counter(Algorithms>Implementation)

題目:
Bob有一個奇怪的計數器。
第一秒 t=1時顯示3，接下來每秒減1，
直到倒數到1時，下一秒顯示為2*起始的數字(3)，
再繼續倒數，倒數到1時，下一秒顯示為上一輪的2倍(2*2*3)，
以此類推。
(即: 3->6->12->24......)
(3 2 1 6 5 4 3 2 1 12 11 10 9 8 7 ...)
給定一個時間t，印出那個時間點計數器顯示的數字。

輸入:
一個代表t的整數。

限制:
1<=t<=10的12次方

輸出:
印出這個奇怪的計數器再給定的時間t時顯示的值。

解題:
題目不難，就是不斷將t減去cycle再存起來，
直到不能再減，代表在本次cycle內會數到t的位置，
再把剩下的數完。
其實本題也可以用等比數列和去逐步計算，
但感覺用減的可能比較快速一些(因為還是要一輪一輪看)
code裡面n沒有用到，不過如果題目有額外要求的話，
可以用來確認經過的cycle數。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    long long int t; 
    scanf("%lli",&t);
    long long int n = 1;
    long long int cycle = 3;
    while(t > cycle){
        t -= cycle;
        n++;
        cycle *= (long long int) 2;        
    }
    printf("%lli", (long long int)cycle - t + 1);    
    
    return 0;
}

HackerRank Save the Prisoner!(Algorithms>Implementation)

題目:
有一個監獄，裡面有N個囚犯，每個都各自有一個獨立的id號S，範圍從1到N。
現在有M個糖果必須要分配給這些囚犯。
獄卒決定用最公平的方法來完成這件事情:讓囚犯們圍坐成一圈(依據S來升序排列)，
接著從一個隨機的S開始來一個一個配發糖果，直到M個糖果被發完。
比如說假設獄卒挑到S = 2，就從2, 3, 4, 5, ... , n-1, n, 1, 2, 3, 4, ...發直到M個糖果發完。

等等，有陷阱! 最後一顆糖果被下毒了!
你可以找到並印出最後一個拿糖果的囚犯讓他能被警告嗎?

(OS:阿哩勒......這樣子也沒有公平阿=口=)
(而且是誰在那邊下毒阿到底!)

輸入:
第一行包含一個整數T，代表總共的測資數。
接下來的T行，每行包含三個以空格隔開的整數:
N(囚犯數)，M(糖果數)，S(開始的囚犯編號)

限制:
1<=T<=100
1<=N<=10的9次方
1<=M<=10的9次方
1<=S<=10的9次方

輸出:
對每個測資，在新的一行印出會拿到的有毒的糖果的囚犯編號。


解題:
簡單來說就是一個算餘數的遊戲，
當餘數是0的話就代表是編號N。

Code：

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

int main() {
    int t;
    scanf("%d\n", &t);
    for(int i=0; i<t; i++)
    {
        int n, m, s, result;
        scanf("%d %d %d\n", &n, &m, &s);
        result = (m % n) + (s-1) % n;
        if (result > n) result %= n;
        if (result == 0) result = n;
        printf("%d\n", result);
    }
    return 0;
}

HackerRank Flatland Space Stations(Algorithms>Implementation)

題目:
Flatland是一個有n個城市的國家，當中m個城市有太空站(space stations)。
所有城市被由0~n-1編號為C0~Cn-1，
每個Ci和Ci+1之間會有一條雙向的1公里長的道路。
對每個城市來說，我們可以知道其到最近的太空站的距離，
試求這些距離當中最大的值。
(如果自己這個城市有太空站的話對這個城市最近的太空站距離即為0)

輸入:
第一行輸入n, m(以空格隔開)
第二行包含m個數字代表那個編號的城市擁有太空站，
這些數字是未經排列且不重複的。

限制為1<=n<=10的5次方，且1<=m<=n。

輸出:
印出當一個太空人在其中一個城市時，
需要到達最近的太空站的最大可能必須旅行的距離。

解題:
請注意m的輸入是未排序的!!!
解決這點以後，解題應該不難。
我們同樣利用qsort進行事先排序，這裡不再贅述。

當n == m時，表示每個城市都有太空站，故max=0，
就直接省去後續了。

排序後考慮對某個城市的最小距離，
分為2種:
1. 0 -> c[0]和c[m-1]-> n，這兩個的最小距離是兩者相減。
2. c[i]和c[i-1]，這兩個要取中間的一個城市並算最小距離，
故將兩者相減除以2。
因為要找這一群最小距離當中的最大值，
故取靠近正中間或剛好正中間的城市。

不斷比較並保留較大值，最後即可印出結果。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int compare(const void *arg1, const void *arg2){
     return  (*(int *)arg1 - *(int *)arg2);
}

int main(){
    int n; 
    int m; 
    scanf("%d %d",&n,&m);
    if(n == m) 
        printf("0");
    else{        
        int *c = malloc(sizeof(int) * m);
        int max = 0, temp = 0;
        for(int i = 0; i < m; i++){
            scanf("%d",&c[i]);
        }
        qsort((void *)c, m, sizeof(int), compare);
        
        max = c[0];        
        for(int i = 1; i < m; i++){
            temp = (c[i]-c[i-1])/2;
            max = (max > temp)? max : temp;
        }
        temp = n-1 - c[m-1];
        max = (max > temp)? max : temp;
        printf("%d", max);        
    }
    return 0;
}

HackerRank New Year Chaos(Algorithms>Implementation)

題目:
新年到了，大家都在排Wonderland的雲霄飛車!
(OS:新年和雲霄飛車到底啥關係=口=)
有n個人在排隊，每個人都會貼上一個貼紙，
用來代表他們原本在隊列中最初的位置。
(例:1, 2, 3, ..., n-1, n，最前面的人編號是1，以此類推)

任何一個人都可以透過賄賂和自己前面的那一個人交換位置。
(只能跟剛好現在在自己前面的，也就是5可以跟4換，但不可以跟3換)
換完位置以後他們身上的貼紙維持原樣，不會跟著交換。
每個人最多只能賄賂兩次，不能再多XD

當你到現場時，只看到最後的隊列長成現在這個樣子，
而你決定你要知道將隊列變成現在這樣子，
所需的最小次數的總賄賂次數是多少。
(別隨便幫我決定阿喂!!!!!)

輸入:
第一行輸入T，代表總數的測資(test cases).
每筆測資由2行組成，第一行為隊列人數n，
第二行則列出最終的隊列排列的樣子(n個數字，由空格隔開)。
限制為1<=T<=10, 1<=n<=10的5次方。

輸出:
如果沒辦法透過每人2次以內的賄賂達到測資要求的狀況，
就印出Too chaotic，
否則則印出最小所需的賄賂次數。

例:
輸入

2
5
2 1 5 3 4
5
2 5 1 3 4

輸出

3
Too chaotic

解題:
這也是Medium Level的題目，
我覺得我的解法並沒有能夠完整證明答案的可靠度，
但基本上應該沒錯，如果有有興趣的讀者或大神，
或許可以幫忙看看要怎麼樣才能更嚴謹地將解題部分證明更詳細些。

我們怎麼檢查這個隊列是否是有解的呢?
其實只要檢查每個人的位置離起始位置是否超過2單位的距離。
因為每個人都只能賄賂2次，
如果那個位置距離你3格以上(比如原本在4，想到1的位置)，
那勢必要賄賂3次以上才行，因為沒有人會跟你賄賂交換後面的位置XD
那麼如果所有人都離自己目標2格以內的話(指後-前= 正2以內)，
從第一個位置開始，讓想到該位置的人開始賄賂排到那個位置，
我們可以排好i=1, 2, 3, ..., n-1的所有人，於是i=n的人也會是剛好的那個人。
(因為前面都排好了)

而且從最前面開始排的話，最前面的人的賄賂次數不會浪費，
因為一排到那邊去接下來就鎖定不動了，故這個排列方式也是花費最少的次數。

在code中為了要實作，
我們定義以下幾個變數和陣列:
bribe_total -> 總賄賂次數
temp -> 交換用
chao -> 是否無法達成此狀態
q_now -> 目前的隊列排列狀態
pos_now -> 編號i+1的人目前所在的位置
q -> 測資給入的最終隊列狀態。

首先輸入q以後，我們可以同步藉由此迴圈，
將q_now和pos_now給輸入完成。
接下來先檢查每個距離差是否>2，
是的話就直接讓chao=1且後面輸出Too chaotic，
否則後面才繼續做。

接下來透過迴圈計算每項的diff(距離差)，
diff為2的話，
表示那個人要賄賂兩次，
比如:

1 2 3 -> 3 1 2

編號3的人賄賂了2次，
於是前移2單位，中間的人則各自後移2單位，
依此更新陣列狀態並將bribe_total加2。

diff為1的話，
則前後交換，更新陣列狀態並將bribe_total加1。

持續從i=0做到i=n-2，
將0~n-1給排好，即可得到總賄賂次數，
並將其印出。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int T; 
    scanf("%d",&T);
    for(int a0 = 0; a0 < T; a0++){
        int n, bribe_total = 0, chao = 0; 
        scanf("%d",&n);
        int *q = malloc(sizeof(int) * n);
        int q_now[n], pos_now[n];
        for(int q_i = 0; q_i < n; q_i++){
            scanf("%d",&q[q_i]);
            q_now[q_i] = q_i + 1;
            pos_now[q_i] = q_i;
        }
        for(int i = 0; i < n; i++){
            if(pos_now[q[i]-1] - i > 2)
            {
                chao = 1;
                break;
            }
        }
        if(chao){
            printf("Too chaotic\n");
        }else{
            for(int i = 0; i < n-1; i++)
            {
                int temp = q[i], diff = pos_now[q[i]-1] - i;
                if( diff == 2 )
                {
                    bribe_total +=2;
                    pos_now[q_now[i+1]-1]++;
                    pos_now[q_now[i]-1]++;
                    pos_now[q_now[i+2]-1] -= 2;
                    q_now[i+2] = q_now[i+1];
                    q_now[i+1] = q_now[i];
                    q_now[i] = temp;
                } else if( diff == 1 ){
                    bribe_total++;
                    pos_now[q_now[i]-1]++;
                    pos_now[q_now[i+1]-1]--;
                    q_now[i+1] = q_now[i];
                    q_now[i] = temp;                    
                }                    
            }    
            printf("%d\n", bribe_total);
        }
    }
    return 0;
}

HackerRank Jumping on the Clouds: Revisited(Algorithms>Implementation)

題目:
Aerith正在玩跳雲朵的遊戲!(是有多好玩啦= =)
遊戲一樣有0~n-1共n朵雲排成一環，
每朵雲可能是普通雲或雷雲。

Aerith從編號0的雲開始，初始能量為E=100。
她可以使用1單位的能量跳躍k朵雲的距離，
直到繞完一圈回到編號0的雲。
如果落在雷雲上，她的能量會額外扣除2單位。

當Aerith回到編號0的雲時則遊戲結束。
給定n, k以及各朵雲的種類，
你可以確定最後殘存的能量E嗎?

輸入:
第一行輸入n和k(以空格間隔)
第二行輸入n個整數來表達0~n-1的雲是什麼雲，
0則為普通雲，1則為雷雲。

限制條件:
2<=n<=25
1<=k<=n
n % k = 0

輸出:
在新的一行印出最終E的值。

解題:
我們可以先計算總共會跳的次數，
最終會回到原點，故總共會跳n/k次。
每次能量先不考慮雷雲的部分的話，
要先扣掉這個部分，並且由於最後會回到0，
我們可以先扣除掉c[0]*2。
(乘以2是因為雷雲的話會-2，正常雲的話-0，剛好符合)

接下來我們可以從i=k開始每次遞增k，
拿energy來扣除c[i]*2，
即可得到答案並印出。
注意底下，如果我們把結尾跳回0的那一跳，
當做是開頭就做的話，
也可以將計算並入最後的迴圈中，
將line a和line b的部分合起來，
只要將int i = k改成int i = 0即可。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n; 
    int k; 
    scanf("%d %d",&n,&k);
    int *c = malloc(sizeof(int) * n);
    for(int c_i = 0; c_i < n; c_i++){
       scanf("%d",&c[c_i]);
    }
    int energy = 100, jumptime = n / k;
    energy -= jumptime;
    energy -= c[0] * 2; // line a

    for(int i = k; i < n; i += k) // line b
        energy -= c[i]*2;
    printf("%d", energy);

    return 0;
}