Redistribució de la riquesa P57539


Statement
 

pdf   zip

thehtml

Considereu una societat amb n persones, on la persona i-èsima té inicialment ai euros. Es vol redistribuir part de la riquesa per reduir tant com sigui possible la diferència entre rics i pobres, amb dues limitacions:

  • No es poden expropiar (per després repartir) més de k euros en total.
  • Els moviments de diners han de ser enters.

Quina és la mínima diferència que es pot aconseguir entre la persona més rica i la més pobra?

Entrada

L’entrada conté diversos casos, només amb nombres enters. Cada cas té una n entre 1 i ‍105, una k entre 0 i 1018, i els ai, tots entre 0 i 109.

Sortida

Per a cada cas, escriviu la mínima diferència que es pot aconseguir.

Public test cases

  • Input

    5 3  1 2 3 4 5
5 2  1 2 3 4 5
5 1  1 2 3 4 5
3 5  10 10 10
4 6  8 1 1 1
1 6  123
10 2400000000  1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0

    Output

    0
2
2
0
1
0
40000000
    • Information
    Author
    Xavier Povill
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python