PreVOI Phú Thọ 2023 - Ngày 04/02 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Phân số - FRACT (PreVOI Phú Thọ)	7 (p)	2.0s	1G
2	Truyền Tin - MSGAME (PreVOI Phú Thọ)	7 (p)	2.0s	1G
3	Trò chơi xếp hình - PIPEGAME (PreVOI Phú Thọ)	6 (p)	2.0s	1G

1. Phân số - FRACT (PreVOI Phú Thọ)

Điểm: 7 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: FRACT.INP Output: FRACT.OUT

Cho phân số \(\frac{p}{q}\), tiến hành biểu diễn phân số trong hệ cơ số thập phân, sau khi loại bỏ dấu chấm thập phân (dấu ngăn cách giữa phần nguyên và phần thực) ta nhận được một xâu số có độ dài vô hạn. Đánh số các kí tự của xâu bắt đầu từ \(1\), để khảo sát phân số, với một xâu mẫu người ta muốn tìm vị trí xuất hiện thứ \(k\) của \(S\) trong \(T\).

Yêu cầu: Cho \(p, q, k\) và xâu \(S\), hãy xác định vị trí xuất hiện thứ \(k\) của \(S\) trong \(T\), trong đó \(T\) là biểu diễn của phân số \(\frac{p}{q}\) trong hệ cơ số thập phân sau khi loại bỏ dấu chấm ngăn cách giữa phần nguyên và phần thực.

Input

Dữ liệu vào từ file văn bản FRACT.INP:
- Dòng đầu tiên chứa ba số nguyên dương \(p, q, k\);
- Dòng thứ hai chứa một xâu số \(S\) có độ dài không vượt quá \(10^5\).

Output

Ghi ra file văn bản FRACT.OUT một số là vị trí xuất hiện thứ \(k\) của \(S\) trong \(T\), nếu không tồn tại ghi số \(0\).

Ràng buộc

Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thỏa mãn: độ dài xâu \(S\) bằng \(1\);
\(40\%\) số test khác ứng với \(40\%\) số điểm của bài thỏa mãn: \(q \le 10^5\);
\(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thỏa mãn: không có ràng buộc nào thêm.

Example

Test 1

Input

3 7 2
2

Output

Test 2

Input

3 5 2
00

Output

2. Truyền Tin - MSGAME (PreVOI Phú Thọ)

Điểm: 7 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: MSGAME.INP Output: MSGAME.OUT

Có \(n\) người đánh số từ \(1\) đến \(n\) xếp thành một hàng và cùng nhau chơi trò chơi truyền tin. Người thứ \(i\) (\(1 \le i \le n\)) có độ trễ khi truyền tin là \(d_i\). Độ trễ khi người thứ \(i\) truyền tin cho người thứ \(j\) (\(1 \le i \le j \le n\)) được tính bằng

\[D(i,j)=\max\{d_i,d_{i+1},\ldots,d_j\}.\]

Người quản trò muốn tìm ra \(k\) (\(1 \le k \le n\)) người chơi để tổng độ trễ liên lạc là nhỏ nhất. Một cách hình thức, cần chọn \(k\) chỉ số

\[1 \le i_1 < i_2 < \cdots < i_k \le n\]

sao cho

\[w=\sum_{1 \le x \le y \le k}D(i_x,i_y)\]

là nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên \(n, k\).
Dòng thứ hai chứa \(n\) số nguyên dương \(d_1,d_2,\ldots,d_n\) (\(d_i \le 10^9\)).

Output

In ra một số nguyên duy nhất là giá trị nhỏ nhất của \(w\).

Example

Test 1

Input

4 3
1 2 2 1

Output

Note

Chọn ba người \(1,2,4\). Tổng độ trễ là

\[D(1,2)+D(1,4)+D(2,4)+D(1,1)+D(2,2)+D(4,4)=10.\]

Scoring

\(20\%\) số điểm: \(n \le 20\).
\(30\%\) số điểm: \(k=3\) và \(n \le 10^4\).
\(30\%\) số điểm: \(n \le 500\).
\(20\%\) số điểm: \(n \le 10^4\).

3. Trò chơi xếp hình - PIPEGAME (PreVOI Phú Thọ)

Điểm: 6 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: PIPEGAME.INP Output: PIPEGAME.OUT

Mỗi ô của bảng được đặt một trong sáu loại mảnh ống. Mỗi mảnh nối đúng hai cạnh của ô vuông; sáu loại lần lượt nối các cặp cạnh:

trên – dưới;
trái – phải;
trên – phải;
trên – trái;
dưới – trái;
dưới – phải.

Xem sáu hình mảnh ống và sáu cách xếp minh họa chính thức trong đề PDF.

Yêu cầu: Tìm số lượng cách xếp các loại hình trên vào đầy bảng \(m \times n\) (\(1 < m \times n \le 100\)) để các nét trong các hình vuông tạo thành một đường khép kín.
Ví dụ: có \(6\) cách xếp vào bảng \(4 \times 4\).

Input

Dữ liệu vào từ file văn bản PIPEGAME.INP gồm một dòng chứa hai số nguyên dương \(m, n\).

Output

Ghi ra file văn bản PIPEGAME.OUT một số nguyên là số lượng cách xếp tìm được.

Example

Test 1

Input

4 4

Output

Test 2

Input

5 7

Output

Test 3

Input

2 8

Output

Ràng buộc

Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn: \(m \times n \le 20\);
Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(n \le 4\);
\(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.