2016年9月12日 星期一

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

2016年9月11日 星期日

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

2016年9月5日 星期一

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

2016年9月2日 星期五

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

2016年9月1日 星期四

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

2016年8月30日 星期二

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

2016年8月28日 星期日

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

2016年4月13日 星期三

[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)

大概就先這樣~

2015年4月13日 星期一

[Linux] linux搜尋小技巧

一般狀態下我們會用find -iname 來找出指定名稱的檔案或資料夾,
以grep -r 來遞迴式搜尋字串,但grep -r 其實無法非常完整的遞迴,
下面利用xargs將前面使用的資料傳遞到後面當作參數的特性,
來進行較快速且較完整的字串搜尋。

find -iname "*"|xargs grep "reboot" // reboot替代成你想要搜尋的字串

在*處進行一些處理就可以進行其他簡單的篩選。
比如只找c語言的檔案: "*.c"