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