URI - 1025 - Estruturas e Bibliotecas - Onde está o Mármore? - C++

Plataforma: URI

Problema: 1025

Enunciado:

Raju e Meena adoram jogar um jogo diferente com pequenas peças de mármores, chamados Marbles. Eles têm um monte destas peças com números escritos neles. No início, Raju colocaria estes pequenos mármores um após outro em ordem ascendente de números escritos neles. Então Meena gostaria de pedir a Raju para encontrar o primeiro mármore com um certo número. Ele deveria contar 1...2...3. Raju ganha um ponto por cada resposta correta e Meena ganha um ponto se Raju falha. Depois de um número fixo de tentativas, o jogo termina e o jogador com o máximo de pontos vence. Hoje é sua chance de jogar com Raju. Sendo um/a cara esperto/a, você tem em seu favor o computador. Mas não subestime Meena, ela escreveu um programa para monitorar quanto tempo você levará para dar todas as respostas. Portanto, agora escreva o programa, que ajudará você em seu desafio com Raju.

Linguagem: C++

Solução:

#include <cstdlib>
#include <iostream>
using namespace std;
int compara(const void *a, const void *b) {
   return (*(int*)a - *(int*)b);
}
int main() {
    int n, q, i, consultas[10000], valores[10000], caso = 1, inicio, meio, fim;
    while (cin >> n >> q) {
        if (!n && !q)
            break;
        for (i = 0; i < n; i++)
            cin >> valores[i];
        for (i = 0; i < q; i++)
            cin >> consultas[i];
        qsort(valores, n, sizeof(int), compara);
        cout << "CASE\# " << caso++ << ":" << endl;
        for (i = 0; i < q; i++) {
            inicio = 0;
            fim = n - 1;
            meio = (inicio + fim) / 2;
            while (inicio <= fim) {
                if (valores[meio] < consultas[i])
                    inicio = meio + 1;
                else if (valores[meio] == consultas[i]) {
                    while (valores[meio - 1] == consultas[i] && meio)
                        meio--;
                    cout << consultas[i] << " found at " << meio + 1 << endl;
                    break;
                }
                else
                    fim = meio - 1;
                meio = (inicio + fim)/2;
            }
            if (inicio > fim)
                cout << consultas[i] << " not found" << endl;
        }
    }
    return 0;
}

URI - 1025 - Estruturas e Bibliotecas - Onde está o Mármore? - C

Plataforma: URI

Problema: 1025

Enunciado:

Raju e Meena adoram jogar um jogo diferente com pequenas peças de mármores, chamados Marbles. Eles têm um monte destas peças com números escritos neles. No início, Raju colocaria estes pequenos mármores um após outro em ordem ascendente de números escritos neles. Então Meena gostaria de pedir a Raju para encontrar o primeiro mármore com um certo número. Ele deveria contar 1...2...3. Raju ganha um ponto por cada resposta correta e Meena ganha um ponto se Raju falha. Depois de um número fixo de tentativas, o jogo termina e o jogador com o máximo de pontos vence. Hoje é sua chance de jogar com Raju. Sendo um/a cara esperto/a, você tem em seu favor o computador. Mas não subestime Meena, ela escreveu um programa para monitorar quanto tempo você levará para dar todas as respostas. Portanto, agora escreva o programa, que ajudará você em seu desafio com Raju.

Linguagem: C

Solução:

#include <stdlib.h>
#include <stdio.h>
int compara(const void *a, const void *b) {
   return ( *(int*)a - *(int*)b);
}
int main() {
    int n, q, i, consultas[10000], valores[10000], caso = 1, inicio, meio, fim;
    while (scanf("%d %d", &n, &q) != EOF) {
        if (!n && !q)
            break;
        for (i = 0; i < n; i++)
            scanf("%d", &valores[i]);
        for (i = 0; i < q; i++)
            scanf("%d", &consultas[i]);
        qsort(valores, n, sizeof(int), compara);
        printf("CASE\# %d:\n", caso++);
        for (i = 0; i < q; i++) {
            inicio = 0;
            fim = n - 1;
            meio = (inicio + fim) / 2;
            while (inicio <= fim) {
                if (valores[meio] < consultas[i])
                    inicio = meio + 1;
                else if (valores[meio] == consultas[i]) {
                    while (valores[meio - 1] == consultas[i] && meio)
                        meio--;
                    printf("%d found at %d\n", consultas[i], meio+1);
                    break;
                }
                else
                    fim = meio - 1;
                meio = (inicio + fim)/2;
            }
            if (inicio > fim)
                printf("%d not found\n", consultas[i]);
        }
    }
    return 0;
}