Mensajes

Solo tienes que limpiar el buffer

Código (c) [Seleccionar] Expandir


#include<stdlib.h>
#include<stdio.h>

float m;
char d;

main(){
    printf("Escribe tu valor en metros: ");
    scanf("%f",&m);
    printf("Este es tu valor en pies: %f\n", m * 3.28084);
    printf("\n¿Quieres hacer otra conversion?(S/N): ");
    fflush(stdin);
    scanf("%c", &d);
    if(d == 'S' || d == 's'){
        system("cls");
        return main();
    }
    return 0;
}

Te dejo este link para que lo entiendas: http://www.carlospes.com/curso_de_lenguaje_c/01_11_la_funcion_fflush.php

Ivancea, lo único que sabia es que usaba la estructura pair y pensaba que un árbol binario de búsqueda, ahora buscare que es ese árbol binario hilvanado y rojo - negro.
Gracias por responder 

Pues quiero saber que usan (arboles, hash table, etcetera) para hacerlo por mi mismo y hacer unas modificaciones.
Gracias por tu atencion.

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 (cpp) [Seleccionar] Expandir


#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...

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:

Código (cpp) [Seleccionar] Expandir


/**
   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;
       }
   }
}



Gracias por contestar, ya intente eso que me comentas y aun asi me da el mismo resultado
.

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 (cpp) [Seleccionar] Expandir


#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;
}

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 (cpp) [Seleccionar] Expandir

#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;
}

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:

Código (cpp) [Seleccionar] Expandir

#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.

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:

Código (cpp) [Seleccionar] Expandir

#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.