[URI ONLINE JUDGE] – 1766 – The Dark Elf

The stable where the reindeers were was intentionally opened by the Dark Elf allowing each of them to run and fly freely around the Santa Claus’ factory, causing the greatest disorder. The elves are desperately trying to do everything possible to let the sled ready for departure. You are responsible for putting each reindeer in its correct position so that it is captured by one of the other elves.

You know the stable follows an organization based on the order that the reindeers will occupy the sled. Thus, at the time of departure all of them can be easily positioned. Unlike what you may think, the reindeers are placed in a single queue ahead in the sled. Not all reindeers in the stable are used on each trip, that depends on the total load of the sled.

You got the list with all the characteristics that are used to determine the reindeer order. They must first be sorted by the descending order of weight. If two or more have the same weight they should be sorted in ascending order by age and height, if the tie still remains, order by name.

Using your last generation magical computer you want to write a program to order the reindeers according to informed characteristics and display only the exact number of reindeers that will be used by the sled (in an orderly manner).

Input

This problem has several test cases. The first line of the input contains an integer T (1 ≤ T ≤ 105) that indicates the number of test cases that follows. The first line of each test case contains two integers Nand M (5 ≤ N, M ≤ 103) respectively indicating the total number of reindeers and the number of reindeers that will pull the sleigh. In the next lines it will be informed an string S followed by two integers W (1 ≤ W≤ 300) and A (1 ≤ A ≤ 300) and a floating point number H (0.00 ≤ H ≤ 3.00), indicating the name, weight, age and height of each raindeer.

Output

For each test case you should print the message “CENARIO {i}” where i indicates the current test case followed by the position and the name of each of the M reindeer that will pull the sleigh, ordered as described above.

Input Sample Output Sample
1
9 5
Rudolph 50 100 1.12
Dasher 10 121 1.98
Dancer 10 131 1.14
Prancer 7 142 1.36
Vixen 50 110 1.42
Comet 50 121 1.21
Cupid 50 107 1.45
Donner 30 106 1.23
Blitzen 50 180 1.84
CENARIO {1}
1 – Rudolph
2 – Cupid
3 – Vixen
4 – Comet
5 – Blitzen

my solution:


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cctype>
#include <string.h>

#define SC1(a) scanf("%d", &a)
#define SC2(a, b) scanf("%d %d", &a, &b)
#define ZERO(x) memset(x, 0, sizeof(x))
#define FOR(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef struct
{
char no[101];
int pe, id;
float al;
}rena;

rena arr[10010];

bool compare_strings (char * c1, char * c2)
{
int sz = (strlen(c1) > strlen(c2) ? strlen(c1) : strlen(c2));

for (int i = 0; i < sz; ++i)
{
if(c1[i] < c2[i]) return true;
if(c1[i] > c2[i]) return false;
}

return true;
}

bool cmp(rena a, rena b)
{
if(a.pe == b.pe){
if(a.id == b.id){
if(a.al == b.al){
if(compare_strings(a.no, b.no)) return a.no > b.no;
else return a.no < b.no;
}else{
return a.al > b.al;
}
}else{
return a.id > b.id;
}
}else{
return a.pe < b.pe;
}
}

int main(int argc, char const *argv[])
{
int t, n, m, c = 1;

SC1(t);

while(t--)
{
SC2(n, m);
ZERO(arr);

FOR(i, n)
cin >> arr[i].no >> arr[i].pe >> arr[i].id >> arr[i].al;

stable_sort(arr, arr + n, cmp);
reverse(arr, arr + n);

printf("CENARIO {%d}\n", c);
c++;

FOR(i, m)
{
printf("%d - ", (i + 1));
cout << arr[i].no << endl;
}
}

return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s