2900 - LEKTIRA

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender: Male
Cuba

2900 - LEKTIRA

Post by dovier » 5 years ago




MarijaKg
Posts: 1
Joined: 5 years ago
Gender: None specified

Re: 2900 - LEKTIRA

Post by MarijaKg » 5 years ago

Albert Kami - Stranac, prepričana lektira

http://www.ucionica.rs/materjal-47986-a ... mi-stranac

facug91
Posts: 12
Joined: 5 years ago
Gender: None specified

Re: 2900 - LEKTIRA

Post by facug91 » 5 years ago

Hola gente! Estoy teniendo problemas con este problema. Primero intenté una solución medio greedy, pensando que funcionaba para todos los casos, pero después del primer WA me di cuenta que no... y ahí hice la cuenta del orden de tiempo de una complete search, y me dio bien, así que implementé eso. Esta vez también me dio WA, y ahora no se me ocurre qué puede estar pasando... osea, literalmente checkeo todas las posibles combinaciones. Acá les dejo mi código, por si tuve algún error. Y si estoy encarando mal el problema, me sería mucha ayuda que me lo digan jajaj. Pero creo que con esto debería funcionar, no sé...

Code: Select all

//quité todos los includes para hacerlo más legible
using namespace std;

char s[100], ans[100], len;

void reverse (int i, int j) {
	for (; i<j; i++, j--) {
		char tmp = s[i];
		s[i] = s[j];
		s[j] = tmp;
	}
}

void search (int k, int i) {
	if (k == 3) {
		if (strcmp(ans, s) > 0)
			strcpy(ans, s);
		return;
	}
	
	int pos;
	for (pos=i; pos<(len+k-2); pos++) {
		reverse(i, pos);
		search(k+1, pos+1);
		reverse(i, pos);
	}
}

int main() {

	scanf("%s", s);
	
	strcpy(ans, s);
	
	len = strlen(s);
	
	search(0, 0);
	
	printf("%s\n", ans);

	return 0;
}

Post Reply

Return to “Problem set”