1792 . Ch10. Section 4. 鑰匙
TopCoder
Tags
Description
“唔 ~ 啊 啊 啊 啊 啊 啊!!!!!!”
妁艷爸爸大吼著,他被妤嬌的攻擊命中了!!!
“父親...你為甚麼要這麼做"妁艷妹妹看著躺在地上的爸爸,呢喃著說...
“事不遲疑,快去救出妁艷吧"剝剝火姬說著
“來~ 走吧~ 事情一定會水落石出的~"妤嬌姐姐拉著妁艷妹妹說
妤嬌一行人走到了祭壇的頂端,打開了門,看見了被綁住的妁艷
“哥哥~~~我好想你~~~”妁艷妹妹哭著喊
“你再不回地球,你的微積分就要被當掉了喔哈哈”妤嬌冷冷的說
“快把我放開啦囧”妁艷說著 妁艷身上有好幾把鎖把妁艷鎖著
每把鎖上都有 $2\times N$ 個點,排成矩形的樣子,左右長為 $N$,上下寬為 $2$,左右、上 下兩點之間距離都一樣。而最左邊還有一個點為起點,最右邊有一個點為終點。 現在希望能從起點畫到終點,並能經過所有的點。
不過還有三個條件:
1.當上面那排點由左到右是由 $X_1$ 到 $X_N$、下面那排由左到右是 $Y_1$ 到 $Y_N$ 時,起點只 能畫到 $X_1$ 或 $Y_1$,且只有 $X_N$ 和 $Y_N$ 能畫到終點。
2.當$ X_1$ 到 $X_i$ 還沒全部畫到前,不可以畫 $X_{i+1}$, $Y$ 也一樣
3.可以由 $X_{i+1}$ 畫到 $Y_i$ 或 $Y_{i+1}$ 畫到 $X_i$,即是可以畫到另一排的前一個,但兩個以上 則不行
另外還有三個數 $A$、$B$、$C$ 代表在 $X,Y$ 兩排之間前進、後退畫時所需的時間
(代表從起點出來或出去到終點皆不用算)
$A$ 代表畫斜率為$ 0 $的線時所需的時間
$B$代表畫斜率為 $1$ 的線時所需的時間
$C$ 代表畫斜率為$-1$ 的線時所需的時間 請你把妁艷放開吧~
$N=5$ 其中一種
時間:$4A+2B$
Input Format
第一行會有一個正整數 $T$ 代表有$ T$ 把鎖要解
接下來會有$2T$ 行,代表 $T$ 把鎖的資料
每一把鎖的第一行會有一個正整數 $N$ 代表鎖的長度
第二行則有三個正整數 $A$、$B$、$C$ 如題目所述
對$100\%$的測資 $T\leq 10$;
對$10\%$的測資 $N\leq 5$;
對$30\%$的測資 $N\leq 10^ {2}$;
對$50\%$的測資 $N\leq 10^ {6}$;
對$70\%$的測資 $N\leq 10^ {7}$;
對$100\%$的測資 $N\leq 10^ {18}$;
對$100\%$的測資 $A, B, C \leq10$.
Output Format
對於每一把鎖輸出兩行
第一行輸出有幾種解法
第二行輸出若畫出所有解法共需的時間為多少
答案太大請$\mod 1000000007$
Sample Input 1
1
1 1 1
Sample Output 1
0
Sample Input 2
5
1 1 1
5
1 2 1
Sample Output 2
704
120
852
Hints
妤嬌把鎖住妁艷的鎖解開了,妁艷便和妤嬌、妁艷妹妹、妤嬌姐姐、剝剝火姬搭 乘太空船,準備返回地球了......
就在他們冥王星起飛後,只見妁艷爸爸要舉起那把改造武器,瞄向太空船,準備 把他們打下來!!!
“妁艷,別想給我走!!!”妁艷爸爸吼著
“不要啊~~~”妁艷妹妹說
“不!父親!!!那武器不能那樣用啊!!!!!!那樣操作會完蛋啊!!!”妁艷大吼著!!!
只見妁艷父親按下了開關,那武器就發出了極大的攻擊......
妁艷等人在太空船上回頭看,只見冥王星被白霧覆蓋著,
白霧消去後,太空中空空的,冥王星已不存在了,而妁艷父親就這樣消失了.......
Problem Source
原TIOJ1792 / problem: lnsuyn; source: TOI 2010 3模
Added $\LaTeX$ by Seanliu on 20201103
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 |