[SPOJ] Dwie cyfry silnii
Ostatnio zmodyfikowano 2011-12-22 10:18
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
#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ć. |
|
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ć |
|
michalp |
» 2011-12-21 21:49:54 Tego nie trzeba liczyć ;) |
|
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ć? |
|
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 |
|
jsc Temat założony przez niniejszego użytkownika |
» 2011-12-22 10:18:17 Dobra, już rozwiązałem. |
|
« 1 » |