Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[SPOJ] Dwie cyfry silnii

Ostatnio zmodyfikowano 2011-12-22 10:18
Autor Wiadomość
jsc
Temat założony przez niniejszego użytkownika
[SPOJ] Dwie cyfry silnii
» 2011-12-21 21:31:54
Na zadanie w SPOJ zrobiłem taki program
C/C++
#include <iostream>

using namespace std;

typedef int liczba;

typedef int kontrolna;

int main()
{
    liczba wejscieSilnii;
    liczba wyjscieSilnii;
   
    liczba tymczas;
   
    liczba kursor;
   
    kontrolna iloscTestow;
    kontrolna ktoryTest;
   
    cin >> iloscTestow;
    for( ktoryTest ^= ktoryTest; ktoryTest < iloscTestow; ktoryTest++ )
    {
        cin >> wejscieSilnii;
       
        if( wejscieSilnii > 1 )
        {
            wyjscieSilnii = 1;
           
            wejscieSilnii++;
           
            for( kursor = 2; kursor < wejscieSilnii; ++kursor )
            {
                wyjscieSilnii *= kursor;
            }
           
            tymczas = wyjscieSilnii % 100;
            cout << tymczas / 10 << " " << tymczas % 10 << endl;
        }
       
        else
        {
            cout << "0 1" << endl;
        }
       
    }
    return 0;
}

Sędzia stwierdza, że przekraczam czas. Program wykonuje tylko niezbędne czynności i nie wiem jak jeszcze to zoptymalizować.
P-46017
ison
» 2011-12-21 21:45:47
Sędzia stwierdza, że przekraczam czas.
i tak ma być ;) Twoje rozwiązanie to zwykły brute.

złożoność O(t*n)
gdzie t to ilość testów a n to liczba dla której wykonujesz obliczenia
Opis każdego przypadku składa się z jednej linii, w której znajduje się jedna nieujemna liczba całkowita n (0 ≤ n ≤ 1 000 000 000).
wykonujesz zatem maksymalnie 10^9 operacji dla 1 liczby, Twój program może to liczyć nawet kilka lat ;D
już pomijam fakt, że liczysz silnię z miliarda, silnia z 13 już się nie mieści w incie, a co tu mówić o silni z 10^9
Rozwiązanie do tego zadania jest, zapewniam Cię :)

a, i tak na przyszłość, nie używaj cout ani cin bo w ten sposób na czasówkach można się nieźle przejechać
P-46018
michalp
» 2011-12-21 21:49:54
Tego nie trzeba liczyć ;)
P-46019
jsc
Temat założony przez niniejszego użytkownika
» 2011-12-21 22:06:52
Twoje rozwiązanie to zwykły brute.

Zrobić na boku tablicę, którą program ma przeglądać?
P-46021
ison
» 2011-12-21 22:15:27
jedyne Twoje zadanie to zrobić tak, aby program dawał poprawne wyniki, zużywał nie więcej niż 32 MB pamięci i wykonywał nie więcej niż ok. 10^8 operacji, to jak to zrobisz to już Twoja kwestia, poczytaj komentarze do tego zadania na spoju

brutem nazywa się rozwiązanie, które działa dla małych danych z wejścia, z powodu wysokiego zużycia pamięciowego lub słabej złożoności
P-46024
jsc
Temat założony przez niniejszego użytkownika
» 2011-12-22 10:18:17
Dobra, już rozwiązałem.
P-46035
« 1 »
  Strona 1 z 1