Đề thi Tin học trẻ tỉnh Yên Bái năm 2023 – Bảng B (khối THCS)
Câu 1. Đua Robot
Có hai robot đang chuyển động thẳng đều, cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí s1 di chuyển với vận tốc là v1 m/s, robot thứ hai đang ở vị trí s2 di chuyển với vận tốc v2 m/s. Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?
Dữ liệu vào từ file văn bản BAI1.INP:
– Dòng đầu tiên gồm số nguyên dương s1 mô tả vị trí của robot thứ nhất;
– Dòng thứ hai gồm số nguyên dương v1 mô tả vận tốc của robot thứ nhất;
– Dòng thứ ba gồm số nguyên dương s2 mô tả vị trí của robot thứ hai;
– Dòng thứ tư gồm số nguyên dương v2 mô tả vận tốc của robot thứ hai;
Các đơn vị khoảng cách được tính bằng mét, thời gian được tính bằng giây và s1 ≠ s2; s1, s2, v1, v2 ≤ 109.
Kết quả ghi ra file BAI1.OUT:
In ra một số nguyên là phần nguyên của kết quả – thời gian mà hai robot gặp nhau. Nếu hai robot không thể gặp nhau thì in ra -1.
Ví dụ:
| BAI1.INP | BAI1.OUT |
| 2
5 7 3 |
2 |
Câu 2. Chuỗi ARN
Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hóa bằng một xâu s gồm các ký tự A,U,G,X. Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hóa bằng xâu x) cho trước.
Yêu cầu: Từ chuỗi ARN có thể cắt được tối đa bao nhiêu đoạn mạch x.
Dữ liệu vào từ file văn bản BAI2.INP
– Dòng đầu tiên gồm một xâu ký tự s mô tả chuỗi ARN.
– Dòng thứ hai gồm xâu ký tự x mô tả đoạn mạch cần cắt ra.
Các xâu chỉ gồm các ký tự A,U,G,X và độ dài các xâu không quá 103 ký tự.
Kết quả ghi ra file văn bản BAI2.OUT
Một số nguyên duy nhất là kết quả của bài toán.
Ví dụ:
| BAI2.INP | BAI2.OUT |
| AUAUGXXAUGXGX
AUGX |
2 |
| AAAA
AAA |
1 |
| AGAX
U |
0 |
Câu 3. Thử tài nhanh trí
Ở đất nước Ba Lan xinh đẹp có nàng công chúa tới tuổi kén chồng. Nhà vua muốn tìm ra một chàng rể thông minh kiệt xuất xứng với công chúa nên đã đề ra cuộc thi “Thử tài nhanh trí”. Nội dung của cuộc thi là chàng hoàng tử nào nhanh chóng đưa ra kết quả của nhà vua trong thời gian tối đa 1s sẽ được gặp mặt công chúa. Là một nhà lập trình tài ba, bạn hãy giúp các chàng hoàng tử nhé.
Cho số tự nhiên n (n ≥ 2), ta có thể phân tích n thành tích các thừa số nguyên tố với dạng n = p1^x1 * p2 ^x2 * … *pk^xk. Trong đó, p1 < p2 < …. < pk là các số nguyên tố và x1, x2, … xk > 0. Gọi s là tổng các số mũ x1 có giá trị lẻ.
Chú ý là s + p = x1 + x2 + … + xk.
Yêu cầu: Hãy đưa ra giá trị s và p
Dữ liệu: Cho file văn bản BAI3.INP gồm một số tự nhiên n (n ≥ 2).
Kết quả: Ghi ra file văn bản BAI3.OUT gồm 2 dòng:
– Dòng thứ nhất ghi giá trị của s
– Dòng thứ hai ghi giá trị của p
Ví dụ:
| BAI3.INP | BAI3.OUT |
| 20 | 2
1 |
| 420 | 2
3 |
| 3 | 0
1 |
| 4 | 2
0 |
Đáp án Câu 1. Đua Robot
Giả sử hai robot di chuyển thẳng đều cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí s1 và di chuyển với vận tốc là v1 m/s, robot thứ hai đang ở vị trí s2 và di chuyển với vận tốc v2 m/s. Ta cần tính thời gian sau bao lâu thì hai robot sẽ gặp nhau.
Gọi t là thời gian hai robot gặp nhau, khi đó ta có phương trình: s1 + v1 * t = s2 + v2 * t
Từ đó suy ra thời gian hai robot gặp nhau: t = (s2 – s1) / (v1 – v2)
Nếu vận tốc của robot thứ nhất lớn hơn hoặc bằng vận tốc của robot thứ hai (v1 ≥ v2), thì hai robot sẽ không bao giờ gặp nhau, do đó ta in ra -1. Nếu không, ta tính thời gian và in ra phần nguyên của kết quả.
Vì input có đơn vị là mét và giây, nên ta không cần chuyển đổi đơn vị.
Cài đặt Câu 1 bằng ngôn ngữ lập trình Python
with open('BAI1.INP', 'r') as f_in:
s1 = int(f_in.readline().strip())
v1 = int(f_in.readline().strip())
s2 = int(f_in.readline().strip())
v2 = int(f_in.readline().strip())
if v1 >= v2:
with open('BAI1.OUT', 'w') as f_out:
f_out.write('-1')
else:
t = (s2 - s1) / (v1 - v2)
with open('BAI1.OUT', 'w') as f_out:
f_out.write(str(int(t)))
Cài đặt Câu 1 bằng ngôn ngữ lập trình C++
#include <iostream>
#include <fstream>
using namespace std;
int main() {
int s1, v1, s2, v2;
ifstream f_in("BAI1.INP");
f_in >> s1 >> v1 >> s2 >> v2;
f_in.close();
if (v1 >= v2) {
ofstream f_out("BAI1.OUT");
f_out << -1;
f_out.close();
} else {
double t = (s2 - s1) * 1.0 / (v1 - v2);
ofstream f_out("BAI1.OUT");
f_out << (int)t;
f_out.close();
}
return 0;
}
Cài đặt Câu 1 bằng ngôn ngữ lập trình Pascal
program BAI1;
var
s1, v1, s2, v2: integer;
f_in, f_out: text;
t: double;
begin
assign(f_in, 'BAI1.INP');
reset(f_in);
readln(f_in, s1);
readln(f_in, v1);
readln(f_in, s2);
readln(f_in, v2);
close(f_in);
if v1 >= v2 then
begin
assign(f_out, 'BAI1.OUT');
rewrite(f_out);
writeln(f_out, '-1');
close(f_out);
end
else
begin
t := (s2 - s1) * 1.0 / (v1 - v2);
assign(f_out, 'BAI1.OUT');
rewrite(f_out);
writeln(f_out, trunc(t));
close(f_out);
end;
end.
Đáp án Câu 2. Chuỗi ARN
Có nhiều thuật toán để giải bài toán này. Dưới đây là một danh sách các thuật toán:
Có nhiều thuật toán có thể giải bài toán trên, ví dụ:
- Thuật toán KMP (Knuth-Morris-Pratt): sử dụng để tìm kiếm các đoạn con trong chuỗi s, trong trường hợp này là tìm kiếm đoạn mạch x trong chuỗi ARN. Sau khi tìm được vị trí của đoạn mạch x trong chuỗi ARN, ta có thể tính toán số lượng các mạch x có thể cắt được.
- Thuật toán Rabin-Karp: tương tự như KMP, sử dụng để tìm kiếm các đoạn con trong chuỗi s. Thuật toán này sử dụng hàm băm để tìm kiếm, cho phép tìm kiếm nhanh hơn trong trường hợp các đoạn con có độ dài lớn.
- Thuật toán Boyer-Moore: cũng là thuật toán tìm kiếm đoạn con trong chuỗi s, nhưng có thể hiệu quả hơn KMP và Rabin-Karp trong một số trường hợp.
- Thuật toán quy hoạch động: sử dụng để tìm kiếm và đếm số lượng các đoạn con trong chuỗi s. Thuật toán này có thể sử dụng để giải quyết bài toán trên nếu ta xem đoạn mạch x là một chuỗi con của chuỗi ARN, và tính toán số lượng các chuỗi con của chuỗi ARN chứa đoạn mạch x.
Trong nội dung đáp án. Ở đây chúng ta lựa chọn thuật toán quy hoạch động.
Để giải quyết bài toán trên bằng thuật toán quy hoạch động, ta có thể sử dụng một ma trận độ dài đường chéo chính để lưu trữ thông tin về độ dài của các chuỗi con của chuỗi ARN chứa đoạn mạch x.
Cụ thể, ta sử dụng ma trận dp với kích thước (m+1) x (n+1), trong đó m là độ dài của chuỗi x, n là độ dài của chuỗi s. Giá trị dp[i][j] sẽ lưu trữ độ dài của chuỗi con của chuỗi s từ vị trí j trở về sau mà chứa chuỗi con x[i:] (tức là từ i đến hết chuỗi x). Ban đầu, ta khởi tạo dp[i][j] = 0 cho tất cả các giá trị i, j.
Sau đó, ta duyệt qua các vị trí j từ n đến 0 và các vị trí i từ m đến 0 (tức là duyệt từ cuối chuỗi s và x về đầu chuỗi). Nếu s[j] == x[i], ta có thể tạo được chuỗi con mới bằng cách thêm ký tự s[j] vào cuối chuỗi con đã có trước đó. Do đó, ta có dp[i][j] = dp[i+1][j+1] + 1. Ngược lại, nếu s[j] != x[i], ta không thể tạo được chuỗi con mới, vì vậy dp[i][j] sẽ bằng 0.
Sau khi duyệt qua toàn bộ ma trận dp, ta có thể tính toán số lượng các mạch x có thể cắt được bằng cách đếm số lượng các giá trị dp[i][j] bằng độ dài của chuỗi x.
Cài đặt Câu 2 bằng ngôn ngữ lập trình Python
# Đọc dữ liệu từ file input
with open('BAI2.INP', 'r') as f:
s = f.readline().strip() # đọc xâu s
x = f.readline().strip() # đọc xâu x
# Tính độ dài của các xâu
n = len(s)
m = len(x)
# Khởi tạo bảng phương án
dp = [[0] * (m+1) for _ in range(n+1)]
# Tính toán bảng phương án bằng thuật toán quy hoạch động
for i in range(1, n+1):
for j in range(1, m+1):
if s[i-1] == x[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Ghi kết quả vào file output
with open('BAI2.OUT', 'w') as f:
f.write(str(dp[n][m]))
Cài đặt Câu 2 bằng ngôn ngữ lập trình C++
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
int main() {
// Mở file input và output
ifstream in("BAI2.INP");
ofstream out("BAI2.OUT");
// Đọc chuỗi ARN và đoạn mạch cần cắt ra
string s, x;
getline(in, s);
getline(in, x);
// Khởi tạo bảng phương án
int n = s.length(), m = x.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// Tính toán bảng phương án
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == x[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Ghi kết quả vào file output
out << dp[n][m];
// Đóng file input và output
in.close();
out.close();
return 0;
}
Cài đặt Câu 2 bằng ngôn ngữ lập trình Pascal
program Bai2;
const
maxn = 1005;
var
s, x: ansistring;
f: array[0..maxn, 0..maxn] of longint;
n, m, i, j, ans: longint;
fi, fo: text;
function max(a, b: longint): longint;
begin
if a > b then max := a
else max := b;
end;
begin
assign(fi, 'BAI2.INP');
assign(fo, 'BAI2.OUT');
reset(fi);
rewrite(fo);
readln(fi, s);
readln(fi, x);
n := length(s);
m := length(x);
for i := 1 to n do
for j := 1 to m do
if s[i] = x[j] then
f[i, j] := f[i-1, j-1] + 1
else
f[i, j] := max(f[i-1, j], f[i, j-1]);
ans := f[n, m];
writeln(fo, ans);
close(fi);
close(fo);
end.
Đáp án Câu 3. Thử tài nhanh trí
Đây là một bài toán phân tích số thành tích các thừa số nguyên tố và tính tổng các số mũ x1 có giá trị lẻ. Cuối cùng, ta cần tính giá trị của s và p dựa trên các thông số đã cho.
Để giải quyết bài toán này, ta có thể sử dụng thuật toán phân tích số thành tích các thừa số nguyên tố, sau đó tính toán giá trị của s và p bằng cách duyệt qua các thừa số nguyên tố và số mũ tương ứng của chúng.
Cài đặt Câu 3 bằng ngôn ngữ lập trình Python
# Đọc số tự nhiên n từ file văn bản BAI3.INP
with open("BAI3.INP", "r") as file_input:
n = int(file_input.readline())
# Khởi tạo biến s và p bằng 0
s = 0
p = 0
# Lặp lại quá trình phân tích số n thành tích các thừa số nguyên tố
while n != 1:
# Tìm thừa số nguyên tố đầu tiên của n
i = 2
while n % i != 0:
i += 1
# Cộng giá trị mũ của thừa số đó vào biến s hoặc p
j = 0
while n % i == 0:
n //= i
j += 1
if j % 2 == 1:
s += j
else:
p += j
# Ghi giá trị của biến s và biến p vào file văn bản BAI3.OUT
with open("BAI3.OUT", "w") as file_output:
file_output.write(str(s) + "\n")
file_output.write(str(p) + "\n")
Cài đặt Câu 3 bằng ngôn ngữ lập trình C++
#include <bits/stdc++.h>
using namespace std;
int main() {
// Đọc dữ liệu từ file BAI3.INP
ifstream cin("BAI3.INP");
int n;
cin >> n;
// Phân tích n thành tích các thừa số nguyên tố
int i = 2, cnt = 0;
while (n > 1) {
if (n % i == 0) {
n /= i;
cnt++;
} else {
i++;
if (cnt % 2 == 1) s += cnt;
cnt = 0;
}
}
if (cnt % 2 == 1) s += cnt;
// Tính giá trị của p
int p = 0;
for (int j = 2; j <= i; j++) {
if (i % j == 0) {
p = j;
break;
}
}
// Ghi kết quả ra file BAI3.OUT
ofstream cout("BAI3.OUT");
cout << s << endl;
cout << p << endl;
return 0;
}
Cài đặt Câu 3 bằng ngôn ngữ lập trình Pascal
program Bai3;
var
n, s, p, x, i, j: integer;
function isPrime(n: integer): boolean;
var
i: integer;
begin
if n < 2 then
isPrime := false
else if n = 2 then
isPrime := true
else
begin
isPrime := true;
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then
begin
isPrime := false;
break;
end;
end;
end;
begin
assign(input, 'BAI3.INP');
assign(output, 'BAI3.OUT');
reset(input);
rewrite(output);
readln(n);
s := 0;
p := 0;
i := 2;
while n > 1 do
begin
if isPrime(i) and (n mod i = 0) then
begin
x := 0;
while n mod i = 0 do
begin
n := n div i;
x := x + 1;
end;
if x mod 2 = 1 then
s := s + x;
p := p + x;
end;
i := i + 1;
end;
writeln(s);
writeln(p);
close(input);
close(output);
end.
