Zadanie w pythonie.

0

Witam, mam problem z jednym zadaniem w pythonie, mianowicie tym:

Podzielne
Limit pamięci: 256 MB
W tym zadaniu Twój program powinien obliczyć, ile liczb z przedziału od do jest podzielnych przez .

Wejście
Pierwszy i jedyny wiersz wejścia zawiera trzy liczby całkowite , , (, ), oznaczające odpowiednio początek i koniec przedziału oraz liczbę, przez którą dzielimy.

Wyjście
Wyjście powinno zawierać jedną liczbę całkowitą, równą liczbie liczb z przedziału , które dzielą się przez .

Przykład
Dla danych wejściowych:

3 10 2
poprawną odpowiedzią jest:

4
a dla danych wejściowych:

10 20 10
poprawnym wynikiem jest:

2>

Mój kod:

n=int(input())
x=input()
a=x.split()
w1=''
w2=''

for i in range(0,len(a),2):
    w1=w1+a[i]+' '
print(w1)

for i in range(1,len(a),2):
    w2=w2+a[i]+' '
print(w2)

Niestety przekroczony jest limit czasu, można te zadanie jakoś inaczej napisać?

0
n=int(input())
x=input()
a=x.split()

Niestety przekroczony jest limit czasu, można te zadanie jakoś inaczej napisać?

Musisz wczytać dane w inny sposób. Np tak:

numArr = [int(x) for x in input().split()]
counter = 0

for number in range(numArr[0], numArr[1]+1):
    if number % numArr[2] == 0:
        counter += 1
print(counter)
0

szybszy, ale da się jeszcze szybciej

pocz, kon, dziel = map(int, input().split())
akt = pocz
wynik = 0
while akt % dziel != 0:
    akt += 1
while akt <= kon:
    akt += dziel
    wynik += 1
print(wynik)
1

Początkowo, dla ułatwienia zakładając że przedział jest otwarty...
Ponieważ jest to zadanie matematyczne bardziej aniżeli brute-force programistyczny który podsunęli koledzy wyżej :)

I teraz prosta sprawa, ile liczb w przedziale jest podzielnych? Dokładnie tyle, ile się w nim mieści.
Całość, w uproszczeniu da się zamknąć w bardzo prostej linijce:

len(range(*map(int, input().split())))

Wygląda to trochę jak codegolf, bo można to śmiało dla czytelności rozbić na więcej linii.
map(int, input().split()) - poda nam tuple z trzema argumentami.
* - rozpakuje ją jako argumenty dla range.
len - poda nam długość range, czyli ilość liczb podzielnych przez tą liczbę w przedziale.

Komplikacja się pojawia poza przykładami które podałeś, gdy modulo z początku i z końca zakresu jest równe bądź większe od liczby dzielącej. Wtedy należy od wyniku odjąć jeden. I to jest właśnie ten element którego nie zawiera powyższe uproszczenie.

Korzystając z przykładu @sig:

pocz, kon, dziel = map(int, input().split()) #~ 4, 17, 3 (Zawiera 4 liczby podzielne przez 3, powyższe uproszczenie poda 5)
suma = len(range(pocz, kon, dziel))
if (pocz%dziel)+(kon%dziel) >= dziel:
    suma -= 1
print(suma)

Zakładając że u ciebie przedział ma być specjalnie zaznaczony gdy domykający wyraz będzie podzielny, możesz dodać trzecie modulo sprawdzające czy przedział jest domknięty.

if not (kon%dziel): #~ Jeśli modulo będzie równe 0
    wynik = str(suma+1)+">"
print(wynik)

Trzy modulo, jedno porównanie i jedno dodawanie + prawie że brak zużycia pamięci przez wykorzystanie generatora. Wydaje mi się że ciężko ten problem byłoby rozwiązać lepiej, ewentualnie niech mnie ktoś poprawi :)

Pozostaje ci złożyć klocki podane wyżej do kupy :D
No i zastanowić się skoro tak brzmi polecenie, co wtedy gdy podadzą nam tylko początek i koniec przedziału, zakładam że wtedy należy po prostu zliczyć liczby w przedziale +1 dla zamkniętego przedziału, ponieważ każda liczba całkowita jest podzielna przez 1.

@Edit:
Koniec końców, jak to przeczytałem ponownie, w sumie chyba trzeba użyć list comprehension aby to jakoś wyglądało, jak podsunął @migmig13, albo skorzystać z funkcji i argumentu domyślnego... Oba rozwiązania w sumie mogą być eleganckie.

def podzielnosc(p, k, d=1):
    suma = len(range(p, k, d))
    if (p%d)+(k%d) >= d: 
        suma -= 1
    if not k%d and k%p:
        return str(suma+1)+">"
    elif not k%d: 
        return str(suma)+">"
    return str(suma)

wynik = podzielnosc(*map(int, input().split()))
#~ LUB:
wynik = podzielnosc( *[int(_) for _ in input().split()])

Odnośnie komentarza z modulo, modulo zawsze jest w przedziale całkowitym od 0 do dzielnika (wyłączając sam dzielnik) skoro suma dwóch modulo będzie równa dzielnikowi bądź większa, to nie ma możliwości aby koniec przedziału był zerem :)

Jest późno, jakbym się gdzieś machnął w rozumowaniu lub kodzie, to mnie poprawcie.
Ale tutaj jeszcze wrzucę jak testowałem pokrótce:

@Edit2:
Jeszcze zrobiłem kilka błędów w logice, zapomniałem o początku zakresu że może napsuć oraz niepotrzebnie liczyć kilka razy modulo, bo to potrafi zająć 'dużo' czasu, ogólnie już bez tłumaczenia, kod + sprawdzenia :)

def podzielnosc(p, k, d=1):
    p_mod_d = p%d
    if p_mod_d:
        suma = len(range(p+(d-p_mod_d), k, d)) #~ Ustawiamy od pierwszej podzielnej
    else:
        suma = len(range(p, k, d)) #~ Jak pierwsza jest podzielna
    if not k%d: #~ Jeśli koniec jest podzielny dodajmy jeden i zamknijmy zakres.
        return str(suma+1)+">"
    return str(suma)


def sprawdz(wynik, a, b, c=1):
    oczekiwany = podzielnosc(a,b,c)
    print("{:>4},{:>4},{:>4} | {:^4} == {:^4} | {}".format(a, b, c, oczekiwany, wynik, oczekiwany==wynik))
    
sprawdz("4>", 3, 10, 2)
sprawdz("2>", 4, 9, 3)
sprawdz("2", 4, 10, 3)
sprawdz("2", 4, 11, 3)
sprawdz("3>", 4, 12, 3)
sprawdz("3>", 5, 12, 3)
sprawdz("3>", 6, 12, 3)
sprawdz("2>", 10, 20, 10)
sprawdz("11>", 10, 20)
print("~"*40)
sprawdz("802550194>", 120321, 3210321096, 4)
sprawdz("508540289", 13216, 8645198132, 17)

Dla długich łańcuchów jak na przykład ostatnie testowe, powinno być bardzo szybkie w stosunku do rozwiązań w innych postach. A podejrzewam że do takich testów właśnie wyskakuje ci timeout, jak to bywa z codewars itd. :)

1

A co z

def licz(pocz, kon, dziel):
   if pocz % dziel == 0:
       pocz -= dziel
   pocz = pocz - (pocz % dziel)
   kon = kon - (kon % dziel)
   return(int(kon / dziel) - int(pocz / dziel))


#pocz, kon, dziel = map(int, input().split())
print(licz(4, 20, 4))
print(licz(4, 17, 3))
0
sig napisał(a):

A co z

def licz(pocz, kon, dziel):
   if pocz % dziel == 0:
       pocz -= dziel
   pocz = pocz - (pocz % dziel)
   kon = kon - (kon % dziel)
   return(int(kon / dziel) - int(pocz / dziel))


#pocz, kon, dziel = map(int, input().split())
print(licz(4, 20, 4))
print(licz(4, 17, 3))

Niestety przekroczono limit czasu, da się jakoś jeszcze szybciej to napisać?

1

Wyrzuciłem zbędną resztę, i dodałem else. Ale skoro zestaw tylko jeden to za bardzo go to nie przyśpieszy

def licz(pocz, kon, dziel):
    resz = pocz % dziel
    if resz == 0:
        pocz -= dziel
    else:
        pocz = pocz - resz
    kon = kon - (kon % dziel)
    return(int(kon / dziel) - int(pocz / dziel))


#pocz, kon, dziel = map(int, input().split())
print(licz(4, 20, 4))
print(licz(4, 17, 3))
print(licz(10, 20, 10))
0

Skoro to tylko jeden zestaw, to możesz spróbować zrezygnować z funkcji i zrobić obliczenia poza nią. Tylko czy to da jakieś mierzalne przyśpieszenie?

1

Jeszcze trochę szybsze:

def licz2(pocz, kon, dziel):
    resz = pocz % dziel
    if resz:
        pocz -= resz
    else:
        pocz -= dziel
    kon -= kon%dziel
    return (kon // dziel - pocz // dziel)

Wyniki:

   7,  13,   2 |  3   ==  3   | True
   3,  10,   2 |  4   ==  4   | True
   4,   9,   3 |  2   ==  2   | True
   4,  10,   3 |  2   ==  2   | True
   4,  11,   3 |  2   ==  2   | True
   4,  12,   3 |  3   ==  3   | True
   5,  12,   3 |  3   ==  3   | True
   6,  12,   3 |  3   ==  3   | True
  10,  20,  10 |  2   ==  2   | True
  10,  20,   1 |  11  ==  11  | True
120321,3210321096,   4 | 802550194 == 802550194 | True
13216,8645198132,  17 | 508540289 == 508540289 | True
Time to complete funkction podzielnosc (in sec):  0.01186
Time to complete funkction podzielnosc2 (in sec):  0.01237
Time to complete funkction licz (in sec):  0.01283
Time to complete funkction licz2 (in sec):  0.00875

Kod w którym już jest masa syfu, ale z testami itd.

from time import time as tm

def podzielnosc(p, k, d=1):
    p_mod_d = p%d
    if p_mod_d: suma = len(range(p+(d-p_mod_d), k, d))
    else: suma = len(range(p, k, d)) 
    if not k%d: return suma+1
    return suma
    
def podzielnosc2(p, k, d=1):
    p_mod_d = p%d
    if p_mod_d:
        return len(range(p+(d-p_mod_d), k+(d-(k%d)), d))
    else: 
        return len(range(p, k+(d-(k%d)), d)) 

def licz(pocz, kon, dziel):
    resz = pocz % dziel
    if resz == 0:
        pocz -= dziel
    else:
        pocz = pocz - resz
    kon = kon - (kon % dziel)
    return(int(kon / dziel) - int(pocz / dziel))
    
def licz2(pocz, kon, dziel):
    resz = pocz % dziel
    if resz:
        pocz -= resz
    else:
        pocz -= dziel
    kon -= kon%dziel
    return (kon // dziel - pocz // dziel)

def sprawdz(func, wynik, a, b, c=1, show=False):
    oczekiwany = func(a,b,c)
    if show:
        print("{:>4},{:>4},{:>4} | {:^4} == {:^4} | {}".format(a, b, c, oczekiwany, wynik, oczekiwany==wynik))
    
funkcja_do_testu = licz2

sprawdz(funkcja_do_testu, 3, 7, 13, 2, True)
sprawdz(funkcja_do_testu, 4, 3, 10, 2, True)
sprawdz(funkcja_do_testu, 2, 4, 9, 3, True)
sprawdz(funkcja_do_testu, 2, 4, 10, 3, True)
sprawdz(funkcja_do_testu, 2, 4, 11, 3, True)
sprawdz(funkcja_do_testu, 3, 4, 12, 3, True)
sprawdz(funkcja_do_testu, 3, 5, 12, 3, True)
sprawdz(funkcja_do_testu, 3, 6, 12, 3, True)
sprawdz(funkcja_do_testu, 2, 10, 20, 10, True)
sprawdz(funkcja_do_testu, 11, 10, 20, show=True)
sprawdz(funkcja_do_testu, 802550194, 120321, 3210321096, 4, True)
sprawdz(funkcja_do_testu, 508540289, 13216, 8645198132, 17, True)

tries = 10000

czas_start = tm()
for i in range(tries):
    sprawdz(podzielnosc, 508540289, 13216, 8645198132, 17)
    sprawdz(podzielnosc, 2, 10, 20, 10)
first_test = round(tm()-czas_start,5)
czas_start = tm()
for i in range(tries):
    sprawdz(licz, 508540289, 13216, 8645198132, 17)
    sprawdz(licz, 2, 10, 20, 10)
secound_test = round(tm()-czas_start,5)
czas_start = tm()
for i in range(tries):
    sprawdz(licz2, 508540289, 13216, 8645198132, 17)
    sprawdz(licz2, 2, 10, 20, 10)
third_test = round(tm()-czas_start,5)
czas_start = tm()
for i in range(tries):
    sprawdz(podzielnosc2, 508540289, 13216, 8645198132, 17)
    sprawdz(podzielnosc2, 2, 10, 20, 10)
fourth_test = round(tm()-czas_start,5)


print ("Time to complete funkction podzielnosc (in sec): ", first_test)
print ("Time to complete funkction podzielnosc2 (in sec): ", fourth_test)
print ("Time to complete funkction licz (in sec): ", secound_test)
print ("Time to complete funkction licz2 (in sec): ", third_test)

Może ktoś jeszcze ma jakiś pomysł jak to przyspieszyć, mnie nic do głowy już nie wpada :)
Cała otoczka też trochę spłaszcza różnicę pomiędzy wynikami, dodatkowy 'if' i kolejne wywołania które są wspólne, ale to nadal pokazuje że nieco podrasowany przykład @sig'a jest najszybszy póki co. I mnie osobiście nie przychodzi do głowy nic jeszcze szybszego, może powinieneś pójść w kod w C zamiast pythona? W samym C mogę się założyć że możnaby to zrobić jeszcze kilkukrotnie szybciej :P

@Edit:
Używając divmoda, w sumie udało mi się to jeszcze trochę przyspieszyć, ale też niewielki speedup w stosunku do tego co licz2:

def licz3(pocz, kon, dziel):
    p_r_d, p_m_d = divmod(pocz, dziel)
    if p_m_d:
        return (kon // dziel - p_r_d)
    else:
        return (kon // dziel - p_r_d+1)

A tu rezultat:

   7,  13,   2 |  3   ==  3   | True
   3,  10,   2 |  4   ==  4   | True
   4,   9,   3 |  2   ==  2   | True
   4,  10,   3 |  2   ==  2   | True
   4,  11,   3 |  2   ==  2   | True
   4,  12,   3 |  3   ==  3   | True
   5,  12,   3 |  3   ==  3   | True
   6,  12,   3 |  3   ==  3   | True
  10,  20,  10 |  2   ==  2   | True
  10,  20,   1 |  11  ==  11  | True
120321,3210321096,   4 | 802550194 == 802550194 | True
13216,8645198132,  17 | 508540289 == 508540289 | True
Time to complete funkction podzielnosc (in sec):  0.01282
Time to complete funkction podzielnosc2 (in sec):  0.0122
Time to complete funkction licz (in sec):  0.01288
Time to complete funkction licz2 (in sec):  0.00889
Time to complete funkction licz3 (in sec):  0.00776
0
  1. Matematyka na poziomie podstawówki:
    Time to complete funkction licz3 (in sec): 0.01425
    Time to complete funkction mozg (in sec): 0.01249
  2. input to ślimak.
  3. Tworzenie ramki (wywołanie funkcji) jest bardzo kosztowne.

1 użytkowników online, w tym zalogowanych: 0, gości: 1