Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Dynamic Progr Contest [Risolto da Piero]
Forum - C/C++ - Dynamic Progr Contest [Risolto da Piero]

Avatar
Car4m (Normal User)
Newbie


Messaggi: 7
Iscritto: 19/06/2015

Segnala al moderatore
Postato alle 19:07
Venerdì, 19/06/2015
Buongiorno a tutti!
Spero di risolvere un problema che credo si risolva similmente alla ricerca LIS. VEDASI IL TESTO ALLEGATO :k:
Ma non son sicuro sicuro:pat:
Codice sorgente - presumibilmente C++

  1. #include <string.h>
  2. #include <fstream>
  3. #include <iostream>
  4. #include <climits>
  5. using namespace std;
  6. typedef struct{
  7.     int x,y,z;
  8. }box;
  9. ifstream in ("in.txt");
  10. ofstream out ("out.txt");
  11. int max_box(box *a, int dim);
  12. int ricbin(box *a, int T[], int l, int r, box elemento);
  13.  
  14. int main(void) {
  15.   int dim;
  16.   in >> dim;
  17.   box a[dim];
  18.    for(int j=0; j<dim; j++)
  19.           in >> a[j].x >> a[j].y >> a[j].z;
  20.   out<< "TOTALE: " << max_box(a, dim)<<endl;
  21.    return 0;
  22. }
  23. int ricbin(box *a, int T[], int l, int r, box elemento) {
  24.   int m;
  25.    while( r - l > 1 ) {
  26.       m = l + (r - l)/2;
  27.  
  28.       if( a[T[m]].x >= elemento.x && a[T[m]].y >= elemento.y && a[T[m]].z >= elemento.z )
  29.          r = m;
  30.       else
  31.          l = m;
  32.    }
  33.   return r;
  34. }
  35.  
  36. int max_box(box *a, int dim) {
  37.  
  38.    int *indicicoda = new int[dim];
  39.    int *indicipreced = new int[dim];
  40.    int lung;
  41.  
  42.    memset(indicicoda, 0, sizeof(indicicoda[0])*dim);
  43.    memset(indicipreced, 0xFF , sizeof(indicipreced[0])*dim);
  44.  
  45.    indicicoda[0] = 0;
  46.    indicipreced[0] = -1;
  47.    /* punta sempre alla posizione vuota */
  48.    lung = 1;
  49.    for( int i = 1; i < dim; i++ ) {
  50.       if( a[i].x < a[indicicoda[0]].x &&  a[i].y < a[indicicoda[0]].y && a[i].z < a[indicicoda[0]].z  ) {
  51.          /* se abbiamo un nuovo valore più piccolo */
  52.          indicicoda[0] = i;
  53.       }  else if ( a[i].x > a[indicicoda[lung-1]].x && a[i].y > a[indicicoda[lung-1]].y && a[i].z > a[indicicoda[lung-1]].z )
  54.          {
  55.       // a[i] vuole trovare la più grande sottosequenza crescente
  56.          indicipreced[i] = indicicoda[lung-1];
  57.          indicicoda[lung++] = i;
  58.          }
  59.       else {
  60.   // a[i] potrebbe essere nella sottosequenza finale e quindi potrebbe rimanere in indicicoda
  61.         int pos = ricbin(a, indicicoda, -1, lung-1, a[i]);
  62.  
  63.         indicipreced[i] = indicicoda[pos-1];
  64.         indicicoda[pos] = i;
  65.       }
  66.    }
  67.    
  68.   /* stampa la sequenza finale risultante, dal più grande intero al più piccolo intero */
  69.    for( int i = indicicoda[lung-1]; i >= 0; i = indicipreced[i] )
  70.       out << a[i].x <<"x"<<a[i].y<<"x"<< a[i].z<<endl;
  71.    //out << endl;
  72.  
  73.    delete[] indicicoda;
  74.    delete[] indicipreced;
  75.  
  76.    return lung;
  77. }




Se in input diamo 3 box:

Codice sorgente - presumibilmente Plain Text

  1. 3
  2. 1 1 1
  3. 2 2 2
  4. 3 3 3


Allora non ci sono problemi.

Ma se abbiamo input disordinati...
Codice sorgente - presumibilmente Plain Text

  1. 3
  2. 3 3 3
  3. 2 2 2
  4. 1 1 1


Non va... Dovrebbe restituire lo stesso output di prima perché si inseriscono una dentro l'altra (come nel caso precedente).
Ed il problema è proprio il LIS che non "guarda indietro".
Che modifiche dovrei fare?
SPERO TANTO IN UN VOSTRO AIUTO

PS: Non si può ordinare in alcun modo... Se no problema risolto :-o
In allegato leggere punto 1 e poi il 3 per la stampa finale:_doubt:


Car4m ha allegato un file: esaustiv.jpg (73907 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Car4m il 24/06/2015 alle 9:46
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 16:10
Sabato, 20/06/2015


Il mio blog: https://piero.dev
PM Quote
Avatar
Car4m (Normal User)
Newbie


Messaggi: 7
Iscritto: 19/06/2015

Segnala al moderatore
Postato alle 16:52
Lunedì, 22/06/2015
Ciao Piero!
Non si può ordinirare, la "pre-elaborazione" non è consentita.
Avevo pensato anch'io ad ordinarli per volumi ma non si può rileggendo il testo allegato :-|
Effitivamente, il testo, è un pochetto ambiguo; diciamo che ci "forza" a vederle/rivederle tutte, così come vengono date, con la PD.

Ultima modifica effettuata da Car4m il 22/06/2015 alle 16:54
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 18:57
Lunedì, 22/06/2015
Testo quotato


Non si può ordinirare, la "pre-elaborazione" non è consentita.



Perchè no? Il testo che hai allegato non lo proibisce. O forse ho interpretato male.

edit: ah, usando un algoritmo DP. Quindi si, non si deve ordinare.

Testo quotato


Una scatola Si può essere inserita in una scatola Sj solo se Si sottoinsieme di Sj e i < j



Per:

3
3 3 3
2 2 2
1 1 1

Nel caso in cui:

Si = 2 2 2 (i = 1)
Sj = 3 3 3 (j = 0)

i < j è falso. Quindi il tuo input non è valido (o il risultato è 0).


Ultima modifica effettuata da pierotofy il 22/06/2015 alle 19:09


Il mio blog: https://piero.dev
PM Quote
Avatar
Car4m (Normal User)
Newbie


Messaggi: 7
Iscritto: 19/06/2015

Segnala al moderatore
Postato alle 22:14
Lunedì, 22/06/2015
Esatto! ;)
Tu cosa consigli di fare?
2 cicli uno dentro l'altro quindi  
Codice sorgente - presumibilmente Plain Text

  1. O(n^2)


In questo caso, parlando in C++ :rotfl: , come si potrebbe fare in modo efficente?8-|

---------
con input:
3
3 3 3
2 2 2
1 1 1

Dovrebbe riuscire a stampare:
3 3 3
2 2 2
1 1 1
TOTALE 3
---------

Poiché 1 1 1 può stare dentro 2 2 2, così 2 2 2 può essere contenuta in 3 3 3.

Ultima modifica effettuata da Car4m il 22/06/2015 alle 22:22
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 23:49
Lunedì, 22/06/2015
No, leggi la mia risposta.


Il mio blog: https://piero.dev
PM Quote
Avatar
Car4m (Normal User)
Newbie


Messaggi: 7
Iscritto: 19/06/2015

Segnala al moderatore
Postato alle 0:06
Martedì, 23/06/2015
Letta e riletta certo, forse allora non ho afferrato.
Devo cambiare proprio "strategia" o, almeno, sono sulla retta via?:_doubt:

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 0:41
Martedì, 23/06/2015
Questo input:

3 3 3
2 2 2
1 1 1

Deve stampare:

TOTALE 0

Testo quotato


Una scatola Si può essere inserita in una scatola Sj solo se Si sottoinsieme di Sj e i < j



La clausola "e i < j" praticamente dice che l'ordine conta!

i e j sono indici. 3 3 3 ha indice 0, 2 2 2 ha indice 1 e 1 1 1 ha indice 2.

Ad esempio non puoi confrontare 2 2 2 (i) e 3 3 3 (j), perchè anche se 2 2 2 < 3 3 3, i = 1 e j = 0, quindi i < j é falso e quindi, 2 2 2 non può essere inserita in 3 3 3.



Il mio blog: https://piero.dev
PM Quote
Avatar
Car4m (Normal User)
Newbie


Messaggi: 7
Iscritto: 19/06/2015

Segnala al moderatore
Postato alle 10:20
Martedì, 23/06/2015
Cavoli non l'avevo notato!
(Forse una sola la può restituire però)
Devo chiedere all'autore dell'esercizio cosa intendesse.
Piero Grazie!

Quindi la soluzione è banalmente fatta col metodo LIS (di cui sopra) ?

Ma se volessimo interpretare il testo, così come "intendevo io" :rofl: , serve almeno un while interno al for?
Ho provato ma c'é sempre qualcosa che non va :d


Ultima modifica effettuata da Car4m il 23/06/2015 alle 10:32
PM Quote