Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 12 ]  Przejdź na stronę 1, 2  Następna strona
[runda 13] - Wężoślad 
Autor Wiadomość
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post [runda 13] - Wężoślad
in:
Kod:
3 20
5 30
5 50
5 70
5 90
20 123456
25 123456789101112

out:
Kod:
0 2
3 -1
10 0
4 -2
-2 0
200 0
3175880 4096

Ofc. każda linia to oddzielny test.


5 mar 2011, o 15:18
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 22:45
Posty: 72
Post Re: [runda 13] - Wężoślad
Potwierdzam wszystkie.


5 mar 2011, o 15:23
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: [runda 13] - Wężoślad
Ja też potwierdzam.
A oto kilka testów ode mnie:
In:
25 29573193745593
25 12165017292157
25 987654321098765
25 293747
Out:
1047552 185
-3469312 -643
49188851 -8192
35213


5 mar 2011, o 23:33
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 22:45
Posty: 72
Post Re: [runda 13] - Wężoślad
Na przedostatnim mam:
25 987654321098765
16777216 424704367677453


6 mar 2011, o 13:19
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: [runda 13] - Wężoślad
Potwierdzam, a nawet zaprzeczam.
Szczegół, że w ostatnim oucie spacji brakuje.
Mnie martwi przedostatni in.
Wg mnie trzeba by dać n=26 albo 2 razy mniejsze d, bo narysowałem sobie węża 25-letniego w pokoju na ścianie i skończył się zanim doszedłem do 987654321098765-ego segmentu.
PS. I właśnie dlatego Wojtku S. masz inny out, ja mam taki jak Nadara, ale to bez znaczenia.


6 mar 2011, o 13:20
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 22:45
Posty: 72
Post Re: [runda 13] - Wężoślad
Racja, faktycznie n jest za małe. :)


6 mar 2011, o 13:22
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: [runda 13] - Wężoślad
Aj racja, sprawdzałem, czy nie jest za długi, ale zapomniałem o jednej rzeczy i wyszło jak wyszło ;p.


6 mar 2011, o 17:09
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: [runda 13] - Wężoślad
Czy wasze programy też działały w złożoności obliczeniowej O(n) ;p? Ale jednak to dobrze, bo by wychodziły różne liczby za zakres, a jakby było coś modulo, to też by było słabo, bo ja jakiegoś dzielenia używałem i robiłem to na doublach :P.


7 mar 2011, o 22:16
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: [runda 13] - Wężoślad
Tak szczerze to nie do końca rozumiem posta wyżej.
Co do złożoności to log4d (słownie: log o postawie 4 z d). Czyli nie wolniej niż O(n), a nawet często szybciej.
n w ogóle nie wczytywałem, bo po co?
Kod:
l=0;
for (p=2; 4*p<=d; p*=4) l++;
while(l)
{
if(d>=3*p) {
d-=3*p;
// coś jeszcze (x+=... y+=...)
}
else if (d>=p) {
d-=p;
// coś jeszcze
}
p/=4;
l--;
}

Czyli ogółem dzielimy d na (przykładowo) węża 5-letniego + 3-letniego (+ 3-letniego odwróconego) + 2-letniego + ogon.
Jeśli ktoś zechce, to mogę opisać.


7 mar 2011, o 22:39
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: [runda 13] - Wężoślad
Poczyniłem pewien skrót myślowy ;p. Chodziło mi o to, że jednak to dobrze, że limit na n jest tak mały, mimo tego, że rozwiązanie działa w złożoności liniowej ;p. Swoją drogą oczywiście jeżeli wiemy, że d jest mniejsze niż długość węża, to n kompletnie nic nie zmienia, ale jednak ciężko, go nie wczytywać, bo występuje na wejściu wcześniej niż d, a d jednak opłaca się wczytać :D. No chyba, że są jakieś magiczne sztuczki pominięcia jednej liczby na wejściu, ale to byłby znaczny przerost formy nad treścią ; D.


7 mar 2011, o 23:17
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 12 ]  Przejdź na stronę 1, 2  Następna strona


Kto przegląda forum

Użytkownicy przeglądający ten dział: Bing [Bot] i 4 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL