Jak to skodzić szybciej (algorytm)

pytanie zadane 17 maja 2015 w C i C++ przez krecik1334 Maniak (58,390 p.)

Mam do skodzenia takie zadanko:

http://www.main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/tar/

Muszę przyspieszyć program, a konkretniej to algorytm bo już programu chyba bardziej się nie da. Jest on napisany w czystym C:

#include <stdio.h>
#include <math.h>

int z;
unsigned long long p,q;
int lewa, prawa, x;

int main()
{
    scanf("%d", &z);
    while(z--)
    {
        scanf("%u %u", &p, &q);
        lewa = 0;
        prawa = pow(q-p, 1/3.0);
        while(lewa < prawa)
        {
            x = (lewa+prawa+1)/2;
            if(x*x*x<q-p*x)
            {
                lewa = x+1;
            }
            else
                prawa = x;
        }
        if(lewa*lewa*lewa == q - p*lewa)
            printf("%d\n", lewa);
        else
            printf("NIE\n");

    }
}

Co do algorytmu, wyszukuję binarnie wszystkie możliwe rozwiązania równania (na podstawie porównań w pętli). Mam zbyt mało czasu. Może jest to spowodowane tym, że program się zapętla a może po prostu da się to jakoś przyspieszyć. Macie jakieś pomysły?

6 odpowiedzi

odpowiedź 17 maja 2015 przez sprtnbst Obywatel (1,710 p.)

Wstaw treść zadania, bo po wejściu w link każe się zalogować :)

komentarz 17 maja 2015 przez krecik1334 Maniak (58,390 p.)
edycja 18 maja 2015 przez krecik1334

http://speedy.sh/GvgXM/tar.pdf

odpowiedź 17 maja 2015 przez hit02 Nałogowiec (33,970 p.)

Myślę, że program się zapętla. Sprawdź dla argumentów 4, 6.

Masz jeszcze kilka ostrzeżeń. Warto by je usunąć.

C:\Documents and Settings\hit02\Pulpit>gcc -Wall -Wextra main.c -o main.exe
main.c: In function 'main':
main.c:13:9: warning: format '%u' expects argument of type 'unsigned int *', but argument 2 has type 'long long unsigned int *' [-Wformat]
main.c:13:9: warning: format '%u' expects argument of type 'unsigned int *', but argument 3 has type 'long long unsigned int *' [-Wformat]
main.c:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
main.c:26:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
main.c:32:1: warning: control reaches end of non-void function [-Wreturn-type]

Musisz zmienić typ unsigned long long na unsigned int i warto by zmienić potrójne mnożenie na funkcję pow() - powinna być szybsza, a przy okazji usuniesz ostrzeżenie o porównaniu liczby ze znakiem z liczbą bez znaku. Brakuje również return 0; na końcu.

A co do zadania, to nie mogę go zobaczyć, bo chcą loginu i hasła.

komentarz 17 maja 2015 przez krecik1334 Maniak (58,390 p.)
edycja 18 maja 2015 przez krecik1334

Zadanie dostępne do pobrania tu w formacie pdf(zapisałem):
http://speedy.sh/GvgXM/tar.pdf

odpowiedź 17 maja 2015 przez MrWeb Stary wyjadacz (10,200 p.)

odpowiedź 18 maja 2015 przez Pan Kulomb Pasjonat (18,630 p.)

odpowiedź 18 maja 2015 przez krecik1334 Maniak (58,390 p.)

Typ zmiennych i redukcja wielomianu (mnożenia), oto kod na AC (1h siedziałem i wpadłem xD):

#include <stdio.h>
#include <math.h>

int z;
unsigned long long p,q, k, lewa, prawa, x;

int main()
{
    scanf("%d", &z);
    while(z--)
    {
        scanf("%llu %llu", &p, &q);
        lewa = 0;
        prawa = pow(q-p, 1/3.0);
        while(lewa < prawa)
        {
            x = (lewa+prawa)/2;
            if(x*(x*x+p)<q)
            {
                lewa = x+1;
            }
            else
                prawa = x;
        }
        if(lewa*(lewa*lewa+p) == q)
            printf("%d\n", lewa);
        else
            printf("NIE\n");

    }
}

Zadanko z kursu wstępu do algorytmiki main2.edu.pl, polecam dla wszystkich amatorów algorytmów i kombinowania xD

odpowiedź 18 maja 2015 przez Fulaphex Początkujący (470 p.)
edycja 18 maja 2015 przez Fulaphex

To zadanie wyglada na klasyczne zadanie na zliczanie liczby inwersji algorytmem sortowania przez scalanie. Tutaj mozesz troche na temat tego poczytac:

http://pl.wikipedia.org/wiki/Sortowanie_przez_scalanie

http://en.wikipedia.org/wiki/Merge_sort

http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0013.php

Algorytm opiera sie na takim pomysle, ze dzielimy ciag wejsciowy na dwie polowy, kazda z nich sortujemy rekurencyjnie a potem scalamy obie te polowy przeplatajac oba ciagi. Przy przeplataniu zliczamy inwersje, tu musisz zastanowic sie jak dokladnie :)

EDIT: Jak tak sie wczytalem w Twoj kod, to on totalnie nie dotyczy zliczania inwersji, a cos takiego podlinkowales w komentarzu. Czekam wiec na poprawna tresc.