GIAO LƯU LẦN 4

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Ray 1 5 (p) 1.0s 1G
2 Ray 2 6 (p) 1.0s 1G
3 Ray 3 9 (p) 1.0s 1G
4 Ray 4 10 (p) 1.0s 1G

1. Ray 1

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Mọi thông tin đều được mã hoá dưới dạng một chuỗi số nhị phân. Để nâng cao độ tin cậy khi truyền tin, mỗi bít được biểu diễn lặp lại 3 lần. Ví dụ, các bít tin ‘011’ được biểu diễn thành ‘000111111’ để thực hiện truyền. Do nhiễu của môi trường nên khi về đến đích, các bít tin có thể bị sai lệch. Vì vậy, khi nhận được thông tin cứ mỗi đoạn 3 bít được giải mã thành một bít. Bít này có giá trị 0 nếu trong nhóm 3 bít xuất hiện ít nhất 2 bít 0, bít này có giá trị 1 nếu trong nhóm 3 bít xuất hiện ít nhất 2 bít 1. Ví dụ, nếu các bít tin nhận được là ‘000110010011’, sau khi đã giải mã ta thu được ‘0101’. Cho chuỗi nhị phân biểu diễn thông tin nhận được, hãy giải mã chuỗi nhị phân đó.

Dữ liệu vào

  • Dòng đầu tiên ghi chuỗi nhị phân cần giải mã, là một dãy các số 0, 1 ghi liền nhau,độ dài không quá 255 kí tự.

Dữ liệu ra

  • Dòng đầu tiên ghi chuỗi nhị phân đã được giải mã, là một dãy các số 0, 1 ghi liền
    nhau.
Ví dụ 1
Input 
001111010110111000
Output 
010110

2. Ray 2

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Không khí thân thiết và cảm động luôn bao trùm lên các cuộc gặp gỡ của những người bạn học cũ. Đã lâu lắm các bạn của Ray mới tổ chức được một cuộc họp mặt như vậy. Phần nghi lễ chính thức được tổ chức trong phòng hội hảo của một khách sạn. Phòng hội thảo có \(N\) hàng ghế, mỗi hàng có \(M\) ghế. Mỗi người, khi tới ngồi vào một ghế nào đó đều bắt tay với những người xung quanh nếu có. Do điều kiện thời tiết, chuyến bay bị chậm giờ, vì vậy Ray là người đến muộn nhất. Đứng ngoài sảnh nhìn vào Ray tìm ghế trống. Nếu còn ghế trống Ray sẽ tới ghế có thể bắt tay được nhiều người nhất. Nếu không còn ghế nào trống thì Ray phải ngồi tạm ở ghế ngoài sảnh và dĩ nhiên, không có dịp bắt tay một ai trước khi phần nghi lễ kết thúc. Hãy xác định bao nhiêu cái bắt tay thân thiết đã được thực hiện khi Ray ngồi vào ghế của mình(ví dụ nếu Ray ngồi ở (2,2)thì Ray có thể bắt tay với các bạn ngồi ở(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)).

Dữ liệu vào

  • Dòng đầu tiên ghi số nguyên dương \(N\) và \(M\) (\(n,m<=1000\)).
  • N dòng tiếp theo chứa xâu độ dài \(M\) chỉ chứa các ký tự thuộc tập {., o},trong đó ‘.’ chỉ ghế trống, ‘o’ – ghế có người ngồi.

Dữ liệu ra

  • Đưa ra một số nguyên – số lượt bắt tay đã được thực hiện.
Ví dụ 1
Input 
2 3
..o
o..
Output 
2

3. Ray 3

Điểm: 9 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho dãy số nguyên dương \(a_1\)..\(a_n\). Hãy đếm xem trong dãy số đã cho có bao nhiêu cặp \((u,v) (1<=u<v<=n)\) thoả mãn:

  • \(a_u\) là số chẵn

  • \(a_v\) là số lẻ.

  • \(a_u+a_v=k\).

Dữ liệu vào

  • Dòng đầu tiên ghi số nguyên dương \(n<=100000\),\(k<=2000000\)
  • Dòng thứ hai ghi \(n\) số nguyên dương \(a_i<=1000000\).

Dữ liệu ra

  • Dòng đầu tiên ghi kết quả tìm được.
Ví dụ 1
Input 
9 13
11 7 1 5 3 2 4 6 9
Output 
1
Giải thích 
Là các cặp số (7, 9)

4. Ray 4

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho dãy số nguyên dương \(a_1\)..\(a_n\) và một số \(k\) (k \(\leq\) n). Với mỗi giá trị i(1\(\leq\) i \(\leq\) \(n-k+1\)). Hãy xác định giá trị nhỏ nhất của đoạn bất kỳ trong dãy a gồm k phần tử liên tiếp.

Dữ liệu vào

  • Dòng đầu tiên ghi số nguyên dương \(n\) \(\leq\) \(100000\)
  • Dòng thứ hai ghi \(n\) số nguyên dương \(a_i\) \(\leq\) \(100\).

Dữ liệu ra

  • Gồm n-k+1 dòng: dòng thứ i ghi giá trị nhỏ nhất trong các phần tử thuộc đoạn: \(a_i, a_{i+1}, ...,a_{i+k-1}\).

Chấm điểm

  • \(80\%\) số điểm có \(n \leq 10000\)
  • \(20\%\) không có giới hạn gì thêm.
Ví dụ 1
Input 
5 3
2 1 5 3 4
Output 
1
1
3
Giải thích 
Đoạn số 2 1 3 cho giá trị 1 là nhỏ nhất khi i = 1
Đoạn số 1 5 4 cho giá trị 1 là nhỏ nhất khi i = 2
Đoạn số 5 3 4 cho giá trị 3 là nhỏ nhất khi i = 3