PRE THI HUYỆN #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 Thay đổi chữ số 100 (p) 1.0s 1G
2 Tổng ước chung lớn nhất 100 (p) 1.0s 1G
3 Xâu nhỏ nhất 100 (p) 1.0s 1G
4 Tín hiệu chuẩn 100 (p) 1.5s 1G

1. Thay đổi chữ số

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: replace.inp Output: replace.out

Trong tiết học môn Toán, cô đã giao cho Quốc \(N\) tấm thẻ, mỗi tấm thẻ ghi một chữ số. Nhiệm vụ mà cô giao cho Quốc chính là nhận biết các chữ số \(0\) và thay thành các chữ số \(5\). Tuy nhiên do kính chưa ship về nên Quốc không thể nhìn ra được các con số cũng như quá nhiều nên em hãy giúp Quốc nhé.

Dữ liệu vào

  • Nhập dữ liệu từ tệp văn bản REPLACE.INP
  • Dòng đầu tiên chứa số nguyên \(T\), là số lượng bộ test. \((T \leq 100000)\)
  • Với mỗi test case, có định dạng như sau:
  • Dòng thứ nhất là số nguyên dương \(N\) - là số lượng thẻ \((1 \leq N \leq 9)\)
  • Mỗi tấm thẻ ghi một chữ số từ \(0\) đến \(9\).

Dữ liệu ra

Ghi dữ liệu ra tệp văn bản REPLACE.OUT

  • Với mỗi test case, ghi ra \(N\) tấm bài đã xử lý trên một dòng.
Sample
Input 
3
4
2 0 0 7
8
1 9 1 2 2 0 0 7
5 
1 2 3 4 5
Output 
2 5 5 7
1 9 1 2 2 5 5 7
1 2 3 4 5

2. Tổng ước chung lớn nhất

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: SUMGCD.INP Output: SUMGCD.OUT

Cho dãy số nguyên dương có \(N\) phần tử \(a_1,a_2,...,a_n\). Tính tổng \(gcd(a_i,a_j)\) với tất cả \(i,j\) thỏa mãn \(1 \leq i < j \leq N\).
Định nghĩa : \(gcd(a,b)\) là số lớn nhất mà cả \(a\) và \(b\) đều chia hết cho nó.

Dữ liệu vào

Dữ liệu nhập từ tệp văn bản SUMGCD.INP

  • Dòng đầu tiên chứa duy nhất một số nguyên \(N\) - là số lượng số của dãy \(a\).
  • Dòng thứ hai chứa \(N\) số nguyên - là các phần tử của dãy \(a\).

Dữ liệu ra.

Dữ liệu in ra tệp văn bản SUMGCD.OUT
- Một dòng duy nhất là kết quả của bài toán

Ràng buộc

  • \(40\%\) số test có \(N \leq 100, a_i \leq 100\).
  • \(60\%\) số test có \(N \leq 10^3, a_i \leq 10^9\)
Sample
Input 
3 
2 4 6
Output 
6

3. Xâu nhỏ nhất

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: DELSTRING.INP Output: DELSTRING.OUT

Cho xâu ký tự \(st(1 \leq |st| \leq 100)\), và số nguyên dương \(K(0 \leq K < |st|)\). Hãy xóa \(K\) chữ số để các chữ số còn lại giữ nguyên thứ tự là số bé nhất.

Dữ liệu vào

Dữ liệu nhập từ tệp văn bản DELSTRING.INP

  • Dòng đầu tiên chứa duy nhất một xâu ký tự \(st\) - chỉ gồm các ký tự chữ số.
  • Dòng thứ hai chỉ chứa một số nguyên \(K\).

Dữ liệu ra

Dữ liệu in ra tệp văn bản DELSTRING.OUT

  • Xâu ký tự còn lại
Sample
Input 
869357495356872
9
Output 
335672

4. Tín hiệu chuẩn

Điểm: 100 (p) Thời gian: 1.5s Bộ nhớ: 1G Input: TINHIEUCHUAN.INP Output: TINHIEUCHUAN.OUT

Trạm thu tín hiệu từ vệ tinh nhận được dãy tín hiệu gồm \(n\) bit, các bit được đánh số từ \(1\) đến \(n\). Một đoạn tín hiệu gồm các bit liên tiếp nhau được gọi là tín hiệu chuẩn nếu số lượng bit \(1\) bằng số lượng bit \(0\). Hai đoạn tín hiệu được gọi là khác nhau nếu tồn tại một vị trí có thứ tự khác nhau trong dãy tín hiệu ban đầu.
Hãy viết chương trình cho biết có bao nhiêu đoạn tín hiệu chuẩn.

Dữ liệu vào

Dữ liệu nhập từ tệp văn bản TINHIEUCHUAN.INP

  • Dòng đầu tiên ghi số nguyên dương \(n ( n \leq 10^6 )\)
  • Dòng thứ hai ghi \(n\) bit, các bit cách nhau một khoảng trắng.

Dữ liệu ra

Dữ liệu in ra tệp văn bản TINHIEUCHUAN.OUT

  • Dòng đầu tiên ghi kết quả tìm được.

Chấm điểm

  • \(50\%\) số điểm có \(n \leq 100\)
  • \(30\%\) số điểm có \(n \leq 10^4\)
  • \(20\%\) số điểm còn lại có \(n \leq 10^6\)
Ví dụ 1
Input 
6 
1 0 1 0 1 1
Output 
6