Connection Status:
Competition Arena > PythTriplets

PythTriplets

SRM 477 · 2009-11-12 · by keshav_57

SRM 477 · 2009-11-12 · by keshav_57 · Graph Theory, Simple Math
Class Name: PythTriplets
Return Type: int
Method Name: findMax
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The prince has just been introduced to primitive pythagorean triplets.
A primitive pythagorean triplet (a, b, c) is a triplet satisfying the following properties:
  • a, b and c are integers
  • a^2 + b^2 = c^2
  • The greatest common divisor of a and b is 1
The prince is not very fond of mathematics. The king is trying to make mathematics fun for his son (the prince). So, the king decides to make as many toys as possible which are triangular in shape having sides (a, b, c) where (a, b, c) form a primitive pythogorean triplet. The wooden framework of the two shorter legs of the toy give the toy its shape and prevent it from breaking, hence each toy with sides of length (a, b, c) must have one wooden stick of length a and one of length b. The third side of length c is not made of wood, and therefore the king does not need a wooden stick for it.

You are given a String[] stick. Concatenate the elements of stick to get a single-space separated list of the lengths of available sticks. The king is a very loving father and would like to make the toys with his own hands. However, he is not skilled enough to cut the sticks, so he must use them in the sizes they are available. Return the maximum possible number of toys the king can make using these sticks.

Notes

  • An integer may be listed multiple times in the String formed by the concatenation of stick . If an integer n is listed k times, then the king has exactly k sticks of length n available with him.

Constraints

  • stick will contain between 1 and 50 elements, inclusive.
  • Each element of stick will contain between 1 and 50 characters, inclusive.
  • When concatenated, stick will represent a single-space separated list of N integers, where N is between 1 and 200 inclusive.
  • Each listed integer will be between 1 and 999999, inclusive.
  • Listed integers will not have leading zeroes.
Examples
0)
{"3 4 4 3 11 5 12 9 4"}
Returns: 3

(3, 4, 5) and (5, 12, 13) are primitive pythagorean triplets. Hence, there are three disjoint pairs (a, b) - (3, 4), (3, 4) and (5, 12).

1)
{"20 21 3021 220"}
Returns: 2

Possible pairs (a, b) are (20, 21), (21, 220) and (220, 3021). The maximum number of disjoint pairs is 2. Namely, (20, 21) and (220, 3021).

2)
{"28 19", "5 1035 21412 37995"}
Returns: 2

Make sure you concatenate the elements of stick.

3)
{"3 7 ", "4"}
Returns: 1
4)
{"26904 251615 147408 87884 124872 169519 226395",
" 177364 328412 189588 241660 5655 654840 225675",
" 519800 35856 43355 105939 126321 78995 91344",
" 107625 56287 69452 528294 138244 836652 113960",
" 528820 156984 27501 21672 74052 842759 149160",
" 3405 262361 103587 230020 314084 44080 385313",
" 5332 3657 227661 362848 5100 8008 3819",
" 16688 396828 133045 12376 44799 6216 258940",
" 50668 40715 15841 698904 55755 742494 40796",
" 111108 567588 64419 168700 45885 269619 93863",
" 104784 23521 34587 48503 24477 833909 60639",
" 141491 233811 78520 118755 533776 400504 88319",
" 448700 30340 37444 167835 327135 19065 25652",
" 34060 148680 271416 4411 354940 5129 101",
" 20880 58188 670956 360591 5595 505680 188487",
" 2313 508300 20020 32984 683100 331425 340445",
" 45008 320229 101380 684004 385216 408152 59325",
" 64452 69388 34188 9752 377832 76172 147725",
" 497352 22211 34365 38253 409116 35155 27816",
" 628056 735572 234835 201699 12236 405867 48081",
" 222300 428575 272363 396435 17572 73102 30099",
" 614980 6437 80340 6345 24600 36816 132207",
" 25553 122428 11544 43249 41313 42148 27936",
" 27652 142715 6435 231217 104397 27713 66521",
" 58533 25615 387723 103391 59052 118131 31595",
" 44415 69460 29128 370905 166731 11484 261617",
" 9617 216195 107272 197087 39767 208875 102185",
" 74228 131428 324868 5687 334875 153725"}
Returns: 88
103)
{"3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ",
 "3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ",
 "3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ",
 "3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ",
 "4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ",
 "4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ",
 "4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ",
 "4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4"}
Returns: 100

trivial case, but a lot of edges and largest possible answer

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

Coding Area

Language: C++17 · define a public class PythTriplets with a public method int findMax(vector<string> stick) · 186 test cases · 2 s / 256 MB per case

Submitting as anonymous