GoldenChain
SRM 147 · 2003-05-22 · by axchma
Problem Statement
Background
I remember a chain problem from my childhood. Suppose you have four sections of a golden chain. Each consists of three links joined together in a line. You would like to connect all four sections into a necklace. The obvious solution is to cut the last link of each section and use it to connect the first section to the second one, then the second to the third, then the third to the fourth, then the fourth to the first one. If you want to minimize the number of cuts, you can do better. You can cut one of the three link sections into its individual links. Using the three loose links you can join the three remaining sections together.
Your task is, given the lengths of the sections, to return the minimum number of cuts to make one big circular necklace out of all of them.
Constraints
- sections has between 1 and 50 elements inclusive
- each element of sections is between 1 and 2,147,483,647 inclusive
- the sum of all elements of sections is between 3 and 2,147,483,647 inclusive
{3,3,3,3}
Returns: 3
{3,3,3}
Returns: 3
{1,1,3}
Returns: 2
{2000000000}
Returns: 1
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 25
Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GoldenChain with a public method int minCuts(vector<int> sections) · 23 test cases · 2 s / 256 MB per case