情太ãã‚“ã¯é•·ã• 2L ã®æ£’を使ã£ã¦ä¸‹ã®å›³ã®ã‚ˆã†ãªç§¤ã‚’作ã£ãŸï¼Ž
棒ã«ã¯ç‰é–“隔㫠2L+1 個ã®ç©´ãŒã‚ã‘られ,左ã‹ã‚‰é †ã« −L,−L+1,⋯,−1,0,1,⋯,L−1,L ã¨ã„ã†ç•ªå·ãŒä»˜ã‘られã¦ã„る.ãã—㦠0 番ã®ç©´ã®å ´æ‰€ã‚’天井ã‹ã‚‰ç´ã§åŠã‚‹ã—ã¦ã‚る.
情太ãã‚“ã¯ï¼Œç§¤ã®ç©´ã« N 個ã®ãŠã‚‚ã‚Šã‚’åŠã‚‹ã—ãŸï¼Ži 番目ã®ãŠã‚‚ã‚Šã‚’åŠã‚‹ã—ãŸç©´ã®ç•ªå·ã¯ xi ã§ï¼ŒãŠã‚‚ã‚Šã®é‡ã•ã¯ wi ã§ã‚る.ãŠã‚‚り㌠1 ã¤ã‚‚åŠã‚‹ã•ã‚Œãªã„穴や,複数ã®ãŠã‚‚ã‚ŠãŒåŠã‚‹ã•ã‚Œã‚‹ç©´ã‚‚å˜åœ¨ã—ã†ã‚‹ï¼Ž
情太ãã‚“ãŒåŠã‚‹ã—ãŸãŠã‚‚ã‚Šã«ã‚ˆã£ã¦ã¯ï¼Œç§¤ãŒå‚¾ã„ã¦ã„ã‚‹ã‹ã‚‚ã—ã‚Œãªã„.姉ã®ç«‹åã•ã‚“ã¯ï¼Œè¿½åŠ ã§ã„ãã¤ã‹ã®é‡ã‚Šã‚’åŠã‚‹ã™ã“ã¨ã§ç§¤ã‚’æ°´å¹³ã«ã—ãŸã„ (ãŠã‚‚ã‚Šã®åº§æ¨™ã¨é‡ã•ç©ã®ç·å’ŒãŒ 0 ã«ãªã‚‹ã¨ã秤ã¯æ°´å¹³ã«ãªã‚‹).æ¡ä»¶ã‚’満ãŸã™ãŠã‚‚ã‚Šã®åŠã‚‹ã—方を 1 ã¤å‡ºåŠ›ã—ãªã•ã„.候補ãŒè¤‡æ•°ã‚ã‚‹å ´åˆã¯ã©ã‚Œã‚’出力ã—ã¦ã‚‚よã„.
L
N
x1 w1
⋮
xN wN
1≤L≤30
1≤N≤30
|xi|≤L
1≤wi≤30
å…¨ã¦æ•´æ•°
ç”ãˆã¯æ¬¡ã®ã‚ˆã†ãªå½¢å¼ã§å‡ºåŠ›ã›ã‚ˆï¼Ž 1 行目㮠N’ ã¯ç«‹åã•ã‚“ãŒåŠã‚‹ã—ãŸãŠã‚‚ã‚Šã®æ•°ã§ã‚る. 1+i 行目㮠x_i’, w_i’ ã¯ï¼Œãã‚Œãžã‚Œç«‹åã•ã‚“ãŒåŠã‚‹ã—ãŸãŠã‚‚ã‚Šã®ä½ç½®ã¨é‡ã•ã§ã‚る.
N'
x_1' \ w_1'
\vdots
x_N' \ w_N'
ç«‹åã•ã‚“ãŒè¿½åŠ ã§åŠã‚Šä¸‹ã’ã‚‹ãŠã‚‚ã‚Šã¯ï¼Œä»¥ä¸‹ã®æ¡ä»¶ã‚’満ãŸã™å¿…è¦ãŒã‚ã‚‹.
0 \leq N' \leq 50000
|x_i'| \leq L
1 \leq w_i' \leq 50000
å…¨ã¦æ•´æ•°
3 3 1 1 2 1 3 1
1 -3 2
ä»–ã«ã‚‚,例ãˆã°ä»¥ä¸‹ã®ã‚ˆã†ãªå‡ºåŠ›ã‚‚æ£è§£ã¨ã—ã¦æ‰±ã‚れる.
2 -3 1 -3 1
ã“れらを図示ã™ã‚‹ã¨æ¬¡ã®ã‚ˆã†ã«ãªã‚‹ï¼Ž
3 3 1 1 0 2 -1 3
1 2 1
10 4 1 2 2 3 -7 1 -1 1
0
秤ã¯æœ€åˆã‹ã‚‰é‡£ã‚Šåˆã£ã¦ã„ã‚‹ã“ã¨ã‚‚ã‚る.