ZeroJudge E541: Where is the marble

UVa 10474 – Where is the marble

Raju and Meena enjoy playing with marbles. They have many marbles with numbers written on them.
Initially, Raju arranges the marbles in ascending order according to the numbers written on them.
Then, Meena requests Raju to find the first marble with a specified number.
If Raju succeeds, he earns one point. If Raju fails, Meena earns one point.
After several inquiries, the game ends, and the player with the highest score wins.
Today, you have the opportunity to help Raju. But don't underestimate Meena; she has written a program to track how much time it takes for you to provide all the answers.
Therefore, you must also write an efficient program to ensure victory.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF input, each test case begins with two integers N and Q.
N represents the number of marbles, and Q represents the number of Meena's queries.
If N = Q = 0, it indicates the end of the input.
Next, N lines contain the numbers written on the N marbles. These marble numbers may appear in any order.
Following that, Q lines will perform Q queries. All numbers are <= 10000 and are not negative.		For each test case, output the test case number.
For each query, if the marble with the number x is found at position y, output "x found at y".
If there is no marble with the number x, output "x not found".
4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0		CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3
ZeroJudge E541 範例測資

Thought Process

First, collect the numbers of the N marbles into an array and sort it. Then, declare a Map and run a for loop from 0 to N-1. If Map[array[i]] is 0, then assign Map[array[i]] = i + 1. This is because if a number appears more than once, we need to take the position of the first occurrence, so we need to check if a position for a number already exists in the Map.

When outputting, check if the number to be queried exists in the Map. If Map[number] == 0, it means the number is not found, so output "not found". Otherwise, output Map[number].

Sample Code－ZeroJudge E541: Where is the marble

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, Q, count = 1;
    while (cin >> N >> Q && N != 0 && Q != 0)
    {
        vector<int>num;
        for (int i = 0; i<N; i++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        sort(num.begin(), num.end());
        map<int, int>MAP;
        for (int i = 0; i<N; i++)
        {
            if (MAP[num[i]] == 0) MAP[num[i]] = i+1;
        }
        cout << "CASE# " << count << ":\n";
        for (int i = 0; i<Q; i++)
        {
            int tmp;
            cin >> tmp;
            if (MAP[tmp] == 0) cout << tmp << " not found\n";
            else cout << tmp << " found at " << MAP[tmp] << "\n";
        }
        count++;
    }
}

//ZeroJudge E541
//Dr. SeanXD
Tags

Related Posts

Comments