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.

Programación - Fast I/O

Para los que participen en concursos de programación con límite de tiempo les voy a dar un pequeño código que les puede ser útil.

Es código que vale para C/C++ y mejora la lectura de datos desde entrada estandar.

Si estamos en C++ lo normal es usar "cin" y en C "scanf". Pues existe una forma de hacer esa lectura aun más rápido, que es usar estos trozos de código:

Nota: Cuando aparece &lt, equivale a <

Para leer números enteros:

inline void fastRead(int *a){
     register char c=0;
     while (c &lt 33) c=getchar();
     *a=0;
     while (c>33)
     {
         *a=*a*10+c-'0';
         c=getchar();
     }
}

Como me han hecho falta para algunos problemas, he creado versiones de este mismo código para leer char, strings y demás, aquí las dejo:

Para leer un char:

inline void fastRead_char(char *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a=c;
}

Para leer un int seguido de un char que no se quiere tener en cuenta (Ej. 12$, 90%, etc):

inline void fastRead_int(int *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a=0;
     while (c> 47 && c &lt 58)
     {
         *a=*a*10+c-'0';
         c=getchar();
     }
}

Para leer un string (C++):

inline void fastRead_string(string *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a="";
     while (c>33)
     {
         *a+=c;
         c=getchar();
     }
}

Para leer un string que contenga espacios (C++) (Ej. Hola mundo, en el anterior solo guardaria "Hola")

inline void fastRead_string2(string *a){
     register char c=0;
     while (c&lt33) c=getchar();
     *a="";
     while (c>31)
     {
         *a+=c;
         c=getchar();
     }
}

Estos códigos se pueden mejorar utilizando getchar_unlocked() en vez de getchar(), probadlo ya que a mi me dice que no encuentra "getchar_unlocked()"