Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 49 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5  Następna strona
Przedzialy - testy 
Autor Wiadomość
Gwiazda 2

Dołączył(a): 7 paź 2010, o 20:33
Posty: 43
Post Re: Przedzialy - testy
Ehh, nie czaję tego - na logikę działa, wszystkie testy z forum zdał, a w punktacji 2/10 :/


15 paź 2010, o 22:25
Zobacz profil
Gwiazda 1Gwiazda 1Gwiazda 1Gwiazda 1
Avatar użytkownika

Dołączył(a): 8 paź 2010, o 21:56
Posty: 40
Post Re: Przedzialy - testy
Ja nie rozumiem tego:
Kod:
1.out   accepted    0.00s
2.out   accepted    0.00s
3.out   accepted    0.00s
4.out   accepted    0.00s
5.out   accepted    0.02s
6.out   time limit exceeded 2.00s
7.out   time limit exceeded 2.00s
8.out   time limit exceeded 2.00s
9.out   time limit exceeded 2.00s
10.out  time limit exceeded 2.00s


15 paź 2010, o 22:32
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Przedzialy - testy
A jaki Pan miałeś algorytm?


15 paź 2010, o 22:33
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 29 maja 2009, o 22:54
Posty: 112
Post Re: Przedzialy - testy
Grzegorz Chuchro napisał(a):
Ja nie rozumiem tego:
Kod:
1.out   accepted    0.00s
2.out   accepted    0.00s
3.out   accepted    0.00s
4.out   accepted    0.00s
5.out   accepted    0.02s
6.out   time limit exceeded 2.00s
7.out   time limit exceeded 2.00s
8.out   time limit exceeded 2.00s
9.out   time limit exceeded 2.00s
10.out  time limit exceeded 2.00s

Wielki Optymalizator się nadział? :D


15 paź 2010, o 22:35
Zobacz profil
Gwiazda 1Gwiazda 1Gwiazda 1Gwiazda 1
Avatar użytkownika

Dołączył(a): 8 paź 2010, o 21:56
Posty: 40
Post Re: Przedzialy - testy
Bruteforce.
Stosując scanf() przy max teście na moim przedpotopowym kompie działało to 17 sekund. Jak wsadziłem własny sposób na sczytywanie, to skróciłem czas do 7. Biorąc pod uwagę, że uprzednio maks testy w zadaniach działały mi też około 7 sekund, a na sprawdzarce miałem 0.09, to stwierdziłem, że już dalej nic nie trzeba robić...
Kod na scanfach:
Kod:
#include <stdio.h>
#include <stdlib.h>
int main(){
    unsigned char z;
    unsigned int n,n2,amount,i,i2;
    int *result[2];
    result[0]=(int*)malloc(1000000*sizeof(int));
    result[1]=(int*)malloc(1000000*sizeof(int));
    scanf("%d",&z);
    while(z--){
        scanf("%u",&n);
        n2=n-1;
        for(i=0;i<n;i++) scanf("%d%d",&result[0][i],&result[1][i]);
        for(i=0;i<n2;i++){
            for(i2=i+1;i2<n;i2++){
                if(result[0][i]<=result[0][i2]){
                    if(result[1][i]>=result[1][i2]){
                        result[0][i2]=result[0][i];
                        result[1][i2]=result[1][i];
                        result[0][i]=1;
                        result[1][i]=0;
                        break;
                    }else if(result[1][i]>=result[0][i2]){
                        result[0][i2]=result[0][i];
                        result[0][i]=1;
                        result[1][i]=0;
                        break;
                    }
                }else if(result[1][i]>=result[1][i2]){
                    if(result[0][i]<=result[1][i2]){
                        result[1][i2]=result[1][i];
                        result[0][i]=1;
                        result[1][i]=0;
                        break;
                    }
                }else{
                    result[0][i]=1;
                    result[1][i]=0;
                    break;
                }
            }
        }
        for(amount=0,i=0;i<n;i++){
            if(result[0][i]<0 && result[1][i]>0) amount+=result[1][i]+result[0][i]*-1+1;
            else amount+=result[1][i]-result[0][i]+1;
        }
        printf("%u\n",amount);
    }
    free(result[0]);
    free(result[1]);
return 0;
}


15 paź 2010, o 22:51
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 14:15
Posty: 106
Post Re: Przedzialy - testy
Max:
8.out accepted 0.58s 12600


15 paź 2010, o 22:54
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 17:54
Posty: 29
Post Re: Przedzialy - testy
Max:
8.out accepted 0.58s 8700

Moja wzorcowka byla napisana na zasadzie eksperymentu:
cos w stylu: "Może zadziała... O! przeszło!" :D


15 paź 2010, o 23:09
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Przedzialy - testy
Dziwne. Powiedz jakie miałeś rozwiązanie, bo jakoś nie wyobrażam sobie jak w tym przypadku można nie być pewnym poprawności.


15 paź 2010, o 23:10
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 17:54
Posty: 29
Post Re: Przedzialy - testy
Po prostu najpierw pomyslalem, ze moze dzialac, potem zaczelem sie zastanawiac nad jego poprawnoscia...

1. Robimy 2 posortowane, niezalezne tablice: 1. okresla poczatki wsyzstkich przedzialow, konce + zmienną minp = pocz[0]
3. Lecimy petla i ustawiamy i = 1 < n, jesli w pewnym momencie zachodzi wlasnosc: pocz[i] > kon[i-1], to dodajemy do wyniku wartosc kon[i]-minp+1;
4. Ustawiamy minp jako pocz[i] i lecimy dalej...
5. I na koniec jeszcze dodajemy kon[n-1]-minp+1

Czyli po prostu, jesli przedzialy sie nachodza, "laczymy" je w jeden i sumujemy wartosci dla polaczonych. minp okresla nam zawsze poczatek tego polaczonego, z ktorym aktulanie mamy do czynienia


15 paź 2010, o 23:37
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 1 sie 2010, o 23:23
Posty: 34
Post Re: Przedzialy - testy
Ja natomiast miałem dosyć intuicyjny pomysł, posortować sobie wszystkie początki i końce przedziałów w jednej tablicy i lecieć z nimi od lewej do prawej, 0.64s na 8 teście. Da się jakoś O(n) zrobić? ;)


15 paź 2010, o 23:39
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 49 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5  Następna strona


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 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

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