e791: a2.空間切割(Cut)
Tags :
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-12-29 16:58

Content

 Y19m12_a02_空間切割(Cut) TOI練習賽2019/12

問題敘述  {題目連結}

在一維空間中,對空間進行一次切割,稱為一刀,會使得空間變為二塊區域。而後我們每次再對空間進行切割,都只能再增加一塊區域,也就是一刀二塊,二刀三塊,三刀四塊等等,以此類推。但在更高維的空間中,每切割一次,不一定只增加一個區域,像在二維空間中,一刀最多會有二塊,二刀四塊,三刀七塊等等。不過當維度變高,計算區域個數也越困難。請你寫一個程式,計算D維空間中切割N次能分出來最多的區域個數。

 

評分說明

此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該組分數。各組詳細限制如下。

第一組(10分):1≤N≤10、1≤D≤2、1≤C≤5。

第二組(30分):1≤N≤10、1≤D≤3、1≤C≤5。

第三組(60分) : 1≤N≤10^4、1≤D≤50、1≤C≤50。

 

 

Input

輸入的第一列為一個正整數N(1≤ N≤ 10^4),代表要計算的資料筆數。接著N列,每一列有兩個正整數,以一個空白隔開,代表空間維度D(1≤ D≤ 50)與切割的次數C(1≤ C≤ 50)。

Output

對每筆資料請輸出N列,每一列為該情況下能切割出的最多區域數。

Sample Input #1
4
1 1
1 2
2 2
1 3	
Sample Output #1
2
3
4
4
Sample Input #2
6
2 1
2 2
2 3
3 1
3 2
3 3	
Sample Output #2
2
4
7
2
4
8
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :
Tags:
出處:
2019年12月TOI練習賽 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」