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

沒有留言:

張貼留言