PascalCount
SRM 230 · 2005-02-08 · by AdminBrett
SRM 230 · 2005-02-08 · by AdminBrett · Math
Problem Statement
Problem Statement
The top few rows of Pascal's triangle are drawn below:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
The leftmost and rightmost values of a particular row are always 1. An inner value v can be found by adding together the 2 numbers found immediately above v, on its right and left sides. For example, the 6 in the above figure is the sum of the two 3s above it. Return the number of values in row i of Pascal's triangle that are evenly divisible by d. The rows are 0-based, so row 3 contains 1,3,3,1.Notes
- The jth element (0-based) of row i can be computed by the formula: i! --------------- j! * (i-j)! where k! = 1*2*...*k and 0! = 1.
Constraints
- i will be between 0 and 5000000 inclusive.
- d will be between 2 and 6 inclusive.
Examples
0)
3 3 Returns: 2
Row 3 is 1,3,3,1 so there are 2 elements divisible by 3.
1)
3 4 Returns: 0
Row 3 has no elements that are divisible by 4.
2)
4 2 Returns: 3
1,4,6,4,1 has 3 elements divisible by 2.
3)
4 6 Returns: 1
Row 4 has a single element divisible by 6.
4)
5000000 6 Returns: 4999315
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PascalCount with a public method int howMany(int i, int d) · 73 test cases · 2 s / 256 MB per case