fork(1) download
copy 
  1. import sys
  2. from collections import Counter
  3.  
  4. def solve():
  5.     try:
  6.         n = int(sys.stdin.readline())
  7.         sticks = list(map(int, sys.stdin.readline().split()))
  8.     except (IOError, ValueError):
  9.         return
  10.  
  11.     counts = Counter(sticks)
  12.  
  13.     all_pairs = []
  14.     singles = []
  15.  
  16.     for length in sorted(counts.keys()):
  17.         all_pairs.extend([length] * (counts[length] // 2))
  18.         if counts[length] % 2 == 1:
  19.             singles.append(length)
  20.  
  21.     singles.sort(reverse=True)
  22.  
  23.     max_perimeter = 0
  24.  
  25.     # Case 0: 0 singles
  26.     if len(all_pairs) >= 2:
  27.         current_pairs = list(all_pairs)
  28.         p_even = sum(current_pairs) * 2
  29.         while len(current_pairs) >= 2:
  30.             s_max = current_pairs[-1]
  31.             if 2 * s_max < p_even:
  32.                 max_perimeter = max(max_perimeter, p_even)
  33.                 break
  34.             else:
  35.                 p_even -= 2 * s_max
  36.                 current_pairs.pop()
  37.  
  38.     # Case 1: 1 single
  39.     if len(all_pairs) >= 1 and len(singles) >= 1:
  40.         current_pairs = list(all_pairs)
  41.         p_pairs = sum(current_pairs) * 2
  42.         while len(current_pairs) >= 1:
  43.             s_pair_max = current_pairs[-1]
  44.             found_valid = False
  45.             for s in singles:
  46.                 p_total = p_pairs + s
  47.                 s_max = max(s_pair_max, s)
  48.                 if 2 * s_max < p_total:
  49.                     max_perimeter = max(max_perimeter, p_total)
  50.                     found_valid = True
  51.                     break
  52.             if found_valid:
  53.                 break
  54.             p_pairs -= 2 * s_pair_max
  55.             current_pairs.pop()
  56.  
  57.     # Case 2: 2 singles
  58.     if len(all_pairs) >= 1 and len(singles) >= 2:
  59.         current_pairs = list(all_pairs)
  60.         p_pairs = sum(current_pairs) * 2
  61.         s1, s2 = singles[0], singles[1]
  62.  
  63.         while len(current_pairs) >= 1:
  64.             s_pair_max = current_pairs[-1]
  65.             p_total = p_pairs + s1 + s2
  66.             s_max = max(s_pair_max, s1)
  67.             if 2 * s_max < p_total:
  68.                 max_perimeter = max(max_perimeter, p_total)
  69.                 break
  70.             else:
  71.                 p_pairs -= 2 * s_pair_max
  72.                 current_pairs.pop()
  73.  
  74.     print(max_perimeter)
  75.  
  76.  
  77. def main():
  78.     try:
  79.         num_tests_str = sys.stdin.readline()
  80.         if not num_tests_str: return
  81.         num_tests = int(num_tests_str)
  82.         for _ in range(num_tests):
  83.             solve()
  84.     except (IOError, ValueError):
  85.         return
  86.  
  87. if __name__ == "__main__":
  88.     main()
Success #stdin #stdout 0.08s 14144KB
comments (?)
stdin
copy 
5
3
5 5 7
3
4 5 7
3
5 5 10
7
4 3 5 1 5 3 3
4
2 3 5 7
stdout
copy 
17
0
0
23
0
https://ideone.com/0PNMuN
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!