¡Acepta el reto!

Discussion on all other matters, maybe unrelated to the COJ.
Forum rules
Discussing politics is not allowed. Any posts containing political comments will be penalized.
MPC1984
Posts: 2
Joined: Tue Jun 09, 2015 1:42 pm
Gender: None specified

¡Acepta el reto!

Postby MPC1984 » Tue Jun 09, 2015 1:56 pm

Hola a todos!

Aquí os dejo la URL de una web con ejercicios de programación bastante interesantes: https://www.aceptaelreto.com

Tengo tres problemas atascados, ¿alguien me podría echar una mano con ellos? Los números de los problemas son: 230, 257, 261.

PROBLEMA 230 https://www.aceptaelreto.com/problem/statement.php?id=230

El código es el siguiente (veredicto TLE):

Code: Select all

#include <stdio.h>

void quicksort (long lista[], int limite_izq, int limite_der)
{
    int izq, der, temporal, pivote;
    izq = limite_izq;
    der = limite_der;
    pivote = lista[(izq + der) / 2];
    do {
        while (lista[izq] < pivote && izq < limite_der)izq++;
        while (pivote < lista[der] && der > limite_izq)der--;
        if (izq <= der)
        {
            temporal = lista[izq];
            lista[izq] = lista[der];
            lista[der] = temporal;
            izq++;
            der--;
        }
    } while (izq <= der);
    if (limite_izq < der)
    {
       quicksort(lista, limite_izq, der);
    }
    if (limite_der > izq)
    {
       quicksort(lista, izq, limite_der);
    }
}

int busquedaBinaria (long vector[], int n, int dato) {
   int centro, inf, sup;
   inf = 0;
   sup = n - 1;
    while(inf <= sup) {
       centro = (sup + inf) / 2;
        if(vector[centro] == dato) {
           return centro;
        } else if(dato < vector[centro]) {
           sup = centro - 1;
        } else {
           inf = centro + 1;
        }
    }
    return -1;
}

int main(void) {
   
int i, j, numHabitantes, contador, pos;
   
   scanf("%d", &numHabitantes);
   while(numHabitantes > 0) {
      contador = 0;
      long diasVividos [numHabitantes];
      long ordenados [numHabitantes];
      for(i = 0; i < numHabitantes; i++) {
         scanf("%d", &diasVividos[i]);
         ordenados[i] = diasVividos[i];
      }
      quicksort(ordenados, 0, numHabitantes - 1);
      for(i = 0; i < numHabitantes; i++) {
         pos = busquedaBinaria(ordenados, numHabitantes - i, diasVividos[i]);
         contador = contador + pos;
         for(j = pos; j < numHabitantes - i; j++) {
            ordenados[j] = ordenados[j + 1];
         }
      }
      printf("%d\n", contador);
      scanf("%d", &numHabitantes);
   }
   return 0;
}


PROBLEMA 257 https://www.aceptaelreto.com/problem/statement.php?id=257

El código es el siguiente (veredicto WA):

Code: Select all

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

int i, j, numCasosPrueba, numPuntosControl, x, y, x1, y1, x2, y2, tiempo, parcial1, parcial2;

int main(void) {
   scanf("%d", &numCasosPrueba);
   for(i = 0; i < numCasosPrueba; i++) {
      scanf("%d", &numPuntosControl);
      scanf("%d", &x1);
      scanf("%d", &y1);
      tiempo = x1 + y1;
      x2 = 0;
      y2 = 0;
      for(j = 0; j < numPuntosControl - 1; j++) {
         scanf("%d", &x);
         scanf("%d", &y);
         parcial1 = abs(x - x1) + abs(y - y1);
         parcial2 = abs(x - x2) + abs(y - y2);
         if(parcial1 < parcial2) {
            tiempo = tiempo + parcial1;
            x1 = x;
            y1 = y;
         } else {
            tiempo = tiempo + parcial2;
            x2 = x;
            y2 = y;
         }
      }
      printf("%d\n", tiempo);
   }
   return 0;
}


PROBLEMA 261 https://www.aceptaelreto.com/problem/statement.php?id=261

El código es el siguiente (veredicto TLE):

Code: Select all

#include <stdio.h>

int posibilidades [6][4] = {{2, 4, 3, 5}, {1, 3, 4, 6}, {1, 2, 5, 6}, {1, 2, 5 ,6}, {1, 3, 4, 6}, {2, 3, 4, 5}};

int juego (int suma, int caraDado, int jugador) {
   int i;
   
   if(suma>= 1000) {
      return jugador;
   } else {
      for(i = 0; i < 4; i++) {
         if(juego(suma+ posibilidades[caraDado- 1][i], posibilidades[caraDado- 1][i], -jugador) == jugador) {
            return jugador;
         }
      }
   }
   return -jugador;
}

int main(void) {
   int i, numCasosPrueba, suma, numero;
   scanf("%d", &numCasosPrueba);
   for (i = 0; i < numCasosPrueba; i++) {
        scanf("%d %d", &suma, &numero);
        if(juego(suma, numero, 1) == -1) {
           printf("PIERDE\n");
        } else {
           printf("GANA\n");
        }
    }
   return 0;
}


Gracias por adelantado. ;)



User avatar
Dariel
Posts: 51
Joined: Fri Nov 18, 2011 7:51 pm
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: ¡Acepta el reto!

Postby Dariel » Wed Jun 10, 2015 3:27 pm

Postea los problemas, la inmensa mayoría no tienen acceso a internet..

MPC1984
Posts: 2
Joined: Tue Jun 09, 2015 1:42 pm
Gender: None specified

¡Acepta el reto!

Postby MPC1984 » Thu Jun 11, 2015 10:29 am

Aquí os dejo los enunciados de los problemas:

PROBLEMA 230

Una vez que un avance tecnológico llega al "gran público" suelen surgir efectos derivados de su uso que nadie habría predicho en un principio. La nomofobia o miedo irracional a salir de casa sin el teléfono móvil, el síndrome de De Quervain por el uso intensivo de los pulgares o la extendida adicción a Internet son tres ejemplos de las secuelas digitales que sufrió la población en el siglo XXI.

Cuando se consiguió viajar en el tiempo, sólo unos pocos psicólogos dieron la voz de alarma por el peligro que podría tener un uso excesivo de esos viajes en las personas. En un primer momento lo llamaron desórdenes temporales aunque el término evolucionó a lo que hoy llamamos el síndrome de Fry en alusión a un personaje de una conocida serie del siglo XXI.

Estos desórdenes son consecuencia de un excesivo consumo de los viajes en el tiempo debido al envejecimiento que sigue sufriendo el cuerpo aunque esté en un momento que no le corresponde. Por ejemplo, si un estudiante de historia de 20 años pasa 30 años en el Antiguo Egipto estudiando in situ las vidas y costumbres de las gentes de esa época, cuando vuelve tiene el cuerpo de un hombre de 50 años aunque su edad para la administración siga siendo 20. Los desórdenes mentales producidos al verse más viejo que su propio padre pueden llevarle a la perdición.

En la última reunión del MIENTE (MInisterio de ENtuertos TEmporales) se decidió tomar medidas ante esta situación. El primer paso es conocer cuánta gente está afectada y el nivel de desorden de cada una. Se ha definido el nivel de desorden temporal de una persona como el número de personas que, aún siendo más viejas que uno mismo desde el punto de vista administrativo, han vivido menos días.

Para eso, el MIENTE maneja el número de días reales que ha vivido cada persona y ahora quiere conocer el desorden temporal de toda la población, o lo que es lo mismo, la suma de los desórdenes temporales de todos los habitantes.

ENTRADA
La entrada estará compuesta por distintos casos de prueba, cada uno en dos líneas. La primera línea tendrá el número de habitantes de la población que está siendo estudiada (hasta 100.000). En la segunda línea aparecerá la edad real (número de días vividos) de cada una de las personas, ordenada por edad administrativa.

El último caso de prueba es seguido por una línea con un 0 que no debe procesarse.

SALIDA
Para cada caso de prueba se mostrará un número indicando el desorden total de la población según la definición dada.

ENTRADA DE EJEMPLO
4
1000 2000 3000 4000
4
10000 2000 8000 1000
0

SALIDA DE EJEMPLO
0
5

NOTAS
La respuesta al segundo caso de prueba del ejemplo es el resultado de sumar los desórdenes temporales de todos los individuos. El desorden temporal del primero es 3, pues a pesar de ser el más joven (desde el punto de vista administrativo) es más viejo que los otros tres. El desorden temporal del segundo es 1, pues es más viejo que el último, y el desorden temporal del tercero es también 1 por la misma razón.

PROBLEMA 257

En la zona residencial de Concursolandia organizan una yincana todos los años. Los concursantes, por parejas, recorren en orden una serie de puntos, repartidos por la urbanización, donde jueces que velan por el buen funcionamiento del concurso plantean una serie de acertijos a los concursantes, según van llegando. Como en muchas yincanas, los acertijos están encadenados: es imposible acertar uno si no se han recogido las pistas proporcionadas al resolver los acertijos planteados en todos los puntos anteriores (con un número menor).

El complejo residencial está formado por una serie de parcelas muy bien alineadas y separadas mediante avenidas horizontales (de este a oeste) o calles verticales (de norte a sur), como muestra el dibujo. Los puestos de control (círculos rojos) se encuentran en intersecciones entre calles. Los concursantes, que comienzan en la esquina inferior izquierda de la urbanización con pistas para resolver el primer acertijo, para alcanzar un punto tienen que caminar por estas calles, de la forma en la que decidan, pero no pueden atravesar por medio de parcelas. Los concursantes, para no perturbar en exceso a los vecinos, siempre van a la misma velocidad y tardan exactamente 1 minuto en ir de una intersección a la siguiente en horizontal o vertical. Gana el concurso el equipo que menos tiempo emplee en resolver todos los acertijos.

Mica y Dina forman pareja, pero tienen claro que ir siempre juntas les perjudica, y que podrían ganar tiempo si cada una sigue una ruta distinta, comunicándose por móvil las pistas según las vayan recibiendo para que la otra pueda avanzar. Al proponérselo a los jueces, estos no tienen claro si supone demasiada ventaja o si de permitirlo se llenaría el barrio de chicos pululando, por lo que imponen una restricción más: si optan por separarse, en todo momento solamente una de ellas podrá estar caminando y la otra deberá estar parada en un punto de control (o en el comienzo).

¿Cuál es el menor tiempo que necesitan Mica y Dina para resolver todos los acertijos respetando todas estas restricciones?

ENTRADA
La entrada comienza con un entero que indica el número de casos de prueba que vendrán a continuación. Cada caso comienza con el número N (entre 1 y 500) de puntos de control que forman la yincana. A continuación aparecen N líneas cada una con dos enteros que indican la avenida y la calle en los que se encuentran cada uno de estos puntos, en el orden en el que deben ser visitados. Todos los puntos están en intersecciones diferentes, y ninguno está en el punto de salida. Tanto las avenidas como las calles están numeradas desde 0 hasta 10.000. Los concursantes parten siempre de la intersección (0,0), pero este punto no se contabiliza dentro de los N a visitar.

SALIDA
Para cada caso de prueba se escribirá el mínimo tiempo necesario para ganar la yincana, si se compite por parejas y se siguen las restricciones impuestas por los jueces.

ENTRADA DE EJEMPLO
2
6
4 5
2 6
3 1
1 4
5 3
3 8
2
4 4
6 6

SALIDA DE EJEMPLO
29
12

PROBLEMA 261

Los dados son objetos habituales en infinidad de juegos. Los clásicos son cubos con sus caras numeradas del 1 al 6, pero la cantidad de variaciones es enorme, haciendo uso de muchos otros poliedros con números de caras diferentes.

La utilidad principal de los dados es la obtención de números aleatorios, pero hay usos más imaginativos, como el del juego para dos personas que nos ocupa, llamado Voltea el dado. En él, el primer jugador coloca el dado (de 6 caras) encima de la mesa, mostrando el número que desee. En cada turno, de manera alterna, los jugadores van haciendo rotar el dado con una ligera presión sobre alguna de las aristas, de modo que la nueva cara superior pase a ser una de las que antes eran caras laterales. El valor de la nueva cara superior se suma al acumulado a lo largo de la partida, empezando con el inicial elegido por el jugador que empieza. El jugador que hace que la suma llegue (o supere) al número 1.000 pierde.

ENTRADA
La entrada estará compuesta por un primer número indicando la cantidad de casos de prueba que vendrán a continuación.

Cada caso de prueba, en una línea, contendrá dos números. El primero 1 ≤ n ≤ 1.000 especifica la suma acumulada hasta este momento, y el segundo 1 ≤ v ≤ 6 el número que es visible en la cara superior del dado, que ya habrá sido sumado.

SALIDA
Para cada caso de prueba, se deberá analizar si el jugador que tiene el turno en la situación descrita ganará la partida si juega bien. Se escribirá "GANA" si ganará, y "PIERDE" en otro caso.

Recuerda que en los dados clásicos, la suma del valor de dos caras opuestas suma siempre 7. Por ejemplo, si la cara superior visible de un dado contiene el 6, la cara oculta, apoyada en la mesa, contendrá un 1. Eso significa que el jugador que tiene el turno únicamente podrá conseguir hacer visibles los valores 2, 3, 4 o 5.

ENTRADA DE EJEMPLO
3
999 1
998 3
971 1

SALIDA DE EJEMPLO
PIERDE
GANA
GANA


Return to “Off topic”

Who is online

Users browsing this forum: No registered users and 1 guest