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
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #154: Exploring Pascal's pyramid.

Project Euler #154: Exploring Pascal's pyramid.

Problem
Submissions
Leaderboard
Discussions

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

A triangular pyramid is constructed using spherical balls so that each ball rests on exactly three balls of the next lower level.

Then, we calculate the number of paths leading from the apex to each position:

A path starts at the apex and progresses downwards to any of the three spheres directly below the current position.

Consequently, the number of paths to reach a certain position is the sum of the numbers immediately above it (depending on the position, there are up to three numbers above it).

The result is Pascal's pyramid and the numbers at each level are the coefficients of the trinomial expansion .

How many coefficients in the expansion of are multiples of ?

Input Format

Each test file contains three lines. First line contains a single number . The second line contains two integers separated by space: and . The third line contains and in the same format.

Constraints

  • , are different primes
  • answer

Output Format

Output a single integer which is the answer to the problem.

Sample Input

3
2 1
3 1

Sample Output

1

Explanation

As we can see on the picture, there is only one number on the rd layer which is a multiple of - itself.

Author

bayleef

Difficulty

Hard

Max Score

100

Submitted By

106

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

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