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