TopCoder

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

92.3% (12/13)

Description

“唔 ~ 啊 啊 啊 啊 啊 啊!!!!!!”
妁艷爸爸大吼著,他被妤嬌的攻擊命中了!!!
“父親...你為甚麼要這麼做"妁艷妹妹看著躺在地上的爸爸,呢喃著說...
“事不遲疑,快去救出妁艷吧"剝剝火姬說著
“來~ 走吧~ 事情一定會水落石出的~"妤嬌姐姐拉著妁艷妹妹說
妤嬌一行人走到了祭壇的頂端,打開了門,看見了被綁住的妁艷
“哥哥~我好想你~”妁艷妹妹哭著喊
“你再不回地球,你的微積分就要被當掉了喔哈哈”妤嬌冷冷的說
“快把我放開啦囧”妁艷說著 妁艷身上有好幾把鎖把妁艷鎖著
每把鎖上都有 2*N 個點,排成矩形的樣子,左右長為 N,上下寬為 2,左右、上 下兩點之間距離都一樣。而最左邊還有一個點為起點,最右邊有一個點為終點。 現在希望能從起點畫到終點,並能經過所有的點。
不過還有三個條件:
1.當上面那排點由左到右是由 X1 到 XN、下面那排由左到右是 Y1 到 YN 時,起點只 能畫到 X1 或 Y1,且只有 XN 和 YN 能畫到終點 n
2.當 X1 到 Xi 還沒全部畫到前,不可以畫 Xi+1,Y 也一樣
3.可以由 Xi+1 畫到 Yi 或 Yi+1 畫到 Xi,即是可以畫到另一排的前一個,但兩個以上 則不行
另外還有三個數 A、B、C 代表在 X,Y 兩排之間前進、後退畫時所需的時間
(代表從起點出來或出去到終點皆不用算)
A 代表畫斜率為 0 的線時所需的時間
B 代表畫斜率為 1 的線時所需的時間
C 代表畫斜率為-1 的線時所需的時間 請你把妁艷放開吧~

N=5 其中一種

時間:4A+2B

Input Format

第一行會有一個正整數 T 代表有 T 把鎖要解
接下來會有 T*2 行,代表 T 把鎖的資料
每一把鎖的第一行會有一個正整數 N 代表鎖的長度
第二行則有三個正整數 A、B、C 如題目所述

對100%的測資 T≤10;
對10%的測資 N≤5;
對30%的測資 N≤102;
對50%的測資 N≤106;
對70%的測資 N≤107;
對100%的測資 N≤1018;
對100%的測資 A 、B 、C≤10.

Output Format

對於每一把鎖輸出兩行
第一行輸出有幾種解法
第二行輸出若畫出所有解法共需的時間為多少
答案太大請%1000000007

Sample Input

Sample Input 1:
1
1
1 1 1

Sample Input 2:
2
5
1 1 1
5
1 2 1

Sample Output

Sample Output 1:
2
0

Sample Output 2:
120
704
120
852

Hints

妤嬌把鎖住妁艷的鎖解開了,妁艷便和妤嬌、妁艷妹妹、妤嬌姐姐、剝剝火姬搭 乘太空船,準備返回地球了......
就在他們冥王星起飛後,只見妁艷爸爸要舉起那把改造武器,瞄向太空船,準備 把他們打下來!!!
“妁艷,別想給我走!!!”妁艷爸爸吼著
“不要啊~~~”妁艷妹妹說
“不!父親!!!那武器不能那樣用啊!!!!!!那樣操作會完蛋啊!!!”妁艷大吼著!!!
只見妁艷父親按下了開關,那武器就發出了極大的攻擊......
妁艷等人在太空船上回頭看,只見冥王星被白霧覆蓋著,
白霧消去後,太空中空空的,冥王星已不存在了,而妁艷父親就這樣消失了.......

Problem Source

原TIOJ1792 / problem: lnsuyn; source: TOI 2010 3模

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10