codeforces-scrape

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

1725B.md (2046B)


      1 Source: https://codeforces.com/problemset/problem/1725/B
      2 
      3 B. Basketball Together
      4 
      5 time limit per test
      6 
      7 1 second
      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 A basketball competition is held where the number of players in a team does not have a maximum or minimum limit (not necessarily $5$ players in one team for each match). There are $N$ candidate players in the competition that will be trained by Pak Chanek, the best basketball coach on earth. The $i$-th candidate player has a power of $P_i$.
     22 
     23 Pak Chanek will form zero or more teams from the $N$ candidate players on the condition that each candidate player may only join in at most one team. Each of Pak Chanek's teams will be sent to compete once with an enemy team that has a power of $D$. In each match, the team sent is said to defeat the enemy team if the sum of powers from the formed players is strictly greater than $D$.
     24 
     25 One of Pak Chanek's skills is that when a team that has been formed plays in a match, he can change the power of each player in the team to be equal to the biggest player power from the team.
     26 
     27 Determine the maximum number of wins that can be achieved by Pak Chanek.
     28 
     29 Input
     30 
     31 The first line contains two integers $N$ and $D$ ($1 \le N \le 10^5$, $1 \le D \le 10^9$) — the number of candidate players and the power of the enemy team.
     32 
     33 The second line contains $N$ integers $P_1, P_2, \ldots, P_N$ ($1 \le P_i \le 10^9$) — the powers of all candidate players.
     34 
     35 Output
     36 
     37 A line containing an integer representing the maximum number of wins that can be achieved by Pak Chanek.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 6 180
     45 90 80 70 60 50 100
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 2
     52 ```
     53 
     54 Note
     55 
     56 The $1$-st team formed is a team containing players $4$ and $6$. The power of each player in the team becomes $100$. So the total power of the team is $100 + 100 = 200 \gt 180$.
     57 
     58 The $2$-nd team formed is a team containing players $1$, $2$, and $5$. The power of each player in the team becomes $90$. So the total power of the team is $90 + 90 + 90 = 270 \gt 180$.