infoarena

Salut.
Este vorba de problema 8 din arhiva de probleme. In ciuda faptului ca(cel putin din punctul meu de vedere) codurile urmatoare sunt absolut identice din privinta modului de rezolvare, sursa A(scrisa de mine) primeste doar 60 de pct, pe cand sursa B(cea din care m-am inspirat din solutiile trimise) primeste 100 de pct. Toate cele patru erori pe care le primeste sursa A sunt: Time Limit Exceeded. Nu vad care este diferenta de eficienta dintre sursa A si sursa B. As aprecia in mode deosebit daca cineva ar putea sa desluseasca misterul Smile.
Sursa pe care am scris-o eu:
//Problema 8 - Cifra
 
#include <iostream>
#include <fstream>
#include <string.h>
 
char numar_mare[256];
int T;
short len;
int main()
{
 
 
    std::ifstream in_cifra("cifra.in");
    std::ofstream out_cifra("cifra.out");
 
    //suma pentru n = 100 este egal cu 0
    //ceea ce inseamna ca suma pentru oricare n este date de n = ultimele doua cifre ale lui n
    //ultimele cifre pentru toate numerele incepand de la 100
    short n_egal_100[100];
 
    for(short num = 1; num <= 99; num++)
    {
        n_egal_100[num] = num;
        //aflu ultima cifra a lui n ^ n
        for(int i = 1; i < num; i++)
        {
            n_egal_100[num] *= num;
            n_egal_100[num] %= 10;
        }
        //memorez suma de pana acum
        n_egal_100[num] += n_egal_100[num - 1];
        n_egal_100[num] %= 10;
    }
 
    //numarul de teste pentru N
    in_cifra >> T;
 
    //din nu stiu ce cauza citeste un rand gol, deci il citesc si trec mai departe
    std::string gol;
    std::getline(in_cifra, gol);
    //efectuez cele T teste pentru N
    while((T--) > 0)
    {
        //voi avea numere mari, asadar le voi citi ca string-uri
        in_cifra >> numar_mare;
        len = strlen(numar_mare);
 
        // daca numarul are o cifra
        if(len == 1)
        {
            out_cifra << n_egal_100[numar_mare[0] - '0'] << std::endl;
        }
        //in caz contrar
        else{
 
            out_cifra << n_egal_100[(numar_mare[len - 2] - '0')* 10 + numar_mare[len - 1] - '0'] << std::endl;
        }
 
    }
 
    return 0;
}

sursa B(inspiratia):

#include <fstream>
#include <cstring>
using namespace std;
 
int l,t,i,cif,j;
int a[102];
char n[102];
ifstream fi("cifra.in");
ofstream fo("cifra.out");
 
int main()
{
    fi>>t;
    for(i=1;i<=99;i++)
    {
        a=i;
        for(j=1;j<i;j++)
        {
            a=a*i;
            a=a%10;
        }
        a=a+a[i-1];
        a=a%10;
    }
    for(i=1;i<=t;i++)
    {
        fi>>n;
        l=strlen(n);
        if(l==1)
            fo<<a[n[l-1]-'0']<<'\n';
        else
            fo<<a[(n[l-2]-'0')*10+(n[l-1]-'0')]<<'\n';
 
    }
}

Sursele par a avea aceeasi complexitate intr-adevar. In schimb sesizez ca folosesti std::endl pentru a afisa rand nou. Aceasta din pacate duce si la golirea fortata a buffer-ului de scriere, ceea ce ia timp mult. Ar trebui sa folosesti "\n" in loc de std::endl, care afiseaza rand nou fara a forta golirea buffer-ului.

PS: Ti-am sters mesajul identic din arhiva de probleme. Incearca sa postezi intr-un singur loc, preferabil pe topicul problemei (il gasesti de pe pagina problemei, dand scroll pana jos la sectiunea de comentarii).