Subset Sum Gaps

AtCoder

IDarc210_e

Time2000ms

Memory256MB

Difficulty—

You are given a sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$. There are $2^N$ subsequences of $A$ when distinguishing subsequences by the indices of their elements. Let $S_1, S_2, \ldots, S_{2^N}$ be the sums of these subsequences, enumerated **in ascending order**. For all integers $k$ ($1\leq k\leq 2^N-1$) that satisfy $1.01 \times S_k\leq S_{k+1}$, output $S_k, S_{k+1}, (k\bmod 998244353)$. What is a subsequence A subsequence of a sequence $A$ is a sequence obtained by removing zero or more elements from $A$ and arranging the remaining elements in their original order. ## Constraints * $2\leq N\leq 5000$ * $1\leq A_i\leq 10^{13}$ ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

3
5 5 3

Output #1

5
0 3 1
3 5 2
5 8 4
8 10 6
10 13 7

We have the following eight subsequences:

*   The empty subsequence. The sum is $0$.
*   $(5)$. The sum is $5$. This subsequence appears twice.
*   $(3)$. The sum is $3$.
*   $(5,5)$. The sum is $10$.
*   $(5,3)$. The sum is $8$. This subsequence appears twice.
*   $(5,5,3)$. The sum is $13$.

$S_1, S_2, \ldots, S_8$ are $0,3,5,5,8,8,10,13$ in order.

Input #2

2
100 101

Output #2

Input #3

2
101 102

Output #3

2
0 101 1
102 203 3

Input #4

20
456 206 448 830 937 793 483 527 772 239 361 925 364 956 355 420 557 739 323 912

Output #4

23
0 206 1
206 239 2
239 323 3
323 355 4
355 361 5
364 420 7
420 445 8
448 456 10
456 483 11
483 527 12
529 557 14
570 594 19
594 600 20
603 626 22
626 654 23
662 678 26
695 716 32
725 733 36
743 763 39
784 793 48
820 830 60
850 865 65
11397 11603 1048575

API Response (JSON)

{
  "problem": {
    "name": "Subset Sum Gaps",
    "description": {
      "content": "You are given a sequence of positive integers $A=(A_1,A_2,\\ldots,A_N)$. There are $2^N$ subsequences of $A$ when distinguishing subsequences by the indices of their elements. Let $S_1, S_2, \\ldots, S_",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc210_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a sequence of positive integers $A=(A_1,A_2,\\ldots,A_N)$.\nThere are $2^N$ subsequences of $A$ when distinguishing subsequences by the indices of their elements. Let $S_1, S_2, \\ldots, S_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments