One interesting c++ problem

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by rabbitroger, 12 Jul 2021.

  1. rabbitroger

    rabbitroger New Member

    Joined:
    10 Jul 2021
    Messages:
    2
    Likes Received:
    0
    Reputations:
    0
    Hi, guys, my son just finished his elementary shcool life, prepared for his junior middle school. Very hard to compete wiht his mates now in Beijing of China, the junior middle school release some problems for them to solve so as to sort the excellent ones out, here are one sample problem. It took me about two hours to make thourgh this problem with C++.

    RUNNING TRIPLETS

    There are nine teams of runners, with three runners in each team. Each team wear uniforms with the same number. They crossed the finish line such that each team's second team member to finish was separated from his teammates by a number of other runners equal to his uniform number, as show below,

    * * * 2 * * 2 * * 2 * * * * * * * *
    (Note every asterisk represents a runner, digit 2 represents the number 2 team runner)

    Team number 2's middle finisher is separated from his teammates by two runners on each side at the finish. (Note that these are not necessaryily the places in which the members of team 2 finished.)

    The same principle applies to the other numbered teams. Given that a member of team 1 won the race, can you figure out how they all crossed the finish line? Is there at least one solution to this puzzle? (No two or more runners cross the finish line in the same time.)

    Later I would post my code here. :)
     
  2. rabbitroger

    rabbitroger New Member

    Joined:
    10 Jul 2021
    Messages:
    2
    Likes Received:
    0
    Reputations:
    0
    Okay, here are the snippet code,
    #define RUNNER_TEAM_SIZE 9
    #define RUNNER_TEAM_RUNNER 3
    #define RUNNER_SIZE RUNNER_TEAM_SIZE * RUNNER_TEAM_RUNNER
    int arrPos[RUNNER_SIZE] = { 0 };
    //int arrOccupied[RUNNER_SIZE] = { 0 };
    int arrMap[RUNNER_TEAM_SIZE+1] = { 0 };
    int iCount = 0;

    bool checkValid(int pos, int iNumber)
    {
    bool Ret = false;
    int next = pos + iNumber + 1;
    int end = next + iNumber + 1;
    do
    {
    if (arrMap[iNumber] > 0)
    break;

    if (pos >= RUNNER_SIZE || next >= RUNNER_SIZE
    || end >= RUNNER_SIZE)
    break;

    if (arrPos[pos] > 0 || arrPos[next] > 0 ||
    arrPos[end] > 0)
    break;

    arrPos[pos] = arrPos[next] = arrPos[end] = iNumber;
    arrMap[iNumber] = true;
    Ret = true;
    } while (false);
    return Ret;
    }

    void revert(int pos, int iNumber)
    {
    int next = pos + iNumber + 1;
    int end = next + iNumber + 1;

    arrPos[pos] = arrPos[next] = arrPos[end] = 0;
    arrMap[iNumber] = false;
    }

    void dfs(int iLevel, int next)
    {
    int i = 0;
    int pos = 0;
    //
    if (iLevel == RUNNER_TEAM_SIZE)
    {
    // match
    for (i = 0; i < RUNNER_SIZE; i++)
    printf("%d ",arrPos);

    iCount++;
    printf("\n");
    return;
    }
    if (iLevel > RUNNER_TEAM_SIZE)
    return;

    for (i = next; i < RUNNER_SIZE; i++)
    {
    if (arrPos == 0)
    {
    pos = i;
    break;
    }
    }

    if (pos < RUNNER_SIZE)
    {
    for (i = 1; i < 10; i++)
    {
    if (checkValid(pos, i))
    {
    dfs(iLevel + 1,pos+1);
    // successfully stuff the arry, need revert
    revert(pos, i);
    }
    }
    }
    }

    int main()
    {

    arrMap[1] = true;
    arrPos[0] = arrPos[2] = arrPos[4] = 1;
    int iLevel = 0;
    int iPos = 1;
    iLevel++;
    dfs(iLevel, iPos);

    return 0;
    }

    Output:
    1 8 1 9 1 5 2 6 7 2 8 5 2 9 6 4 7 5 3 8 4 6 3 9 7 4 3
    1 9 1 2 1 8 2 4 6 2 7 9 4 5 8 6 3 4 7 5 3 9 6 8 3 5 7
    1 9 1 6 1 8 2 5 7 2 6 9 2 5 8 4 7 6 3 5 4 9 3 8 7 4 3
     
Loading...