Nie jesteś zalogowany.
Jeśli nie posiadasz konta, zarejestruj je już teraz! Pozwoli Ci ono w pełni korzystać z naszego serwisu. Spamerom dziękujemy!
Prosimy o pomoc dla małej Julki — przekaż 1% podatku na Fundacji Dzieciom zdazyć z Pomocą.
Więcej informacji na dug.net.pl/pomagamy/.
Robie sobie przed obozem informatycznym różne zadanka.
I http://sio.mimuw.edu.pl/user.phtml/zap.pdf?op=get&id=77871 w tym mam taki problem ze tam jest pewna zaleznosc z NWD ale reczne liczenie na chama w pętlach sie wywali na wiekszych liczbach. Macie jakiś inny pomysł, chętnie poprosiłbym o jakies podpowiedzi matematyczne?
Moj obecny kod:
#include <iostream> using namespace std; int nwd(int a,int b) { if(b==0) return a; nwd(b,a%b); } struct zapytanie { int a; int b; int d; int je; }; int main() { int n; cin >> n; zapytanie *tab = new zapytanie[n]; for(int i=0;i<n;i++) cin >> tab[i].a >> tab[i].b >> tab[i].d; for(int i=0;i<n;i++) { tab[i].je=0; for(int x=1;x<=tab[i].a;x++) for(int y=1;y<=tab[i].b;y++) if(nwd(x,y)==tab[i].d) tab[i].je++; } for(int i=0;i<n;i++) cout << tab[i].je <<endl; return 0; }
Offline
[url=http://pl.wikipedia.org/wiki/Algorytm_Euklidesa]link[/url] ?
//jeśli dobrze zrozumiałem
pzdr.
Offline
Właśnie tak mam to zrobione ale na zestawie tysięcy liczb kilkucyfrowych do miliona bede czekał w nieskonczonosc z moim rozwiazaniem - musi istniec jakis bardziej elegancki sposob i szybszy ?
Offline
Próbowałeś funkcji bez rekurencji?
Z tego co pamiętam to na tego typu konkursach raczej nie używa się strumieni tylko stdio.h (ewentualnie cstdio jak już chcesz w ++);)
Na upartego tą linijkę:
if(nwd(x,y)==tab[i].d) tab[i].je++;
można by zamienić na
tab[i].je += (nwd(x, y) == tab[i].d);
ale to już może przesada =) no i większej różnicy nie będzie..
A gdyby tak zadeklarować tablice/tablicę struktur o określonym(czyt. max dopuszczalnym w zadaniu) rozmiarze zamiast przydzielać pamięć dynamicznie?
//takie luźne przemyślenia
pzdr.
Offline
Ja to bym Ci polecil niebieskie ksiazeczki z OI. Sam zawsze do nich zagladam jak mam jakis problem. Nie wkleje Ci linka, bo w tej chwili strona OI nie dziala, a nie jestem pewien, czy znajdziesz tam najnowsze wydania.
Offline
Zapomniałem o książeczkach - Dzięki za przypomnienie i sugestie ;-)
Offline
Time (s) | Query |
---|---|
0.00011 | SET CHARSET latin2 |
0.00004 | SET NAMES latin2 |
0.00112 | SELECT u.*, g.*, o.logged FROM punbb_users AS u INNER JOIN punbb_groups AS g ON u.group_id=g.g_id LEFT JOIN punbb_online AS o ON o.ident='3.149.214.32' WHERE u.id=1 |
0.00073 | REPLACE INTO punbb_online (user_id, ident, logged) VALUES(1, '3.149.214.32', 1715736906) |
0.00053 | SELECT * FROM punbb_online WHERE logged<1715736606 |
0.00063 | SELECT t.subject, t.closed, t.num_replies, t.sticky, f.id AS forum_id, f.forum_name, f.moderators, fp.post_replies, 0 FROM punbb_topics AS t INNER JOIN punbb_forums AS f ON f.id=t.forum_id LEFT JOIN punbb_forum_perms AS fp ON (fp.forum_id=f.id AND fp.group_id=3) WHERE (fp.read_forum IS NULL OR fp.read_forum=1) AND t.id=8667 AND t.moved_to IS NULL |
0.00005 | SELECT search_for, replace_with FROM punbb_censoring |
0.00194 | SELECT u.email, u.title, u.url, u.location, u.use_avatar, u.signature, u.email_setting, u.num_posts, u.registered, u.admin_note, p.id, p.poster AS username, p.poster_id, p.poster_ip, p.poster_email, p.message, p.hide_smilies, p.posted, p.edited, p.edited_by, g.g_id, g.g_user_title, o.user_id AS is_online FROM punbb_posts AS p INNER JOIN punbb_users AS u ON u.id=p.poster_id INNER JOIN punbb_groups AS g ON g.g_id=u.group_id LEFT JOIN punbb_online AS o ON (o.user_id=u.id AND o.user_id!=1 AND o.idle=0) WHERE p.topic_id=8667 ORDER BY p.id LIMIT 0,25 |
0.00127 | UPDATE punbb_topics SET num_views=num_views+1 WHERE id=8667 |
Total query time: 0.00642 s |