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!

Ogłoszenie

Prosimy o pomoc dla małej Julki — przekaż 1% podatku na Fundacji Dzieciom zdazyć z Pomocą.
Więcej informacji na dug.net.pl/pomagamy/.

Strony: 1

 

#1  2007-07-31 10:35:27

  djlinux1992 - Użytkownik

djlinux1992
Użytkownik
Skąd: Zamość
Zarejestrowany: 2005-05-22

Zadanie z OI

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:

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;
}
[url=http://www.djlinux.xt.pl]Wojciech Stępniak[/url]

Offline

 

#2  2007-07-31 11:26:58

  mi5tic - Członek DUG

mi5tic
Członek DUG
Skąd: Wrocław
Zarejestrowany: 2006-08-24

Re: Zadanie z OI

[url=http://pl.wikipedia.org/wiki/Algorytm_Euklidesa]link[/url] ?
//jeśli dobrze zrozumiałem

pzdr.

[b][color=cadetblue]Lubię słowo [i]indolencja[/i].
Dzięki niemu moje lenistwo wydaje się czymś niezwykle wyrafinowanym.[/color][/b]
[i][b] - Bern Williams[/b][/i]

Offline

 

#3  2007-07-31 14:32:24

  djlinux1992 - Użytkownik

djlinux1992
Użytkownik
Skąd: Zamość
Zarejestrowany: 2005-05-22

Re: Zadanie z OI

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 ?

[url=http://www.djlinux.xt.pl]Wojciech Stępniak[/url]

Offline

 

#4  2007-07-31 20:20:54

  mi5tic - Członek DUG

mi5tic
Członek DUG
Skąd: Wrocław
Zarejestrowany: 2006-08-24

Re: Zadanie z OI

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ę:

Kod:

if(nwd(x,y)==tab[i].d) tab[i].je++;

można by zamienić na

Kod:

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.

[b][color=cadetblue]Lubię słowo [i]indolencja[/i].
Dzięki niemu moje lenistwo wydaje się czymś niezwykle wyrafinowanym.[/color][/b]
[i][b] - Bern Williams[/b][/i]

Offline

 

#5  2007-08-01 11:58:59

  zimzum - Członek DUG

zimzum
Członek DUG
Zarejestrowany: 2006-09-04

Re: Zadanie z OI

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

 

#6  2007-08-01 15:15:11

  djlinux1992 - Użytkownik

djlinux1992
Użytkownik
Skąd: Zamość
Zarejestrowany: 2005-05-22

Re: Zadanie z OI

Zapomniałem o książeczkach - Dzięki za przypomnienie i sugestie ;-)

[url=http://www.djlinux.xt.pl]Wojciech Stępniak[/url]

Offline

 

 

Strony: 1

Stopka forum

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson
To nie jest tylko forum, to nasza mała ojczyzna ;-)

[ Generated in 0.015 seconds, 12 queries executed ]

Informacje debugowania

Time (s) Query
0.00013 SET CHARSET latin2
0.00006 SET NAMES latin2
0.00118 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='18.216.94.152' WHERE u.id=1
0.00191 REPLACE INTO punbb_online (user_id, ident, logged) VALUES(1, '18.216.94.152', 1715795982)
0.00087 SELECT * FROM punbb_online WHERE logged<1715795682
0.00137 DELETE FROM punbb_online WHERE ident='85.208.96.195'
0.00091 SELECT topic_id FROM punbb_posts WHERE id=66111
0.00164 SELECT id FROM punbb_posts WHERE topic_id=8667 ORDER BY posted
0.00118 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.00008 SELECT search_for, replace_with FROM punbb_censoring
0.00156 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.00145 UPDATE punbb_topics SET num_views=num_views+1 WHERE id=8667
Total query time: 0.01234 s