GCJっぽい問題2
現在自分でも解答中だけど一応はっとく
問題
m個の買い物かごにそれぞれ値段(各
円 (i=0,・・・,n-1))のついたn個の商品を分けて入れる。そしてこれらを買い物かごごとに清算するが、日本では消費税5%がかかるので、(買い物かごの中の商品の合計金額)*1.05を切り捨てた値が払うべき金額となる。
さて、商品の入れ方を工夫すれば、全体の合計金額を減らすことができる。その最小額を求めてほしい。
入力
すごく単純に考えて
の組み合わせがあるため、m=6, n=20程度でも相当難しそうな・・
GCJっぽい問題(簡易版2)
1〜nの整数を並べ替えて、それぞれの2進数表示を1の位を揃えて縦に並べる。
1,2,3,4,5,6,7(n=7)であれば
0001
0010
0011
0100
0101
0110
0111
のように。
さてこれらの行を並べ替える。たとえば
1,6,2,3,4,7,5と並べ替えて
0001
0110
0010
0011
0100
0111
0101
とすると、1の領域はゆるい連結となる。
つまり、どの1からどの1へも、1だけを通って縦移動または横移動または斜め移動で行ける。
このような、ゆるい連結となる組み合わせは何通りあるか。
答えが爆発的に増えることが予想されるので10007で割った余りを答えよう。
input setは、第1行がinput数、その後nの値が並ぶ。
outputは、各nに対応して求めた上記の組み合わせの値を並べればよい。
small:
10
1
2
3
4
5
6
7
8
9
10
large:
10
11
12
13
14
15
16
17
18
19
20
exlarge:
??
GCJっぽい問題(簡易版)
1〜nの整数を並べ替えて、それぞれの2進数表示を1の位を揃えて縦に並べる。
1,2,3,4,5,6,7(n=7)であれば
0001
0010
0011
0100
0101
0110
0111
のように。
さてこれらの行を並べ替える。たとえば
4,6,2,3,1,7,5と並べ替えて
0100
0110
0010
0011
0001
0111
0101
とすると、1の領域は連結となる。
つまり、どの1からどの1へも、1だけを通って縦移動または横移動で行ける。
このような組み合わせは何通りあるか。
答えが爆発的に増えることが予想されるので10007で割った余りを答えよう。
input setは、第1行がinput数、その後nの値が並ぶ。
outputは、各nに対応して求めた上記の組み合わせの値を並べればよい。
といってもまだ自分でもプログラムをつくってないわけだが。
small:
6
3
4
6
7
12
13
large:
じゅんびちゅ
