codeforces-scrape

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

1046F.md (2112B)


      1 Source: https://codeforces.com/problemset/problem/1046/F
      2 
      3 F. Splitting money
      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 After finding and moving to the new planet that supports human life, discussions started on which currency should be used. After long negotiations, Bitcoin was ultimately chosen as the universal currency.
     22 
     23 These were the great news for Alice, whose grandfather got into Bitcoin mining in 2013, and accumulated a lot of them throughout the years. Unfortunately, when paying something in bitcoin everyone can see how many bitcoins you have in your public address wallet.
     24 
     25 This worried Alice, so she decided to split her bitcoins among multiple different addresses, so that every address has at most $x$ satoshi (1 bitcoin = $10^8$ satoshi). She can create new public address wallets for free and is willing to pay $f$ fee in satoshi per transaction to ensure acceptable speed of transfer. The fee is deducted from the address the transaction was sent from. Tell Alice how much total fee in satoshi she will need to pay to achieve her goal.
     26 
     27 Input
     28 
     29 First line contains number $N$ ($1 \leq N \leq 200\,000$) representing total number of public addresses Alice has.
     30 
     31 Next line contains $N$ integer numbers $a_i$ ($1 \leq a_i \leq 10^9$) separated by a single space, representing how many satoshi Alice has in her public addresses.
     32 
     33 Last line contains two numbers $x$, $f$ ($1 \leq f \lt x \leq 10^9$) representing maximum number of satoshies Alice can have in one address, as well as fee in satoshies she is willing to pay per transaction.
     34 
     35 Output
     36 
     37 Output one integer number representing total fee in satoshi Alice will need to pay to achieve her goal.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 3  
     45 13 7 6  
     46 6 2
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 4
     53 ```
     54 
     55 Note
     56 
     57 Alice can make two transactions in a following way:
     58 
     59 0. 13 7 6 (initial state)
     60 
     61 1. 6 7 6 5 (create new address and transfer from first public address 5 satoshies)
     62 
     63 2. 6 4 6 5 1 (create new address and transfer from second address 1 satoshi)
     64 
     65 Since cost per transaction is 2 satoshies, total fee is 4.