Czołem, niezalogowana osobo!

Paciak.pl to społeczność motocyklistów skupiająca się głównie na świetnej atmosferze. Nasze forum jest dostępne dla zarejestrowanych użytkowników. Nie krępuj się i dołącz do nas.

Episode Three


  • Krzoki BBB MotoWarszawa

    FR_04_10 - Dwa po(d)ciągi

    https://pl.spoj.com/problems/FR_04_10/

    Jasiu jest manewrowym na kolei. Do jego obowiązków należy między innymi sprzęganie i rozprzęganie taboru. Od jakiegoś czasu na stacji manewrowej pojawia się pociąg ze specjalnym składem, nie jest to jednak złoty pociąg…
    Skład ten złożony z wagonów należy rozdzielić na dwa składy tak, aby spełniony był pewien warunek. Jasiu nie dopytuje dlaczego tak, po prostu wykonuje swoją robotę. Warunkiem tym jest jednakowa suma oznaczeń wagonów w obu rozdzielonych składach. Czasem nie jest to możliwe, wówczas Jasiu musi przestawiać lub doczepiać inne wagony, tego chce jednak uniknąć, bo to sporo dodatkowej pracy. Czasem jednak taki podział możliwy jest na więcej niż jeden sposób, wówczas maszynowy już sam decyduje, gdzie nastąpi rozdzielenie składu. Twoim zadaniem jest pomóc Jasiowi i udzielić odpowiedzi, na ile sposobów może rozdzielić skład na dwa składy, aby spełniony był warunek. Inaczej mówiąc, na ile sposobów można ciąg liczb całkowitych podzielić na dwa spójne podciągi tak, aby sumy wyrazów obu podciągów były takie same?

    text alternatywny


  • MotoWungiel

    @tosyu Dobra w końcu zrozumiałem zadanie. 😛
    e2b40703-7d8c-4729-9663-50ac76b1aa53-obraz.png


  • MotoAutyzm admin

    Nie udało mi się zmieścić w czasie, ograniczenie dla pythona było tutaj zabójcze (w py3 tylko 1 rozwiązanie widziałem na liście), próbowałem różnych sztuczek, różnego podejścia i mi się nie udało zoptymalizować kodu - nawet odrzucanie przypadków z nieparzystą sumą jest za wolne (raczej lang-specific, bo samego algo wątpię by się dało zoptymalizować bardziej):

    #!/usr/bin/env python3
    
    def main():
        fsum = sum
        fstr = str
        fint = int
        s = "\n"
    
        i = 1
        j = 1
        input = [*map(fint, open(0, "rb").read().split())]
        output = open(2, "w")
        out = ""
    
        for t in range(input[0]):
            j = i + input[i] + 1
            out = out + fstr(
                    fsum(
                        [
                            fsum(input[i+1:k]) == fsum(input[k:j])
                                for k in range(i+2, j)
                        ]
                    )
                ) + s
            i = j
        open(1, "wb").write(out.encode())
    
    main()
    

    Miałem wersje mniej i bardziej czytelne. Z funkcjami i bez. Nawet wielowątkową miałem. Wcześniejsze zadania pokazują, ze uzywanie własnej funkcji zamiast wbudowanej nie przyniesie żadnego przyspieszenia (wręcz będzie wolniej -tak było z gcd)


  • Krzoki MotoWarszawa

    Moje też nie przeszło, a nie miałem za bardzo czasu siedzieć nad tym.


Zaloguj się, aby odpowiedzieć