Bỏ qua để đến nội dung

Bảng B 2023 - Chung kết thành phố Hà Nội

HỘI THI TIN HỌC TRẺ THÀNH PHỐ HÀ NỘI Vòng chung kết – Năm 2023

ĐỀ THI THỰC HÀNH BẢNG B – KHỐI TRUNG HỌC CƠ SỞ Thời gian: 90 phút (không kể thời gian phát đề)


STTTên bàiĐiểm
1Chia hết100
2Đếm cặp100
3Số tuần hoàn100
4Dãy số đối xứng100

Cho hai số nguyên N và K.

Yêu cầu: Tìm số nguyên M nhỏ nhất sao cho N × M chia hết cho 10ᴷ.

Input: Gồm một dòng chứa hai số nguyên N, K (|N| ≤ 109, 0 ≤ K ≤ 18).

Output: In ra một số nguyên duy nhất là kết quả của bài toán.

Chấm điểm:

  • Subtask 1 (70% số điểm): K ≤ 6.
  • Subtask 2 (30% số điểm): không có ràng buộc gì thêm.

Ví dụ:

InputOutput
8 225

Cho dãy số nguyên A gồm N phần tử A1, A2, …, A_N và một số nguyên K.

Yêu cầu: Đếm số cặp số L, R (1 ≤ L ≤ R ≤ N) sao cho dãy con liên tiếp A_L, A_(L+1), …, A_R có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá K.

Input:

  • Dòng đầu tiên gồm hai số nguyên dương N, K (N ≤ 105, K ≤ 1018).
  • Dòng thứ hai gồm N số nguyên A1, A2, …, A_N (|Ai| ≤ 109).

Output: In ra một số nguyên duy nhất là kết quả của bài toán.

Chấm điểm:

  • Subtask 1 (50% số điểm): N ≤ 100.
  • Subtask 2 (20% số điểm): N ≤ 5000.
  • Subtask 3 (30% số điểm): không có ràng buộc gì thêm.

Ví dụ:

InputOutput
5 2
2 -1 3 1 3
8

Số T được gọi là số tuần hoàn chu kì I nếu tồn tại một số B có I chữ số và có thể xếp các số B cạnh nhau để thu được số T. Ví dụ:

  • 10101010 là số tuần hoàn chu kì 2 và cũng là số tuần hoàn chu kì 4, 8.
  • 2023 là số tuần hoàn chu kì 4.
  • 154154 là số tuần hoàn chu kì 3 và cũng là số tuần hoàn chu kì 6.

Yêu cầu: Tìm một số tuần hoàn chu kì N bất kì lớn hơn L và nhỏ hơn R.

Input: Gồm một dòng chứa ba số nguyên dương N, L, R (1 ≤ N ≤ 105, 1 ≤ L ≤ R ≤ 10^(107)).

Output: In ra một số nguyên là số tuần hoàn thoả mãn. Nếu không có kết quả thoả mãn, in ra −1.

Chấm điểm:

  • Subtask 1 (40% số điểm): R ≤ 105.
  • Subtask 2 (20% số điểm): R − L ≤ 105.
  • Subtask 3 (20% số điểm): R = 10^(107).
  • Subtask 4 (20% số điểm): không có ràng buộc gì thêm.

Ví dụ:

InputOutput
2 1234 98762222

Dãy số B gồm M phần tử B1, B2, …, B_(M−1), B_M được gọi là dãy số đối xứng độ dài M khi viết dãy số theo thứ tự ngược lại vẫn thu được dãy số B. Ví dụ hai dãy số (3, 2, 3), (4, −1, −1, 4) là dãy số đối xứng độ dài 3 và 4.

Cho dãy số A gồm N phần tử A1, A2, …, A_(N−1), A_N và một số nguyên dương K.

Yêu cầu: Tìm cách bỏ đi ít phần tử nhất của dãy số A để thu được dãy số đối xứng có độ dài không vượt quá K.

Input:

  • Dòng đầu tiên gồm hai số nguyên dương N, K (1 ≤ N ≤ 105, 1 ≤ K ≤ 100).
  • Dòng thứ hai gồm N số nguyên dương A1, A2, …, A_(N−1), A_N (1 ≤ Ai ≤ 105).

Output: In ra một số nguyên là độ dài của dãy số đối xứng thoả mãn đề bài.

Chấm điểm:

  • Subtask 1 (30% số điểm): N ≤ 20.
  • Subtask 2 (20% số điểm): N ≤ 103.
  • Subtask 3 (20% số điểm): Ai ≤ 10.
  • Subtask 4 (30% số điểm): không có ràng buộc gì thêm.

Ví dụ:

InputOutput
5 4
1 1 2 1 1
4