JOI 2010 Final Camp - Ngày 1 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2010 - JOI Poster	100 (p)	1.0s	64M
2	JOI 2010 - Sengoku	100 (p)	0.75s	64M
3	JOI 2010 - Stairs	100 (p)	1.5s	64M

1. JOI 2010 - JOI Poster

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Ủy ban Olympic Tin học Nhật Bản quyết định làm áp phích để quảng bá trại huấn luyện Olympic Tin học Nhật Bản (JOI) năm nay. Áp phích được thiết kế dựa trên logo của JOI.

Trên áp phích, các chữ cái được in thành một hình vuông gồm \(2^N\) hàng và \(2^N\) cột. Cách in được quy định như sau:

Khi \(N \ge 1\), chia hình vuông kích thước \(2^N \times 2^N\) thành bốn hình vuông kích thước \(2^{N-1} \times 2^{N-1}\). In chữ J vào toàn bộ hình vuông phía trên bên trái, chữ O vào toàn bộ hình vuông phía trên bên phải và chữ I vào toàn bộ hình vuông phía dưới bên trái. Trong hình vuông phía dưới bên phải, in một áp phích kích thước \(2^{N-1} \times 2^{N-1}\) theo cùng quy tắc.
Khi \(N = 0\), in áp phích kích thước \(1 \times 1\) chỉ gồm một chữ J.

Dưới đây là các chữ cái trên áp phích kích thước \(8 \times 8\) khi \(N = 3\):

JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO
IIIIJJOO
IIIIJJOO
IIIIIIJO
IIIIIIIJ

Người ta phát hiện hàng thứ \(K\) của áp phích đã in bị sai. Trại huấn luyện JOI năm nay đã bắt đầu, nên không còn đủ thời gian để nhờ nhà in in lại áp phích. Vì vậy, họ quyết định khắc phục bằng cách dán hàng thứ \(K\) được in đúng lên áp phích.

Yêu cầu

Cho hai số nguyên \(N\) và \(K\), hãy viết chương trình in ra hàng thứ \(K\) của áp phích kích thước \(2^N \times 2^N\).

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách. \(N\) xác định kích thước áp phích, còn \(K\) là số thứ tự của hàng cần in ra.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa hàng thứ \(K\) của áp phích kích thước \(2^N \times 2^N\).

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
\(0 \le N \le 20\).
\(1 \le K \le 2^N\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm.

Các bộ kiểm thử có tổng cộng \(50\) điểm thỏa mãn \(N \le 10\).

Ví dụ

Ví dụ 1

Input

1 1

Output

JO

Ví dụ 2

Input

2 4

Output

IIIJ

Ví dụ 3

Input

3 7

Output

IIIIIIJO

2. JOI 2010 - Sengoku

Điểm: 100 (p) Thời gian: 0.75s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Đang giữa thời Chiến Quốc. Để chuẩn bị cho trận chiến sắp tới, vị tướng JOI, người lãnh đạo nước JOI, quyết định bố trí lính canh trên lãnh thổ của mình.

Lãnh thổ nước JOI có dạng hình vuông, với chiều đông–tây và chiều bắc–nam đều bằng \(L\). Lãnh thổ được chia thành các ô vuông kích thước \(1 \times 1\). Mỗi ô được biểu diễn bằng cặp số nguyên \((x, y)\) thỏa mãn \(0 \le x < L\) và \(0 \le y < L\). Ô \((0, 0)\) nằm ở góc tây bắc; ô \((x, y)\) nằm cách ô \((0, 0)\) một khoảng \(x\) về phía đông và \(y\) về phía nam.

Mỗi lính canh đứng cố định tại một ô trong lãnh thổ. Lính canh ở ô \((x, y)\) canh gác tất cả các ô \((i, j)\) trong lãnh thổ thỏa mãn:

\[ |x - i| = |y - j|. \]

Phạm vi này không thay đổi theo vị trí của các lính canh khác. Không có hai lính canh nào đứng cùng một ô.

Yêu cầu

Cho vị trí của \(N\) lính canh do tướng JOI bố trí, hãy viết chương trình tính số ô trong lãnh thổ được ít nhất một lính canh canh gác.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

Dòng đầu tiên chứa hai số nguyên \(L\) và \(N\), cách nhau bởi dấu cách.
\(N\) dòng tiếp theo mô tả các lính canh, mỗi dòng mô tả một người. Dòng thứ \(i\) trong số này chứa hai số nguyên \(x_i\) và \(y_i\), cách nhau bởi dấu cách, cho biết vị trí của lính canh thứ \(i\); \(0 \le x_i < L\) và \(0 \le y_i < L\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: số ô được ít nhất một lính canh canh gác.

Lưu ý: Kết quả có thể vượt quá phạm vi biểu diễn của kiểu số nguyên 32 bit. Cần sử dụng kiểu số nguyên 64 bit, chẳng hạn long long trong C/C++.

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(0{,}75\) giây, bộ nhớ \(64\) MB.
\(1 \le L \le 100\,000\,000\): độ dài một cạnh của lãnh thổ.
\(1 \le N \le 100\,000\): số lính canh.
\(0 \le x_i < L\) và \(0 \le y_i < L\) với mọi \(1 \le i \le N\).
Không có hai lính canh nào đứng cùng một ô.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(16\) bộ dữ liệu, mỗi bộ \(5\) điểm, và \(2\) bộ dữ liệu, mỗi bộ \(10\) điểm.

Các bộ kiểm thử có tổng cộng \(15\) điểm thỏa mãn \(L \le 1\,000\) và \(N \le 1\,000\).
Các bộ kiểm thử có tổng cộng \(40\) điểm thỏa mãn \(N \le 1\,000\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Lãnh thổ nước JOI trong ví dụ này được minh họa trong hình dưới đây. Có \(18\) ô được canh gác. Các chấm tròn màu đen biểu thị lính canh; các ô được tô màu xám là những ô được canh gác.

3. JOI 2010 - Stairs

Điểm: 100 (p) Thời gian: 1.5s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Bạn muốn tìm hiểu có bao nhiêu cách đi lên một cầu thang. Cầu thang gồm \(N\) bậc; độ chênh cao của bậc thứ \(k\) là \(h_k\) mm, với \(1 \le k \le N\).

Trong một lần bước, bạn có thể đi lên một hoặc nhiều bậc có tổng độ chênh cao không vượt quá \(P\) mm. Khi đi lên cầu thang, bạn không giậm chân tại chỗ trên cùng một bậc và không đi xuống. Hai cách đi lên được xem là giống nhau nếu các bậc được đặt chân lên là giống nhau.

Yêu cầu

Hãy tính số cách đi lên hết cầu thang, lấy phần dư khi chia cho \(1\,234\,567\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

Dòng đầu tiên chứa hai số nguyên \(N\) và \(P\), cách nhau bởi dấu cách.
Dòng thứ \(k\) trong \(N\) dòng tiếp theo chứa số nguyên \(h_k\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: phần dư của số cách đi lên cầu thang khi chia cho \(1\,234\,567\).

Ràng buộc

Giới hạn trong kỳ thi gốc: thời gian \(1{,}5\) giây, bộ nhớ \(64\) MB.
\(1 \le N \le 500\,000\): số bậc của cầu thang.
\(1 \le P \le 500\,000\,000\): tổng độ chênh cao tối đa có thể vượt qua trong một lần bước, tính bằng mm.
\(1 \le h_k\) với mọi \(1 \le k \le N\): độ chênh cao của bậc thứ \(k\), tính bằng mm.

Tổng độ chênh cao của các bậc thỏa mãn:

\[ h_1 + \cdots + h_N \le 500\,000\,000. \]

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

Các bộ kiểm thử có tổng cộng \(50\) điểm thỏa mãn \(N \le 3\,000\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Cầu thang này gồm \(6\) bậc và có \(9\) cách đi lên:

\(1, 2, 3, 4, 5, 6\).
\(1, 2, 3, 4, 6\).
\(1, 2, 3, 5, 6\).
\(1, 2, 4, 5, 6\).
\(1, 2, 4, 6\).
\(1, 2, 5, 6\).
\(1, 3, 4, 5, 6\).
\(1, 3, 4, 6\).
\(1, 3, 5, 6\).

Chẳng hạn, ký hiệu \(1, 3, 5, 6\) biểu diễn cách đi lên bậc thứ \(6\) bằng cách đặt chân lên các bậc thứ \(1\), \(3\) và \(5\) trước đó.