CSES - Suuri ja pieni

Annettuna on lista, jossa on kokonaislukuja. Tehtäväsi on muodostaa mahdollisimman monta paria, jossa suurempi luku on vähintään kaksinkertainen pienempään nähden. Jokainen luku voi kuulua enintään yhteen pariin.

Tarkemmin sanoen pari (a,b)(a,b) on kelvollinen pari, jos pätee ehto 2ab2a \le b.

Esimerkiksi kun lista on [4,5,1,4,7,8][4,5,1,4,7,8], voidaan muodostaa enintään kaksi paria. Yksi mahdollinen ratkaisu on valita parit (1,5)(1,5) ja (4,8)(4,8).

Toteuta tiedostoon bigsmall.py funktio count_pairs, jolle annetaan lista lukuja. Jokainen listan luku on positiivinen kokonaisluku. Funktion tulee palauttaa suurin mahdollinen parien määrä.

Sinun tulee toteuttaa funktio niin, että se laskee vastauksen tehokkaasti myös suurelle listalle. Funktion tulee antaa vastaus välittömästi myös tehtäväpohjan viimeisessä testissä.

def count_pairs(numbers):
    # TODO

if __name__ == "__main__":
    print(count_pairs([1])) # 0
    print(count_pairs([1, 2, 3])) # 1
    print(count_pairs([1, 2, 3, 4])) # 2
    print(count_pairs([1, 1, 1, 1])) # 0
    print(count_pairs([10**9, 1, 1, 1])) # 1
    print(count_pairs([4, 5, 1, 4, 7, 8])) # 2
    print(count_pairs([1, 2, 3, 2, 4, 6])) # 3

    numbers = [(x * 999983) % 10**6 + 1 for x in range(10**5)]
    print(count_pairs(numbers)) # 41176