Piastrelle. Solo 5 punti

Aiuto
1

Qualcuno riesce a capire perché mi da solo 5 punti nonostante l’algoritmo sembri giusto?

#include <fstream>


#include <algorithm>


#include <vector>


using namespace std;


int N;

vector<int> p;


int main(){

	ifstream in("input.txt");

	in >> N;

	in.close();

	

	ofstream out("output.txt");

	for(int cont=0, i; cont<=(N/2); cont++){

		p.resize(N-cont);

		for(i=0; i<N-(cont*2); i++)

			p[i]=1;

		for( ; i<N-cont; i++)

			p[i]=2;


		do{

			for(int i=0; i<p.size(); i++)

				out << ((p[i]==1)?"[O]":"[OOOO]");

			out << "\n";

		}while(next_permutation(p.begin(), p.end()));

	}

	out.close();

	return 0;

}
2

Beh, almeno esponi a parole l’algoritmo :stuck_out_tongue:

3

Ma perchè non fate una banale ricorsiva? :smiley:

4

Giusto scusami. Praticamente cont contiene il numero progressivo di piastrelle larghe 2. Quindi ad ogni passo del ciclo (il quale durerà fino a quando le piastrelle larghe 2 non saranno la metà di N) riempio il vettore con (N-cont*2) x 1 e cont x 2, ne analizzo tutte le permutazioni e le stampo. Con input di esempio e altri di prova funziona. Sul correttore invece mi prende il primo subtask e tutti quelli del secondo tranne uno. Poi nessuno di tutti gli altri.

5

quindi per il tuo algoritmo questo:

[0000][0][0][0]

“viene prima” di:

[0][0000][0000]

?

7

Secondo il mio algoritmo si… Appena posso faccio la procedura ricorsiva ahahah

8

Non che sia strettamente necessaria eh! Puoi ad esempio aggiungere tutte le piastrellature in un vettore (invece di stamparle direttamente). Lo ordini. Lo stampi tutto :slight_smile:

Nel caso prova a risolverlo in entrambi i modi e vedi quale va più veloce (beh… :P)

9

Era come volevo farlo all’inizio ma poi pensavo che fosse una perdita di tempo. Non avevo capito bene come ordinare le sequenze

10

Uhm… tecnicamente potresti tenerle come stringhe e ordinare l’array di stringhe (vector<string>) l’unico problema è che i separatori ‘[’ e ‘]’ hanno un valore ASCII maggiore di ‘0’. Potresti sostituirli con ‘(’ e ‘)’, ordinare l’array, stamparlo ri-sostituendo le parentesi… :slight_smile:

11

Oppure puoi usare un vettore di interi (1 e 2) e quando stampi sostituisci 1 con [O] e 2 con [OOOO]

12
Oppure puoi usare un vettore di interi (1 e 2) e quando stampi sostituisci 1 con [O] e 2 con [OOOO]

Degiac

È esattamente quello che ho fatto.
Comunque faccio qualche prova e vi faccio sapere ;)
13
Oppure puoi usare un vettore di interi (1 e 2) e quando stampi sostituisci 1 con [O] e 2 con [OOOO]

Degiac

Sì ma dovresti comunqe sapere «come ordinare le sequenze» (ad esempio passando a sort una funzione di compare, oppure definendo un operatore "minore" tra i vector). Con le stringhe chiamerebbe solo sort (non che io consigli di farlo... è bruttissimo :P... molto meglio ordinare i vector in questo caso)
14

Rettifico, a quanto pare vector<> definisce già i suoi bei operatori <, <=, >, etc… http://en.cppreference.com/w/cpp/container/vector/operator_cmp

Quindi puoi chiamare sort su un vector di vector senza problemi :slight_smile:

15

Ordinando il vector di vector da 100/100, grazie :wink:

16

Ottimo. Adesso se vuoi prova ad implementare anche la versione ricorsiva :slight_smile: quella di cui parlava @mark03

17
Ordinando il vector di vector da 100/100, grazie ;)

Lawliet

Tra l’altro ho notato che nella tua ultima sottoposizione per ordinare il vector<vector> passi una funzione di compare, questo non è strettamente necessario (come ho scritto in un commento poco sopra) dal momento che la classe vector ha gli operatori di confronto già definiti (<, <=, >, etc…) quindi se hai due vector v1 e v2 e fai la cosa seguente:

if (v1 < v2) {
    …
}

automaticamente verrà fatta la cosa giusta (internamente, verrà chiamata lexicographical_compare). Quindi puoi fare sort senza passare alcuna funzione di compare :slight_smile:

18
Ordinando il vector di vector da 100/100, grazie ;)

Lawliet

Tra l’altro ho notato che nella tua ultima sottoposizione per ordinare il vector<vector> passi una funzione di compare, questo non è strettamente necessario (come ho scritto in un commento poco sopra) dal momento che la classe vector ha gli operatori di confronto già definiti (<, <=, >, etc…) quindi se hai due vector v1 e v2 e fai la cosa seguente:

if (v1 < v2) {
    …
}

automaticamente verrà fatta la cosa giusta (internamente, verrà chiamata lexicographical_compare). Quindi puoi fare sort senza passare alcuna funzione di compare :slight_smile:

wil93

Capito :slight_smile:

Grazie per la disponibilità. Quando avrò un po’ di tempo implementerò la funzione ricorsivamente!