THICC '17 P1 - Carol's Carnivorous Plants

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Carol has too many carnivorous plants! She has only one three-foot wide shelf and her plants are growing very quickly (as they are being fed properly) so she need to sell some. Being very poor, Carol decides to scam her friends so that the more plants they buy, the more the plants will cost. She charges them c ^ x dollars per plant, with x being the number of flowers that person has bought, and c being the cost of the specific plant. The first plant will be very cheap and cost one dollar, however following plants will quickly increase in price. This may make it difficult for even your computer to store the costs!

Unfortunately, all her friends are computer nerds, and they catch onto her scam! However, they really want carnivorous plants as Carol is a very good collector, so they try to buy plants anyway. The computer nerd tries to scam Carol back, by bringing m friends (including themselves) to buy plants for the computer nerd. The computer nerd wants n plants and, because he's a computer nerd, wishes to minimize the cost of the plants.

Input Specification

The first line will contain two space separated integers n and m.

The second line will contain n space separated integers, which are the costs of the plants.

Constraints

1 \le n, m \le 100

0 \le c \le 50

Output Specification

The minimum cost to buy all n plants, mod 1\,000\,000\,007.

Sample Input

4 2
1 2 3 4

Sample Output

5

Explanation

One person can buy the $4 plant for 1 dollar (4^0) and the $1 plant for $1 (1^1). The second person will buy the $3 plant for $1 (3^0) and the $2 plant for $2 (2^1). 1 + 1 + 1 + 2 = 5, our total cost.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation.

Comments


  • -9
    IanHu  commented on Oct. 15, 2019, 11:41 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 3
      Tzak  commented on Oct. 16, 2019, 1:41 a.m.

      The maximum possible c is 50, and the maximum possible x is 99 when n = 100 and m = 1. What's the maximum possible c ^ x?