/* Input: nothing for default test cases, copy some comments on this code and paste into the prompt for some existing tests, or a positive integer on initial line for test cases followed by two lines per case. The first line has two integers: a positive integer for a string length and a power of zero or more. The second line has a string of that length with I, M, X, _, or : characters. Created for this challenge: https://www.codechef.com/NOV20B/problems/FEMA2 Chef loves to play with iron (Fe) and magnets (Ma). He took a row of N cells (numbered 1 through N) and placed some objects in some of these cells. You are given a string S with length N describing them; for each valid i, the i-th character of S is one of the following: 'I' if the i-th cell contains a piece of iron 'M' if the i-th cell contains a magnet '_' if the i-th cell is empty ':' if the i-th cell contains a conducting sheet 'X' if the i-th cell is blocked If there is a magnet in a cell i and iron in a cell j, the attraction power between these cells is P(i,j)=K+1−|j−i|−S(i,j) where S(i,j) is the number of cells containing sheets between cells i and j. This magnet can only attract this iron if P(i,j)>0 and there are no blocked cells between the cells i and j. Chef wants to choose some magnets (possibly none) and to each of these magnets, assign a piece of iron which this magnet should attract. Each piece of iron may only be attracted by at most one magnet and only if the attraction power between them is positive and there are no blocked cells between them. Find the maximum number of magnets Chef can choose. Input The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.The first line of each test case contains two space-separated integers N and K.The second line contains a single string S with length N. Output For each test case, print a single line containing one integer ― the maximum number of magnets that can attract iron. Constraints 1≤T≤2,000 1≤N≤10^5 0≤K≤10^5 S contains only characters 'I', 'M', '_', ':' and 'X'the sum of N over all test cases does not exceed 5*10^6 Subtasks Subtask #1 (30 points): there are no sheets, i.e. S does not contain the character ':' Subtask #2 (70 points): original constraints Example Input 2 4 5 I::M 9 10 MIM_XII:M Example Output 1 2 Explanation Example case 1: The attraction power between the only magnet and the only piece of iron is 5+1−3−2=1. Note that it decreases with distance and the number of sheets. Example case 2: The magnets in cells 1 and 3 can attract the piece of iron in cell 2, since the attraction power is 10 in both cases. They cannot attract iron in cells 6 or 7 because there is a wall between them. The magnet in cell 9 can attract the pieces of iron in cells 7 and 6; the attraction power is 8 and 7 respectively */ // Function to process a test case. Arguments // and variables are: the number of cells, // attraction power of the magnets, the set // of cells, the map of iron locations to // the list of magnets with their power (the // list will be most powerful one or two // with equal power), and the map of magnet // locations and the count of irons they // attract. fun process(n: Int, k: Int, s: String) { val iron = mutableMapOf>>() val magnet = mutableMapOf() // Function to check the power of each // magnet to each iron updating the // most powerful as discovered. fun check() { // For each magnet and iron, calculate // the power from the magnet that reaches // the iron. for (m in magnet.keys) for (i in iron.keys) { // Allocate the magnet power at the // source. For each cell between it // and our target iron, adjust the // power. var power = k+1 for (spot in if (m < i) m..i else m downTo i) // When the cell is empty or iron, // if it is not our target, our // power loses one unit. when (s[spot]) { 'I', '_' -> if (i != spot) power-- // When the cell is an sheet, // our power loses two units. ':' -> power -= 2 // When the cell is another // magnet or block, if the // spot is not our starting // point, our magnet can not // reach the iron. Otherwise, // this is our starting point // so lose one unit. 'M', 'X' -> if (m != spot) power = -1 else power-- } // when // If the power is positive, it // might be worth remembering. If // it is more than the magnet // currently remembered, save it. // If it happens to be a tie, // remember both for later so we // can pick the winner. if (power > 0) if (iron[i]!![0].component2() < power) iron[i] = mutableListOf( Pair(m, power)) else if (power == iron[i]!![0].component2()) iron[i]!!.add(Pair(m, power)) } // for } // check // Function to initialize both maps. For // each magnet and iron cell, create a // map entry. Default the magnet count to // zero and the iron power to negative. fun setup() { for (i in s.indices) when (s[i]) { 'M' -> magnet[i] = 0 'I' -> iron[i] = mutableListOf( Pair(-1, -1)) } // when } // setup // Function to update the counts amd remove // one in case of a tie. fun update() { // For each magnet, count which irons // they were the most powerful at // including ties. for (m in magnet.keys) magnet[m] = iron.count { (k, v) -> v[0].component1() == m || v.size > 1 && v[1].component1() == m } // For each iron, if it has a tie, we // need to pick a winner. If the left // magnet has more irons or the same // as the right, the left wins so // remove one count from the right. // Otherwise, the right has more so // remove one count from the left. for (i in iron.keys) if (iron[i]!!.size > 1) if (magnet[iron[i]!![0]. component1()]!! >= magnet[ iron[i]!![1].component1()]!!) magnet[iron[i]!![1]. component1()] = magnet[iron[i]!![1]. component1()]!!-1 else magnet[iron[i]!![0]. component1()] = magnet[iron[i]!![0]. component1()]!!-1 } // update // Display our test case. Setup our maps. // Check the magnet powers. Update the // counts and handle ties. Display the // result. Optionally, display the maps. println("N="+n+"; K="+k+"; S=\"$s\";") setup() check() val debug = false if (debug) println(iron) update() if (debug) println(magnet) println(magnet.count { (k, v) -> v > 0 }) } // process // Main function for this challenge. fun main(args: Array) { // Try reading the user's test cases. On // errors, cause an exception. try { // Read the number of test cases causing // an exception on non positive integer. // For each cases, read, verify, and // process it. val tests = readLine()!!.toInt() if (tests < 1) throw IllegalArgumentException( "Bad tests!") for (test in 1..tests) { // Read the number of cells and magnet // power causing an exception on // invalid integers. val (n, k) = readLine()!!.split(" "). map { it.toInt() } if (n < 1) throw IllegalArgumentException( "Bad length!") if (k < 0) throw IllegalArgumentException( "Bad power!") // Read the cells causing an exception // on invalid length or character. val s = readLine()!! if (s.length != n || s.filter { it in listOf('M', 'I', 'X', '_', ':') }.length != n) throw IllegalArgumentException( "Bad String!") // Process this test case. process(n, k, s) } // for // On exception, complain and process a few // default test cases. } catch (error: Throwable) { println("Invalid data using defaults!") process(4, 5, "I::M") process(9, 10, "MIM_XII:M") process(4, 5, "MIMI") } // try } // main

fema2 ch