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
 (因為有時候我解的方式可能也不是最好的)