Python - Programas de práctica Nuclear Reactors

Esta es una solución al problema de practica Nuclear Reactors de codechef.com, la solución es correcta pero para los casos grandes se pasa del tiempo.

Enunciado:

There are K nuclear reactor chambers labelled from 0 to K-1. Particles are bombarded onto chamber 0. The particles keep collecting in the chamber 0. However if at any time, there are more than N particles in a chamber, a reaction will cause 1 particle to move to the immediate next chamber(if current chamber is 0, then to chamber number 1), and all the particles in the current chamber will be be destroyed and same continues till no chamber has number of particles greater than N. Given K,N and the total number of particles bombarded (A), find the final distribution of particles in the K chambers. Particles are bombarded one at a time. After one particle is bombarded, the set of reactions, as described, take place. After all reactions are over, the next particle is bombarded. If a particle is going out from the last chamber, it has nowhere to go and is lost.

Enunciado completo

Código:

#!/usr/bin/env python
linea = raw_input()
i=0
c=0
linea = linea.split()
n_centrales = 0
n_centrales = int(linea[2])
max = 0 
max = int(linea[1])
n_bombardeos = 0 
n_bombardeos = int(linea[0])
centrales = [0] * n_centrales
def bombardear( n ):
 if n >= n_centrales:
  return
 else:
  centrales[n] = centrales[n] + 1
  if centrales[n] > max:
   centrales[n] = 0
   bombardear(n+1)
  return
  
while i < n_bombardeos:
 bombardear(0)
 i = i + 1

while c < n_centrales - 1:
 print centrales[c],
 c = c + 1

print centrales[n_centrales - 1], 

Para mejorar el tiempo habría que eliminar la recursividad.

Programación - Programas de practica

Hoy muestro la solución de uno de los problemas de practica de la web codechef.com, titulado Closind the Tweets.
Aqui el enunciado:

Little kids, Jack and Evan like playing their favorite game Glass-and-Stone. Today they want to play something new and came across Twitter on their father's laptop.

They saw it for the first time but were already getting bored to see a bunch of sentences having at most 140 characters each. The only thing they liked to play with it is, closing and opening tweets.

There are N tweets on the page and each tweet can be opened by clicking on it, to see some statistics related to that tweet. Initially all the tweets are closed. Clicking on an open tweet closes it and clicking on a closed tweet opens it. There is also a button to close all the open tweets. Given a sequence of K clicks by Jack, Evan has to guess the total number of open tweets just after each click. Please help Evan in this game. 

Aquí el enunciado completo.

Código:

#include &ltcstdlib>
#include &ltiostream>
#include &ltstdio.h>
#include &ltcstring>
#include &ltmath.h>
using namespace std;

inline void fastRead_string(string *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a="";
     while (c>33)
     {
         *a+=c;
         c=getchar();
     }
}
inline void fastRead(int *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a=0;
     while (c>33)
     {
         *a=*a*10+c-'0';
         c=getchar();
     }
}
int main(int argc, char *argv[])
{
    int N,K;
    fastRead(&N);
    fastRead(&K);
    int tweets[N];
    memset(tweets, 0, sizeof(tweets));
    int click_tweet;
    int tweet_open=0;
    string read;
    for(int i=0; i<K; i++){
        fastRead_string(&read);
        if(read[read.length()-1] == 'L'){
            memset(tweets, 0, sizeof(tweets));
            printf("0\n");
            tweet_open=0;
        }else{
            fastRead(&click_tweet);
            if(tweets[click_tweet-1] == 1){
                tweets[click_tweet-1] = 0;
                tweet_open--;
                }else{
                    tweets[click_tweet-1] = 1;
                    tweet_open++;
                }
                printf("%d\n",tweet_open); 
        }
    }

    return EXIT_SUCCESS;
}

La solución tarda 0.03 segundos, quedando la 144 de 335, podría quedar mejor de entregarlo antes ya que los programas se ordenan por el tiempo que tardan y si hay empates el ultimo en subirse queda al final.

Programación - Codechef November Challenge 2012

Ha terminado el concurso de diciembre, y aquí dejo la solución a uno de los problemas planteados:

Coin Flip

El enunciado es este:

Little Elephant was fond of inventing new games. After a lot of research, Little Elephant came to know that most of the animals in the forest were showing less interest to play the multi-player games.Little Elephant had started to invent single player games, and succeeded in inventing the new single player game named COIN FLIP.

In this game the player will use N coins numbered from 1 to N, and all the coins will be facing in "Same direction" (Either Head or Tail),which will be decided by the player before starting of the game.

The player needs to play N rounds.In the k-th round the player will flip the face of the all coins whose number is less than or equal to k. That is, the face of coin i will be reversed, from Head to Tail, or, from Tail to Head, for i ≤ k.

Elephant needs to guess the total number of coins showing a particular face after playing N rounds. Elephant really becomes quite fond of this game COIN FLIP, so Elephant plays G times. Please help the Elephant to find out the answer.

Podeis encontrar el enunciado completo aqui: Enunciado

La solución que he propuesto es la siguiente:

#include &ltcstdlib>
#include &ltstdio.h>
#include &ltcstdio>
using namespace std;

inline void fastRead(int *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a=0;
     while (c>33)
     {
         *a=*a*10+c-'0';
         c=getchar();
     }
}
    
int main(int argc, char *argv[])
{
    int T, G;
    fastRead(&T);
    for(int k=0; k<T; k++){
    fastRead(&G);
    int games[G][3]; 
    for(int i=0; i<G;i++){
        for(int j=0; j<3;j++){
        fastRead(&games[i][j]);
    }
        if(games[i][1]%2 == 0){ 
                printf("%d\n", games[i][1]/2);
        }else{
            if(games[i][0] == games[i][2]){ 
               printf("%d\n", games[i][1]/2);
            }else{printf("%d\n", (games[i][1]/2)+1);}
        }

}  
}

    return 0;
}

Esta solución ha quedado la 129 de 2192 soluciones correctas. En comparación con la mejor solución, yo tengo una peor I/O, y aunque los dos nos hemos dado cuenta de que la clave era la comparación de los números de la entrada, el otro programador se ahorra una comparación que yo si hago, que posiblemente no sea necesaria. Para practicar de cara al concurso de diciembre intentaré hacer algunas practicas que hay en la web y las subire si salen bien.

¿Concursos de informática?

Esta entrada va a tratar sobre los concursos de informática, en estos concursos se participia resolviendo problemas, de programación, de inteligencia artificial, de hacking, etc.

Se pueden encontrar concursos de muchos niveles de dificultad, no hace falta ser experto. Y como todo concurso la mayoria tiene un premio, muchas veces económico de hasta 10,000$ los más grandes.

Pueden ser un punto de partida para los aficionados a la programación de resolver cosas con un cierto nivel de complejidad. Ya que no es solo resolver el problema, ya que muchas veces hay límite en el tiempo de respuesta o se nos van a dar unos datos de entrada muy grandes y el programa no debe fallar.

Para los interesados dejo los enlaces, avisaré por twitter de los nuevos concursos o fechas.

Programación
Codechef (Concursos mensuales)	http://www.codechef.com/
Google Code Jam	http://code.google.com/codejam
Challenge24	http://ch24.org/
Programacion en matlab	http://www.mathworks.com/matlabcentral/contest/
Tuenti Contest	https://contest.tuenti.net/

Inteligencia Artificial
AI Challenge	http://aichallenge.org/
Mario AI Championship	http://www.marioai.org/
Ms Pac-Man vs Ghosts League	http://www.pacman-vs-ghosts.net/

Hacking
Facebook Hacker Cup	https://www.facebook.com/hackercup/

También compartiré los trucos que me encuentre que puedan ser utiles para los concursos.
Saludos y si os animais no olvideos contar como habeis quedado