No.3397 Max Weighted Floor of Linear
タグ : / 解いたユーザー数 27
作問者 :
amentorimaru
👑
cleantted
Problem Statement
There are $T$ test cases.
For each test case, you are given positive integers $N,M$ and integers $A,B,C,D$.
Find $\max\left\lbrace Ax+B\left\lfloor(Cx+D)/M\right\rfloor\mid x\in\mathbb{Z},\ 0\leq x\lt N\right\rbrace$.
In other words, find the maximum value that the expression $Ax+B\left\lfloor(Cx+D)/M\right\rfloor$ can take as the integer $x$ ranges over values at least $0$ and less than $N$.
$\lfloor\cdot\rfloor$ denotes the floor function (the function that returns, for a real number, the largest integer not exceeding it).
Input
$T$ $N _ 1$ $M _ 1$ $A _ 1$ $B _ 1$ $C _ 1$ $D _ 1$ $N _ 2$ $M _ 2$ $A _ 2$ $B _ 2$ $C _ 2$ $D _ 2$ $\vdots$ $N _ T$ $M _ T$ $A _ T$ $B _ T$ $C _ T$ $D _ T$
- $1\leq T\leq 10^5$
- $1\leq N,M\leq 10^{9}$
- $-10^{9}\leq A,B\leq 10^{9}$
- $0\leq C,D\lt M$
- All input values are integers.
Output
Print $T$ lines.
Print a newline at the end.
Sample
Sample 1
Input
8 1 1 0 0 0 0 5 3 7 2 2 1 3 2 -6 7 1 1 4 2 1 -10 1 0 6 3 -8 9 2 2 10 5 -3 10 2 0 12 10 -1 7 4 1 12 4 -18 19 3 3
Output
0 34 1 1 2 6 18 3
Let $f(x)=Ax+B\left\lfloor(Cx+D)/M\right\rfloor$.
- When $N=1, M=1, A=0, B=0, C=0, D=0$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0\rbrack$, and the maximum value $f(0)=0$ is attained at $x=0$.
- When $N=5, M=3, A=7, B=2, C=2, D=1$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0, 9, 16, 25, 34\rbrack$, and the maximum value $f(4)=34$ is attained at $x=4$.
- When $N=3, M=2, A=-6, B=7, C=1, D=1$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0, 1, -5\rbrack$, and the maximum value $f(1)=1$ is attained at $x=1$.
- When $N=4, M=2, A=1, B=-10, C=1, D=0$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0, 1, -8, -7\rbrack$, and the maximum value $f(1)=1$ is attained at $x=1$.
Sample 2
Input
10 65536 52220 7325 -20393 18757 11822 65536 47257 -20148 27317 34855 9762 65536 58215 -20112 35971 32549 36876 65536 57269 -19804 32041 35397 53181 65536 60607 14512 -37473 23471 16441 65536 57995 26034 -33647 44873 14564 65536 56689 -24409 39848 34725 14205 65536 50405 22027 -35447 31322 8 65536 25573 11413 -18490 15785 7935 65536 53895 19237 -33308 31127 29265
Output
15775 5642 22785 29754 27308 25196 9985 35441 12752 15221
Sample 3
Input
10 1000000000 102334155 433494437 -701408733 63245986 31415926 1000000000 102334155 -433494437 701408733 63245986 31415926 1000000000 484213958 185444158 -300051715 299263911 32091580 1000000000 771251471 185127374 -485073613 294346581 538843377 1000000000 679842423 -216301801 395451124 371856676 421561913 1000000000 687384999 -262204151 424255264 424827257 346851418 1000000000 432108097 -119358786 164913823 312744541 344218736 1000000000 779304889 -280890788 483327461 452901153 335911945 1000000000 452352635 109686923 -286225731 173349784 301388694 1000000000 971385323 370977589 -600253428 600350066 12805751
Output
486080765 215327987 280165601 146171564 245214372 214077322 131370897 208333696 95522302 592340299
-
$f(x) = 433494437 x - 701408733 \lfloor (63245986 x + 31415926) / 102334155 \rfloor$
-
$f(x) = -433494437 x + 701408733 \lfloor (63245986 x + 31415926) / 102334155 \rfloor$
(Japanese statement version)
(English statement version)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。