Connection Status:
Competition Arena > Workshop

Workshop

SRM 166 · 2003-10-01 · by dimkadimon

SRM 166 · 2003-10-01 · by dimkadimon · Brute Force, Simple Math
Class Name: Workshop
Return Type: int
Method Name: pictureFrames
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You work in a workshop which makes garden instruments from metal. At the end of each working day there remains a pile of scrap metal that cannot be used to make anything useful. Because you dislike the idea of throwing things away (even scrap metal), you decide to utilize this metal to make some triangular picture frames that can be sold at the local market.

Given a int[] pieces where each element represents the length of a straight metallic piece, return the number of possible different picture frames that can be made from those pieces. Two picture frames are considered to be identical if each of their corresponding sides is equal in length. If no picture frames can be created from pieces then return 0.

Notes

  • A triangle can be formed if, and only if, for every pair of its sides the sum of that pair is longer than the third side.

Constraints

  • pieces will have between 0 and 50 elements inclusive.
  • Each element in pieces will be between 1 and 10000 inclusive.
  • pieces will not have any repeated elements.
Examples
0)
{1,2,3,4,5}
Returns: 3

We can form picture frames with the following sides: {2, 3, 4}, {2, 4, 5} and {3, 4, 5}. So we can form 3 different picture frames.

1)
{8,5,3}
Returns: 0

8 + 5 is longer than 3 and 8 + 3 is longer than 5, but 5 + 3 is not longer than 8. Thus we cannot form a single picture frame from these pieces.

2)
{4,23,76,22,87,3,1,99}
Returns: 7
3)
{10000,9999,9998,9997,9996,1,2,3,4,5}
Returns: 43
4)
{100}
Returns: 0

We cannot form any picture frames with just one piece of metal.

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

Coding Area

Language: C++17 · define a public class Workshop with a public method int pictureFrames(vector<int> pieces) · 40 test cases · 2 s / 256 MB per case

Submitting as anonymous