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
    }
}