Fișierul intrare/ieșire combat.in, combat.out Sursă CodinGame
Autor autor necunoscut Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.05 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Combat

Sunteți în spațiu. Aveți o navă pe care o controlați. Nava voastră are un număr H de puncte de viață și o armă laser cu care poate lovi un inamic, cauzându-i o daună egală cu D puncte de viață.

Nava voastră este atacată de N nave inamice. Fiecare navă i are un număr h[i] de puncte de viață și o armă laser care provoacă o daună egală cu d[i] puncte de viață.

Bătălia se desfășoară pe tururi, astfel:

  • La fiecare tur, fiecare navă inamică trage pe rând împotriva navei voastre.
  • Dacă nava noastră a rezistat atacurilor din acest tur (dacă a rămas cu un număr de puncte de viață mai mare strict decât 0), aceasta va alege o navă inamică și va trage împotriva ei.
  • Dacă nava aleasă este distrusă în urma atacului (dacă a rămas cu un număr de puncte de viață egal cu 0), nu va mai lua parte în următoarele tururi.

Bătălia încetează în două cazuri:

  • Fie nava voastră este distrusă.
  • Fie toate navele adverse sunt distruse.

Cerință

Misiunea voastră este ca în fiecare tur să alegeți eficient nava inamică pe care să o atacați, astfel încât la finalul bătăliei nava voastră să supraviețuiască. În cazul în care acest lucru este posibil, trebuie să afișați numărul maxim de puncte de viață cu care nava voastră poate încheia bătălia. În cazul în care acest lucru este imposibil și nava este distrusă în urma bătăliei, veți afișa -1.

Date de intrare

Fișierul de intrare combat.in conține pe prima linie 3 numere naturale despărțite între ele prin câte un spațiu, N H D, având semnificația din enunț. Pe fiecare linie i din următoarele N linii, se vor găsi 2 numere naturale: h[i] și d[i], având semnificația din enunț.

Date de ieșire

În fișierul de ieșire combat.out se va găsi un singur număr natural, reprezentând numărul maxim de puncte de viață cu care nava voastră poate încheia bătălia. În cazul în care acest lucru nu este posibil, se va găsi valoarea -1.

Restricții

  • 1 ≤ N ≤ 5.000
  • 1 ≤ H ≤ 1.000.000.000
  • 1 ≤ D ≤ 100
  • 1 ≤ h[i], d[i] ≤ 100, pentru orice 1 ≤ i ≤ N

Exemplu

combat.in combat.out
2 20 10
5 10
8 4
2

Explicație

Sunt 2 nave inamice, ambele pot fi distruse cu un singur atac al navei voastre:

  • În primul tur vom primi 14 puncte de daună și vom rămâne astfel cu 20 – 10 – 4 = 6 puncte de viață. Vom distruge prima navă, pentru că este mai puternică (provoacă o daună mai mare).
  • În cel de-al doilea tur vom primi 4 puncte de daună de la cea de-a doua navă inamică și vom rămâne cu 6 – 4 = 2 puncte de viață. Vom distruge nava și astfel încheiem bătălia.

Dacă am fi ales să distrugem mai întâi cea de-a doua navă, am fi primit în primul tur 14 puncte de daună, iar în cel de-al doilea tur încă 10, pierzând astfel bătălia.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii