let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

Codechef July 17 - Calculator

solution.md

Ta dễ thấy rằng, cách để đạt được kết quả cao nhất là bấm phím thứ nhất nhiều lần, sau đó tiếp tục bấm phím thứ hai, chứ không bấm xen kẽ 2 phím này.

Gọi số lần bấm phím thứ nhất là \(x\), số lần bấm phím thứ 2 là \(y\). Ta cần tìm max của \(xy\) với \(x + By \le N\).

Dễ thấy \(xy\) đạt cực đại thì \(x + By = N\). Thay \(x = N - By\) vào \(xy\), ta có:

\[xy = (N - By)\times y = -By^2 + Ny\]

Hàm số trên đạt cực đại khi \(y = \frac{N}{2B}\).

Vì \(y\) trong đề là số nguyên nên ta dùng hàm round để làm tròn về giá trị nguyên gần nhất.

main.py
Open in Github • Download 
for _ in range(int(input())):
    n, b = [int(x) for x in input().split()]
    y = round(n / (2*b))
    print(-b * y * y + n * y)
Comments