simulation_frog.c

simulation_frog.c

#include <stdio.h>
#include <string.h>

void simulate(int instruction[], int n, int pos, int dir)
{
    int seen[n][2]; // if you land at a location and face the same direction as
    // your previous visit -> cycle
    memset(seen, -1, sizeof(seen));
    if (dir == -1) // change -1 to 0, so we can use array with ease
        dir = 0;

    int cur = 0, k = -1;
    while (0 <= pos && pos < n) {
        cur++;
        if (seen[pos][dir] == -1) { // not visited before
            seen[pos][dir] = cur;

            int orig = pos; // if you don't store this value, you can not update dir
            // at line 32 correctly since your pos is already changed
            if (instruction[pos] > 0) {
                if (dir == 1)
                    pos += instruction[pos];
                else
                    pos -= instruction[pos];
            } else {
                if (dir == 1)
                    pos -= -instruction[pos];
                else
                    pos += -instruction[pos];
            }

            if (instruction[orig] < 0)
                dir = dir == 0 ? 1 : 0;
        } else {
            k = cur - seen[pos][dir];
            break;
        }
    }

    if (pos < 0)
        printf("Backward\n");
    else if (pos >= n)
        printf("Forward\n");
    else
        printf("Cycle %d\n", k);
}

void solve(int n, int m)
{
    int instruction[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &instruction[i]);

    for (int i = 0; i < m; i++) {
        int pos, dir;
        scanf("%d %d", &pos, &dir);

        simulate(instruction, n, pos, dir);
    }
}

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && (n || m))
        solve(n, m);

    return 0;
}