Bubble Cup V9 I R3D3's summer adventure

View as PDF

Submit solution

Points: 25
Time limit: 0.6s
Memory limit: 256M

Problem types
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

R3D3 spent some time on an internship in MDCS. After earning enough money, he decided to go on a holiday somewhere far, far away. He enjoyed suntanning, drinking alcohol-free cocktails and going to concerts of popular local bands. While listening to "The White Buttons" and their hit song "Dacan the Baker", he met another robot for whom he was sure was the love of his life. Well, his summer, at least.

Anyway, R3D3 was too shy to approach his potential soulmate, so he decided to write her a love letter. However, he stumbled upon a problem. Due to a terrorist threat, the Intergalactic Space Police was monitoring all letters sent in the area. Thus, R3D3 decided to invent his own alphabet, for which he was sure his love would be able to decipher.

There are N letters in R3D3's alphabet, and he wants to represent each letter as a sequence of 0s and 1s, so that no letter's sequence is a prefix of another one's sequence. Since the Intergalactic Space Communications Service has lately introduced a tax for invented alphabets, R3D3 must pay a certain amount of money for each bit in his alphabet's code. He is too lovestruck to think clearly, so he asked you for help.

Given the costs C_0 and C_1 for each 0 and 1 in R3D3's alphabet, respectively, you should come up with a coding for the alphabet (with properties as above) with minimal total cost.

Input Specification

The first line of input contains 3 integers:

  • N - the number of letters in the alphabet
  • C_0 - cost of 0s
  • C_1 - cost of 1s

Output Specification

Output a single number - the minimal cost of the whole alphabet.


  • 2\le N \le 10^8
  • 0\le C_0 \le 10^8
  • 0\le C_1 \le 10^8

Example Input

4 1 2

Example Output



The alphabet is 00, 01, 10, 11. So minimal total cost is 12.


There are no comments at the moment.