UVa : 10474 (Where is the Marble?)


Title : Where is the Marble?

Link : http://uva.onlinejudge.org/external/104/10474.html

Tricky Lines :

  1. place the marbles one after another in ascending order
  2. Be assured, none of the input numbers are greater than 10000 and none of them are negative.

Analysis :

  1. Data type : integer
  2. Total number of marbles : <= 10000
  3. Use STL sort or quick sort (stdlib.h)
  4. if a marble’s number is greater than query then break immediately.

Runtime : 0.572s

Critical Input : 
5 2
2
2
3
3
3
1
4
0 0

Critical Output : 
CASE# 1:
1 not found
4 not found

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;

int main ()
{
    int n, q;
    int cases = 0;

    while ( scanf ("%d %d", &n, &q) ) {
        if ( n == 0 && q == 0 ) break;

        int a [10000 + 10];

        for ( int i = 0; i < n; i++ ) scanf ("%d", &a [i]);

        sort (a, a + n);

        printf ("CASE# %d:\n", ++cases);

        int query;
        bool found;

        for ( int i = 0; i < q; i++ ) {
            scanf ("%d", &query);
            found = false;
            for ( int j = 0; j < n; j++ ) {
                if ( a [j] == query ) {
                    printf ("%d found at %d\n", query, j + 1);
                    found = true;
                    break;
                }
                else if ( a [j] > query ) break;
            }

            if ( !found ) printf ("%d not found\n", query);
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE

One thought on “UVa : 10474 (Where is the Marble?)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s