GIAO LƯU LẦN 9

Cho dãy gồm \(n\) phân số \(\frac{x_1}{y_1},\frac{x_2}{y_2},\frac {x_3}{y_3},...,\frac{x_n}{y_n}\)

Yêu cầu

Đếm xem có bao nhiêu phân số tối giản trong dãy

Dữ liệu vào

• Dòng đầu ghi số nguyên dương \(n\) (\(n \leq 10^5\))
• \(n\) dòng tiếp theo mỗi dòng ghi hai số nguyên dương \(𝑥_i\), \(y_i\) ghi cách nhau một dấu cách là tử số và mẫu số của phân số \((\frac{x_i}{y_i}); 1 \leq x_i, y_i \leq 10^9\).

Dữ liệu ra

• Ghi số lượng các phân số tối giản.

3
2 3
2 4
8 3

2

Tại bến xe Bus có \(n\) chiếc xe, chiếc xe thứ \(i\) (\(1 \leq i \leq n\)) mỗi ngày tiêu hao lượng nhiên liệu là \(a_i\) . Quản lí muốn chọn \(k\) chiếc xe xuất bến sao cho tổng lượng tiêu hao nhiên liệu là ít nhất.

Yêu cầu: Hãy giúp quản lí tính tổng giá trị tiêu hao nhiên liệu trong một ngày là ít nhất.

Dữ liệu vào:

• Dòng thứ nhất ghi hai số nguyên dương lần lượt là \(n\) và \(k\)
• Dòng thứ hai ghi 𝑛 số nguyên\(a_1, a_2, a_3, ..., a_n\). Các số viết cách nhau một dấu cách.

Kết quả:

• Ghi một số nguyên duy nhất là tổng giá trị tiêu hao nhiên liệu trong một ngày của \(k\) chiếc xe được chọn.

5 3
3 4 2 1 5

6

Ràng buộc

• \(1 < k < n \leq 3.10^5; 0 <a_i \leq 10^9\)

Em và nhóm bạn đang tham gia chương trình game show "Thử thách với các con số". Thử thách của nhóm như sau: Máy tính đưa ra một dãy số tự nhiên liên tiếp bắt đầu từ 1 và kết thúc tại \(N\) , tiếp theo máy tính sẽ bí mật xóa đi \(K\) số bất kì từ dãy đã cho (\(1 \leq K < N \leq 10^6\)) rồi hoán đổi ngẫu nhiên vị trí các số còn lại trong dãy. Sau khi thực hiện xong máy tính sẽ hiển thị các giá trị \(N\) và \(K\) và dãy số sau biến đổi rồi yêu cầu xác định các số mà máy tính đã xóa.

Yêu cầu:

Với dữ liệu đã cho, em hãy viết chương trình để tìm ra những số đã bị xóa.

Dữ liệu vào:

• Dòng 1: Ghi hai số \(N\) và \(K\), mỗi số cách nhau một khoảng trống.
• Dòng 2: Ghi (\(N-K\)) số của dãy số sau biến đổi, mỗi số cách nhau một khoảng trống.

Dữ liệu ra:

• Dòng 1: Ghi ra các số tìm được theo giá trị tăng dần, mỗi số cách nhau một khoảng trống.

 5 2
 3 1 4

2 5

Các chữ số từ 0 đến 9, nếu một chữ số bất kỳ có một đường khép kín thì ta gọi chữ số đó có 1 lỗ hổng, có hai đường khép kín thì ta gọi số đó có 2 lỗ hổng, và không có đường khép kín nào thì ta gọi chữ số đó có 0 lỗ hổng. Vậy các chữ số 0, 4, 6, 9 có 1 lỗ hổng, chữ số 8 có 2 lỗ hổng và các chữ số 1, 2, 3, 5, 7 có 0 lỗ hổng. Cho một số nguyên dương \(k\), \(1 ≤ k ≤ 10^6\), ta luôn đếm được số lỗ hổng của các chữ số xuất hiện trong nó.

Ví dụ: Với \(k=247883\) thì ta đếm được N có 5 lỗ hổng.

Yêu cầu:

Sắp xếp dãy số đã cho theo thứ tự không giảm số lổ hổng của số đó, nếu 2 số có cùng số lổ hổng thì số nhỏ hơn ưu tiên xếp trước.

Input:

• Dòng 1: Ghi số nguyên dương N (\(N \leq 10^5\))
• Dòng 2: Ghi \(N\) số nguyên \(a_1, a_2, a_3, ..., a_n\), \(0 \leq a_i \leq 10^6\), mỗi số cách nhau ít nhất 1 ký tự trắng.

Output:

• Dòng 1: Ghi số nguyên dương sau khi đã sắp xếp không giảm. Với \(b_i\) là số lỗ hổng của số nguyên dương \(a_i\).

 7
234  24689   34   12  123  234  4567

12 123 34 234 234 4567 24689