Ôn Tập THT B 2025 - 2026 Contest #01

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Tích lấy dư 6 (p) 1.0s 256M
2 Điểm thưởng 5 (p) 1.0s 256M
3 Tìm xâu 5 (p) 1.0s 256M
4 Di chuyển cây 4 (p) 1.0s 256M

1. Tích lấy dư

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: BAI1.INP Output: BAI1.OUT

Cho ba số nguyên dương \(a, b, c\).

Yêu cầu

Tìm số dư của phép chia tích các số nguyên trong đoạn \([a..b]\) cho số \(c\).

Input

  • Dữ liệu vào từ tệp BAI1.INP chứa ba số nguyên dương \(a, b, c\).
  • Với:
  • \(1 \le a < b \le 10^4\)
  • \(1 \le c \le 10^9\)

Output

  • Ghi ra tệp BAI1.OUT số dư cần tìm.

Example

Test 1

Input 
5 10 11
Output 
5

2. Điểm thưởng

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: BAI2.INP Output: BAI2.OUT

Trong cuộc thi Tin học trẻ, mỗi thí sinh phải trả lời \(n\) câu hỏi.
Để tăng tính hấp dẫn của cuộc thi, ban tổ chức đưa ra \(n\) số điểm thưởng:

\[ a_1, a_2, \dots, a_n \]

Theo thể lệ của cuộc thi, nếu thí sinh trả lời đúng \(k\) câu hỏi \((1 \le k \le n)\) thì sẽ nhận được số điểm thưởng bằng giá trị lớn nhất trong các số:

\[ a_1, a_2, \dots, a_k \]

Yêu cầu

Xác định số điểm thưởng của thí sinh ứng với từng giá trị \(k\) từ \(1\) đến \(n\).

Input

  • Dữ liệu vào từ tệp BAI2.INP.
  • Dòng đầu chứa số nguyên dương \(n\) \((n \le 30000)\).
  • Dòng thứ hai chứa \(n\) số nguyên dương:
\[ a_1, a_2, \dots, a_n \]

Trong đó mỗi số không vượt quá \(10^3\).

Output

  • Ghi ra tệp BAI2.OUT gồm \(n\) số:
  • Số thứ \(i\) là điểm thưởng khi trả lời đúng \(i\) câu hỏi.

Example

Test 1

Input 
3
6 1 7
Output 
6 6 7

3. Tìm xâu

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: BAI3.INP Output: BAI3.OUT

ho xâu ký tự \(s\) độ dài \(n\) chỉ gồm các chữ cái tiếng Anh.

Từ xâu \(s\), thực hiện phép quay vòng các ký tự sẽ tạo ra một dãy gồm \(m\) xâu khác nhau \((m \le n)\).

Ví dụ với:

\[ s = \texttt{BCA} \]

ta nhận được các xâu:

BCA
CAB
ABC

Sau khi sắp xếp theo thứ tự từ điển:

ABC
BCA
CAB

xâu ban đầu \(s\) đứng ở vị trí thứ \(2\).

Yêu cầu

Cho biết:

  • Một xâu \(x\) thuộc dãy nhận được bằng phép quay vòng.
  • Vị trí \(k\) của xâu \(s\) trong danh sách đã sắp xếp.

Hãy xác định xâu ban đầu \(s\).

Input

  • Dữ liệu vào từ tệp BAI3.INP.
  • Dòng đầu chứa số nguyên dương \(k\).
  • Dòng thứ hai chứa xâu \(x\) độ dài \(n\).

Với:

\[ k \le n \le 100 \]

Output

  • Ghi ra tệp BAI3.OUT xâu \(s\) tìm được.
  • Nếu không xác định được thì ghi -1.

Example

Test 1

Input 
2
ABC
Output 
BCA

4. Di chuyển cây

Điểm: 4 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: BAI4.INP Output: BAI4.OUT

Thành phố \(ZXY\) có một vườn bách thảo được mô tả bằng một bảng hình chữ nhật gồm \(m\) dòng và \(n\) cột.

Trong vườn có \(k\) loại cây khác nhau, đánh số từ \(1\) đến \(k\).

Mỗi ô của bảng:

  • Chứa số nguyên dương \(i\) nếu có cây loại \(i\).
  • Chứa số \(0\) nếu ô trống.

Chính quyền muốn giữ lại những hàng cây có ít nhất \(t\) cây liên tiếp cùng loại nằm:

  • trên cùng một hàng,
  • hoặc trên cùng một cột.

Các cây không thuộc bất kỳ dãy hợp lệ nào sẽ bị di chuyển đi nơi khác.

Yêu cầu

Đếm số lượng cây cần phải di chuyển.

Input

  • Dữ liệu vào từ tệp BAI4.INP.
  • Dòng đầu chứa ba số nguyên dương:
\[ m, n, t \]

Với:

\[ 1 < m, n, t \le 100 \]
  • \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả khu vườn.

Output

  • Ghi ra tệp BAI4.OUT số lượng cây cần phải di chuyển.

Example

Test 1

Input 
5 6 3
1 3 3 3 3 4
1 2 3 2 0 4
3 2 2 2 4 4
1 0 0 2 4 0
1 2 3 0 4 4
Output 
10