# 1025 - Onde está o Mármore?

## Descrição

{% embed url="<https://www.urionlinejudge.com.br/judge/pt/problems/view/1025>" %}

## Solução

O problema consiste de ordenar todos os mármores em ordem crescente e ir respondendo qual a primeira posição de um determinado número de mármore.

Para solucioná-lo, podemos usar duas diferentes abordagens:

* Ordenar o vetor de mármores e fazer cada consulta com pesquisa binária, com complexidade O(log n) de tempo para cada consulta
* Acumular todos os valores de mármore em um vetor auxiliar, usando-o para contar quantos mármores de cada tem na entrada (ver [Counting sort](/solucoes-da-beecrowd/base-teorica/estruturas-e-bibliotecas/ordenacao.md#counting-sort)) para poder fazer as consultas em tempo O(1) (mas com gasto de espaço proporcional ao maior N possível)

{% hint style="warning" %}
Na versão em JavaScript, usar `lines.shift()` é lento demais, então tive que utilizar o acesso direto.
{% endhint %}

### Alternativa 1 - Pesquisa Binária

|              |                     |
| ------------ | ------------------: |
| Complexidade | Notação assintótica |
| Tempo        |            O(log n) |
| Espaço       |                O(1) |

{% tabs %}
{% tab title="C99" %}

```c
#include <stdlib.h>
#include <stdio.h>

int comp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int pesquisaBinaria(int *v, int n, int valor)
{
    int inicio = 0, fim = n, meio;

    while (inicio < fim)
    {
        meio = (inicio + fim) / 2;

        if (v[meio] < valor)
            inicio = meio + 1;
        else
            fim = meio;
    }

    return v[inicio] == valor ? inicio + 1 : -1;
}

int main()
{
    int *marmores;
    int T, N, Q, consulta, resposta;

    T = 1;
    while (scanf("%d %d", &N, &Q))
    {
        if (!N && !Q)
            break;

        marmores = (int *)malloc(sizeof(int) * N);
        for (int i = 0; i < N; ++i)
        {
            scanf("%d", &marmores[i]);
        }

        qsort(marmores, N, sizeof(int), comp);

        printf("CASE# %d:\n", T++);
        for (int i = 0; i < Q; ++i)
        {
            scanf("%d", &consulta);

            resposta = pesquisaBinaria(marmores, N, consulta);

            if (resposta == -1)
                printf("%d not found\n", consulta);
            else
                printf("%d found at %d\n", consulta, resposta);
        }

        free(marmores);
    }

    return 0;
}
```

{% endtab %}

{% tab title="C++17" %}

```cpp
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> marmores;
    int T, N, Q, consulta;

    T = 1;
    while (cin >> N >> Q)
    {
        if (!N && !Q)
            break;

        marmores.assign(N, 0);
        for (int i = 0; i < N; ++i)
        {
            cin >> marmores[i];
        }

        sort(marmores.begin(), marmores.end());

        cout << "CASE# " << T++ << ":" << endl;
        for (int i = 0; i < Q; ++i)
        {
            cin >> consulta;

            vector<int>::iterator it = lower_bound(marmores.begin(), marmores.end(), consulta);

            if (it == marmores.end() || *it != consulta)
                cout << consulta << " not found" << endl;
            else
                cout << consulta << " found at " << (it - marmores.begin()) + 1 << endl;
        }
    }

    return 0;
}
```

{% endtab %}

{% tab title="JavaScript 12.18" %}

```javascript
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.trim().split('\n');

const comp = (a, b) => a - b;

const pesquisaBinaria = (v, valor) => {
    let [inicio, fim, meio] = [0, v.length, 0];

    while(inicio < fim)
    {
        meio = Math.floor((inicio + fim)/2);

        if(v[meio] < valor)
            inicio = meio + 1;
        else
            fim = meio;
    }

    return inicio < v.length && v[inicio] === valor ? inicio + 1 : -1;
};

lines.pop();

let T = 1, p = 0;
while(p < lines.length){
    let [N, Q] = lines[p++].trim().split(' ').map((x) => parseInt(x));

    let marmores = [];
    for(let i = 0; i < N; ++i){
        marmores.push(parseInt(lines[p++].trim()));
    }

    marmores.sort(comp);

    console.log(`CASE# ${T++}:`);
    for(let i = 0; i < Q; ++i){
        let consulta = parseInt(lines[p++].trim());

        let resposta = pesquisaBinaria(marmores, consulta);

        if(resposta === -1)
            console.log(`${consulta} not found`);
        else
            console.log(`${consulta} found at ${resposta}`);
    }
}
```

{% endtab %}

{% tab title="Python 3.9" %}

```python
def pesquisaBinaria(v, valor):
    inicio, fim, meio = 0, len(v), 0

    while(inicio < fim):
        meio = (inicio + fim)//2

        if(v[meio] < valor):
            inicio = meio + 1
        else:
            fim = meio

    return inicio + 1 if inicio < len(v) and v[inicio] == valor else -1


T = 1
while True:
    try:
        N, Q = [int(x) for x in input().strip().split(' ')]

        if(N == 0 and Q == 0):
            break

        marmores = []
        for _ in range(N):
            marmores.append(int(input()))

        marmores.sort()

        print(f'CASE# {T}:')
        T += 1
        for _ in range(Q):
            consulta = int(input())

            resposta = pesquisaBinaria(marmores, consulta)

            if(resposta == -1):
                print(f'{consulta} not found')
            else:
                print(f'{consulta} found at {resposta}')
    except EOFError:
        break

```

{% endtab %}
{% endtabs %}

### Alternativa 2 - Contando os mármores

É importante notar que não sabemos o valor máximo `m` que N pode assumir.

|              |                     |
| ------------ | ------------------: |
| Complexidade | Notação assintótica |
| Tempo        |                O(1) |
| Espaço       |                O(m) |

{% tabs %}
{% tab title="C99" %}

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

int main()
{
    int marmores[10000];
    int T, N, Q, x, consulta;

    T = 1;
    while (scanf("%d %d", &N, &Q))
    {
        if (!N && !Q)
            break;

        memset(marmores, 0, sizeof(marmores));

        for (int i = 0; i < N; ++i)
        {
            scanf("%d", &x);

            marmores[x] += 1;
        }

        for (int i = 1; i < 10000; ++i)
        {
            marmores[i] += marmores[i - 1];
        }

        printf("CASE# %d:\n", T++);
        for (int i = 0; i < Q; ++i)
        {
            scanf("%d", &consulta);

            if (marmores[consulta] == marmores[consulta - 1])
                printf("%d not found\n", consulta);
            else
                printf("%d found at %d\n", consulta, marmores[consulta - 1] + 1);
        }
    }

    return 0;
}
```

{% endtab %}

{% tab title="C++17" %}

```cpp
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int T, N, Q, x;
    vector<int> marmores;

    T = 1;
    while (cin >> N >> Q)
    {
        if (!N && !Q)
            break;

        marmores.assign(10000, 0);
        for (int i = 0; i < N; ++i)
        {
            cin >> x;

            marmores[x] += 1;
        }

        for (int i = 1; i < 10000; ++i)
        {
            marmores[i] += marmores[i - 1];
        }

        cout << "CASE# " << T++ << ":" << endl;
        for (int i = 0; i < Q; ++i)
        {
            cin >> x;

            if (marmores[x] == marmores[x - 1])
                cout << x << " not found" << endl;
            else
                cout << x << " found at " << marmores[x - 1] + 1 << endl;
        }
    }

    return 0;
}
```

{% endtab %}

{% tab title="JavaScript 12.18" %}

```javascript
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.trim().split('\n');

lines.pop();

let T = 1, p = 0;
let marmores = Array(10000);
while(p < lines.length){
    let [N, Q] = lines[p++].trim().split(' ').map((x) => parseInt(x));

    marmores.fill(0);
    for(let i = 0; i < N; ++i){
        let x = parseInt(lines[p++].trim());

        marmores[x] += 1;
    }

    for(let i = 1; i < 10000; ++i){
        marmores[i] += marmores[i - 1];
    }

    console.log(`CASE# ${T++}:`);
    for(let i = 0; i < Q; ++i){
        x = parseInt(lines[p++].trim());

        if(marmores[x] === marmores[x - 1])
            console.log(`${x} not found`);
        else
            console.log(`${x} found at ${marmores[x - 1] + 1}`);
    }
}
```

{% endtab %}

{% tab title="Python 3.9" %}

```python
T = 1
while True:
    try:
        N, Q = [int(x) for x in input().strip().split(' ')]

        if(N == 0 and Q == 0):
            break

        marmores = [0 for _ in range(10000)]
        for _ in range(N):
            marmores[int(input())] += 1

        for i in range(1, 10000):
            marmores[i] += marmores[i - 1]

        print(f'CASE# {T}:')
        T += 1
        for _ in range(Q):
            x = int(input())

            if(marmores[x] == marmores[x - 1]):
                print(f'{x} not found')
            else:
                print(f'{x} found at {marmores[x - 1] + 1}')
    except EOFError:
        break

```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xtecna.gitbook.io/solucoes-da-beecrowd/estruturas-e-bibliotecas/1025-onde-esta-o-marmore.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.