Maximum Perimeter

Computer Science Level 4

A triangle is constructed using three sticks. The text file contains an array of numbers representing the length of various sticks. We pick 3 sticks to form a non-degenerate triangle. What is the maximum perimeter of the triangle that can be formed?


The answer is 2063.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Beakal Tiliksew
Jul 6, 2016

An efficent method to solve this problem is to first sort the array. Then we iterate over the list starting from the end. This will reduce the effort to check every time for valid triangle because if the sum of two smaller sides is greater than 3rd then obviously it is a valid triangle. Since the array is already sorted you can just traverse the array from end and if any triangle exists, that will the answer itself., otherwise we decrement down the list. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
l.sort()
i=len(l)-1
while True:
  if l[i]<l[i-1]+l[i-2]:
       print (l[i]+l[i-1]+l[i-2])
       break
  else:
     if i==2:
         print ("Null")
         break
     i-=1

6 Helpful 0 Interesting 0 Brilliant 0 Confused

Nice problem. Should have put a longer list to fail naive approaches. By the way, how should I suppose to take the input? I use a very ugly 

1
 
L = raw_input()[1:-1].split(', ')

Any better way to do this?

Christopher Boo - 4 years, 10 months ago

Log in to reply

Yeah probably should have...

I don't see any better way to take the input. You might us well take the array itself as it ain't big.

Beakal Tiliksew - 4 years, 10 months ago
Hung Woei Neoh
Jul 12, 2016

A solution in C++ (I'm using Visual Studio 2013):

First of all, we need to find the number of values in the set: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    string a = "[481, 580, 490, 149, 512, 327, 489, 288, 327, 237, 594, 183, 142, 29000, 326, 20000, 593, 571, 305000, 534, 641, 68, 208, 622, 577, 487, 340, 50000, 9000, 110, 80, 188, 493, 478, 235, 459, 11, 3, 359, 80000, 8200, 611, 86, 178, 58, 19, 592, 400, 511, 294, 80, 128, 342, 198, 546, 262, 437, 395, 610, 538, 486, 369, 684, 315, 148, 411, 579, 197, 419, 573, 267, 332, 393, 225, 244, 471, 631, 511, 189, 79, 487, 227, 606, 10, 527, 66, 255, 459, 42, 204, 484, 433, 386, 568, 368, 507, 323, 542, 289, 186, 671, 388, 599, 561, 542, 653, 141, 528, 275, 70, 38, 64, 378, 437, 226, 308, 39, 502, 229, 167, 130, 491, 576, 357, 530, 109, 284, 535, 637, 672, 360, 434, 552, 675, 502, 684, 103, 398, 255, 145, 122, 486, 643, 165, 334, 116, 631, 657, 461, 31, 310, 420, 536, 390, 210, 483, 250, 586, 236, 82, 587, 676, 34, 695, 107, 215, 573, 97, 475, 442, 323, 537, 268, 676, 663, 507, 572, 657, 2, 313, 289, 292, 504, 625, 18, 185, 224, 351, 336, 619, 162, 226, 361, 343, 333, 506, 20, 581, 426]";
    int count = 1;

//Every ',' in the string represents a new number
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == ',')
            count++;
    }

    cout << count;

    return 0;
}

We find that the number of values in the text file is 199 199 . We then write a program to find the largest triangle perimeter: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    int list[199] = { 481, 580, 490, 149, 512, 327, 489, 288, 327, 237, 594, 183, 142, 29000, 326, 20000, 593, 571, 305000, 534, 641, 68, 208, 622, 577, 487, 340, 50000, 9000, 110, 80, 188, 493, 478, 235, 459, 11, 3, 359, 80000, 8200, 611, 86, 178, 58, 19, 592, 400, 511, 294, 80, 128, 342, 198, 546, 262, 437, 395, 610, 538, 486, 369, 684, 315, 148, 411, 579, 197, 419, 573, 267, 332, 393, 225, 244, 471, 631, 511, 189, 79, 487, 227, 606, 10, 527, 66, 255, 459, 42, 204, 484, 433, 386, 568, 368, 507, 323, 542, 289, 186, 671, 388, 599, 561, 542, 653, 141, 528, 275, 70, 38, 64, 378, 437, 226, 308, 39, 502, 229, 167, 130, 491, 576, 357, 530, 109, 284, 535, 637, 672, 360, 434, 552, 675, 502, 684, 103, 398, 255, 145, 122, 486, 643, 165, 334, 116, 631, 657, 461, 31, 310, 420, 536, 390, 210, 483, 250, 586, 236, 82, 587, 676, 34, 695, 107, 215, 573, 97, 475, 442, 323, 537, 268, 676, 663, 507, 572, 657, 2, 313, 289, 292, 504, 625, 18, 185, 224, 351, 336, 619, 162, 226, 361, 343, 333, 506, 20, 581, 426 };
    int per = 0;
    int large = 0;
    int triangle[3] = { 0, 0, 0 };

    for (int a = 0; a <= 196; a++)
    {
        for (int b = a + 1; b <= 197; b++)
        {
            for (int c = b + 1; c <= 198; c++)
            {
//By triangle inequality: For a triangle to exist, no side must be larger or equal to the sum of the other two sides
                if (list[a] >= list[b] + list[c] || list[b] >= list[a] + list[c] || list[c] >= list[a] + list[b])
                    continue;
                per = list[a] + list[b] + list[c];
                if (per > large)
                {
                    large = per;
                    triangle[0] = a;
                    triangle[1] = b;
                    triangle[2] = c;
                }
            }
        }
    }

    cout << large << "\n" << list[triangle[0]] << "\n" << list[triangle[1]] << "\n" << list[triangle[2]] << "\n";
    return 0;
}

We find that the largest possible perimeter is 2063 \boxed{2063} , formed by sticks of length 684 , 684 , 695 684,684,695

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...