|
Mostrar Mensajes
|
Páginas: 1 [2] 3 4
|
14
|
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#problemsL-¿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%: #include<bits/stdc++.h> using namespace std; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n, amigos, aux, suma = 0, cont; cin>>n>>amigos; int ar[n]; for(int i = 0; i < n; i++){ cin>>ar[i]; suma += ar[i]; } int optimo = suma / amigos; while(optimo){ cont = 0; for(int j = 0; j < n; j++) cont += ar[j] / optimo; if(cont >= amigos) break; else optimo--; } cout<<optimo; return 0; }
Si tienes alguna otra idea a la mia, por favor mencionala, me ayudarias mucho...
|
|
|
15
|
Programación / Programación C/C++ / Re: Juego Gato: definir ganador y repetir coordenada
|
en: 3 Diciembre 2016, 22:12 pm
|
Hola que tal, hace poco me encargaron en el colegio un proyecto y opte por hacer un gato, eso de usar coordenadas (al momento de ingresarlas) en lo personal es un poco incomodo, espero y te ayude: /** Alumno: Luis Eduardo Garza Medina programa: Juego Nombre: Gato El juego posee un menu amigable con el usuario, entendible para cualquier usuario. para el menu solo se usan las teclas: 'i', 'e' y 's'; y para jugar son los numeros, donde para acceder a una casilla debe presionarse el siguiente numero: 1 2 3 4 5 6 7 8 9 el jugador uno es representado por un '1' equivalente a X el jugador dos es representado por un '2' equivalente a O Al finalizar el programa, este indica los resultados finales de cada jugador. */ #include <stdio.h> #include<windows.h> #define uno gato[0][0] #define dos gato[0][1] #define tres gato[0][2] #define cuatro gato[1][0] #define cinco gato[1][1] #define seis gato[1][2] #define siete gato[2][0] #define ocho gato[2][1] #define nueve gato[2][2] //el compilador sustituye la cadena en #define short gato[3][3] ={{0,0,0}, //definimos matriz {0,0,0}, {0,0,0}}; short won[2]; //definimos array int verifica(){ //comprobamos si un jugador ya ganó if(uno == dos && dos == tres) return uno; if(uno == cuatro && cuatro == siete) return uno; if(uno == cinco && cinco == nueve) return uno; if(tres == cinco && cinco == siete) return tres; if(tres == seis && seis == nueve) return tres; if(cuatro == cinco && cinco == seis) return cuatro; if(siete == ocho && ocho == nueve) return siete; if(dos == cinco && cinco == ocho) return dos; return 0; } void mostrar(){ //ponemos en pantalla el gato system("cls"); for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++) if(j < 2) printf("%d|", gato[i][j]); else printf("%d", gato[i][j]); if(i < 2) printf("\n-----\n"); else printf("\n"); } } void instrucciones(){ //funcion que muestra las instrucciones del jueo system("cls"); printf("Los controles son los numeros del 1 al 9, por ejemplo:\n\n"); printf("para acceder a la casilla superior izquierda se presiona 1\n\n"); printf("para acceder a la casilla inferorior intermedia se presiona 8\n\n"); system("pause"); } int main (){ short numero, k; char opcion; while(1){//while infinito system("cls"); //limpia la pantalla printf("JUEGO DEL GATO\n\n"); printf("Menu\n\n"); printf("presiona 'i' para ver instrucciones:\n"); printf("Presiona 'e' para comenzar\n"); printf("Presiona 's' para salir\n\n"); scanf("%s", &opcion); switch(opcion){ case 'i': instrucciones(); break; case 'e': memset(gato, 0, sizeof(gato));//inicializa la matriz con valores de 0 for(k = 1; k <= 9; k++){ //este for se repite 9 veces porque son 9 casillas mostrar(); scanf("%d", &numero); if(numero == 1) if(k % 2 == 0) //la operacion del modulo ayuda a determinar de quien es el turno uno = 2; else uno = 1; else if(numero == 2) if(k % 2 == 0) dos = 2; else dos = 1; else if(numero == 3) if(k % 2 == 0) tres = 2; else tres = 1; else if(numero == 4) if(k % 2 == 0) cuatro = 2; else cuatro = 1; else if(numero == 5) if(k % 2 == 0) cinco = 2; else cinco = 1; else if(numero == 6) if(k % 2 == 0) seis = 2; else seis = 1; else if(numero == 7) if(k % 2 == 0) siete = 2; else siete = 1; else if(numero == 8) if(k % 2 == 0) ocho = 2; else ocho = 1; else if(numero == 9) if(k % 2 == 0) nueve = 2; else nueve = 1; int ganador = verifica();//le asignamos a ganador el valor que retorne la funcion verifica if(ganador > 0){ mostrar(); printf("\nEl jugador %d es el GANADOR", ganador); won[ganador - 1]++; //aumentamos en 1 el contador del ganador break; } } system("pause>null"); break; case 's': system("cls"); printf("El jugador 1 gano: %d partidas\n", won[0]); printf("El jugador 2 gano: %d partidas\n", won[1]); printf("Gracias por jugar!\n\n"); return 0; break; default: break; } } }
|
|
|
17
|
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 #include<bits/stdc++.h> #define MAX 1000002 using namespace std; vector<int>ady[MAX]; bool visitado[MAX]; int path[MAX]; int N; //recorrido con recursion void DFS(int u, int fin){ path[N++] = u; visitado[u] = true; for(int v = 0; v < ady[u].size(); ++v) if(ady[u][v] == fin){ path[N++] = fin; for(int i = 0; i < N; i++) cout<<path[i]<<" "; exit(0); } else if(!visitado[ady[u][v]]) DFS(ady[u][v], fin); } //recorrido con cola void DFS_cola(int u, int fin){ queue<int>cola; cola.push(u); while(!cola.empty()){ int tope = cola.front(); visitado[tope] = true; path[N++] = tope; cola.pop(); for(int v = 0; v < ady[tope].size(); ++v) if(ady[tope][v] == fin){ path[N++] = fin; for(int i = 0; i < N; i++) cout<<path[i]<<" "; exit(0); } else if(!visitado[ady[tope][v]]) cola.push(ady[tope][v]); } } int main(){ int n, a, b, m(0); cout<<"Dame numero de enlaces: "; cin>>n; for(int i = 0; i < n; i++){ cin>>a>>b; ady[a].push_back(b); ady[b].push_back(a); } int inicial, fin; cout<<"Dame nodo raiz: "; cin>>inicial; cout<<"Dame nodo fin: "; cin>>fin; //DFS(inicial, fin); DFS_cola(inicial, fin); return 0; }
|
|
|
18
|
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#problemsO 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. #include<bits/stdc++.h> using namespace std; #define MAX 1000 char ady[MAX][MAX]; bool visitado[MAX][MAX]; struct Estado{ int x; int y; int d; Estado(int x1, int y1, int d1) : x(x1), y(y1), d(d1) {} }; int BFS(int x, int y, int h, int w){ Estado inicial(x,y,0); queue<Estado>estados; estados.push(inicial); memset(visitado, false, sizeof(visitado)); int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; while(!estados.empty()){ Estado actual = estados.front(); estados.pop(); if(ady[actual.x][actual.y] == 'O') return actual.d; visitado[actual.x][actual.y] = true; for(int i = 0; i < 4; i++){ int nx = dx[i] + actual.x; int ny = dy[i] + actual.y; if(nx >= 0 && nx < h && ny >= 0 && ny < w && ady[nx][ny] != 'X' && !visitado[nx][ny]){ Estado adyacente(nx, ny, actual.d + 1); estados.push(adyacente); } } } return -1; } int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int h, w, x, y, t; cin>>h>>w>>t; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ cin>>ady[i][j]; if(ady[i][j] == 'C'){ x = i; y = j; } } } cout<<BFS(x, y, h, w); return 0; }
|
|
|
19
|
Programación / Programación C/C++ / Re: ¿Mejor algoritmo? Problema con aproximaciones de Grafos
|
en: 28 Julio 2016, 06:40 am
|
Alberto un pregunta en cuanto a tu video, como te comente ya habia hecho un arbol binario, pero yo en la estructura del nodo solo habia utilizado el dato y los dos punteros izquierdo y derecho, mi pregunta es ¿Para que sirve el nodo padre? Bueno y otra duda, en tu arbol binario del problema quien es la raiz o como funciona eso de ir añadiendo nodos (disculpa mi ignorancia)? Mira este es mi codigo: #include <bits/stdc++.h> using namespace std; struct nodoArbol { struct nodoArbol *ptrIzq; int dato; struct nodoArbol *prtDer; }; typedef struct nodoArbol NodoArbol; typedef NodoArbol *ptrNodoArbol; void insertaNodo( ptrNodoArbol *ptrArbol, int valor ){ if (*ptrArbol == NULL) { /*ARBOL VACIO*/ *ptrArbol = (NodoArbol*)malloc(sizeof(NodoArbol)); (*ptrArbol)->dato = valor; (*ptrArbol)->ptrIzq = NULL; (*ptrArbol)->prtDer = NULL; } else { /* el dato a insertar es menor que el dato en el nodo actual */ if (valor < (*ptrArbol)->dato) { insertaNodo(&((*ptrArbol)->ptrIzq), valor); } else if (valor > (*ptrArbol)->dato) { insertaNodo(&((*ptrArbol)->prtDer), valor); } } } void inOrden(ptrNodoArbol ptrArbol){ if (ptrArbol != NULL) { inOrden(ptrArbol->ptrIzq); cout<<ptrArbol -> dato<<" "; inOrden(ptrArbol->prtDer); } } void preOrden(ptrNodoArbol ptrArbol){ if (ptrArbol != NULL){ cout<<ptrArbol -> dato<<" "; preOrden(ptrArbol->ptrIzq); preOrden(ptrArbol->prtDer); } } void postOrden(ptrNodoArbol ptrArbol) { if (ptrArbol != NULL){ postOrden(ptrArbol->ptrIzq); postOrden(ptrArbol->prtDer); cout<<ptrArbol -> dato<<" "; } } int main(){ ptrNodoArbol ptrRaiz = NULL; int limite,elemento; cout<<"INTRODUCE CUANTOS ELEMENTOS TENDRA EL ARBOL: "; cin>>limite; for (int i = 1; i <= limite; i++) { cout<<"INGRESE ELEMENTO: "; cin>>elemento; insertaNodo(&ptrRaiz, elemento); } cout<<"\nEL RECORRIDO EN PREORDEN ES:\n"; preOrden(ptrRaiz); cout<<"\nEL RECORRIDO EN INORDEN ES:\n"; inOrden(ptrRaiz); cout<<"\nEL RECORRIDO EN POSTORDEN ES:\n"; postOrden(ptrRaiz); return 0; }
Gracias por tu ayuda.
|
|
|
20
|
Programación / Programación C/C++ / Re: Propuestas para resolver problema en C++
|
en: 28 Julio 2016, 01:09 am
|
Alberto muchas gracias por compartir tu respuesta y por la propuesta. Mira la verdad no entiendo mucho el tema de los arboles binarios, solo he creado uno (hace 1 semama aprox.)y pues conozco muy pocas cosas, ademas de que usas cosas nuevas para mi como calloc, strtok , strtol, etc.. Pero me esforzare mucho en tratar de entenderlo. En cuanto a mi, les comparto mi respuesta ya la envie a la pagina y me da estos resultados: Status: Tiempo Limite Excedido. Porcentaje: 90%. Memoria: 48.98 MB. Tiempo: >2.78 s. Como ven es buena respuesta pues me da el 90%. Y ahora explicare que fue lo que hice: Después de buscar en internet me encontré con el set que es un contenedor asociativo que tiene la característica de no guardar valores repetidos y los guarda en orden. entonces aqui reemplazaba los vectores por los sets. ahora, lo mas complicado es donde se saludan lo explique anteriormente, ahora lo hare mejor: se saluda 1 y 2. en el set de 1 pongo el 2. en el set de 2 pongo el 1. ahora recorro el set de 1 y a los amigos de 1 les agregare los amigos de 1, lo mismo hago con el 2, pero como ambos sets tienen un solo elemento que son 1 y 2 respectivamente no pasa nada. se saluda 2 y 3. en el set de 2 pongo el 3. en el set de 3 pongo el 2. ahora recorro el set de 2 y a sus amigos les añado los amigos de 2. lo mismo hago con el 3. entonces hasta ahora los sets quedan asi: persona: conocidos: 1 2,3 2 1,3 3 1,2 preguntan 2 conoce a 4 ? checo, si cualquier set esta vacio (A o B)entonces quiere decir que no, pues no a saludado a nadie, sino recorro el set de la persona A y busco si esta la persona B. en este caso es NO. se saluda 4 y 5. en el set de 4 pongo el 5. en el set de 5 pongo el 4. ahora recorro el set de 4 y a los amigos de 4 les agregare los amigos de 4, lo mismo hago con el 5, pero como ambos sets tienen un solo elemento que son 4 y 5 respectivamente no pasa nada. entonces hasta ahora los sets quedan asi: persona: conocidos: 1 2,3 2 1,3 3 1,2 4 5 5 4 ahora preguntan 5 conoce a 3? checo, si cualquier set esta vacio (A o B) entonces quiere decir que no, pues no a saludado a nadie, sino recorro el set de la persona A y busco si esta la persona B. en este caso es NO. Por ultimo se saluda 5 con 1. en el set de 5 pongo el 1. en el set de 1 pongo el 5. ahora recorro el set de 5 y a todos sus amigos les añado los amigos que no tengan de 5, lo mismo hago con el 1 y si nos damos cuenta ya todos son amigos, por ende las siguientes preguntas son SI. Aqui les dejo el codigo: #include<bits/stdc++.h> using namespace std; /*DECLARO TODO LO QUE USARE DE SET Y EL VECTOR QUE GUARDARA LAS RESPUESTAS*/ typedef struct arrays{ set<int>amigos; }ar; set<int>::iterator j; set<int>::iterator k; vector<string>respuestas; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); bool encontrado; char opcion; int personas, comandos, a, b; int i, l, z; cin>>personas>>comandos; ar persona[personas + 1]; /*CREAMOS UN ARRAY DE SETS DE TAMAÑO PERSONAS*/ for(i = 0; i < comandos; i++){ cin>>opcion>>a>>b; if(opcion == 'S'){ persona[a].amigos.insert(b); persona[b].amigos.insert(a); for(j = persona[a].amigos.begin(); j != persona[a].amigos.end(); j++){ /* PERSONA A*/ for(k = persona[a].amigos.begin(); k != persona[a].amigos.end(); k++){ persona[*j].amigos.insert(*k); } } for(j = persona[b].amigos.begin(); j != persona[b].amigos.end(); j++){ /*PERSONA B*/ for(k = persona[b].amigos.begin(); k != persona[b].amigos.end(); k++){ persona[*j].amigos.insert(*k); } } } else{ if(persona[a].amigos.empty() || persona[b].amigos.empty()) respuestas.push_back("0\n"); else{ encontrado = false; for(j = persona[a].amigos.begin(); j != persona[a].amigos.end(); j++){/*BUSCAMOS SI EN LOS AMIGOS DE A ESTA B*/ if(*j == b){ encontrado = true; break; } } if(encontrado) respuestas.push_back("1\n"); else respuestas.push_back("0\n"); } } } for(i = 0; i < respuestas.size(); i++) cout<<respuestas[i]; return 0; }
Creo que si optimizamos la búsqueda de la persona B en A y al agregar amigos podría dar el 100% Encontre en internet algo llamado set_union y merge para eso de añadir los amigos pero eso de buscar los amigos pensaba en una búsqueda binario aunque según yo que no es posible.
|
|
|
|
|
|
|