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
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
The contest is finished. Use this link instead: http://www.codechef.com/problems/FX/
How the hell is printf("0") a
How the hell is printf("0") a correct solution ???? -- Submitted by Pankaj139
Leaving that aside, the solution given in the example is incorrect. The correct solution would look something like this:
2
1 1 3
2 1 3
Total Cost: 11*11*1 + 5*5*5 + 2*2*10 + 10 + 10 = 306.
This is a challenge problem.
This is a challenge problem. The aim is not to find the optimal solution (which is impossible within the time limit); any valid solution is accepted and the aim is to have the best possible score.
(Though the fact it was added to the problemset without any mention of it being a challenge problem is indeed a bit silly. Was from this contest: http://www.codechef.com/AUG09/)