Kod do przerobiania

[Freddnik]

Witam otoż mam pewien problem a mianowicie potrzebuje przerobić poniższy kod tak aby dzialał szybciej, ponieważ kiedy daję to do sprawdzarki dostaję 75 pkt i bład timelimit.

 

 

 

 

#include <iostream>

using namespace std;

int ilosc(int x, int w)
{
int a=0;
while (x<w)
     {

a++;

x=x*2;

}
return a;
}


int main()
{
int z;
cin >> z;
int x[z],w[z],a[z];
for (int i = 0; i < z; i++)
     {
cin >> x[i] >> w[i];
a[i]=0;
}

for (int i = 0; i < z; i++)
     {
cout << ilosc(x[i],w[i]) << endl;
}
    cin.ignore(2);
    return 0;
}
 

[metin1998]

Możesz napisać treść zadania?

[Freddnik]

Asia dostała na urodzinki magiczną piłeczkę. Piłeczka ta spadająca z pewnej wysokości odbija się na wysokość dwa razy większą. Asia zrzuciła piłeczkę z balkony z pewnej wysokości X. Zastanawia się teraz po ilu odbiciach piłeczka doleci do wysokości W.

Zadanie: Napisz program, który dla każdego zestawu danych:

- Wczyta wysokość X na której stoi Asia, oraz liczbę W,

-Obliczy po ilu obiciach piłeczka doleci do wysokości W,

- Wypisze wynik na standardowe wyjście.

Wejście: W pierwszej linii wejścia liczba Z , oznaczająca ilość zestawów danych. Dla każdego zestawu danych 2 liczby całkowite X i W .

Wyjście: Dla każdego zestawu danych w Z kolejnych wierszach ilość odbić po których piłeczka doleci do wysokości W.

Przykład:

Dla danych wejściowych:

2

3 4

2 6

poprawnym wynikiem jest:

1

2

 

Dopowiem jeszcze, że timelimit wynosi 2s.

Dorzucam jeszcze skróconą wersje kodu:

 

#include <iostream>

using namespace std;

int main()
{
	int c;
	cin >> c;
    int a[c], b[c];
    for(int i = 0; i<c; i++)
    {
    	cin >> a[i] >> b[i];
    }
    for(int i = 0; i<c; i++)
    {
    	int ile = 0;
    	while(a[i]<b[i])
    	{
    		ile++;
    		a[i]=a[i]*2;
    	}
    	cout << ile << endl;
    }
	cin.ignore(2);
	return 0;
}

 

[metin1998]

#include <iostream>
#include <cmath>
using namespace std;


int main() {
int n;
double a,b;
cin >> n;
for(int i=0; i <n; i++) {
    cin >> a >> b;
//a * (2^x) = b
cout << ceil(log2(b/a));

}

return 0;
}
 

 

Użyłem tutaj logarytmu.

Spójrz jak to wygląda w twoim kodzie:

 

a = a *2*2*2....

 

dopóki a nie bedzie rowne lub wieksze b;

mozna to zapisac jako

 

a * 2^x = b ( nie uwzgledniam tutaj "lub wieksze" po prostu póżniej sie zaokrągli do góry)

 

gdzie x jest tym ile razy musimy zpotegowac dwojke czyli iloscia odbic pilki.

Jak znalezc x? Użyć do tego logarytmu.

log2(a) zwraca potege do której musimy podnieść 2 żeby otrzymac a.

 

możemy to przekształcić w

 

2^x = b/a

 

czyli żeby uzyskac potege do ktorej musimy podniesc 2 żeby uzyskac b/a uzywamy log2(b/a)

zapewne liczba bedzie z ulamkiem dlatego zaokraglamy do góry

 

 

Aha i ja tu usunelem uzywanie tablic poniewaz jest to nie potrzebne, wypisywanie wyników od razu też będzie poprawne.

 

 

 

 

 

 

@edit

 

nie podałeś jak duze mogą być dane, ale wpisujac tresc zadania w google znalazłem że od 1 do 109.

Czyli można by zrobić stala tablice

int tab[109][109]; //  ok 50 kb ramu, chyba ok ?

 

w ktorej bysmy zapisali wszystkie możliwe wartosci, i petla wygladała by tak:

for(int i=0; i <n; i++) {
 cin >> a >> b;
cout << tab[a][b];
}
 

to jest najwydajniejszy sposób.

 

 

 

 

 

 

 

[Freddnik]

Dzieki wielkie za pomoc, a i co do tego 109 to nie 109 tylko 10 do potegi 9

 

@EDIT

 

A i jeszcze co do usunięcia tablic, to nie bardzo jest to poprawne, ponieważ sprawdzarka wymaga aby wyniki były na koncu podawane.

[Sopelek997]

jakby dalej były timeoty, to spróbuj przeczytać to

http://stackoverflow.com/questions/9411823/fast-log2float-x-implementation-c

I zamiast używania cin do pobierania intów użyj scanf. Jest trochę szybszy.

 

@up. to wypisuj je na końcu, cóż za problem

[metin1998]

Dzieki wielkie za pomoc, a i co do tego 109 to nie 109 tylko 10 do potegi 9

 

@EDIT

 

A i jeszcze co do usunięcia tablic, to nie bardzo jest to poprawne, ponieważ sprawdzarka wymaga aby wyniki były na koncu podawane.

jesteś pewny? A nie sprawdza to po prostu na końcu zawartości stdout? Mam trochę doświadczenie w tego typu sprwadzarkach i to powinno być poprawne. Być może w Twojej nie jest, ale sprawdź.

[Freddnik]

Okej dzieki wielkie za pomoc i fatyge już jest wszystko OK