CrystalsProblem code: FX |
All submissions for this problem are available.
The Evil Magician of Byteland was performing evil magical experiments, and he has left you with an impressive collection of evil magical crystals which he produced. Honestly, you would be overjoyed to dispose of (or in other words: destroy) these crystals, but destroying a magical crystal is not so easy. To achieve thus, you need to connect three different crystals (red, green and blue) and cast some magic spell to destroy this particular triplet. Each magical crystal has its own mana level. You need a certain amount of your own mana to destroy the triplet, precisely equal to the product of the mana levels of the crystals in the triplet you are destroying. Fortunately, your crystals are all already grouped in triplets, and there are no leftovers (so it is possible to actually destroy all of them); unfortunately, the composition of the triplets is not necessarily optimal from the point of view of mana consumption. However, you are allowed to choose two crystals of the same color, and swap them within triplets (crystals become very unstable and hazardous when not part of a triplet, so you cannot perform any operations more complicated than swapping). But there is a catch (there always is, isn't there?): swapping crystals requires a magic spell -- a spell with a significant mana cost, and what makes matters worse, using this spell (as any other spell) on the crystals being swapped makes them accumulate more mana into their mana level (exactly by 1). Try to minimize the amount of mana you need to use to destroy all the crystals!
Input
First, 2 ≤ n ≤ 105, the number of crystals of each color. Then, 0 ≤ c ≤ 104, the mana cost of the swapping spell. After that, n triplets of integers follow, the ith triplet consisting of 0 ≤ ri ≤ 100, 0 ≤ gi ≤ 100, 0 ≤ bi ≤ 100, representing the initial mana levels of successive Red, Green and Blue crystals, respectively.
Output
First 0 ≤ t ≤ 106, the number of swaps. Then, t descriptions of the swaps in the order in which they are applied, each of the form: 1≤p≤3, 1≤x≤n, 1≤y≤n, meaning a swap between crystals of the xth and yth triplets (p=1 stands for Red, 2 for Green, 3 for Blue).
Example
Input: 3 10 1 1 1 5 5 5 10 10 10 Output: 2 1 1 3 3 1 2 Score: 11*1*6 + 5*5*2 + 2*10*10 + 10 + 10 = 336
| Author: | admin |
| Date Added: | 10-07-2009 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can you please confirm the explanation of this problem. I quote: "To achieve thus, you need to connect three different crystals (red, green and blue) and cast some magic spell to destroy this particular triplet."
Yet your sample problem seems to destroy the following set 2*10*10 which would make it a color combination of R B B.
Clarification anyone? Thanks.
please, read input definition carefully, then ask questions
@Christopher Please re-read the problem statement.
<- Fail. I got it now. Thanks.
in the result of this problem, we get two numbers, one number which says like 7xxxxxxxxxxxxx.x , and 0.xyz pts. What does the first number mean?
It specifies the score of your solution according to the scoring mechanism specified in the problem statement.
will this not be the optimum solution for d problem
2
1 1 3
3 1 3
The score will be
11*11*1 5*5*5 2*2*10 10 20=306
Nobody said the provided one was optimal.
now that contest is over, can somebody tell me about his solution for this problem.
why is there no submit option?