codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1574C.md (2951B)


      1 Source: https://codeforces.com/problemset/problem/1574/C
      2 
      3 C. Slay the Dragon
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Recently, Petya learned about a new game "Slay the Dragon". As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of $n$ heroes, the strength of the $i$-th hero is equal to $a_i$.
     22 
     23 According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon's defense is equal to $x$, then you have to send a hero with a strength of at least $x$ to kill it. If the dragon's attack power is $y$, then the total strength of the heroes defending the castle should be at least $y$.
     24 
     25 The player can increase the strength of any hero by $1$ for one gold coin. This operation can be done any number of times.
     26 
     27 There are $m$ dragons in the game, the $i$-th of them has defense equal to $x_i$ and attack power equal to $y_i$. Petya was wondering what is the minimum number of coins he needs to spend to defeat the $i$-th dragon.
     28 
     29 Note that the task is solved independently for each dragon (improvements are not saved).
     30 
     31 Input
     32 
     33 The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — number of heroes.
     34 
     35 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), where $a_i$ is the strength of the $i$-th hero.
     36 
     37 The third line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of dragons.
     38 
     39 The next $m$ lines contain two integers each, $x_i$ and $y_i$ ($1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18}$) — defense and attack power of the $i$-th dragon.
     40 
     41 Output
     42 
     43 Print $m$ lines, $i$-th of which contains a single integer — the minimum number of coins that should be spent to defeat the $i$-th dragon.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 3 6 2 3
     52 5
     53 3 12
     54 7 9
     55 4 14
     56 1 10
     57 8 7
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 1
     64 2
     65 4
     66 0
     67 2
     68 ```
     69 
     70 Note
     71 
     72 To defeat the first dragon, you can increase the strength of the third hero by $1$, then the strength of the heroes will be equal to $[3, 6, 3, 3]$. To kill the dragon, you can choose the first hero.
     73 
     74 To defeat the second dragon, you can increase the forces of the second and third heroes by $1$, then the strength of the heroes will be equal to $[3, 7, 3, 3]$. To kill the dragon, you can choose a second hero.
     75 
     76 To defeat the third dragon, you can increase the strength of all the heroes by $1$, then the strength of the heroes will be equal to $[4, 7, 3, 4]$. To kill the dragon, you can choose a fourth hero.
     77 
     78 To defeat the fourth dragon, you don't need to improve the heroes and choose a third hero to kill the dragon.
     79 
     80 To defeat the fifth dragon, you can increase the strength of the second hero by $2$, then the strength of the heroes will be equal to $[3, 8, 2, 3]$. To kill the dragon, you can choose a second hero.