Zadanie ze SPOJ
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Zadanie ze SPOJ

AutorWiadomość
Temat założony przez niniejszego użytkownika
Zadanie ze SPOJ
» 2018-05-04 15:19:09
Witam, rozwiązuję zadania z anglojęzycznego SPOJ

Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example
Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

oto program :
C/C++
#include <iostream>
#include <vector>

using namespace std;

void sprawdzanie( vector < unsigned int > & xd, int o, vector < unsigned int > & xd2 )
{ for( unsigned int kasz = xd[ o ]; kasz <= xd[ o + 1 ]; kasz++ )
    {
        for( int i = 2; i <= kasz; i++ )
        { if( kasz % i == 0 && i < kasz )
                 break;
           
            if( i == kasz )
                 xd2.push_back( kasz );
           
        }
    }
}
void wypisywanie( vector < unsigned int > xd3 )
{
    for( int p = 0; p < xd3.size(); p++ )
    {
        cout << xd3[ p ] << endl;
        if( xd3[ p ] > xd3[ p + 1 ] )
             cout << endl;
       
    }
}


int main()
{ unsigned int a, b, c;
    vector < unsigned int > in, zbiera;
    cin >> a;
   
    while( a-- )
    {
        cin >> b >> c;
        in.push_back( b );
        in.push_back( c );
    }
    for( int j = 0; j < in.size(); j += 2 )
         sprawdzanie( in, j, zbiera );
   
    wypisywanie( zbiera );
    return 0;
}

Program kompiluję się poprawnie, problem w tym że nie mieści się w limicie czasowym przez co SPOJ nie chce mi zaliczyć tego programu.
Co (oprócz wskaźników, słyszałem że wskaźniki przyśpieszają pracę programu, niestety jeszcze się ich porządnie nie douczyłem dlatego je ominąłem) może przyspieszyć tutaj pracę tego programu?
P-170924
» 2018-05-04 15:51:10
Nie przekazuj wektorów przez wartość i nie używaj push_back() bez wcześniejszego zarezerwowania pamięci.
P-170925
» 2018-05-04 15:51:33
Ja bym zaczął od takiego nazywania zmiennych i formatowania kodu aby nie zniechęcać czytających do jego analizy.
P-170926
» 2018-05-04 15:53:15
Po przeczytaniu treści zadania: nie używaj w ogóle wektora. Nie przechowuj w ogóle wszystkich danych naraz.
P-170927
Temat założony przez niniejszego użytkownika
» 2018-05-04 16:30:18
Ja bym zaczął od takiego nazywania zmiennych i formatowania kodu aby nie zniechęcać czytających do jego analizy.

Wybacz, zapomniałem zmienić nazwy zmiennych na bardziej 'oficjalne' :) A jeśli chodzi o formatowanie kodu to co miałeś na myśli? Brak komentarzy?


Po przeczytaniu treści zadania: nie używaj w ogóle wektora. Nie przechowuj w ogóle wszystkich danych naraz.

Na początku chciałem to zrobić za pomocą tablic, ale nie jest to takie proste gdy na wejściu dopiero dowiadujemy się z ilu elementów ma składać się taka tablica (przynajmniej dla mnie to było zbyt trudne) Przeszukałem trochę zagraniczne fora i większość programistów w tym zadaniu w swoim kodzie miało wektor.
P-170928
» 2018-05-04 17:01:08
Przeszukałem trochę zagraniczne fora i większość programistów w tym zadaniu w swoim kodzie miało wektor.
Większość programistów robiąca zadania ze SPOJa nie powinno się nazywać programistami. Raczej bandą kompletnych nowicjuszy, którzy nie wiedzą jak działają standardowe wejście i wyjście. W zadaniu najpierw jest podana specyfika wejścia, potem specyfika wyjścia, więc taki żółtodziób z zadaniem przełożenia jabłek z jednego wiadra do drugiego nagle ma problem, bo potrzebuje trzeciego wiadra.

Pytanie awansowało do grona "często zadawanych"
» Kurs C++ / FAQMam problem z zadaniem ze SPOJa pytanie/odpowiedź
P-170929
Temat założony przez niniejszego użytkownika
» 2018-05-09 20:57:32
Zrobiłem tak jak pisałeś z plikami i dalej jest problem z czasem 'time limit exceeded'

Program po poprawkach
C/C++
#include <iostream>
#include <fstream>
using namespace std;

void sprawdzanie( unsigned int & d, unsigned int & e ) //stara nazwa funkcji, obecnie program sprawdza i wypisuje liczby pierwsze
{ for( unsigned int liczba = d; liczba <= e; liczba++ ) //pêtla przesuwa kolejne liczby z podanego przedzia³u
    {
        for( unsigned int i = 2; i <= liczba; i++ )
        { if( liczba % i == 0 && i < liczba ) //sprawdza czy liczba jest pierwsza, jesli nie to przerywa petle
                 break;
           
            if( i == liczba ) //jesli dojdzie do konca to znaczy ze jest pierwsza
                 cout << liczba << endl;
           
        }
    }
}


int main()
{ unsigned int a, b, c;
    fstream plik;
    plik.open( "dane.txt", ios::out );
    cin >> a; //podanie ilosci przedzialow
    plik << a << endl;
   
    while( a-- )
    {
        cin >> b >> c; //wpisywanie przedzialow a razy
        plik << b << c << endl;
        sprawdzanie( b, c );
        cout << endl;
    } plik.close();
    return 0;
}

Wszystkie uwagi dotyczące funkcji przyjmę z pokorą :)
P-170985
» 2018-05-09 20:59:22
Co? Skąd ty wytrzasnąłeś ten plik?
P-170986
« 1 » 2
 Strona 1 z 2Następna strona