ビット全探索 練習問題 1 CoffeeScript(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
ビット全探索を使う問題をもっと解いていきましょう。
N 個のランプが横一列に並べられています。
あなたはいまどのランプが光っているのか知りません。
そこで、M 人の友達から情報をもらうことにしました。
i 番目の友達は、左から l_i 個目 ~ r_i 個目のランプのうち、光っているランプの個数は x_i 個だと教えてくれました。
友達の情報に矛盾しないような光っているランプの組合せはいくつありますか？
- 入力される値
-
N M
l_1 r_1 x_1
l_2 r_2 x_2
...
l_M r_M x_M
・ 1 行目には整数 N, M が与えられます。
・ 続く M 行には、友達からの情報 l_i, r_i, x_i が空白区切りで与えられます。
・ 入力は合計で M+1 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
友達の情報に矛盾しないような光っているランプの組合せの個数を一行に出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 16
・ 1 ≦ M ≦ 30
・ 1 ≦ l_i ≦ r_i ≦ N
・ (l_i, r_i) ≠ (l_j, r_j) (i ≠ j)
・ 0 ≦ x_i ≦ r_i - l_i + 1
- 入力例1
-
6 3
1 4 2
3 3 1
3 5 2
- 出力例1
-
6
- 入力例2
-
6 5
3 6 2
2 4 2
5 5 0
2 2 1
4 4 0
- 出力例2
-
2
- 入力例3
-
3 2
1 3 3
2 3 0
- 出力例3
-
0
