No.303 Indivisible
タグ : / 解いたユーザー数 22
作問者 :
LayCurse
Problem Statement
Newlywed Takahashi wants to build a fence of length $L$ surrounding the kitchen garden of his newly built house.
In the town where Takahashi lives, for every positive integer $k$, a block of length $k$ is sold for $k$ yen.
Takahashi intends to buy any number of these blocks and join them together to make a fence of length $L$.
He may freely cut the blocks he bought (in the direction that divides their length), but each $1$ cut costs $1$ yen.
However, being newly married, Takahashi loathes being divisible by $2$.
Therefore, he has decided not to buy blocks of even length.
Also, in the completed fence of length $L$, the exact middle, the point at distance $L/2$ from the end, must not be a joint between blocks.
Now, find the minimum cost of building a fence satisfying these conditions.
Hmm, I hear voices saying that this is too easy and boring, so also find the number of ways of building the fence that achieve the minimum cost.
$2$ ways of building a fence are considered different if either the numbers of blocks composing them differ, or there exists some $i$ such that the lengths of the $i$-th block from the left differ.
If it is impossible to build the fence in any way, output $\verb|INF|$ as the minimum cost and $\verb|0|$ as the number of ways.
If there are infinitely many ways of building that achieve the minimum cost, output $\verb|INF|$ as the number of ways.
Input
$L$
$1 \leq L \leq 3000000 = 3 \times 10^6$: $L$ is an integer
Output
Output the minimum cost on line $1$ and the number of ways on line $2$.
Sample
Sample 1
Input
5
Output
5 5
With $1$ square having length $1$ and a run of the same color representing the same block, the following $5$ ways can be built at a cost of $5$ yen.
□□□□□ □□□■□ □■□□□ □■□■□ □■■■□
Incidentally, □□■■□ cannot be built at a cost of $5$ yen, because blocks of length $2$ cannot be bought.
All these $5$s feel so satisfying, don't they?
Sample 2
Input
1
Output
1 1
All these $1$s feel so satisfying, don't they?
Sample 3
Input
10
Output
10 30
For $10$ yen, the following $30$ fences can be built.
□□□□□□□□□■ □□□□□□□■□■ □□□□□□□■■■ □□□■□□□□□■ □□□■□□□■□■ □□□■□□□■■■ □□□■■■□□□■ □□□■■■□■□■ □□□■■■□■■■ □□□■■■■■□■ □□□■■■■■■■ □■□□□□□□□■ □■□□□□□■□■ □■□□□□□■■■ □■□■□□□□□■ □■□■□□□■□■ □■□■□□□■■■ □■□■■■□□□■ □■□■■■□■□■ □■□■■■□■■■ □■□■■■■■□■ □■□■■■■■■■ □■■■□□□□□■ □■■■□□□■□■ □■■■□□□■■■ □■■■■■□□□■ □■■■■■□■□■ □■■■■■□■■■ □■■■■■■■□■ □■■■■■■■■■
Incidentally, □□□□□■■■■■ is not allowed, because the point exactly $L/2=5$ away from the end is a joint.
It's not all $10$s, but $30$ is divisible by $10$, so it feels satisfying, doesn't it?
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。