square869120Contest #3

A - カレンダー / Calendar


Time limit時間制限 : 1sec / Memory limitメモリ制限 : 256MB

Max Score: $250$ Points

Problem Statement

Snuke has a very long calendar. It has a grid with $n$ rows and $7$ columns. One day, he noticed that calendar has a following regularity.
  • The cell at the $i$-th row and $j$-th column contains the integer $7i+j-7$.
A good sub-grid is a $3 \times 3$ sub-grid and the sum of integers in this sub-grid mod $11$ is $k$.
How many good sub-grid are there? Write a program and help him.

Input

The input is given from standard input in the following format.

$n \quad k$

Output

  • Print the number of good sub-grid. If there are no solution exists, print 0.

Constraints

  • $1 \le n \le 10^9$
  • $0 \le k \le 10$

Subtasks

Subtask 1 [ $150$ points ]

  • The testcase in the subtask satisfies $1 \le n \le 100$.

Subtask 2 [ $100$ points ]

  • There are no additional constraints.

Sample Input 1

7 7

Sample Output 1

2
In this case, the calendar likes this matrix.
Sun. Mon. Tue. Wed. Thu. Fri. Sat.
Week 1 1 2 3 4 5 6 7
Week 2 8 9 10 11 12 13 14
Week 3 15 16 17 18 19 20 21
Week 4 22 23 24 25 26 27 28
Week 5 29 30 31 32 33 34 35
Week 6 36 37 38 39 40 41 42
Week 7 43 44 45 46 47 48 49

The cell at $i$-th row and $j$-th column is denoted $(i, j)$.
  • If upper-left is $(1, 5)$, the sum of integers is $5+6+7+12+13+14+19+20+21=117$.
  • If upper-left is $(3, 2)$, the sum of integers is $16+17+18+23+24+25+30+31+32=216$.
Therefore, there are 2 good sub-grids.

Sample Input 2

6 0

Sample Output 2

2
If upper-left is $(1, 3)$ or $(4, 4)$, it is a good sub-grid.

Sample Input 3

18 10

Sample Output 3

7

Sample Input 4

100 8

Sample Output 4

45

Writer:square1001
配点: $250$ 点

問題文

E869120は, 縦に長いカレンダーらしいものを持っていた。
ある日, E869120はそのカレンダーに以下の規則性があることを発見した。
  • 上から $i$ 番目, 左から $j$ 番目に書かれている整数は $7i+j-7$ である。
また, E869120は $3 \times 3$ の正方形の枠を持っていた。
そこで、以下の条件を満たす正方形の置き方を数え上げしてみることにした。
  • 正方形の枠内に入っている $9$ 個の数字の和を $11$ で割った余りは $k$ である。
そのとき, 条件を満たす枠の置き方は何通りあるでしょうか?

入力

入力は以下の形式で標準入力から与えられる。

$n \quad k$
  • 1行目には、カレンダーの段数 $n$ と, 正方形を置く時の条件となる数 $k$ が空白区切りで与えられる。

出力

  • 条件を満たす $3 \times 3$ の正方形の置き方の通り数を1行に出力しなさい。
  • ただし, 1つも条件を満たすような置き方ができない場合, $0$ と出力しなさい。

制約

  • $1 \le n \le 10^9$
  • $0 \le k \le 10$

小課題

小課題1 [ $150$点 ]

  • $1 \le n \le 100$ を満たす。

小課題2 [ $100$ 点 ]

  • 追加の制約はない。

入力例1

7 7

出力例1

2
この場合、以下の表のようなカレンダーになっている。
1列目 2列目 3列目 4列目 5列目 6列目 7列目
1行目 1 2 3 4 5 67
2行目 8 9 10 11 12 13 14
3行目 15 16 17 18 19 20 21
4行目 22 23 24 25 26 27 28
5行目 29 30 31 32 33 34 35
6行目 36 37 38 39 40 41 42
7行目 43 44 45 46 47 48 49

ここでは, $(i, j)$ を上から $i$ 番目, 左から $j$ 番目のマスとする。
  • 左上が $(1, 5)$ のとき, $5+6+7+12+13+14+19+20+21=117$ となり, $11$ で割った余りは $7$ となる。
  • 左上が $(3, 2)$ のとき, $16+17+18+23+24+25+30+31+32=216$ となり, $11$ で割った余りは $7$ となる。
条件を満たすのはこの2つのみである。

入力例2

6 0

出力例2

2
左上が $(1, 3)$ または $(4, 4)$ のときのみ条件を満たす。

入力例3

18 10

出力例3

7
左上のマスが $(2,2), (5,3), (8,4), (10,1), (11,5), (13,2), (16,3)$ のとき, 条件を満たす。

入力例4

100 8

出力例4

45
この入力例は小課題1を満たす。

問題文担当者:square1001

Submit提出する