De2

Số đặc biệt là số nguyên dương có đúng 3 ước số.

Ví dụ: 4 là số đặc biệt vì có 3 ước là 1, 2 và 4.

Yêu cầu: Cho 2 số nguyên dương a và b, hãy đếm số lượng số đặc biệt trong đoạn $[a,b]$.

Dữ liệu: Vào từ file văn bản BAI1.INP chứa hai số nguyên dương $a,b\left(1\le a\le b\le {10}^9\right).$

Kết quả: Ghi ra file văn bản BAI1.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

BAI1.INP	BAI1.OUT	Giải thích
5 30	2	Đoạn $\left[\mathrm{5,30}\right]$ có 2 số 9 và 25 là số đặc biệt

Chú ý: $70\%$ điểm có $1\le a\le b\le {10}^3.$

Cho dãy số nguyên gồm $n$ phần tử, đoạn con của dãy đã cho là đoạn gồm các phần tử liên tiếp của dãy đó. Độ hoàn hảo của đoạn con là trung bình cộng các phần tử của đoạn con đó. Hãy tìm đoạn con có độ hoàn hảo lớn nhất và tổng các phần tử lớn hơn hoặc bằng $k$ cho trước.

Dữ liệu: Vào từ file văn bản BAI2.INP:

• Dòng đầu tiên chứa 2 số nguyên $n,k(1\le n\le {10}^5;\left|k\right|\le {10}^{10})$;
• Dòng thứ 2 chứa $n$ số nguyên $a_1,a_2,..,a_n\left(\left|a_i\right|\le {10}^9,1\le i\le n\right).$

Kết quả: Ghi ra file văn bản BAI2.OUT một số nguyên duy nhất là phần nguyên của độ hoàn hảo lớn nhất tìm được, nếu không tìm được kết quả ghi NO.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
5 6 1 5 4 2 3	4	Đoạn con $[5,4]$ có tổng các phần tử $\ge 6$ và độ hoàn hảo lớn nhất bằng $4.5$ Kết quả ghi ra phần nguyên của $4.5$ là 4.
BAI2.INP	BAI2.OUT	Giải thích
3 6 1 -5 2	NO	Không có đoạn con nào có tổng lớn hơn hoặc bằng 6.

Chú ý:

• $30\%$số điểm có $1\le n\le {10}^2$;
• $40\%$số điểm có ${10}^2<n\le {10}^3$.

Công ty HP có hai tổ hoàn thiện sản phẩm, tổ 1 có $m$ công nhân, tổ 2 có $n$ công nhân. Giám đốc yêu cầu 2 tổ phải hoàn thiện $m+n$ sản phẩm sao cho:

• Mỗi công nhân phải hoàn thiện 1 sản phẩm;
• Sản phẩm $i(1\le i\le m+n)$ nếu giao cho tổ 1 hoàn thiện mất $a_i$ giây, nếu giao cho tổ 2 hoàn thiện thì mất $b_i$ giây.
• Một số sản phẩm chỉ có thể giao cho tổ 1 hoàn thiện, ngược lại một số sản phẩm chỉ có thể giao cho tổ 2 hoàn thiện.

Bạn hãy giúp giám đốc công ty giao việc cho các công nhân 2 tổ sao cho tổng thời gian hoàn thiện $m+n$ sản phẩm của các công nhân là nhỏ nhất.

Dữ liệu: Vào từ file văn bản BAI3.INP:

• Dòng đầu tiên ghi 2 số nguyên dương m, n ($1\le m,n\le {10}^5$)
• $m+n$dòng tiếp theo, dòng thứ $i\left(1\le i\le m+n\right)$ là 3 số $a_i,b_i,c_i\left(1\le a_i,b_i\le {10}^6\right):$
  • $c_i=0$: sản phẩm $i$ có thể hoàn thiện bởi công nhân của cả 2 tổ;
  • $c_i=1$: sản phẩm $i$ chỉ được hoàn thiện bởi công nhân tổ 1;
  • $c_i=2$: sản phẩm $i$ chỉ được hoàn thiện bởi công nhân tổ 2.

Kết quả: Ghi ra file văn bản BAI3.OUT một số nguyên duy nhất là tổng thời gian ít nhất để hoàn thiện $m+n$sản phẩm. Dữ liệu vào đảm bảo luôn hoàn thiện $m+n$ sản phẩm.

Ví dụ:

BAI3.INP	BAI3.OUT	GIẢI THÍCH
1 1 9 8 0 7 8 0	15	Tổ 1 hoàn thiện sản phẩm 2 hết 7 giây Tổ 2 hoàn thiện sản phẩm 1 hết 8 giây Tổng thời gian hoàn thiện 2 sản phẩm là $7+8=15$ giây
BAI3.INP	BAI3.OUT	GIẢI THÍCH
2 3 5 2 0 8 5 1 1 6 2 1 5 0 2 9 0	23	Tổ 1 hoàn thiện sản phẩm 2 và 5 hết $8+2=10$ giây Tổ 2 hoàn thiện sản phẩm 1, 3 và 4 hết $2+6+5=13$ giây Tổng thời gian hoàn thiện 5 sản phẩm là $10+13=23$ giây

Chú ý:

• $15\%$số điểm có$m=1,n=1;$
• $15\%$ số điểm có $c_i\ne 0\left(\forall i:1\le i\le m+n\right);$
• $40\%$ số điểm có $1<m,n\le 10.$

Cho một ma trận kích thước $n\times n$, ô giao dòng $i$ và cột $j$ được gọi là ô $\left(i,j\right).$ Một robot đang ở ô $(u,v)$ muốn di chuyển về ô góc dưới phải $(n,n)$ của ma trận.

Yêu cầu: Hãy trả lời $q$ truy vấn, mỗi truy vấn cho biết số cách di chuyển của robot về ô $\left(n,n\right)$ biết rằng robot chỉ đi được xuống dưới hoặc sang phải. Vì số cách đi là rất lớn nên kết quả được lấy dư cho 10⁹+7.

Dữ liệu:Vào từ tệp văn bản BAI4.INP:

• Dòng đầu chứa 2 số nguyên $n$ $(2\le n\le {10}^3)$ và $q(1\le q\le {10}^3)$trong đó $\mathrm{q}\mathrm{}$là số truy vấn;
• q dòng tiếp theo, dòng thứ $i(1\le i\le q)$ chứa 2 số $u,v(1\le u,v\le n)$là vị trí của robot (dòng $u$, cột $v$) ở truy vấn $i$.

Kết quả: Ghi ra file văn bản BAI4.OUT trên $q$ dòng, dòng thứ $i(1\le i\le q)$ là kết quả của truy vấn $i$.

Ví dụ

BAI4.INP	BAI4.OUT	Giải thích
5 3 4 4 4 2 5 5	2 4 1	Hình trên mô tả 2 cách di chuyển của robot từ ô $\left(\mathrm{4,4}\right)$ về ô $\left(\mathrm{5,5}\right)$

Chú ý:

• $10\%$ số điểm có $n=2;$
• $20\%$ số điểm có $n=3$;
• $20\%$ số điểm có $q=1;$
• $20\%$ số điểm có $2\le n,q\le {10}^2.$

--------- Hết ---------

(Thí sinh không sử dụng tài liệu, cán bộ coi thi không cần giải thích gì thêm)

Họ tên thí sinh..............................................................Số báo danh.................................................

Cán bộ coi thi số 1...............................................Cán bộ coi thi số 2................................................