We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #219: Skew-cost coding

Project Euler #219: Skew-cost coding

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 219 from projecteuler.net

Let and be bit strings (sequences of and ).
If is equal to the leftmost bits of , then is said to be a prefix of .
For example, is a prefix of , but not of or .

A prefix-free code of size is a collection of distinct bit strings such that no string is a prefix of any other. For example, this is a prefix-free code of size :

  • , , , , ,

Now suppose that it costs one penny to transmit a bit, but pence to transmit a .
Then the total cost of the prefix-free code shown above is pence, which happens to be the cheapest possible for the skewed pricing scheme in question.
In short, we write .

Given several tuples of numbers find the total cost of the cheapest prefix-free code of size with costs and of transmission bit and bit respectively.

Calculate the result modulo ().

Input Format

First line of each test file contains a single integer that is the number of tuples. Then lines follow, each containing three integers: , and size of prefix-free code, cost of and cost of .

Constraints

Output Format

Print exactly lines with a single integer on each: an answer to the corresponding query modulo .

Sample Input 0

2
6 1 4
9 1 1

Sample Output 0

35
29

Explanation 0

The first prefix-free code is the following:
, , , , ,
Its cost is

The second prefix-free code is the following:
, , , , , , , ,
Its cost is . This code is not unique.

Author

yakutovd

Difficulty

Medium

Max Score

100

Submitted By

185

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy