David Compra Paninis


Enviar solució

Punts: 20
Temps Límit: 1.0s
Límit de memòria: 64M

Autor/a:
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, PK

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 DC 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ó DC 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 6 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