InequalityChecker

SRM 230 · 2005-02-08 · by AdminBrett

SRM 230 · 2005-02-08 · by AdminBrett · Brute Force

Show categories

Class Name: InequalityChecker

Return Type: int[]

Method Name: getDifferences

Arg Types: (int)

Problem Statement

Using mathematical induction it is possible to prove the following inequality when n>1:

	s = 1³ + 2³ + ... + (n-1)³ < n⁴/4 < 1³ + 2³ + ... + n³ = S

Given n return (S+s)/2 - n⁴/4 as a int[] with 2 elements. Elements 0 and 1 denote the numerator and denominator of the return value, respectively, when written in least terms (reduced).

Constraints

n will be between 2 and 100 inclusive.

Examples

2
Returns: { 1,  1 }

We have s = 1^3 = 1 S = 1^3 + 2^3 = 9 (S+s)/2 = (1+9)/2 = 5 n^4/4 = 16/4 = 4 Since 5-4 = 1, we return the fraction 1/1.

3
Returns: { 9,  4 }

We have s = 1^3 + 2^3 = 9 S = 1^3 + 2^3 + 3^3 = 36 (S+s)/2 = 45/2 n^4/4 = 81/4 We return the fraction 9/4.

100
Returns: { 2500,  1 }

Largest case.

4
Returns: { 4,  1 }

5
Returns: { 25,  4 }

Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class InequalityChecker with a public method vector<int> getDifferences(int n) · 23 test cases · 2 s / 256 MB per case