Jump to content

ONI 2009 - Qualificação - Problema A


Joao brandao
 Share

Recommended Posts

Boas pessoal, estava a resolver um exercicio das olimpiadas de 2009 e com a minha submissao apenas obtive 62 pontos. A questão que coloco é se me podem ajudar a melhorar o algoritmo em si dando outras ideias de fazer o mesmo exercicio ou pegar na resoluçao que se encontra ai em baixo e melhor um pouco.

Enunciado: http://www.dcc.fc.up.pt/oni/problemas/2009/qualificacao/probA.html

#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
     vector <int>vect;
     vector <unsigned int>maiores;
      int num,prenum,c,f,np,maior=-1;
cin>>np;
for(int i=1;i<=np;i++)
{
        cin>>num;
        vect.push_back(num);
}
        cin>>prenum;
        for(int j=1;j<=prenum;j++)
        {
        cin>>c>>f;
        for(int i=c-1;i<=f-1;i++)
        {   
           if(vect[i]>=maior)
           {
             if(vect[i]>maior)
             {
               maior=vect[i];
               maiores.clear();
             }
             if(vect[i]==maior)
             maiores.push_back(i);
           }
        }
        cout<<maior;
        maior=-1;
        for(unsigned int i=0;i<=maiores.size()-1;i++)
        {
          cout<<" "<<maiores[i]+1;
        }
        cout<<endl;
        maior=-1;
        maiores.clear();
        }
    return 0;
}

Link to comment
Share on other sites

Nao pensei muito a serio no problema.

Ve la se consegues fazer com que passes no array das alturas dos edificios sequencialmente, uma so vez.

Talvez ordenar as fotos pelo primeiro edificio ajude ...

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Tens o array das alturas dos predios, por exemplo: 350 150 200 400 831 450 200 350 100 350

O que eu dizia era para percorreres o array de alturas sequencialmente e calculares a altura maxima para cada foto: assim so passarias em cada edificio uma vez.

Mais ou menos assim para as fotos (4 a 7), (6 a 9), e (2 a 5):

Edificio 1: nao e preciso para nada

Edificio 2: foto 3: max 150 @ 2

Editifio 3: foto 3: max 200 @ 3

Edificio 4: foto 1: max 400 @ 4 --- foto 3: max 400 @ 4

Edificio 5: foto 1: max 831 @ 5 --- foto 3: max 831 @ 5

Edificio 6: foto 1: nao muda max --- foto 2: max 450 @ 6

Edificio 7: foto 1: nao muda max --- foto 2: nao muda max

Edificio 8: foto 2: nao muda max

Edificio 9: foto 2: nao muda max

Edificio 10: nao e preciso para nada

Agora imprimes os resultados

Foto 1 -- 831 @ 5

Foto 2 -- 450 @ 6

Foto 3 -- 831 @ 5

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Podes associar a cada altura a sua posição e depois fazeres uma ordenação, percorres o vetor ordenado até que a posição (do edifício na foto) da posição do vetor onde te encontras esteja compreendida entre os intervalos dados

Exemplo:

10

350 150 200 400 831 450 200 350 100 350

a cada um desses valores das a sua posição na foto:

831 corresponde ao 5;

450 corresponde ao 6;

400 corresponde ao 4;

350 corresponde ao 1, 8, 10;

200 corresponde ao 3, 7;

150 corresponde ao 2;

100 corresponde ao 9;

Ordenas o teu vetor e ele fica: 831 450 400 350 350 350 200 200 150 100

                     

Percorres o vetor ordenado e se a posição a que ele corresponde estiver entre os intervalos dados então podes imprimir, tens também de verificar se os valores que vêm a frente são iguais a ele e se estão entre os intervalos dados, se isso ocorrer então tens de imprimir a sua posição também.

Link to comment
Share on other sites

Eu quando o ano passado treinava, resolvi da seguinte forma:

1(preprocessamento)- Guardar a melhor fotografia para as fotografias que pertencas a conjuntos na forma [224n,224(n+1)[, n€N. Ou seja, guarda a melhor fotografia para os blocos:

0, 224

225, 448

...

na array M[225]

2- Para cada fotografia, calculas o maior edificio, utilizando o préprocessamento:

2.1-Ex1:

Imagina que queriam a melhor fotografia entre 3, 2248;

Entao, podias aproveitar os cálculos que já tinhas feito e fazer (nota que a seguinte notacao não representa nenhuma linguagem de programacao em especifico):

ans = std::max(E[3...224],M[1...9],E[2240...2248]);

Assim, apenas tens de fazer (sqrt(N)+448)*F calculos para o pior caso, o que passa no tempo.

Edit: Enganei-me no numero de edificios.

<Signature goes here>

Link to comment
Share on other sites

As soluções para 100 pontos dos problemas das ONI são, normalmente, bastante complicadas. Muito poucos alunos universitários os conseguiriam resolver, portanto não se sintam mal quando encontram uma solução mais difícil do que o que estavam à espera.

Resta ler, reler e implementar.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.