URI PROBLEMA 2663 - Fase SOLUÇÃO EM C

URI Online Judge | 2663

Fase

Por Maratona de Programação da SBC – 2017  Brazil

Timelimit: 1

Em diversas competições acadêmicas, como a Olimpíada Brasileira de Informática (OBI), uma certa quantidade de competidores se classifica de uma fase para a fase seguinte, garantindo uma das vagas disponíveis. Entretanto, normalmente essa quantidade é variável, pois dada uma certa quantidade mínima de classificados, é frequente que haja empate na última vaga de classificação. Neste caso, é comum que todos os competidores empatados na última colocação se classifiquem.

Sua tarefa é ajudar a calcular o número de competidores classificados para a próxima fase. Você receberá uma lista de pontuações obtidas pelos competidores e o número mínimo de vagas para a fase seguinte e você deve decidir quantos competidores de fato vão se classificar.

Entrada

A primeira linha da entrada contém um número inteiro N, 1 ≤ N ≤ 1000, representando o número de competidores. A segunda linha conterá um inteiro K, 1 ≤ K ≤ N, indicando o número mínimo de competidores que devem se classificar para a próxima fase. Em seguida, N linhas conterão, cada uma um número entre 1 e 1000, inclusive, correspondente á pontuação de um competidor.

Saída

Seu programa deve imprimir uma linha, contendo o número de classificados para a próxima fase.

#include <stdio.h>

int w[1002];

void intercala (int v[],int p,int q,int r)

{

    int i,j,k = 0;

    i = p;

    j = q;

    while(i < q && j < r)

    {

        if(v[i] >= v[j])

            w[k++] = v[i++];

        else

        {

            w[k++] = v[j++];

        }

    }

    while(i < q) w[k++] = v[i++];

    while(j < r) w[k++] = v[j++];

    for (i = p; i < r; i++)

        v[i] = w[i-p];

}

void Mergesort(int v[],int p,int r)

{

    int q;

    if(p < r-1)

    {

        q = (p+r)/2;

        Mergesort(v,p,q);

        Mergesort(v,q,r);

        intercala(v,p,q,r);

    }

}

int vet[1005];

int verifica(int a,int i,int f)

{

    int j,c=0;

    for(j=i; j<f; j++)

    {

        if(vet[j]==a)

        {

            c++;

        }

    }

    return c;

}

int main()

{

    int m,n,i,aux=0;

    scanf("%d%d",&m,&n);

    for(i=0; i<m; i++)

    {

        scanf("%d",&vet[i]);

    }

    Mergesort(vet,0,m);

    aux=verifica(vet[n-1],n,m);

    printf("%d\n",aux+n);

    return 0;

}