Jump to content
Sign in to follow this  
xtrm0

Oni 2009 - Problema C (Comprar Pixels)

Recommended Posts

mogers

Btw, numa prova até é relativamente raro conseguir-se os 100 pontos nos problemas. Qual seria a melhor solução em que pensaste?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Pensei em duas.:

A primeira era testar todas as possibilidades. Tipo por tentar pôr no 1x1, depois no 1x2, etc

A segunda era quando punha os quadrados, marcava todos os pixels que se encontrassem a uma distancia menor que o lado do quadrado com um -1. E depois se esses pontos fossem marcados outra vez punha-lhes um -2 e depois não o testava. Só que assim tinha de ter uma matriz de  1000000*1000000. Mesmos que fizesse com duas matrizes bool não dava.


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Tenta desenvolver a 1ª ideia. Se fizeres isso de forma inteligente consegues 60 pontos, o que já era muito bom se fosse numa prova. (considero que era um problema dificil)

Para os 100 pontos tens de perceber que não precisas de testar todas as possibilidades da grelha. Mas desenha uns exemplos que talvez te ajude a perceber.

PS: Os limites dos problemas às vezes dão dicas acerca da complexidade da solução esperada para os 100 pontos.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Tamos a falar no irc, e talvez dê se fizer assim:

1-guardar os rectangulos num vector.

Ciclo: ir testando todas as possibilidades, se der cout. Se bater num rectangulo, avançar até ao fim do rectangulo, ou até à linha seguinte.

Achas que dà para os 100p?


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Achas que dà para os 100p?

Isso não melhora nada (ou melhor, não melhora substancialmente o runtime para que tenhas mais pontos). Continuas nos 60, isto se implementares uma solução O(L*C).

Deviam começar por tentar os 60 e depois tentar subir. (conseguir os 60 não é trivial)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
mogers

Então, nenhum dos que tava no irc submeteu?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Parece que não.

Já cheguei a algum lado com o código (acho eu 😳), mas dá sempre 1 1.

#include <iostream>
#include <vector>
#define max(a, b)  (a > b) ? a : b
using namespace std;

struct rectangulo {
   int x, y, x2, y2;
};
struct nvrc {
   int l, c;
};
vector <rectangulo> rect;
int X,Y;
int intersecta(nvrc tr) {
   int sz = rect.size();
   int maxdis=-1;
   for (int i=0; i<sz; i++) {
       if (X >= rect[i].x  && X <= rect[i].x2 && Y >= rect[i].y && Y <= rect[i].y2) {
           maxdis= max(maxdis, rect[i].x2-X);
       } else {
           if (tr.c+X >= rect[i].x  && tr.c+X <= rect[i].x2 && Y >= rect[i].y && Y <= rect[i].y2) {
               maxdis= max(maxdis, rect[i].x2-X);
           } else {
               if (X >= rect[i].x  && X <= rect[i].x2 && tr.l + Y >= rect[i].y && tr.l + Y <= rect[i].y2) {
                   maxdis= max(maxdis, rect[i].x2-X);
               } else {
                   if (tr.c+X >= rect[i].x  && tr.c+X <= rect[i].x2 && tr.l + Y >= rect[i].y && tr.l + Y <= rect[i].y2) {
                       maxdis= max(maxdis, rect[i].x2-X);
                   }
               }
           }
       }
       cout << rect[i].x2-X << endl;
//        cout << rect[i].x << " " <<  rect[i].y << endl;
   }
//    cout << endl << maxdis << endl;
   return maxdis;
}


int programa() {
   rect.clear();
   rectangulo trect;
   nvrc nr;
   int L, C, R;
   int rin;
   cin >> L >> C;
   cin >> nr.l >> nr.c;
   cin >> R;
   for (int i=0; i < R; i++) {
       cin >> trect.y >> trect.x >> trect.y2 >> trect.x2;
       rect.push_back(trect);
   }
   for (Y=1; Y<=L; Y++) {
     for (X=1; X<=C; X++) {
         rin = intersecta(nr);
         if (rin!=-1) {
             if ((nr.c + X + rin) <= C)   {
                 X += rin;
             } else {
                 Y += 1;
                 goto continuar;
             }
         } else {
             cout << Y << " " << X << endl;
             return 0;
         }
     }
     continuar:
     cout <<"Acabei de passar pela linha " << X << endl;
   }
   cout << "Impossivel" << endl;
   return 0;
}

int main() {
   int c;
   cin >> c;
   while (c!=0) {
       programa();
       c--;
   }
   return 0;
}

Onde está o erro?


<Signature goes here>

Share this post


Link to post
Share on other sites
xtrm0

Já percebi onde estavam os meus erros.

Mas agora como é que verifico as intercepções?

Tenho de verificar com umas 32 condições seguidas seguidas?


<Signature goes here>

Share this post


Link to post
Share on other sites
pedrosorio

Assim de repente, onde tens tens

                  Y += 1;
                  goto continuar;

Devias ter apenas "break;" que sai do loop dos X e é o que tu queres (aquele Y+=1 vai saltar uma linha porque depois o Y++ é executado, no fim do ciclo for dos Y).

        if (X > rect[i].x  && X < rect[i].x2 && Y > rect[i].y && Y < rect[i].y2) {
            maxdis= max(maxdis, rect[i].x2-X);
        } else {
            if (tr.c+X > rect[i].x  && tr.c+X < rect[i].x2 && Y > rect[i].y && Y < rect[i].y2) {
                maxdis= max(maxdis, rect[i].x2-X);
            } else {
                if (X > rect[i].x  && X < rect[i].x2 && tr.l + Y > rect[i].y && tr.l + Y < rect[i].y2) {
                    maxdis= max(maxdis, rect[i].x2-X);
                } else {
                    if (tr.c+X > rect[i].x  && tr.c+X < rect[i].x2 && tr.l + Y > rect[i].y && tr.l + Y < rect[i].y2) {
                        maxdis= max(maxdis, rect[i].x2-X);
                    }
                }
            }
        }

Aqui de certeza que queres <= e >=. Parece-me que não precisas de fazer aqueles if else encaixados, basta-te fazer if's consecutivos. A coordenada X dos vértices do rectângulo à direita não é tr.c+X, mas sim tr.c+X-1. O mesmo se aplica às coordenadas Y.

Se corrigires o código como te indiquei, no segundo caso de teste exemplo, quando tentas colocar o rectângulo 6x7 em Y=1, X=1 ele vai colidir com o rectângulo 2 2 5 4, porque nenhum dos vértices do rectângulo que tentas colocar fica dentro deste rectângulo (o rectângulo que estás a colocar "tapa" o rectângulo que já está colocado) e este caso não está contemplado no teu código pelo que terás 1 1 incorrectamente como resposta nesse caso.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
xtrm0

Então, o que tenho de fazer para a resposta dar certa nesse caso?

Codigo Editado:

#include <iostream>
#include <vector>
#define max(a, b)  (a > b) ? a : b
using namespace std;

struct rectangulo {
   int x, y, x2, y2;
};
struct nvrc {
   int l, c;
};
vector <rectangulo> rect;
int X,Y;
int intersecta(nvrc tr) {
   int sz = rect.size();
   int maxdis=-1;
   for (int i=0; i<sz; i++) {
       if (X >= rect[i].x  && X <= rect[i].x2 && Y >= rect[i].y && Y <= rect[i].y2) {
           maxdis= max(maxdis, rect[i].x2-X);
       } else {
           if (tr.c+X-1 >= rect[i].x  && tr.c+X-1 <= rect[i].x2 && Y >= rect[i].y && Y <= rect[i].y2) {
               maxdis= max(maxdis, rect[i].x2-X);
           } else {
               if (X >= rect[i].x  && X <= rect[i].x2 && tr.l + Y -1 >= rect[i].y && tr.l + Y -1 <= rect[i].y2) {
                   maxdis= max(maxdis, rect[i].x2-X);
               } else {
                   if (tr.c+X-1 >= rect[i].x  && tr.c+X-1 <= rect[i].x2 && tr.l + Y-1 >= rect[i].y && tr.l + Y-1 <= rect[i].y2) {
                       maxdis= max(maxdis, rect[i].x2-X);
                   }
               }
           }
       }
//       cout << rect[i].x2-X << endl;
//        cout << rect[i].x << " " <<  rect[i].y << endl;
   }
//    cout << endl << maxdis << endl;
   return maxdis;
}


int programa() {
   rect.clear();
   rectangulo trect;
   nvrc nr;
   int L, C, R;
   int rin;
   cin >> L >> C;
   cin >> nr.l >> nr.c;
   cin >> R;
   for (int i=0; i < R; i++) {
       cin >> trect.y >> trect.x >> trect.y2 >> trect.x2;
       rect.push_back(trect);
   }
   for (Y=1; Y<=L; Y++) {
     for (X=1; X<=C; X++) {
         rin = intersecta(nr);
         if (rin!=-1) {
             if ((nr.c + X + rin) <= C)   {
                 X += rin;
             } else {
                 Y += 1;
                 break;
             }
         } else {
             cout << Y << " " << X << endl;
             return 0;
         }
     }
   }
   cout << "Impossivel" << endl;
   return 0;
}

int main() {
   int c;
   cin >> c;
   while (c!=0) {
       programa();
       c--;
   }
   return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
pedrosorio

Continuas a ter aquele Y+=1 ali. Vais saltar linhas se fizeres isso.

Não precisas de verificar 32 condições seguidas. Bastam 4.

As condições que devem ser testadas têm a ver com as faces dos rectângulos (i.e. Xmin,Xmax,Ymin,Ymax) e não com os vértices.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
xtrm0

Sim, já tinha pensado nisso, mas como é que aplico?


<Signature goes here>

Share this post


Link to post
Share on other sites
pedrosorio

Se conseguires perceber quais é que são as condições, só precisas de usar as coordenadas y,x,y1,y2 dos dois rectângulos que estás a testar (o novo rectângulo tem coordenadas Y,X,Y+rc.l-1,X+rc.c-1).

Posso dizer-te ainda que têm que se verificar 4 condições relativas às arestas dos rectângulos em simultâneo. Desenha rectângulos e tenta perceber quais são.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
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
Sign in to follow this  

×
×
  • 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.