David Compra Paninis

Enviar solució
Punts: 20
Temps Límit: 1.0s
Límit de memòria: 64M
Autor/a:
marc
tipus del problema
Cerca Binària, Programació Dinàmica
Categoria
Competitiu
Llenguatges permesos
Bash, C#, C++, Haskell, Java, Kotlin, PHP, Python

aireacondicionat

David va a una fleca a comprar paninis, i diferents productes de pa, perquè a David li agrada el pa

A la fleca hi ha N diferents productes de pa, i cascun d'ells té un Preu P .

David va amb Chen a la fleca, compren M i Chen decideix dividir el cost per a cada producte de la següent forma.

Si el cost es menor a K, David ho pagarà tot. Si el cost es superior a K, David pagarà K, i Chen pagarà la resta, és a dir, P−K

Assumim que D és el que pagarà David i C el que pagarà Chen. David no sap si Chen l'està estafant, així que intentarà buscar els productes per als quals la diferència D−C sigui el més petita possible. Ja que Chen no sap quants productes comprarà, David vol saber quina és la forma a on la diferència sigui millor per a ell per a Q diferents valors de K i M

Entrada

La primera línea conté dos enters, N i Q La segona línea conté N enters, els preus de cadascun dels productes de la fleca Després venen Q linies, cadascuna amb dos nombres, K i M,

Sortida

S'imprimiran Q línies, cadascuna amb la expressió D−C més petita (és a dir, el cas més favorable per a David)

Exemple d'Entrada

Copy
5 2
1 9 22 10 19
18 4
5 2

Exemple de Sortida

Copy
34
-21

Explicació de l'exemple

En la primera línea, David pot agafar els productes amb cost 1,9,22 i 10. Pagarà 38 (1+9+18+10), i Chen 4 (22-18), per tant, 38-4 = 34 Fixa't que si agafés 19 en comptes de 10, pagaria (1+9+18+18) 46 i Chen 5 ((22-18)+(19-18)), per tant 41, que és més alt que 34.

En la segona línea, David agafa 22 i 19 i paga (5+5) 10, i Chen paga ((22-5)+(19-5)) 31, per tant, 10-31 = -21

Comentaris


  • -5
    EricMM8  comentat a les nov. 21, 2023, 5:04 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 5
      arnau  comentat a les nov. 21, 2023, 5:22 p.m.

      A ti lo que te da envidia es ver a un cliente satisfecho delante de una panadería que no es la tuya ;)


  • 7
    hector  comentat a les nov. 14, 2023, 5:07 p.m. ← editat

    David racista (Chen chino)


  • 5
    arnau  comentat a les nov. 14, 2023, 5:05 p.m.

    Chen, paga lo que le debes a David. Primer aviso.


    • 2
      DavidFeliciano  commented 7 months ago

      Chen paga lo que me debes, segundo aviso


      • 1
        arnau  commented 6 months ago

        Chen, paga lo que le debes a David. Tercer aviso.


  • 5
    arnau  comentat a les nov. 14, 2023, 4:57 p.m.

    No es dejéis engañar: ese tipo destrozó Java y petó el JOEL una vez con su código terrorista (pero también arreglamos un bug, paradójicamente). onO


    • -7
      chchen  comentat a les nov. 14, 2023, 5:05 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.


      • 3
        Themonster  comentat a les nov. 14, 2023, 5:08 p.m.

        中国人闭嘴


        • -2
          arnau  comentat a les nov. 14, 2023, 5:55 p.m.

          "¡Meowth, bien dicho!"


      • 2
        arnau  comentat a les nov. 14, 2023, 5:06 p.m.

        Pues cómete esta


    • 4
      Keita58  comentat a les nov. 14, 2023, 5:05 p.m.

      totalment cert