(Kotlin) 백준 17830: 이진수의 일상

문제가 있는 링크

문제

주어진 조건에 따라 이진수를 곱할 때 최대 자릿수와 최소 자릿수를 찾아야 합니다. 그러나 이진 곱셈이지만 실제로 곱셈을 하면 최대값이 \(2^{2,000,000}\)가 되므로 실제 곱셈을 할 수 없다. BigInteger로 계산해도 값이 너무 커서 타임아웃된다.

오늘의 이진수를 최대 자릿수로 만들기 위해서는 모든 ? 1 반대로 오늘의 이진수를 가장 작은 자리로 만들려면 모두 ? 0이 되십시오.

이 문제를 해결하려면 이진수의 속성을 사용해야 합니다. 이진수의 각 자릿수는 \(2^n\)이므로 \(2^m\)을 곱하면 전체 자릿수 \(n+m+1\)이 됩니다. 예: \(1111 \times 1000=1111000\). 따라서 두 이진수를 곱하여 구한 자릿수는 기본적으로 선행 0을 제외한 자릿수의 합 – 1입니다.

여기서 고려해야 할 두 가지 경우가 있습니다. \(B\)에 1이 여러 개 있는 경우와 없는 경우입니다. \(B\)에 1이 없는 경우는 \(B=0\), 즉 곱한 결과가 0이므로 자릿수는 반드시 1이 된다. ) 1이 여러 개 있고 \(A\)의 모든 비트가 1이므로 선행 0이 없는 숫자의 합입니다. 이 경우의 예는 \(1111\times 1??1\)입니다. 이 경우 결과는 \(1111000\)에 \(111100\), \(11110\), \(1111\) 중 하나 이상을 더한 값이며, 셋 중 하나를 더해도 자릿수는 1씩 증가합니다. .

자릿수를 구하는 방법을 알았으니 이제 수학만 하면 됩니다. 최대 자릿수를 찾으려면 1과 ?를 사용하십시오. 중간의 자릿수가 크면(=주어진 문자열 \(B\)에서 1과 ?의 첨자 중 작은 값) 1과 ?의 합을 기준으로 분기 처리한다. 실시. 최소 자릿수를 얻으면 ?를 무시하고 1의 수를 기준으로 분기 처리를 수행합니다.

암호

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    repeat(readLine().toInt()) {
        val st = StringTokenizer(readLine())
        val n = st.nextToken().toInt()
        val bin = st.nextToken()
        val indexOfQ = bin.indexOf('?')
        val indexOf1 = bin.indexOf('1')
        var countQ = 0
        var count1 = 0
        for (c in bin) {
            when (c) {
                '1' -> count1++
                '?' -> countQ++
            }
        }
        val max = if (indexOfQ < 0 || indexOf1 < 0) n + (bin.length - maxOf(indexOfQ, indexOf1)) else n + (bin.length - minOf(indexOfQ, indexOf1))
        val min = n + (bin.length - indexOf1)
        bw.write(if (count1 + countQ == 0) "1 " else if (count1 + countQ == 1) "${max - 1} " else "$max ")
        bw.write(if (count1 == 0) "1\n" else if (count1 == 1) "${min - 1}\n" else "$min\n")
    }
    bw.close()
}