2014年7月16日水曜日

Lesson 2: FrogRiverOne (Frog River One)

What you need to do is to check the input ArrayA until leaves fall on all the positions from 1 to X. So the strategy is to use flags to check if any leave fell there. 

If the leaves fell on all the positions from 1 to X, the time T when the last leave fell on a certain position (between 1 to X) is the answer.







int solution(int X, int A[], int N) 
{
    //the array to store flags
    int B[X];

    //clear the flags.
    memset(B, 0x00, sizeof(B[0]) * X);
    
    //let leaves fall!
    int t;
    int cnt = 0;
    int ans = -1;
    for (t = 0; t < N; t++){
        //get the position where a leave fall at time T. 
        int p = A[t] - 1; //(the array B is from 0 to X-1)
        //if it is between 0 to X-1 and 
        //no leave has fallen onto the position before, count it.
        if (p < X && B[p] == 0){
            B[p] = 1;
            cnt++;
            //is the route filled with leaves?
            if (cnt == X){
                ans = t;
                break;
            }
        }
    }

    return ans;
}

0 件のコメント:

コメントを投稿