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;
}

HackerRank Bigger is Greater(Algorithms>Implementation)

這應該是本部落格第一篇HackerRank Medium難度的文章XD

題目:
給定一個字(word) w, 重新排列成另一個字s,
使得s在辭典順序排列上大於w. (s lexicographically greater w)
排列方式有多個可能解，
請找出當中最小的一個。

輸入:
第一行輸入t (代表測項的數目)，
接下來的t行每行包含了一個w(也就是每行一個字)。
限制條件為
1 <= t <= 10的5次方
1 <=|w|<=100
w只會包含小寫的英文字母，且它的長度不會超過100。

輸出:
對每個測項，輸出新的排列後辭典順序比原來大的w。
如果有多種可能，則輸出辭典順序最小的解，
而如果不存在解，則印出"no answer"。


解題:
這題的目的是尋找next permutation(下一個排列)。
思路上，首先我們要先看看目前的排列是否是字典順序上最大的排列，
舉例來說，如果有一個數列如下:

0 1 2 5 3 3 0

那我們當然直覺可以講出其最大辭典排法為:

5 3 3 2 1 0 0

也就是由左至右為遞減的排列。
那麼今天我們要找下一個排列的話，
首先就要確認其是否已經是最大排列，
是的話直接表示no answer，
不是的話則可以由右至左看這樣的排序會持續到什麼地方。

0 1 2 5 3 3 0

紅字標起來的地方是完整的遞減排序，
意味著在這塊區域內任意的調換，
辭典排法的順序只有可能變小，不可能變大。

那怎麼辦呢? 想要讓字典順序變大，
那麼就拿左邊黑色區域的2來跟右邊紅色區域的換好了!
因為拿更右邊的換，位數越低，
不管怎樣換，拿越靠右邊來換辭典順序理應能更小。

那麼，跟誰換?
跟最少比2大的換，因為比2小的話，
換過來辭典順序反而會變小。

0 1 2 5 3 3 0

0 1 3 5 3 2 0

換完以後就是所有可能中的辭典順序最小的解嗎?
並非如此，因為5 3 2 0剛好是由大到小排序。
注意這邊換過以後，由於前面2和3換的方式和條件，
(從右至左，找比2大的值做交換)
換完後(2的左邊的數) >= 3 > 2 >= (2的右邊的數)
自然令換完以後的右半邊的排列還是由大到小排序。
那麼，只要令這部分的值兩兩做交換，
我們就可以得到由小到大排序的辭典順序最小的狀況了。

統整一下流程結論: (設陣列為a_0~a_n-1)
1. 若陣列長 = 0或1 => no answer
2. 令i from n-1 -> 0, 找出首個i的值使得a[i-1] < a[i]
3. 如果i為0的話，表示此排序為辭典最大 => no answer
4. 令j from a_n-1->a_i, 找出第一個j，令a[j] > a[i-1];
5. a[j] 和 a[i-1]交換
6. 將i~j之間的的所有數兩兩交換，如此升序變降序。
7. 印出新的排序，此即所有解當中的最小的辭典排序的解。

Code：

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

void swap(char *x, char *y){
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
        
}

int next_permutation(char *a, size_t length){
    size_t i, j;
    if (length == 0) return 0;
    
    i = length - 1;
    while (i > 0 && a[i-1] >= a[i])
        i--;
    if (i == 0)
        return 0;
    
    // 現在保證存在一個i使得 a[i-1] < a[i], 
    // 在此之前其他的數字由左到右都是越來越小
    // 也就是本來就是排序較大的permutation,這部分換了字串不會比較大
    // 所以如果全部都是降序排列，就直接回傳0
    // 接下來再找一個j，滿足a[j]比a[i-1]大，swap過來，可以保證現在的陣列比較大
    // 且由右往回找，可以確保換的值是最小的。
    // 剩下的部分就是把原本降序排列改成升序，這樣才是比較小的排列方式。
    j = length - 1;
    while (a[j] <= a[i-1])
        j--;
    swap(&a[i-1], &a[j]);
    
    j = length - 1;
    while(i < j){
        swap(&a[i], &a[j]);
        i++;
        j--;
    }    
    return 1;
}

int main() {
    int n;    
    scanf("%d\n", &n);
    for(int i=0; i<n; i++){
        char word[100];
        scanf("%s", word);
        if (next_permutation(word, strlen(word))){
            printf("%s\n", word);
        } else {
            printf("no answer\n");
        }
    }   
    return 0;
}

HackerRank Jumping on the Clouds(Algorithms>Implementation)

題目:
Emma在玩一個新的手機遊戲，裡面有n朵雲，
分別從0~n-1將之編號。
玩家開始時在C0的雲朵，每次可以跳1或2朵雲的高度，
最終目的是到達Cn-1的雲朵。

雲朵分兩類，正常雲和雷雲，
雷雲踏上去就會game over，
Cn-1和C0保證是正常雲，
跳到Cn-1則遊戲獲勝。

輸入:
第一行輸入總共的雲朵數n，
第二行輸入n個用空格隔開的integer，
從C0到Cn-1，當中以數字0代表正常雲，
數字1代表雷雲。
本題輸入條件會保證總是有遊戲獲勝的可能性。

輸出:
最少次數能跳到Cn-1的解。

解題:
當限制遊戲保證有獲勝可能性時，
問題便大幅簡化，
因為一次最多跳2層，
也就表示不會2層都是雷雲。
那麼只要每次都檢查能否跳2層，
可以的話就跳2層，否則就跳1層，
並更新cnt數，就可以輕鬆得到最少次數的解了。

code裡面由於迴圈條件每次會++，
故在跳2層時只要將i再額外加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 n; 
    scanf("%d",&n);
    int *c = malloc(sizeof(int) * n);
    for(int c_i = 0; c_i < n; c_i++){
       scanf("%d",&c[c_i]);
    }
    int cnt = 0;
    for(int i = 0; i+1 < n; i++){        
        cnt++;    
        if((i+2) < n)
            if(c[i+2] == 0)
                i++;
    }
    printf("%d", cnt);
    return 0;
}

HackerRank Maximizing XOR(Algorithms>Bit Manipulation)

題目:
給定L和R兩個integer，找出L和R之間最大的A xor B，
當中A和B滿足 L<=A<=B<=R。

輸入:
兩行分別輸入L和R，
限制為1<=L<=R<=10的3次方。

輸出:
輸出如題所述的值。

解題:
基本上使用兩層的巢狀迴圈即可找出最大值，
唯獨要注意的是，
因為bitwise xor的符號"^"在編譯器的優先序會低於">"和"<"，
故記得將其用括號包起來。

Code：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
/*
 * Complete the function below.
 */
int maxXor(int l, int r) {
    int max = 0;
    for(int a=l; a<=r; a++)
        for(int b=a; b<=r; b++)
            if((a^b) > max)
                max = (a^b);        
    return max;
}
int main() {
    int res;
    int _l;
    scanf("%d", &_l);
    
    int _r;
    scanf("%d", &_r);
    res = maxXor(_l, _r);
    printf("%d", res);
    
    return 0;
}

HackerRank Day 0: Mean, Median, and Mode (Tutorials>10 Days of Statistics)

題目:
輸入n個正整數的陣列X，
輸出其平均值，中位數及眾數。
(如有多個眾數則取最小者)

輸入:
第一行為數字n，代表陣列的個數。
第二行為以空格隔開的n個正整數。
輸入限制10 <= N <= 2500，且每個正整數<=10的5次方。

輸出:
分三行輸出平均值(mean)，中位數(median)，眾數(mode)，
如解為小數，則輸出到第1位。

解題:
首先讀入後，先經過排序由小至大。
(這邊還是使用之前用過的qsort)

平均值->加起來除以n即可。

中位數->取n/2，整除的話，
答案是為x[n/2-1]+x[n/2+1-1]的一半，
否則解為x[(n+1)/2-1]。
(-1的原因是因為陣列由0開始，全部平移1單位)

留意%0.1lf可以保證輸出的小數點後面顯示1位。

眾數->在輸入值有限的狀況，使用類似bucket sort的方法。
直接開一個every_cnt[100000]並初始化，
接著依次讀出x[i]的值，並以every_cnt[x[i]]++達到記數的效果。
最後，遍歷各項有值的every_cnt，
經比較即可得出眾數為何。

這個方法較為占用記憶體，但除去前面sorting的部分，
後面進行記數以及查找均為線性的複雜度。
(記數為O(n)，查找為遍歷x[0]~10^5)


Code：

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

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

int main() {
    int n;
    scanf("%d\n", &n);
    int x[n];
    double mean = 0.0;
    for(int i = 0; i < n; i++)
    {    
        scanf("%d\n", &x[i]);
        mean += (double) x[i];
    }
    mean /= (double) n;
    printf("%0.1lf\n", mean);
    qsort((void *)x, n, sizeof(int), compare);    
    
    if(n % 2 == 1)
        printf("%d\n", x[(n+1)/2 - 1]);
    else
        printf("%0.1lf\n", (double)(x[n/2 - 1] + x[n/2+1-1])/2.0);
    
    int every_cnt[100000] = {0};
    int max_n = x[0];
    for(int i = 0; i < n; i++){
        every_cnt[x[i]]++;
    }
    
    for(int j = x[0]; j < 100000; j++)
    {
        if(every_cnt[j] == 0) 
            continue;
        if(every_cnt[j] > every_cnt[max_n])
            max_n = j;
    }    
        
    printf("%d\n", max_n);
    
    return 0;
}

HackerRank Non-Divisible Subset(Algorithms>Implementation)

題目:
給定一個由n個不同integer所成之集合S，
印出最大的子集合S'，當中S'必須符合以下條件:
S'中任意2元素之和無法被k所整除。

輸入:
第一行分別給入n, k，用空格隔開。
第二行給入n個數字，代表這個集合的所有元素。

輸出:
印出符合前述之最大可能的子集合S'的大小。

範例輸入:

4 3
1 7 2 4

輸出則為

3

解題:
思路請參照
http://cs.stackexchange.com/questions/57873/maximum-subset-pairwise-not-divisible-by-k

簡單來說，2個數的和能被k整除的話，
代表它們除以k的餘數和也能被k整除(同餘定理)。
舉例來說:
a = bk + c, d = ek + f
a+d = k(b+d) + c+f
前項當然能被k整除，那麼a+d能不能被k整除，
就要看c+f能不能被k整除。

知道這點的話，那麼除以k的餘數可能為0~k-1，
我們可以先分類記錄成一個陣列，
用來表示除以k的餘數為s_i的話，
num[s_i]有幾個。

當k是奇數的時候，兩個數要加起來能被k整除的話，
必然是一個比k/2小，一個比k/2大。
於是遍歷從1到比k/2小的整數，
for(int i = 1; i < k/2; i++)
檢查是num[i]比較大呢，還是num[k-i]比較大呢?
因為兩個互斥，我們就取比較大的放入S'中。

接著留意k是偶數的時候，由於餘數是k/2的話，
兩個一配起來就可以被k整除了，
所以在num[k/2]>0的狀況仍然只能取1個進S'中。
同樣的，餘數是0的狀況下也只能取1個進S'中。

由於在計算時k/2比較特殊，下面的code中有特別分開來計算，
請參閱下方的code。

另外特殊的case為n只有1個或k剛好是1的狀況，
這時候就只能取1個了!

這題在從頭仔細思考過一遍以後，
其實並不算太過複雜，
根本核心在於同餘的概念，
以及如何處理k/2的case。
難怪雖然是Easy Level，答對率卻並不是太高。

Code：

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

int main() {
    int n, k, result=0;
    scanf("%d %d",&n, &k);
    // Special case: 1. integer num only 1 -> result = 1; 
    //               2. divisor k = 1 -> result = 1
    if(n == 1 || k == 1){
        printf("%d", 1);
    }else{    
        int s_i, num[k];
        for(int i = 0; i < k; i++) 
            num[i] = 0;
        // Store num of those whose remainder is k' at num[k'].
        for(int arr_i = 0; arr_i < n; arr_i++){
           scanf("%d",&s_i);
           s_i %= k;
           num[s_i] += 1;
        }

        for(int i = 1; i < k/2; i++){
            if(num[i] > num[k-i])
                result += num[i];
            else
                result += num[k-i];
        }
        if(num[0] > 0) result++;
        if(k % 2 == 0){ 
            if(num[k/2] > 0)
                result++;
        }else{
            if(num[k/2] > num[k/2 + 1])
                result += num[k/2];
            else
                result += num[k/2 +1];
        } 
        printf("%d", result);
    }           
    
    return 0;
}

HackerRank Cut the sticks(Algorithms>Implementation)

題目:
給定N根樹枝，每根的長度均為正整數，
每次進行cut的操作直到所有的樹枝都被削減到最小的長度。
假設我們有6根樹枝，長度如下:

5 4 4 2 2 8

在一次cut的操作中，我們將6根樹枝都減去2的長度，
在下一次cut的操作之前就只有4根樹枝留下(非0長度的樹枝)，
其長度為:

3 2 2 6

重複上述的操作直到沒有樹枝留下。

輸入:
第一行包含1個integer N。
下一行為N個integers:a_0, a_1, ... a_N-1，以空格空開，
代表各樹枝的長度。

輸出:
在每次的操作中，印出當次有幾根樹枝被cut。

解題:
第一次肯定是全部的樹枝都會被cut，
而被cut成0的樹枝，就是當下長度最小的那幾根。
故，只要我們將樹枝由小到大排列，
就可以知道每次會被cut成0的樹枝數，
也就知道每次有幾隻樹枝會被cut。
我們直接使用ANSI C中的qsort進行排序。

qsort要分別提供陣列pointer，陣列長度，
陣列元素的大小，以及比較大小用的function。

底下這邊使用cut_num來計算每次cut有幾隻樹枝被cut掉，
再逐次以remain_num扣掉並印出來。

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; 
    scanf("%d",&n);
    int arr[n];
    for(int arr_i = 0; arr_i < n; arr_i++){
       scanf("%d",&arr[arr_i]);
    }
    qsort((void *)arr, n, sizeof(int), compare);
    int remain_num = n, cut_num = 1;
    printf("%d\n", remain_num);
    
    for(int i = 1; i < n ; i++){
        if (arr[i] > arr[i-1]){
            remain_num -= cut_num;
            printf("%d\n", remain_num);
            cut_num = 1;
        }else {
            cut_num++;
        }
    }
    return 0;
}

HackerRank Angry Professor(Algorithms>Implementation)

題目:
一個教授有一班N個學生的離散數學課，
由於學生缺乏紀律讓他感到很挫折，
玻璃心破碎的他決定如果出席的人數少於K人的話，
他就不上課了!

輸入data:
給定T個testcases，N(學生數量)，K(是否上課的門檻人數)
以及每個學生到課的時間點(小於0早到，大於0遲到)。
注意等於0仍視作在上課前到課。
例如:

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

表示有兩個test case，
case1:
4名學生，3名以上開課，
前2名學生早到，後2名學生遲到。
case2:
4名學生，2名以上開課，
前2名學生分別準時及早到，後2名學生遲到。

輸出:
如果該case為取消上課就印出YES，
否則印出NO，
如上例輸出應為

YES
NO

解題:
網站預設C Code讀進來的的陣列a[n]會在迴圈中被重置，
故直接在迴圈內進行判斷，
計算早到+準時到的學生數量(cnt)，
如果k > cnt則此testcase為取消上課，
紀錄到陣列result中，
隨後在外面判斷進行印出YES/NO出來即可。

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);
    bool result[t];
    for(int a0 = 0; a0 < t; a0++){
        int n; 
        int k; 
        scanf("%d %d",&n,&k);
        int a[n], cnt = 0;
        for(int a_i = 0; a_i < n; a_i++){
           scanf("%d",&a[a_i]);
           if(a[a_i] <= 0) cnt++; 
        }
        if (k > cnt)
            result[a0] = true;
        else
            result[a0] = false;
    }
    
    for(int a0 = 0; a0 < t; a0++){
        if(result[a0])
            printf("YES\n");
        else
            printf("NO\n");
    }    
    return 0;
}

HackerRank Divisible Sum Pairs(Algorithms>Implementation)

題目:
給定一個長度為n的integer陣列a_0, a_1, ... , a_n-1及一個正整數k，
找到並印出總共的i, j組合數目，
當中a_i + a_j可以被k所整除。

解題:
開出雙重迴圈即可遍歷所有組合。
a_0的搭配: a_1, a_2, ... , a_n-1
a_1的搭配: a_2, a_3, ... , a_n-1
以此類推可知，
第一個迴圈的條件為0 ~ n-2，
第二個迴圈的條件為i+1 ~n-1。
(i為第一個迴圈的當次起始值)

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 *a = malloc(sizeof(int) * n);
    for(int a_i = 0; a_i < n; a_i++){
       scanf("%d",&a[a_i]);
    }
    int cnt = 0;
    for(int i = 0; i < n-1; i++)
        for(int j = i+1; j < n; j++)
            if ((a[i]+a[j]) % k == 0) cnt++;

    printf("%d", cnt);
    
    return 0;
}

HackerRank Kangaroo(Algorithms>Implementation)

題目:
給定兩隻在x軸上往正方向移動的袋鼠，
起始座標分別為x1, x2，其速度分別為v1, v2，
當中 0 <= x1 < x2 <= 10000, 1 <= v1, v2 <= 10000,且均為integer.
若兩隻袋鼠有機會同時間在同座標相遇，印出"YES"，否則印出"NO"。

解題:
簡單的題目。
先考慮若v1 <= v2時，再怎麼樣也是追不上，可以直接印NO。
接下來就直接計算距離差/速度差能否整除(餘數為0)，
即可依此印出YES或NO。


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 x1; 
    int v1; 
    int x2; 
    int v2; 
    scanf("%d %d %d %d",&x1,&v1,&x2,&v2);
    if (v1 <= v2) {
        printf("NO");
    }else {
        if ((x2-x1)%(v1-v2) == 0)
            printf("YES");
        else
            printf("NO");
    }
        
    return 0;
}

HackerRank Start.

從今天起將會開始不定時解HackerRank的題目，
基本上主體會使用C語言，歡迎有興趣的朋友觀看及給予建議XD
 (因為有時候我解的方式可能也不是最好的)

[Android] Android Studio 2.0 with java8

在實際使用新的Android Studio 2.0後，
發現有好多都不認得了XD
不知道什麼時候冒出來的Gradle Script(天啊我到底埋在Driver層多久了)以外，
然後Android N也有preview了。

在build的時候，
由於電腦環境先前先裝過java7，而後升成java8，
在編譯一個單純的activity時可能會出現類似這樣的錯誤:

Unsupported major.minor version 52.0

經過查詢了一下， 最簡單的方式就是更改指定build的sdk路徑:
File->Project Stucture...

找到SDK Location頁籤中的JDK Location, 將其改成1.8的路徑即可。

當然，如果要降版使用1.7也是可以的，

只是這樣的話就要改Gradle Script.

於build.gradle裡面:

android { 
          compileSdkVersion 19
          buildToolsVersion "19.0.0"
    defaultConfig {
          minSdkVersion 7
          targetSdkVersion 19
    }
    compileOptions {
          sourceCompatibility JavaVersion.VERSION_1_7
          targetCompatibility JavaVersion.VERSION_1_7
    }
}

[Android] 回歸。

好久不見了，不曉得還有沒有朋友在看這個部落格。
最初的想法是將工作前及開始上班後，
所遇到的問題，來為自己整理一份how-to-solve.
但後來隨著忙碌及趕工，疏於回頭整理。
(同時被bug追著跑的感覺很差，尤其被前人的bug，哈哈)

總之呢，
最近應該會有一段比較不那麼緊迫的時間，
因應工作內容也許又要重新回到跟Application層相關的東西，
所以可能會寫一點在執行Android Studio 2.0相關的簡單操作方法吧XD

對於之前留言詢問問題的各位，
已經有一一做回覆，希望雖然有點晚了，
這些思路仍能幫助到您。

(不過話說，Blogger它能不能送留言通知到我email信箱呀?
真的很容易沒注意到有新留言XD)

大概就先這樣~