Losers Are Winners

Interview

Time limit1sMemory limit128 MB

Summary
Group contestants into teams of two, compute each team's percentage of combined weight lost, and print the winner with one decimal place.
Level

Easy3 of 10

Topics
Hash map, Implementation, Sorting, Math
Solved
No attempts yet

Problem

A local Health and Nutrition Counseling Center is running a contest to encourage overweight couples to lose weight. The prize goes to the two-person team that loses the greatest percentage of their combined starting weight over the course of the contest.

A team's percentage of weight lost is

percent lost=combined initial weight−combined final weightcombined initial weight×100.\text{percent lost} = \frac{\text{combined initial weight} - \text{combined final weight}}{\text{combined initial weight}} \times 100.

For example, consider the following two teams:

TeamMembers (initial → final)Combined initialCombined final% lost
GreenAmanda 220.6 → 162.5, Ernesto 320.9 → 231.0541.5393.527.3%
OrangePaula 212.0 → 155.1, Eduardo 240.9 → 170.1452.9325.228.2%

Team Orange loses the higher percentage, so Orange wins.

Write a program that processes the weight-loss data and declares the winning team for each contest.

Input

The input consists of several datasets, each describing one contest.

The first line of a dataset is a positive integer NN, the number of teams in that contest (1≤N≤1001 \le N \le 100). A line containing 00 marks the end of the input and is not processed.

The next 2N2N lines each describe one contestant. A line contains four whitespace-separated fields: the contestant's name, the name of the contestant's team, and two floating-point numbers between 50.050.0 and 500.0500.0 giving the contestant's initial weight and final weight, in that order. Each team consists of exactly two members. Names contain only alphabetic characters with no embedded blanks and are at most 100100 characters long. Team names are unique within a dataset; contestant names are not guaranteed to be unique.

Output

For each dataset, print one line: the name of the winning team, a single space, and the percentage of weight the team lost rounded to one decimal place, followed immediately by a percent sign (%).

If two or more teams tie for the greatest percentage lost, print the team whose name comes first in alphabetical order.

Examples3

  1. Example 1

    Input
    2
    Amanda Green 220.6 162.5
    Paula Orange 212.0 155.1
    Eduardo Orange 240.9 170.1
    Ernesto Green 320.9 231.0
    6
    Carlos White 243.9 176.8
    Kandy Red 275.7 208.2
    Amanda Green 220.6 162.5
    Paula Orange 212.0 155.1
    Fred Brown 300.9 210.7
    Nadia Pink 217.8 155.9
    Ray Red 254.8 166.2
    Curtis White 321.1 216.2
    Adrian Brown 284.6 201.2
    Kara Pink 233.1 176.6
    Eduardo Orange 240.9 170.1
    Ernesto Green 320.9 231.0
    0
    
    Expected output
    Orange 28.2%
    White 30.4%
    
  2. Example 2

    Input
    1
    Alice Team 200.0 150.0
    Bob Team 200.0 170.0
    0
    
    Expected output
    Team 20.0%
    
  3. Example 3

    Input
    2
    Ann Alpha 100.0 60.0
    Bob Alpha 100.0 40.0
    Cid Beta 150.0 75.0
    Dan Beta 150.0 75.0
    0
    
    Expected output
    Alpha 50.0%