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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #186: Connectedness of a network.

Project Euler #186: Connectedness of a network.

Contest ends in
Problem
Submissions
Leaderboard
Discussions

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

Here are the records from a busy telephone system with one million users:

image

The telephone number of the caller and the called number in record are and where come from the "Lagged Fibonacci Generator":

For ,
For ,

If = then the user is assumed to have misdialled and the call fails; otherwise the call is successful.

From the start of the records, we say that any pair of users and are friends if calls or vice-versa. Similarly, is a friend of a friend of if is a friend of and is a friend of ; and so on for longer chains.

The Prime Minister's phone number is . After how many successful calls, not counting misdials, will % of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?

Input Format

Every input file contains exactly one line with two integers separated by a single space: and .

Constraints

is a -digit integer from to .

.

Output Format

Output the only number - an answer to the problem.

Sample Input

000000 1

Sample Output

622572

Author

bayleef

Difficulty

Easy

Max Score

100

Submitted By

998

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