codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

579B.md (1914B)


      1 Source: https://codeforces.com/problemset/problem/579/B
      2 
      3 B. Finding Team Member
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There is a programing contest named SnakeUp, 2*n* people want to compete for it. In order to attend this contest, people need to form teams of exactly two people. You are given the strength of each possible combination of two people. All the values of the strengths are distinct.
     22 
     23 Every contestant hopes that he can find a teammate so that their team’s strength is as high as possible. That is, a contestant will form a team with highest strength possible by choosing a teammate from ones who are willing to be a teammate with him/her. More formally, two people *A* and *B* may form a team if each of them is the best possible teammate (among the contestants that remain unpaired) for the other one.
     24 
     25 Can you determine who will be each person’s teammate?
     26 
     27 Input
     28 
     29 There are 2*n* lines in the input.
     30 
     31 The first line contains an integer *n* (1 ≤ *n* ≤ 400) — the number of teams to be formed.
     32 
     33 The *i*-th line (*i* > 1) contains *i* - 1 numbers *a**i*1, *a**i*2, ... , *a**i*(*i* - 1). Here *a**ij* (1 ≤ *a**ij* ≤ 106, all *a**ij* are distinct) denotes the strength of a team consisting of person *i* and person *j* (people are numbered starting from 1.)
     34 
     35 Output
     36 
     37 Output a line containing 2*n* numbers. The *i*-th number should represent the number of teammate of *i*-th person.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2  
     45 6  
     46 1 2  
     47 3 4 5
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 2 1 4 3
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 3  
     60 487060  
     61 3831 161856  
     62 845957 794650 976977  
     63 83847 50566 691206 498447  
     64 698377 156232 59015 382455 626960
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 6 5 4 3 2 1
     71 ```
     72 
     73 Note
     74 
     75 In the first sample, contestant 1 and 2 will be teammates and so do contestant 3 and 4, so the teammate of contestant 1, 2, 3, 4 will be 2, 1, 4, 3 respectively.