IOI'94 - Day 1 - Problem 1: The Triangle

Competition Rules

Problem Statement

Example input and output files from the problem statement: There are 6 tests. Each successfully completed test gives 5 points. Therefore the maximum number of points for this problem is 30. The maximum execution time is 30 seconds per test.

Test Data

N.B.The following test data were not available during the competition. They were used to judge the programs of the competitors after the competition.
  1. Input / Output (6 rows; maximum route sum = 469)
  2. Input / Output (10 rows; maximum route sum = 727)
  3. Input / Output (15 rows; maximum route sum = 976)
  4. Input / Output (30 rows; maximum route sum = 2135)
  5. Input / Output (60 rows; maximum route sum = 4466)
  6. Input / Output (100 rows; maximum route sum = 7178)

Analysis and Solution