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

 

 


Tema destacado: Entrar al Canal Oficial Telegram de elhacker.net


  Mostrar Temas
Páginas: [1] 2
1  Foros Generales / Dudas Generales / Ayuda con el contenedor TableRow en desarrollo android en: 18 Febrero 2018, 04:12 am
Buenas a todos!
Pues como voy empezando en el mundo del desarrollo android me he propuesto desarrollar un TicTacToe, el problema radica en que no se como hacer que las tres celdas ocupen el mismo espacio proporcional.

Leí por internet que empleando android:layout_weight="1" se solucionaba, pero no...
Gracias por leerlo!

El código que empleo
Código
  1.  <TableRow
  2.         android:layout_height="wrap_content"
  3.         android:layout_width="fill_parent"
  4.         >
  5.  
  6.         <TextView
  7.             android:id="@+id/uno"
  8.             android:layout_width="fill_parent"
  9.             android:layout_height="fill_parent"
  10.             android:layout_weight="1"
  11.  
  12.             android:text="X"
  13.             android:textSize="35sp"
  14.             android:textColor="#000000"
  15.  
  16.             android:padding="25dp"
  17.             android:gravity="center"
  18.             android:background="#F78181"
  19.             />
  20.  
  21.         <TextView
  22.             android:id="@+id/dos"
  23.             android:layout_width="fill_parent"
  24.             android:layout_height="fill_parent"
  25.             android:layout_weight="1"
  26.  
  27.             android:text="X"
  28.             android:textSize="35sp"
  29.             android:textColor="#000000"
  30.  
  31.             android:padding="25dp"
  32.             android:gravity="center"
  33.             android:background="#FF00FF"
  34.             />
  35.         <TextView
  36.             android:id="@+id/tres"
  37.             android:layout_width="fill_parent"
  38.             android:layout_height="fill_parent"
  39.             android:layout_weight="1"
  40.  
  41.             android:text="X"
  42.             android:textSize="35sp"
  43.             android:textColor="#000000"
  44.  
  45.             android:padding="25dp"
  46.             android:gravity="center"
  47.             android:background="#F78181"
  48.             />
  49. </TableRow>
  50.  
2  Foros Generales / Dudas Generales / Automatizar "tareas" en la web parte 2 en: 19 Enero 2018, 11:05 am
Buenas a todos!!

Hace poco tenia la siguiente cuestión:
https://foro.elhacker.net/dudas_generales/automatizar_tareas_en_la_web-t479005.0.html

Gracias a su apoyo he tenido un gran avance pero tengo una duda que no he encontrado como resolverla...

Antes que nada he hecho un formulario, el cual consta de 4 campos:
*ID
*Fecha de nacimiento

Cuando el usuario ingresa la información correcta (Id = A5 Dia = 1 Mes = 2 año = 3) en un nueva pagina se le da el mensaje de bienvenida, de lo contrario se abre una nueva pagina con el mensaje sigue intentando.

El problema es que supongamos el usuario olvida su contraseña y no hay otra manera de obtenerla mas que usando la bruta, el sabe que el ID solo consta de una letra mayúscula del alfabeto ingles y un numero, es decir el total de combinaciones posibles seria:
26 * 10 * 5 * 5 * 5 = 32500

Notar que la ID en este caso consta de una letra mayúscula del alfabeto ingles y un numero, los demás datos (día, mes, año) están limitados a 5 valores.

Intentar manualmente esas 32,500 combinaciones seria prácticamente imposible...

Encontré la manera de acceder desde el DOM a los campos del formulario:

document.getElementsByTagName("form")[0].ID.value
document.getElementsByTagName("form")[0].dia.value
document.getElementsByTagName("form")[0].mes.value
document.getElementsByTagName("form")[0].año.value
document.getElementById("Enviar").click()


Mi pregunta es la siguiente:

Como puedo intentar todas las posibles combinaciones hasta que ingrese los datos correctos, es decir, hasta que el formulario me envié a la pagina de bienvenido?

Mi idea es la siguiente (pero no se como llevarla acabo):

A cada campo del formulario le asigno el valor de una posible combinación, por ejemplo:

document.getElementsByTagName("form")[0].ID.value = "A1"
document.getElementsByTagName("form")[0].dia.value = "1"
document.getElementsByTagName("form")[0].mes.value = "1"
document.getElementsByTagName("form")[0].año.value = "1"
document.getElementById("Enviar").click()

Y después encuentro la manera de pegar ese código en la consola (cuando damos inspeccionar pagina) y si me da el mensaje de bienvenida pues excelente, allí paro, sino seguir intentado las demás combinaciones...

Dejo el código del formulario en HTML Y javascript y el generador de combinaciones en lenguaje C++

Código
  1. <html>
  2.  
  3. 	<head>
  4. 		<title>"Example 1"</title>
  5. 	</head>
  6.  
  7. 	<body>	
  8.  
  9. 		<h1>Formulario</h1>
  10. 		<br/>
  11.  
  12. 		<form target = "_blank" action = ""  method = "POST">
  13.  
  14. 			<input type = "text" id = "ID", name = "ID" placeholder = "Introduce tu ID aqui">			
  15. 			<select id = "dia" name = "dia">
  16. 				<option value = "0">Selecciona el Dia</option>
  17. 				<option value = "1">01</option>
  18. 				<option value = "2">02</option>
  19. 				<option value = "3">03</option>
  20. 				<option value = "4">04</option>
  21. 				<option value = "5">05</option>
  22. 			</select>
  23. 			<select id = "mes" name = "mes">
  24. 				<option value = "0">Selecciona el Mes</option>
  25. 				<option value = "1">01 Enero</option>
  26. 				<option value = "2">02 Febrero</option>
  27. 				<option value = "3">03 Marzo</option>
  28. 				<option value = "4">04 Abril</option>
  29. 				<option value = "5">05 Mayo</option>
  30. 			</select>
  31. 			<select id = "año" name = "año">
  32. 				<option value = "0">Selecciona el año</option>
  33. 				<option value = "1">2001</option>
  34. 				<option value = "2">2002</option>
  35. 				<option value = "3">2003</option>
  36. 				<option value = "4">2004</option>
  37. 				<option value = "5">2005</option>
  38. 			</select>			
  39. 			<br/>
  40. 			<br/>
  41. 			<input type = "submit" id = "Enviar" name = "Enviar" value = "Enviar" onclick = "Evaluar()">
  42.  
  43. 		</form>
  44.  
  45. 		<script>
  46. 			function Evaluar(){
  47. 				var ID = document.getElementById("ID").value,
  48. 					Dia = document.getElementById("dia").value,
  49. 					Mes = document.getElementById("mes").value,
  50. 					año = document.getElementById("año").value;									
  51. 				if(ID === "A5" && Dia === "1" && Mes === "2" && año === "3")					
  52. 					document.write("Bienvenido");				
  53. 				else
  54. 					document.write("Sigue intentado");
  55. 			}
  56. 		</script>
  57. 	</body>
  58. </html>
  59.  

Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<string>Combinacion;
  5.  
  6. void genera_combinaciones(){
  7.     for(char i = 'A'; i <= 'Z'; i++)
  8.         for(char j = '0'; j <= '9'; j++){
  9.             string cad = "";
  10.             cad.push_back(i);
  11.             cad.push_back(j);
  12.             Combinacion.push_back(cad);
  13.         }
  14. }
  15.  
  16. int main(){
  17.     ofstream File("Combinaciones.txt");
  18.     int t = 0;
  19.     genera_combinaciones();
  20.     for(int i = 0; i < Combinacion.size(); i++)
  21.         for(int dia = 1; dia <= 5; dia++)
  22.             for(int mes = 1; mes <= 5; mes++)
  23.                 for(int año = 1; año <= 5; año++)
  24.                     File<<Combinacion[i]<<" "<<dia<<" "<<mes<<" "<<año<<"\n", t++;
  25.     File<<"Total de combinaciones: "<<t;
  26.     File.close();
  27. }
  28.  
Gracias por tu atencion :rolleyes:
3  Foros Generales / Dudas Generales / Automatizar "tareas" en la web en: 11 Enero 2018, 01:10 am
Buenas a todos!
Desde hacer tiempo que en mi colegio (cursando la preparatoria) suben las calificaciones en una plataforma en donde cada estudiante se le asigna una clave, ya con esta ingresas tu fecha de nacimiento y puedes entrar a tu cuenta para ver tu perfil.

Le pedí a varios amigos su clave y me doy cuenta que de 9 caracteres  los primeros 6 son los mismos, y los tres últimos (que son solo números) es lo que cambia.

Afortunadamente tengo fuertes conocimientos en algoritmos (y solo conozco el lenguaje C/C++), puedo obtener todas las combinaciones posibles, pero mi problema es:

Como lleno cada campo de la plataforma automáticamente?

Es decir, en vez de yo usuario copiar y pegar cada combinación (poner la clave, y fecha de nacimiento) en su campo correspondiente me gustaría hacer esto de manera automática

Si pudieran indicarme que aprender para hacer esto (realizar tareas iterativas automáticamente) o compartirme algún pdf relacionado estaría genial!
Cualquier información sirve, gracias por su atención!
4  Programación / Programación C/C++ / Uso de la estructura Pair en C++ en: 26 Julio 2017, 09:44 am
Hola a todos!
Quiero hacer una cola que guarde cinco valores y para ello estoy usando la estructura PAIR de c++, el problema esta en como acceder a estos elementos.

El codigo de abajo muestra como defino el estado y la cola de este tipo
Código
  1. #define Estado pair<int, pair<int, pair<int, pair<int, int> > > >
  2. set<Estado>Cola;

Por ejemplo, se que para acceder al primer elemento es:
Código
  1. int a = (*Cola.begin()).first;

Para el segundo elemento es:
Código
  1. int a = (*Cola.begin()).second.first;

Podrias ayudarme por favor?
5  Programación / Programación C/C++ / 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.  
6  Programación / Programación C/C++ / Como esta implementado el Map de la STL? en: 19 Febrero 2017, 06:47 am
Pues quiero saber que usan (arboles, hash table, etcetera) para hacerlo por mi mismo y hacer unas modificaciones.
Gracias por tu atencion. ;)
7  Programación / Programación C/C++ / Problema de reparticiones de chocolates en: 5 Diciembre 2016, 04:56 am
Hola a todos, pues hoy me encuentro con este problema:

https://omegaup.com/arena/problem/cuanto#problems

L-¿Cuánto nos toca?

Límite de memoria   32MB
Límite de tiempo (caso)   1s   
Límite de tiempo (total)   60s

Descripción
El fin de semana pasado Karel celebró que había obtenido puntaje perfecto en su examen, por lo que hizo una fiesta para autofestejarse. En la fiesta hubo de todo, pero lo que más llamo la atención fueron unas barras de frutas con chocolate.
Al lunes siguiente, Karel planeó darle barras a sus amigos que no fueron invitados a la fiesta. Sin embargo, sus amigos estaban un poco molestos por no haber sido invitados. Como las barras de fruta no tienen la misma cantidad de chocolate , te has metido en un pequeño embrollo para compartirlas:
Para empezar, todos tienen que recibir la misma cantidad de chocolate.
Si alguno de ellos recibe mas chocolate que los demás, entonces se enojarán para siempre contigo.
Siempre puedes partir cualquier barra para darle a uno o más amigos (una parte a cada uno) o inclusive darles una barra completa.
En tu reparto, a cada uno de tus amigos sólo le puedes dar ya sea un único trozo de barra o una barra completa, ya que si alguno de ellos recibe más de un trozo o barra completa (aunque tenga la misma cantidad de chocolate que los demás amigos), también se enojarán contigo.
Para compensar el que no los hayas invitado, quieres darles la mayor cantidad de chocolate, siguiendo las restricciones de arriba, aunque implique que te quedes con barras incompletas y/o completas.
Entrada
En la primera línea habrá dos enteros NN y AA,que indican la cantidad de barras de chocolate y la cantidad de amigos a los que quiere repartir Karel.
En las siguientes NN líneas habrá un entero CiCi que indica la cantidad de chocolate que tiene la barra ii.
Salida
Un único número entero que representa la mayor cantidad de chocolate que les puedes dar a cada uno de tus amigos respetando las restricciones. Nota que es posible darles una cantidad racional de chocolate, pero como no tienes tanta precisión al partir, solo quieres darles cantidades enteras.
Ejemplo
Entrada   Salida   Descripción
2 2
2
2
2
Le das un barra a cada uno de tus amigos.
2 3
7
4
3
Como no es posible darles un pedazo que tenga 4 "unidades" de chocolate, es necesario partir ambas barras (barra [7] -> [3] [3] [1] y barra [4] -> [3] [1]) para que haya 3 pedazos con 3 "unidades" de chocolate y le das una de estas partes a cada uno de tus amigos.
Límites
1 <= NN, AA <= 100000
1 <= CiCi <= 100000

Esta es mi respuesta, la cual me da "Tiempo limite excedido"  y 46.67%:
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.  
  5.     cin.tie(0);
  6.     ios_base::sync_with_stdio(0);
  7.     int n, amigos, aux, suma = 0, cont;
  8.     cin>>n>>amigos;
  9.     int ar[n];
  10.  
  11.     for(int i = 0; i < n; i++){
  12.         cin>>ar[i];
  13.         suma += ar[i];
  14.     }
  15.  
  16.     int optimo = suma / amigos;
  17.  
  18.     while(optimo){
  19.  
  20.         cont = 0;
  21.         for(int j = 0; j < n; j++)
  22.             cont += ar[j] / optimo;
  23.  
  24.         if(cont >= amigos)
  25.             break;
  26.         else
  27.             optimo--;
  28.     }
  29.     cout<<optimo;
  30.     return 0;
  31. }
  32.  

Si tienes alguna otra idea a la mia, por favor mencionala, me ayudarias mucho...
8  Programación / Programación C/C++ / Grafos: camino mas corto entre dos nodos[c++] en: 8 Noviembre 2016, 03:27 am
Dados dos nodos A y V de un grafo, quiero encontrar el camino  (el mas corto) que empiece en A y culmine en V

POR EJEMPLO :



queremos iniciar en el nodo 1 y finalizar en el nodo 3

Entrada:
Dame numero de enlaces: 6
6 4
4 3
4 5
5 1
3 2
2 5
Dame nodo raiz: 1
Dame nodo fin: 3

Salida: 1 5 4 3

Error, lo optimo es: 1, 2, 3

Lo que intente primero fue recorrer a profundidad con recursion, luego con la cola (como el recorrido es por niveles crei que el recorrido seria optimo, pero no)pero ninguno me funciona, me han comentado que puedo hacerlo con backtracking, pero aun no entiendo muy bien esa tecnica y pues si pueden ayudarme, adelante.

Mi codigo
Código
  1. #include<bits/stdc++.h>
  2. #define MAX 1000002
  3. using namespace std;
  4.  
  5. vector<int>ady[MAX];
  6. bool visitado[MAX];
  7. int path[MAX];
  8. int N;
  9.  
  10. //recorrido con recursion
  11. void DFS(int u, int fin){
  12.     path[N++] = u;
  13.     visitado[u] = true;
  14.     for(int v = 0; v < ady[u].size(); ++v)
  15.         if(ady[u][v] == fin){
  16.             path[N++] = fin;
  17.             for(int i = 0; i < N; i++)
  18.                 cout<<path[i]<<" ";
  19.             exit(0);
  20.         }
  21.         else if(!visitado[ady[u][v]])
  22.             DFS(ady[u][v], fin);
  23. }
  24.  
  25. //recorrido con cola
  26. void DFS_cola(int u, int fin){
  27.     queue<int>cola;
  28.     cola.push(u);
  29.     while(!cola.empty()){
  30.         int tope = cola.front();
  31.         visitado[tope] = true;
  32.         path[N++] = tope;
  33.         cola.pop();
  34.         for(int v = 0; v < ady[tope].size(); ++v)
  35.             if(ady[tope][v] == fin){
  36.                 path[N++] = fin;
  37.                 for(int i = 0; i < N; i++)
  38.                     cout<<path[i]<<" ";
  39.                 exit(0);
  40.             }
  41.             else if(!visitado[ady[tope][v]])
  42.                 cola.push(ady[tope][v]);
  43.     }
  44.  
  45. }
  46.  
  47. int main(){
  48.  
  49.     int n, a, b, m(0);
  50.     cout<<"Dame numero de enlaces: ";
  51.     cin>>n;
  52.  
  53.     for(int i = 0; i < n; i++){
  54.         cin>>a>>b;
  55.         ady[a].push_back(b);
  56.         ady[b].push_back(a);
  57.     }
  58.     int inicial, fin;
  59.     cout<<"Dame nodo raiz: ";
  60.     cin>>inicial;
  61.     cout<<"Dame nodo fin: ";
  62.     cin>>fin;
  63.     //DFS(inicial, fin);
  64.     DFS_cola(inicial, fin);
  65.     return 0;
  66. }
9  Programación / Programación C/C++ / Optimizar algoritmo de búsqueda BFS en: 3 Agosto 2016, 07:01 am
Hola a todos!!
Como algunos sabran estoy aprendiendo busquedas y me he topado con el siguiente problema:
LINK: https://omegaup.com/arena/problem/colosus-Laberinto#problems
O bien aqui lo escribo:

Colosus (Laberinto)

Límite de memoria   32MB
Límite de tiempo (caso)   1s
Límite de tiempo (total)   60s

Descripción

En este problema tu tomas el papel de el gran héroe Colossus tiene la misión de rescatar a la princesa omitilda de un laberinto, pero el maligno pachus quiere matar a la princesa.Lo único con lo que cuentas es con el mapa del laberinto y el tiempo en el que pachus va a llegar a la princesa, por lo que tu tienes que llegar en el menor tiempo posible a ella. El mapa consta de una cuadricula la cual tiene una 'X' en el lugar donde no puedes pasar Una 'C' donde tú te encuentras al principio, y una 'O' donde se encuentra la hermosa omitilda y una 'L' en aquellos lugares donde el campo este libre y puedas pasar.

Problema

Tu tarea consiste en escribir un programa que determine el menor tiempo en el que puedes llegar a rescatar a tu princesa tomando en cuenta que tu te mueves a una velocidad de un cuadro por seg. En caso de que no puedas llegar a salvarla escribirás en la pantalla un -1 en el caso contrario escribirás el tiempo en el que llegaste a ella. en caso de llegar al mismo tiempo considera que la princesa se salva.

Entrada

Tu programa deberá leer del teclado los siguientes datos: En la primera línea los números M, N y T separados por un espacio donde los primeros dos son las dimensiones del laberinto y T el tiempo en que pachus llegara con la princesa. Las siguientes M líneas contendrán N caracteres que representaran el mapa. Donde 3 <= M,N <=1000.

Salida

Tu programa deberá escribir un solo número que represente el tiempo en que llegaste ó -1 en caso de que no hayas llegado.

Ejemplos

Entrada   Salida
5 5 8           6
XXXXX
XCLLX
XXXLX
XOLLX
XXXXX

Consideraciones

Tu programa deberá ejecutarse en un tiempo máximo de 1 segundo.

Lo que yo hago es usar el algoritmo de búsqueda por anchura en un grafo (BFS), desafortunadamente mi respuesta me la 80% porque da limite de memoria podrian explicarme como puedo optimizar este programa por favor?
GRACIAS.
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 1000
  5. char ady[MAX][MAX];
  6. bool visitado[MAX][MAX];
  7.  
  8. struct Estado{
  9.     int x;
  10.     int y;
  11.     int d;
  12.     Estado(int x1, int y1, int d1) : x(x1), y(y1), d(d1) {}
  13. };
  14.  
  15. int BFS(int x, int y, int h, int w){
  16.     Estado inicial(x,y,0);
  17.     queue<Estado>estados;
  18.     estados.push(inicial);
  19.     memset(visitado, false, sizeof(visitado));
  20.     int dx[4] = {0, 0, 1, -1};
  21.     int dy[4] = {1, -1, 0, 0};
  22.  
  23.     while(!estados.empty()){
  24.         Estado actual = estados.front();
  25.         estados.pop();
  26.         if(ady[actual.x][actual.y] == 'O')
  27.             return actual.d;
  28.         visitado[actual.x][actual.y] = true;
  29.         for(int i = 0; i < 4; i++){
  30.             int nx = dx[i] + actual.x;
  31.             int ny = dy[i] + actual.y;
  32.  
  33.             if(nx >= 0 && nx < h && ny >= 0 && ny < w && ady[nx][ny] != 'X' && !visitado[nx][ny]){
  34.                 Estado adyacente(nx, ny, actual.d + 1);
  35.                 estados.push(adyacente);
  36.             }
  37.         }
  38.     }
  39.     return -1;
  40. }
  41.  
  42. int main(){
  43.     cin.tie(0);
  44.     ios_base::sync_with_stdio(0);
  45.     int h, w, x, y, t;
  46.     cin>>h>>w>>t;
  47.     for(int i = 0; i < h; i++){
  48.         for(int j = 0; j < w; j++){
  49.             cin>>ady[i][j];
  50.             if(ady[i][j] == 'C'){
  51.                 x = i;
  52.                 y = j;
  53.             }
  54.         }
  55.     }
  56.     cout<<BFS(x, y, h, w);
  57.     return 0;
  58. }
10  Programación / Programación C/C++ / ¿Mejor algoritmo? Problema con aproximaciones de Grafos en: 27 Julio 2016, 09:43 am
Hola que tal a todos!!
llevo horas quemandome la cabeza y aun no encuetro una solucion optima para este problema, podras ayudarme? te lo agradeceria mucho.

este es el problema:
Amigos Interactivos

      Límite de memoria   128MB
                Límite de tiempo (caso)   1s   
                Límite de tiempo (total)   60s
Existe una serie de personas definidas en un espacio, dichas personas tienen la capacidad nata de comuncarse entre ellas y formar relaciones sociales, sin embargo hay relaciones muy especiales que dicen llamarce amistad, dichos individuos son conciderados amigos si realizan algun tipo de saludo especial. Una empresa de analisis de comportamiento humano te ha pedido que les ayudes a saber si un individuo A es amigo de un individuo B., un dato curioso es que si existen tres invidividuos A, C, B pertenecientes al espacio, y A es amigo de C y C amigo de B, se genera un lazo mistico mediante el cual A y B son amigos, aunque pudieren no conocerse.

Problema

Dada una descripcion de los sucesos que existen durante la estancia de N individuos en un espacio definido, responder secuencialmente a las preguntas fornuladas, de manera tal que se sepa si en algun momento un indiviuo es amigo del otro.

Entrada

Un unico numero N indicando la cantidad de Individuos

Un numero M indicando la cantidad de preguntas o sucesos que acontecen

Las siguientes M lineas contendran una letra 'P' seguida de dos enteros A y B de tal modo que se debera saber si A es amigo de B en base a los saludos que hallan sido registrados hasta el momento, en caso contrario, una letra 'S' seguida de dos numero A y B indicando que el individuo Ase ha saludado con el individuo B

Ejemplo:
Entrada   Salida
5 8  
 S 1 2  
 S 2 3  
 P 2 4  
 S 4 5  
 P 5 3  
 S 5 1  
 P 2 4  
 P 5 3
Salida

Un numero en una linea por cada pregunta dada en la entrada con un 1 si es que son amigos y un cero en caso contrario

Ejemplo:
Entrada   Salida
0  
 0  
 1  
 1
Límites

0< N < 100,000

0<M < 100,000

por el momento lo que llevo pensado es lo siguiente:
crear un array del tamaño de los amigos donde ese array almacenara vectores.
ahora como en el ejemplo meten un saludo de las personas 1 y 2.
en el vector de la persona 1 meto el 2
en el vector de la persona 2 meto el 1
con esto se que ambos se conocen.
ahora meten un salud de las personas 2 y 3.
hago lo mismo que arriba pero si nos damos cuenta tambien deben conocerse 1 y 3 asi que debo hacer algo mas.
aqui segun yo lo complicado:
          hago un for que recorra los amigos amigos de "a" donde a cada amigo de "a"
          le agrego un amigo de "a" que no tenga (por el lazo misterioso que mencionan        en el el problema)
por ejemplo:
en este caso el amigo a es 2 que tiene de amigos 1 y 3.
recorro el 2 llego al 1 y checo es amigo de 3 ? no, entonces añadelo
ahora llego al tres y checo es amigo de 1 ? no, entonces añadelo
bueno eso es todo lo que llevo ahora el codigo, que aun no acabo mi idea por lo que les mencione arriba:
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct arrays{
  4.     vector<int>amigos;
  5. }persona;
  6. int main(){    
  7.     bool encontrado;
  8.     char opcion;
  9.     int individuos, preguntas, a, b;
  10.     int i, j, k, l;
  11.     cin>>individuos>>preguntas;
  12.     persona ar[individuos + 1];
  13.     for(i = 0; i < preguntas; i++){
  14.         cin>>opcion>>a>>b;
  15.         if(opcion == 'S'){
  16.             ar[a].amigos.push_back(b);
  17.             ar[b].amigos.push_back(a);
  18.             for(j = 1; j < ar[a].amigos.size(); j++)                
  19.                 for(k = j + 1; k < ar[a].amigos.size() + 1; k++)
  20.                     for(l = 0; l < ar[j].amigos.size(); l++)
  21.  
  22.  
  23.         }
  24.         else{
  25.  
  26.         }
  27.     }
  28.     return 0;
  29. }
  30.  
si se les ocurre una idea mejor a la mia por favor!! avisenme!!!
Páginas: [1] 2
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines