Tehtäväsi on pakata $n$ tavaraa laatikoihin. Jokaisessa laatikossa voi olla yksi tai kaksi tavaraa, ja lisäksi laatikon tavaroiden yhteispaino saa olla enintään $x$. Mikä on pienin mahdollinen laatikoiden määrä?

Esimerkiksi kun tavaroiden painot ovat $[7,2,3,9]$ ja $x=10$, tarvitset ainakin $3$ laatikkoa. Yksi ratkaisu on pakata yhteen laatikkoon tavarat, joiden painot ovat $7$ ja $2$, ja muut tavarat omiin laatikoihin.

Voit olettaa, että $n$ on välillä $1 \dots 10^5$ ja $x$ on välillä $1 \dots 10^9$. Jokaisen tavaran paino on enintään $x$.

Python

Toteuta tiedostoon boxes.py funktio count, jolle annetaan tavaroiden painot sekä painoraja $x$. Funktion tulee palauttaa tarvittava laatikoiden määrä.

def count(t,x):
    # TODO

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

Java

Toteuta tiedostoon Boxes.java metodi count, jolle annetaa tavaroiden painot sekä painoraja $x$. Funktion tulee palauttaa tarvittava laatikoiden määrä.

public class Boxes {
    public int count(int[] t, int x) {
        // TODO
    }

    public static void main(String[] args) {
        Boxes b = new Boxes();
        System.out.println(b.count(new int[] {1,2,3,4}, 10)); // 2
        System.out.println(b.count(new int[] {4,4,4,4}, 4)); // 4
        System.out.println(b.count(new int[] {7,2,3,9}, 10)); // 3
        System.out.println(b.count(new int[] {4,2,1,5,3}, 6)); // 3
    }
}