問題一覧 > 通常問題

No.2700 Please Hack Greedy Solution!

レベル : / 実行時間制限 : 1ケース 0.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 59
作問者 : hirayuu_yc / テスター : 👑 hamamu Magentor
お気に入りにしたユーザー ProblemId : 10613 / 自分の提出
問題文最終更新日: 2024-04-11 14:03:32
Please Hack Greedy Solution!
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 424 (順位表) の他の問題:

Problem Statement

This is an output-only problem.

In the 0-1 knapsack problem, can the exact solution beat the greedy solution in almost all cases?

Find one tuple of positive integers $N,W$ and a sequence of pairs of positive integers $((v_1,w_1),(v_2,w_2),\dots,(v_N,w_N))$ that satisfies the following conditions.

  • $1\leq N\leq 2000$
  • $1000\leq W\leq 2000$
  • $1\leq v_i\leq 10^9$
  • $1\leq w_i\leq W$
  • Among $p=1,2,\dots,W$, at most $1$ value of $p$ does not satisfy the following condition.
    • Let $R$ be the maximum of $\sum_{i\in S} v_i$ over subsets $S$ of $\{1,2,\dots,N\}$ satisfying $\sum_{i\in S} w_i\leq p$. Here, if no non-empty $S$ satisfies $\sum_{i\in S} w_i\leq p$, let $R=0$.
    • Replace $((v_1,w_1),(v_2,w_2),\dots,(v_N,w_N))$ with the sequence sorted in descending order of $\frac{v_i}{w_i}$ (ties are broken by descending order of $w_i$), let $q=p,G=0$, and perform the following operation for $i=1,2,\dots,N$ in this order.
      • If $w_i\leq q$, replace $q\gets q-w_i$ and $G\gets G+v_i$.
    • Then, $R$ is strictly greater than the final value of $G$.

Input

No input is given.

Output

Output $N,W,((v_1,w_1),(v_2,w_2),\dots,(v_N,w_N))$ satisfying the conditions in the following format.

$N\ W$
$v_1\ w_1$
$v_2\ w_2$
$\vdots$
$v_N\ w_N$

Sample

Sample 1
Output
2 3
3 1
4 2

This output illustrates the output format; it does not satisfy the conditions for the following reasons, so it is judged as WA.

  • It does not satisfy $1000\leq W\leq 2000$.
  • Among $p=1,2,\dots,W$, there are $2$ values of $p$ that do not satisfy the condition, namely $1,3$.
    • When $p=1$, we have $R=G=3$, so the condition is not satisfied.
      • There are $2$ sets $S$ satisfying $\sum_{i\in S} w_i\leq p$, namely $\{\},\{1\}$, and $\sum_{i\in S} v_i$ reaches its maximum of $3$ when $S$ is $\{1\}$. Thus, $R=3$.
      • Replace $((v_1,w_1),(v_2,w_2))$ with $((3,1),(4,2))$, which is the sequence sorted in descending order of $\frac{v_i}{w_i}$, and let $q=p,G=0$.
        • Since $w_1\leq q$, replace $q$ with $q-w_1=0$ and $G$ with $G+v_1=3$.
        • Since $w_2\leq q$ does not hold, do nothing.
        • Thus, the final value of $G$ is $3$.
    • When $p=2$, we have $R=4,G=3$, so the condition is satisfied.
      • There are $3$ sets $S$ satisfying $\sum_{i\in S} w_i\leq p$, namely $\{\},\{1\},\{2\}$, and $\sum_{i\in S} v_i$ reaches its maximum of $4$ when $S$ is $\{2\}$. Thus, $R=4$.
      • Replace $((v_1,w_1),(v_2,w_2))$ with $((3,1),(4,2))$, which is the sequence sorted in descending order of $\frac{v_i}{w_i}$, and let $q=p,G=0$.
        • Since $w_1\leq q$, replace $q$ with $q-w_1=1$ and $G$ with $G+v_1=3$.
        • Since $w_2\leq q$ does not hold, do nothing.
        • Thus, the final value of $G$ is $3$.
    • When $p=3$, we have $R=G=7$, so the condition is not satisfied.
      • There are $4$ sets $S$ satisfying $\sum_{i\in S} w_i\leq p$, namely $\{\},\{1\},\{2\},\{1,2\}$, and $\sum_{i\in S} v_i$ reaches its maximum of $7$ when $S$ is $\{1,2\}$. Thus, $R=7$.
      • Replace $((v_1,w_1),(v_2,w_2))$ with $((3,1),(4,2))$, which is the sequence sorted in descending order of $\frac{v_i}{w_i}$, and let $q=p,G=0$.
        • Since $w_1\leq q$, replace $q$ with $q-w_1=2$ and $G$ with $G+v_1=3$.
        • Since $w_2\leq q$, replace $q$ with $q-w_2=0$ and $G$ with $G+v_2=7$.
        • Thus, the final value of $G$ is $7$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。