Đề ACM

Bài A: Nghỉ trưa

Giới hạn thời gian mỗi test: 2 seconds

         Sau cuộc thi, các chú thỏ quyết định ăn trưa. Các chú thỏ có k đơn vị thời gian cho việc
ăn trưa.
         Các chú thỏ có 1 danh sách n nhà hàng để ăn trưa: nhà hàng thứ i được mô tả bằng 2 số
nguyên fi và ti. Trong đó ti là thời gian để các chú thỏ ăn trưa ở nhà hàng i. Nếu ti vượt
quá k thì thời gian ăn mừng là fi - (ti – k). Ngược lại, thời gian ăn mừng sẽ là fi.
Nhiệm vụ của bạn là tìm giá trị thời gian ăn mừng lớn nhất có thể. Các chú thỏ phải chọn
1 nhà hàng để ăn. Lưu ý, kết quả không cần thiết phải là số dương.

Input
Dòng đầu tiên là t - số test (1 <= t <= 25)
Trong mỗi test, dòng đầu là số n (1 <= n <= 10^4) và số k (1 <= k <= 10^9). Mỗi dòng trong số n dòng tiếp theo chứa 2 số nguyên fi và ti (1 <= fi <= 10^9, 1 <= ti <= 10^9).
Output
Với mỗi test, in ra 1 số nguyên duy nhất trên một dòng - thời gian ăn mừng lớn nhất có thể của chú thỏ.
Sample test(s)
Input
1
2 5
3 5
4 5
Output
4

Bài B: Trò chơi

Giới hạn thời gian mỗi test: 2 seconds

             Bạn tham gia 1 trò chơi với Alice và Bob. Đầu tiên Alice và Bob mỗi người viết 1 chuỗi 

chỉ chứa kí tự “0” và “1”. Gọi 2 chuỗi đó là a và b tương ứng. Sau đó bạn cố gắng biến 

đổi a thành b sử dụng 2 phép biến đổi sau:

•  Viết parity của a vào cuối a. Ví dụ 1010 → 10100
•  Bỏ kí tự đầu tiên của a. Ví dụ 1001 → 001. Bạn không thể thực hiện phép biến đổi này nếu a rỗng.

             Bạn có thể dùng không giới hạn số lượng phép biến đổi. Yêu cầu là có thể biến đổi a 

thành b không? Biết parity của chuỗi a là 1 nếu số lượng kí tự “1” trong chuỗi a là lẻ, 

ngược lại là 0.

Input

Dòng đầu tiên là số test (1 <= t <= 25).

Mỗi test có 2 dòng. Dòng đầu tiên chứa chuỗi không rỗng a và dòng tiếp theo chứa chuỗi b. Độ dài của 2 chuỗi này không quá 1000. Cả 2 chuỗi chỉ chứa kí tự "0" và "1".

Output

Xuất "YES" nếu kết quả là có thể biến đổi a thành b và "NO" nếu ngược lại.

Sample test(s)

Input

2

01011

0110

0011

1110

Output

YES

NO

Giải thích

Trong test đầu tiên, các bước biến đổi: 01011 -> 1011 -> 011 -> 0110

Bài E: Số 5

Giới hạn thời gian mỗi test: 2 second

             Có 1 chuỗi B có n chữ số. Nguyên muốn xóa m chữ số (0≤ m<n) để tạo thành 1 số ma 

thuật, là số chia hết cho 5. Lưu ý, kết quả có thể là số bắt đầu bằng số 0.

Nguyên muốn đếm số cách thực hiện điều đó và mod 1000000007.

2 cách thực hiện là khác nhau nếu tập các vị trí xóa là khác nhau.

Input

Dòng đầu tiên là t - số test (1 <= t <= 20).

Tiếp theo là t test. Mỗi test gồm: dòng đầy là chuỗi a không rỗng có độ dài không quá 100000, chỉ chứa chữ số, dòng tiếp theo là số nguyên dương k (1 <= k <= 10^9). Chuỗi b gồm k chuỗi a ghép lại.

Output

In ra kết quả, mỗi test 1 dòng.

Sample test(s)

Input

2

1256

1

13990

2

Output

4

528 

Giải thích

Trong test đầu tiên, có 4 cách tạo ra số ma thuật là: 5, 15, 25, 125.

Trong test tiếp theo, chuỗi b là: 1399013990.