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

沒有留言:

張貼留言