CHEFSLP - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Utkarsh Gupta
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef has N slippers, of which L are left slippers and the rest are right slippers. Slippers need to be sold in pairs of one left and one right slipper. If each pair sells for X, how much can Chef earn at maximum?

QUICK EXPLANATION:

The answer is X\cdot min(L, N-L).

EXPLANATION:

There are L left slippers and N slippers in total, which leaves N-L right slippers.

Each pair of slippers sold consists of one left and one right slipper. So, Chef certainly cannot sell more pairs than there are left slippers, or more pairs than there are right slippers. This means that Chef can sell at most \min(L, N-L) pairs of slippers.

Further, this upper bound is attainable, i.e, Chef can definitely sell \min(L, N-L) pairs - for example, if there are less left slippers than right slippers, pair up each left slipper with a right slipper.

So, Chef is able to sell \min(L, N-L) slippers, each for rupees X. Chef’s maximum earning is hence X\cdot\min(L, N-L).

TIME COMPLEXITY:

\mathcal{O}(1) per test.

CODE:

Tester (Kotlin) 
import java.io.BufferedInputStream
import kotlin.math.min

fun main(omkar: Array<String>) {
    val jin = FastScanner()
    repeat(jin.nextInt(1000)) {
        val n = jin.nextInt(0, 1000, false)
        val l = jin.nextInt(0, n, false)
        val x = jin.nextInt(0, 1000)
        println(x * min(l, n - l))
    }
    jin.assureInputDone()
}

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null

    constructor() {
        `in` = BufferedInputStream(System.`in`, BS)
    }

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun assureInputDone() {
        if (char != NC) {
            throw IllegalArgumentException("excessive input")
        }
    }

    fun nextInt(endsLine: Boolean): Int {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                throw IllegalArgumentException("found character other than newline")
            }
        } else {
            if (c != ' ') {
                throw IllegalArgumentException("found character other than space")
            }
        }
        return if (neg) -res else res
    }

    fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
        val res = nextInt(endsLine)
        if (res !in from..to) {
            throw IllegalArgumentException("$res not in range $from..$to")
        }
        return res
    }

    fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
}
Editorialist (Python) 
for _ in range(int(input())):
    n, l, x = map(int, input().split())
    print(x*min(l, n - l))