BearDarts
SRM 671 · 2015-08-31 · by Errichto
Problem Statement
Limak is an old brown bear who likes to play darts.
Limak just picked up an empty scorecard.
He then threw a sequence of darts into a dartboard and for each dart he recorded the point value of the area it hit.
You are given a
Today there is a special jackpot. In order to win the jackpot, the player must present a scorecard with exactly four scores: (a, b, c, d). Additionally, these scores must be such that a*c = b*d. Note that order matters: the scores a, b, c, d must have been obtained in this particular order.
Limak wants to erase all but four scores from his scorecard in such a way that he will win the jackpot. Compute and return the number of different ways in which he can do that.
Constraints
- w will contain between 4 and 1000 elements, inclusive.
- Each element in w will be between 1 and 10^9, inclusive.
{6,8,4,3,6}
Returns: 2
Limak must present a scorecard with four scores, so here he has to erase exactly one of these five scores. There are two ways to do that and win the jackpot: he can erase either the first throw or the last throw. If he erases the first throw, he will be left with (a,b,c,d) = (8,4,3,6), and indeed 8*3 = 4*6. If he erases the last throw, he will be left with (a,b,c,d) = (6,8,4,3), and we have 6*4 = 8*3.
{3,4,12,1}
Returns: 0
Limak cannot erase anything, so the only thing he can try is to present this scorecard without any changes. However, 3*12 does not equal 4*1, so he won't win the jackpot.
{42,1000000,1000000,42,1000000,1000000}
Returns: 3
In this case there are three valid solutions: Erase the elements with 0-based indices 4 and 5. Erase the elements with 0-based indices 1 and 2. Erase the elements with 0-based indices 0 and 3.
{1,1,1,1,1}
Returns: 5
Here, Limak can erase any single score. Note that the five ways are considered different, even though they all produce a scorecard with four 1s.
{1,2,3,4,5,6,5,4,3,2,1}
Returns: 22
Submissions are judged against all 79 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearDarts with a public method long long count(vector<int> w) · 79 test cases · 2 s / 256 MB per case