elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Problema de Backtracking (recursion)
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema de Backtracking (recursion)  (Leído 2,419 veces)
KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Problema de Backtracking (recursion)
« en: 6 Julio 2017, 08:17 am »

Hola que tal, ando intentando un problema de un juez en linea https://omegaup.com/arena/problem/decepcion#problems

Dado un entero n, se forma una fila de n torres con alturas desde 1 hasta n centímetros, ninguna altura aparece más de una vez. Se quieren conocer todas las permutaciones de esta fila tal que viendo la fila de frente solo se vean F torres diferentes y vista por detrás solo se vean B torres. Se dice que podemos ver una torre con altura H si no hay otra torre delante de ella (con respecto a nuestra visión) con altura mayor a H.

Entrada

Tres enteros separados por espacios: n, F y B.

Salida

Un entero que representa el número de permutaciones que cumplen con las condiciones establecidas.

Ejemplo

4 2 3
3
Las tres permutaciones posibles son:
Frente → 2 4 3 1
Frente → 1 4 3 2
Frente → 3 4 2 1

Límites

1≤n,F,B≤13


En el cual tengo una respuesta que me da 55 puntos, me da tiempo limite excedido
Podrias darme una ayuda?
Por ejemplo alguna poda o mucho mejor alguna pagina donde expliquen temas de este tipo
, etc..., todo es bueno.
Bueno y pues lo que hago es literal hacer lo que pide el problema, no tengo ninguna poda
(en un principio pense que el numero mayor seria un numero fijo, si viste en el ejemplo viene:

4 2 3
3
Las tres permutaciones posibles son:
Frente → 2 4 3 1
Frente → 1 4 3 2
Frente → 3 4 2 1

pero si pongo este otro caso ya no es factible

5 3 2

unas permutaciones posibles son:

12534

13254

)
Código
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool visitado[15];
  5. string cad[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", ":",";", "<", "="};//si checas el codigo ascii despues del 9 sigue el ":" y luego el ";", etc..., es decir, que poner ":" es como poner 10, etc.
  6.  
  7. int n, x, y, C;//C = contador = permutaciones validas
  8.  
  9. bool esValido_izq(string tmp){
  10.    int a = 1, mayor = tmp[0];
  11.    for(int i = 1; i < n; i++)
  12.        if(tmp[i] > mayor)
  13.            mayor = tmp[i], a++;
  14.    return (a == x);
  15. }
  16.  
  17. bool esValido_der(string tmp){
  18.    reverse(tmp.begin(), tmp.end());
  19.    int a = 1, mayor = tmp[0];
  20.    for(int i = 1; i < n; i++)
  21.        if(tmp[i] > mayor)
  22.            mayor = tmp[i], a++;
  23.    return (a == y);
  24. }
  25.  
  26. void permutar(string tmp = ""){
  27. if(tmp.size() == n){
  28.        if(esValido_izq(tmp) && esValido_der(tmp)){
  29.            C++;
  30.            //cout<<"\n"<<tmp<<"\n"; //descomentar para ver las permutaciones validas
  31.        }
  32.        return;
  33. }
  34. for(int i = 0; i < n; i++)
  35. if(!visitado[i]){
  36. visitado[i] = true;
  37. permutar(tmp + cad[i]);
  38. visitado[i] = false;
  39. }
  40. }
  41.  
  42. int main(){
  43.    cin>>n>>x>>y;
  44.    permutar();
  45.    cout<<C;
  46. }
  47.  


« Última modificación: 6 Julio 2017, 08:26 am por KINGARZA » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
gramatica sin recursión a la izquierda
Dudas Generales
m@o_614 0 1,660 Último mensaje 5 Septiembre 2014, 03:52 am
por m@o_614
Java Recursion
Java
josephb401 2 1,901 Último mensaje 3 Diciembre 2015, 19:00 pm
por josephb401
problema de backtracking y programacion dinamica
Programación C/C++
aprendiz de programador 6 6,411 Último mensaje 12 Diciembre 2015, 16:08 pm
por SnzCeb
Problema en ejercicio de backtracking
Programación General
xXJoSe13Xx 0 2,333 Último mensaje 3 Noviembre 2018, 18:15 pm
por xXJoSe13Xx
Ayuda con problema de backtracking (recursividad) de optimización en C
Programación C/C++
Albpenu 2 6,333 Último mensaje 4 Octubre 2021, 23:07 pm
por fzp
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines