CANDY2 - Candy II

no tags 

Little Michael loves candies. Most of all, he likes chocolate, strawberry and banana flavored ones. No wonder that he has candy bags everywhere - there are at least four bags on his table, one or two in the pockets of his jeans, and one under his bed (just in case). Each bag contains some candies of all three flavors. Whenever he wants to eat a candy, he finds the nearest bag (which is usually is not very far because he has really A LOT of them) and eats the candy he wants.

Yesterday, he wanted a strawberry one, so he opened one of his bags and... It is almost impossible to describe how great his disappointment was when he found out that there were no strawberry candies left in that bag. To make the matters worse, there were also none in the second bag he found. He was sure that he had lots of strawberry candies left, but he didn't know in which bags they were. Therefore, he decided to reorganize his candies, and keep the candies of the three different flavors in three distinct bags. He brought all his bags into the center of his room and realized, that there are really an awful lot of them.

Michael has N bags full of candies. He knows the number of candies of each flavor in each bag. He wants to put all chocolate ones into one bag, all strawberry ones into another bag and all banana ones into yet another bag. He has to move the candies one-by-one, because he always has to look at it to determine its flavor. Moving one candy from one bag into another takes 1 second. Your task is to select the bag for each flavor, so that the total time required for Michael to move all the candies into their bags would be minimal.

Input file specification

The first line of the input file contains a single integer N - the number of bags (N<=5000). Each of the following N lines consists of three numbers ci, si, bi - the numbers of chocolate, strawberry and banana candies in the i-th bag. The bags are numbered from 0 to N-1 in the order in which they appear in the input.

Output file specification

Output file should contain three lines with the following text:

C[Bag for chocolate candies]
S[Bag for strawberry candies]
B[Bag for banana candies]

The numbers C, S, B have to be such that the total number of the required moves is minimal. If there are more solutions, you may choose any of them.


Input file:
10 10 10
40 39 40
10 20 30
30 20 10
1 2 27

Output file:

Note: In this case Michael has to move 200 candies. If the bags for the different flavors were chosen in any other way, he would have to move more than 200 candies.

Note: the test data is very naive for this problem.

hide comments
flyingduchman_: 2016-06-13 20:39:46

Only unusual thing is ,
the output should be like this :
printf("Bag for chocolate candies: %d\n
Bag for strawberry candies: %d\n
Bag for banana candies: %d",r1,r2,r3);

moaz rashad : 2015-09-09 09:20:12

output format cost me 3 WA , the output should be like this :
printf("Bag for chocolate candies: %d\n
Bag for strawberry candies: %d\n
Bag for banana candies: %d",r1,r2,r3);

Stupid Dog: 2015-02-14 01:01:57

"The bags are numbered from 0 to N-1" !!!!

TUSHAR SINGHAL: 2015-01-06 14:49:46

Last edit: 2015-01-06 14:50:10
NEXES: 2014-11-28 13:41:47

can anybody explain the q

Sujay: 2013-11-13 08:40:25

Plz explain given sample I/O.

: 2013-08-30 01:12:10

can anyone explain given test case!!

Hendra Jaya: 2011-02-13 10:49:02

My "naive" interpretation on "naive test case" costs me 2 failed submission. Don't fall into same trap folks!

:D: 2010-12-30 15:09:39

It means that your program can pass, even if it would TLE or WA in general case (on some tricky data).

Last edit: 2010-12-30 15:10:08
Muhammad Ichsan Abdillah: 2010-12-30 12:18:24

"the test data is very naive for this problem." what's the meaning of this statement?

Added by:Fudan University Problem Setters
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:IPSC 2001