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

Zadanie ze SPOJ

Ostatnio zmodyfikowano 2018-05-09 21:32
Autor Wiadomość
Pawełek
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
pekfos
» 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
michal11
» 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
pekfos
» 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
Pawełek
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
pekfos
» 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
Pawełek
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
pekfos
» 2018-05-09 20:59:22
Co? Skąd ty wytrzasnąłeś ten plik?
P-170986
« 1 » 2
  Strona 1 z 2 Następna strona