King of Diamonds
Difficulty : Very Hard
Community success rate: 25%
Approved by RaulButuc an anonymous CodinGamer EduLibrary.org
A higher resolution is required to access the IDE
- 3
What will I learn?
Statement
Goal
---- KING OF DIAMONDS -----------------------------------------------------------------------------------------------------You (the King of Diamonds) once ruled a peaceful kingdom. But the kingdom is now under attack from the Queen of Spades!
The battlefield is represented by a two-dimensional grid of width W and of height H.
Each square of the grid is occupied by one of three types of entities:
"
"
"
As the King of Diamonds, you have a secret ability: a spell called "Diamond Blast". This spell immediately destroys all Minions, Allies and Charms in a diamond-shaped area on the grid.
The diamond can have any odd-numbered height (one cannot construct a diamond with even-numbered height) and the diamond must be completely inside the battlefield.
Any combination of sizes is allowed on any one test case; not all diamonds have to be of the same size.
However you are only powerful enough to cast the spell N times before you run out of energy.
In order to defend your kingdom you want to determine the maximum number of Minions you can kill while not harming Allies and also destroying all Charms.
---- EXAMPLE ----------------------------------------------------------------------------------------------------------------------
3
10 5
.....A....
..........
..........
..........
.A........
Here you have N = 3, W = 10 and H = 5, and you must compute the maximum number of Minions you can kill (following the other aforementioned rules as well).
The correct output is 32.
One possible optimal solution is to cast three Diamond Blast spells of height 5 like this:
(The full stops "
╭──────────╮ ╭──────────╮ ╭──────────╮ ╭──────────╮
│·····A····│ │····█A····│ │··█·░A····│ │··░·░A·█··│
│··········│ │···███····│ │·███░░····│ │·░░░░░███·│
│··········│ > │··█████···│ > │█████░░···│ > │░░░░░█████│
│··········│ │···███····│ │·███░░····│ │·░░░░░███·│
│·A········│ │·A··█·····│ │·A█·░·····│ │·A░·░··█··│
╰──────────╯ ╰──────────╯ ╰──────────╯ ╰──────────╯
Minions Killed 13 21 32
These three moves kill a total of 32 out of 48 Minions.
In case the example above did not render properly here is a link to a screenshot of it:
https://pasteboard.co/IKkatu5.png
Input
Line 1: One integer N, the maximum number of times you can cast the Diamond Blast spell.
Line 2: Two space-separated integers W and H, the width and height of the battlefield.
Next H Lines: W characters on each line that represent the battlefield.
Line 2: Two space-separated integers W and H, the width and height of the battlefield.
Next H Lines: W characters on each line that represent the battlefield.
Output
Line 1: One integer, the maximum number of Minions you can kill.
Constraints
1 ≤ N ≤ 5000
1 ≤ W ≤ 70
1 ≤ H ≤ 70
The number of Charms will not exceed N, so it is always possible to destroy all Charms.
WARNING: The majority of the validator data (used to compute your score) are very large!
That serves only to prevent pathetic, weak, slow and unoptimised solutions from passing.
1 ≤ W ≤ 70
1 ≤ H ≤ 70
The number of Charms will not exceed N, so it is always possible to destroy all Charms.
WARNING: The majority of the validator data (used to compute your score) are very large!
That serves only to prevent pathetic, weak, slow and unoptimised solutions from passing.
Example
Input
3 10 5 .....A.... .......... .......... .......... .A........
Output
32
A higher resolution is required to access the IDE
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD Online Participants