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 #151: Paper sheets of standard sizes: an expected-value problem.

Project Euler #151: Paper sheets of standard sizes: an expected-value problem.

Problem
Submissions
Leaderboard
Discussions

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

A printing shop runs batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Now let's assume that foreman suddenly collapsed and the other one came to the rescue. That means that the second foreman could start from some various configurations of envelope. Now, for each possible starting configuration of envelope print the expected number of times that the foreman beginning from this configuration finds a single sheet of paper in the envelope.

Input Format

The only line contains a single integer where A is the smallest needed size of sheet of paper.

Constraints

Output Format

For every possible configuration of envelope print the expected number of times that the foreman beginning from this configuration finds a single sheet of paper in the envelope. As the expected number may be represented as , output it modulo , i.e. . Follow the sample for format needed.

Sample Input

3

Sample Output

0 0 0: 0
0 0 1: 1
0 0 2: 1
0 1 0: 2
0 1 1: 500000005
1 0 0: 500000006

Explanation

If the second foreman starts with empty envelope they will obviously meet no single paper sheets.

When there are one A2 and one A3 sheet after one cut we stay with two A3-s with the probability and with a single A2 with the same probability . In the first case the number of meeting the single sheet is and in the second case it is . That gives us the average

Author

bayleef

Difficulty

Medium

Max Score

100

Submitted By

98

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