Cho ma trận nhị phân gồm N hàng và M cột chỉ bao gồm các số 0 và 1. Hãy đếm số lượng miền các số 1 trong ma trận, các ô số 1 được coi là cùng miền nếu chúng có chung đỉnh.

Ràng buộc: 1 ≤ N,M ≤ 50

Input 01:

3 3
1 0 1
0 0 1
1 1 0

Output 01:

2

Input 01:

8 8
1 1 0 1 1 1 1 0
0 1 1 1 0 0 0 1
1 1 0 0 0 0 1 1
0 1 0 1 0 0 1 1
1 0 0 1 0 0 0 1
0 1 0 1 1 1 1 0
0 0 0 0 1 0 1 1
1 0 0 0 0 0 0 0

Output 02:

2

Cho số nguyên dương N và hệ cơ số B. Hàm F(B,N) được định nghĩa như sau: Nếu N được biểu diễn trong hệ cơ số B có dạng:

Hãy tính giá trị hàm F với mỗi cặp B và N cho trước.

Định dạng đầu vào:

Dòng đầu ghi số lượng bộ test, không quá 1000.

Mỗi bộ test gồm 2 số nguyên: B(3≤B≤16) và số nguyên dương N (trong phạm vi số nguyên không dấu 32 bit).

Định dạng đầu ra: Với mỗi bộ test, ghi ra trên một dòng giá trị hàm F tính được.

Input:

3
10 1234
3 98765
16 987654321

Output:

30 
19 
696

Năm mới sắp đến và bạn rất hào hứng muốn biết còn lại bao nhiêu phút trước Tết. Bạn biết rằng hiện tại đồng hồ hiển thị h giờ và m phút, trong đó 0≤h<24 và 0≤m<60. Chúng tôi sử dụng định dạng thời gian 24 giờ! Nhiệm vụ của bạn là tìm số phút trước Tết. Bạn biết rằng năm mới đến khi đồng hồ hiển thị 0 giờ và 0 phút. Bạn phải trả lời t trường hợp kiểm tra độc lập.

Input: Dòng đầu tiên của đầu vào chứa một số nguyên t (1≤t≤1439) - số lượng trường hợp kiểm tra. Các dòng t sau đây mô tả các trường hợp thử nghiệm. Dòng thứ i chứa thời gian là hai số nguyên h và m (0≤h<24, 0≤m<60). Đảm bảo rằng thời gian này không phải là nửa đêm, tức là hai điều kiện sau đây không thể được đáp ứng cùng một lúc: h = 0 và m = 0. Nó được đảm bảo rằng cả h và m được đưa ra mà không có số 0 đứng đầu.

Output: Đối với mỗi trường hợp kiểm tra, hãy in câu trả lời trên đó - số phút trước Tết.

Ví dụ:

Input:

5
23 55
23 0
0 1
4 20
23 59

Output:

5
60
1439
1180
1

Cho một số tự nhiên n. Hãy in ra màn hình các chữ số của n trên các dòng khác nhau theo cách viết sau:

Số 0 được viết như sau:

###
#.#
#.#
#.#
###

Số 1 được viết như sau:

..#
.##
#.#
..#
..#

Số 2 được viết như sau:

###
..#
.#.
#..
###

Số 3 được viết như sau:

###
..#
###
..#
###

Input: Gồm một số tự nhiên n duy nhất (n gồm 4 chữ số, các chữ số của n chỉ có thể là 0, 1, 2, 3).

Output: In ra các chữ số n theo cách viết như đề bài, mỗi số cách nhau một dòng.

Sample Test

Input:

1112

Output:

..#
.##
#.#
..#
..#

..#
.##
#.#
..#
..#

..#
.##
#.#
..#
..#

###
..#
.#.
#..
###

Cho một mảng ~a~ gồm ~n~ số nguyên.

Một dãy được gọi là không nghịch biến đặc biệt nếu thỏa mãn điều kiện:

~-~ Dãy không giảm ( nghĩa là ~a[i] <= a[i+1]~ với mọi ~i~ )

~-~ Không tồn tại 3 phần tử liên tiếp bằng nhau.

Nhiệm vụ của bạn: Kiểm tra xem mảng đã cho có phải là dãy không nghịch biến đặc biệt hay không !

Đầu vào

Dòng đầu tiên là số ~n~.

Dòng tiếp theo có ~n~ số phần tử trong mảng.

Giới hạn

~1≤n≤500~

Các phần tử trong mảng là số nguyên dương không quá ~500~.

Đầu ra

In ra "YES" nếu thỏa mãn đề bài còn "NO" nếu ngược lại.

Ví dụ :

Input:

4
4 3 2 1

Output:

NO

Một hoán vị của các số nguyên từ ~1, 2, ..., n~ được gọi là "hoán vị đẹp" nếu không có hai phần tử liền kề nào có hiệu bằng 1.

Cho một số nguyên n, hãy tạo ra một hoán vị đẹp của dãy số từ 1 đến n nếu tồn tại. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ một hoán vị nào. Nếu không tồn tại hoán vị đẹp, hãy in ra "NO SOLUTION".

Dữ liệu vào:

Dòng duy nhất chứa số nguyên ~n~.

Dữ liệu ra:

In ra hoán vị đẹp nếu có thể, mỗi số cách nhau bởi khoảng trắng.

Nếu không thể, in ra "NO SOLUTION".

Ví dụ 1:

Input:

5

Output:

4 2 5 3 1

Ví dụ 2:

Input:

3

Output:

NO SOLUTION

Giải thích:

Với ~𝑛= 5~ một hoán vị như 4 2 5 3 1 là hợp lệ, vì không có hai số liền kề nào chênh lệch đúng 1 đơn vị.

Với ~𝑛= 3~ không có cách nào để sắp xếp ba số sao cho không có cặp nào liền nhau có hiệu bằng 1.

Cho một mảng số nguyên gồm n phần tử. Hãy viết chương trình C++ để đếm xem có bao nhiêu số chính phương trong mảng đã cho.

Đầu vào

Dòng đầu tiên là số ~n~.

Dòng tiếp theo có ~n~ số.

Giới hạn

~1≤n≤500~

Các phần tử trong mảng là số nguyên dương không quá ~500~.

Đầu ra

Số lượng số chính phương có trong mảng.

Ví dụ :

Input:

5
1 4 8 6 5

Output:

2

Cho ma trận A cỡ NxM, ma trận B cỡ MxP. Hãy tính ma trận tích của A và B.

Định dạng đầu vào: Dòng đầu tiên là 3 số N, M, P: N dòng tiếp theo, mỗi dòng M của ma trận A; M dòng tiếp theo, mỗi dòng P số của ma trận B

Ràng buộc: 1 ≤ N, M, P ≤ 50; Các phần tử trong ma trận là số dương không quá 100000;

Định dạng đầu ra: In ra ma trận tích của A và B

Input:

3 4 5
1 2 3 4
5 6 7 8
9 10 11 12
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20

Output:

110 120 130 140 150 
246 272 298 324 350 
382 424 466 508 550

Ma trận xoáy ốc cấp N là ma trận vuông có N*N phần tử. Các số được điền vào ma trận trận theo chiều kim đồng hồ theo thứ tự tăng dần bắt đầu từ 1

INPUT:

3

OUTPUT:

1 2 3
8 9 4
7 6 5

Tèo khá thích chơi cờ vua và quân cờ mà Tèo yêu thích chính là quân Xe, bây giờ Tèo có một bàn cờ cỡ NxN, trên bàn cờ sẽ có những ở trồng và có những ô có vật cản, nhiệm vụ của bạn là hãy xác định xem số lượng ô trên bàn cờ mà quân Xe có thế di chuyển tới, biết ràng nó có thế đi qua đi lại 1 ô trống nhiều lần và không thể đi vào ô có vật cản.

Bàn cờ gồm N hàng N cột, mỗi ô là số 1 tương ứng với vật cản và ô số 0 tương ứng với ô trồng. Ban đầu quân Xe năm ở vị trí hàng 5 và cột T và ô (5, T) là ô trống

Định dạng đầu vào:

• Dòng 1 là N, S, T

• N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc:

~5 \leq N＜=20~

~0 \leq A[i][j] \leq 1~

Đầu ra:

In ra số lượng ô trên bàn cờ mà quân Xe có thể đến được

Ví dụ:

Input:

7 4 6
1 1 1 0 0 1 0
1 1 0 0 0 1 1
0 1 0 0 0 0 0
1 0 1 0 1 0 1
1 0 1 1 1 1 0
1 1 0 0 1 0 1
0 0 0 0 1 1 0

Output:

12

Tèo khá thích chơi cờ vua và quân cờ mà Tèo yêu thích chính là quân Tịnh, bây giờ Tèo có một bàn cờ cỡ NxN, trên bàn cờ sẽ có những ô trống và có những ô có vật cản, nhiệm vụ của bạn là hãy xác định xem số lượng ô trên bàn cờ mà quân Tịnh có thế di chuyển tới, biết rằng nó có thể đi qua đi lại 1 ô trống nhiều lần và không thể đi vào ô có vật cản.

Bàn cờ gồm N hàng N cột, mỗi ô là số 1 Tương ứng với vật cản và ô số 0 tương ứng với ô trống. Ban đầu quân Tịnh năm ở vị trí hàng S và cột T và ô (S, T) là ô trống

Định dạng đầu vào:

• Dòng 1 là N, S, T

• N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc:

~5 \leq N＜=20~

~0 \leq A[i][j] \leq 1~

Đầu ra:

In ra số lượng ô trên bàn cờ mà quân Tịnh có thể đến được

Ví dụ:

Input:

6 1 3
0 0 0 1 1 0
1 1 1 0 1 0
1 0 0 1 0 1
1 1 1 1 1 0
0 0 1 1 1 0
0 1 1 0 1 0

Output:

6

Cho bàn cờ vua cỡ N * N, các ô trên bàn cờ có giá trị là 0 hoặc 1. Một con mã xuất phát từ ô (s, t) và muốn di chuyến tới ô (u, v), con mã chỉ có thể di chuyển ở các ô mà tại ô đó có giá trị là 1 và nó có thế di chuyến qua lại 1 ô nhiều lần. Hãy xác định xem con mã có thế tìm được đường đi hay không, dữ liệu đảm bảo ô (s, t) và ô (u, v) đều có giá trị là 1.

Ràng buộc: 1 ≤ N,M ≤ 100; 1 ≤ s,t,u,v ≤ N; 0 ≤ A[i][j] ≤ 1;

In YES nếu con mã có thể tìm được đường đi, ngược lại in NO.

Input:

9
7 5 4 3
1 0 1 0 1 0 1 1 1
1 1 1 1 0 0 0 0 1
1 0 1 1 1 0 1 1 1
1 0 1 0 1 0 0 0 0
0 1 1 0 1 0 1 1 1
1 0 0 0 0 1 1 0 1
1 0 1 0 1 0 1 1 0
0 1 1 0 0 0 0 1 1
0 0 1 1 0 0 0 0 1

Output:

YES