LQDOJ Contest #10 - Sinh Nhật LQDOJ (Bảng B)

Cho một xâu \(S\) chỉ gồm các kí tự chữ cái,chữ số và một khoảng trắng (không có kí tự đặc biệt nào khác).

Yêu Cầu: Tính theo xâu \(S\), cần ít nhất bao nhiêu chữ cái (có phân biệt in hoa và in thường) và khoảng trắng nữa để có thể chọn chúng và ghép thành bảng Chuc mung sinh nhat LQDOJ.

Input

• Chứa một xâu \(S\) duy nhất (Xâu \(S\) không quá \(50\) kí tự).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Example

Chuc mngsin nhat LQDOJ

3

chuc mung sinh nhat LQDOJ

1

Cho hai số nguyên dương \(L\) và \(R\). Bạn hãy đếm tất cả các số nguyên tố có trong đoạn \([L;R]\) mà có tổng các chữ số của chúng chia hết cho \(5\).

Input

• Chứa hai số nguyên dương lần lượt là \(L\) và \(R\) \((1 \le L \le R \le 3\times 10^6)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(R \le 5000\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(R \le 10^5\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

20 50

3

Vào thứ hai hàng tuần, trường THPT chuyên Lê Quý Đôn Đà Nẵng tổ chức lễ chào cờ, lớp của Flower_On_Stone Có \(N\) học sinh xếp thành một hàng dọc. Học sinh thứ \(i\) cao \(a_i\) cm.

Để một hàng dọc nhìn trở nên cân đối và đẹp hơn, Flower_On_Stone sẽ cho một vài học trò đứng lên các chiếc gạch sao cho người ở trước mặt mình sẽ không thấp hơn mình. Biết rằng mỗi chiếc gạch có chiều cao tùy ý Flower_On_Stone (chiều cao là một số nguyên và nó không âm).

Yêu cầu: Bạn hãy tính tổng chiếc gạch ít nhất có thể mà thỏa mãn điều kiện Flower_On_Stone đề ra.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \le N \le 10^6)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((1 \le a_i \le 10^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(N \le 5000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
2 1 4 3 5

2

Vào ngày sinh nhật của LQDOJ, shiba - một thành viên của Team Shiba quyết định tặng kẹo cho các bạn trẻ trong trường. Có \(N\) đứa trẻ muốn được nhận kẹo và shiba có một bịch kẹo gồm \(M\) vị khác nhau. Có một điều khiến shiba phải băn khoăn rằng tất cả đứa trẻ muốn tất cả viên kẹo mà mình có đều phải có cùng một vị. shiba cũng biết rằng các bạn trẻ sẽ ghen tị nếu có một bạn được quá nhiều kẹo. Để giải quyết các điều này một cách êm đềm nhất, shiba quyết định chia kẹo sao cho mức độ ghen tị sẽ là nhỏ nhất có thể, biết rằng mức độ ghen tị là số kẹo nhiều nhất mà một bạn trẻ có được.

Ví dụ bịch kẹo của shiba có \(7\) viên kẹo vị \(X\) và \(4\) viên kẹo vị \(Y\) thì mà cần chia cho \(5\) đứa trẻ thì shiba có thể chia như sau: \(XX\),\(XX\),\(YY\),\(YY\),\(YYY\). Mức độ ghen tị lúc này là \(3\), là mức độ ghen tị nhỏ nhất có thể.

Tuy nhiên thực hiện việc chia kẹo là quá khó với shiba. Anh ấy nhờ các bạn lập trình tài năng của LQDOJ giúp shiba tìm cách chia sao cho mức độ ghen tị là nhỏ nhất có thể.

Yêu cầu: Bạn hãy giúp shiba tính mức độ ghen tị nhỏ nhất có thể. Biết rằng trường hợp có đứa trẻ không nhận được một viên kẹo nào là có thể xảy ra.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N \le 10^9,1 \le M \le 3 \times 10^5, M \le N)\).
• \(M\) dòng tiếp theo mỗi dòng chứa một số nguyên dương là số kẹo của từng vị mà shiba có. Số kẹo của từng vị nằm trong đoạn \([1;10^9]\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 25\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
4
7

3

Nhà ông \(T\) có nuôi \(n\) con mèo, con mèo thứ \(i\) hiện tại đang ở vị trí \(x_i\), vì có dự báo sắp có bão đổ bộ, nên ông tìm cách đưa các con mèo vào \(1\) nơi an toàn. May mắn thay, nhà ông có \(m\) lồng cho mèo, lồng thứ \(i\) có sức chứa \(b_i\) con mèo và được đặt tại vị trí \(a_i\). Ông muốn nhốt các con mèo của mình vào các lồng sao cho số lượng mèo ở \(1\) lồng bất kì không vượt quá sức chứa của lồng đấy đồng thời tổng độ mệt mỏi của \(n\) con mèo là ít nhất. (Độ mệt mỏi của \(1\) con mèo khi di chuyển từ vị trí \(x\) sang \(y\) là \(|x - y|\)). Vì không giỏi tính toán, nên bạn hãy tính độ mệt mỏi nhỏ nhất giúp ông \(T\) nhé.
NOTE : Các con mèo khác nhau sẽ ở vị trí khác nhau, các lồng khác nhau sẽ ở vị trí khác nhau

Input

• Dòng đầu tiên ghi \(2\) số \(n\) và \(m\) \((1 \le n, m \le 5*10^3)\) lần lượt là số mèo và số lồng;
• Dòng tiếp theo gồm \(n\) số nguyên phân biệt mô tả mảng \(x\) \((1 \le x_i \le 10^9)\) là vị trí của từng con mèo.
• \(m\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên \(a_i\) và \(b_i\) lần lượt là vị trí và sức chứa của lồng thứ \(i\) (\(1 \le a_i \le 10^9\), \(0 \le b_i \le n\)).

Output

• Gồm \(1\) số nguyên tổng độ mệt mỏi bé nhất của \(n\) con mèo (Nếu không có cách chia thỏa mãn thì in ra \(-1\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm):\(0 \le b_i \le 1\) (với mọi \(i\) từ \(1\) đến \(m\)).
• Subtask \(2\) (\(70\%\) số điểm): Không có rằng buộc gì thêm.

3 5
1 4 7
3 1
5 1 
2 2
7 3
9 3

2

Nhân dịp sinh nhật LQDOJ, chủ tiệc Flower_On_Stone đã tổ chức trò chơi có tên là "Vàng Và Bạc". Trò chơi gồm \(N\) bịch, mỗi bịch gồm \(f_i\) cục bạc và \(g_i\) cục vàng, một ván sẽ có hai người chơi A và B. A và B sẽ thay phiên nhau thực hiện các thao tác, nếu một người chơi không thể thực hiện thao tác nào nữa thì người đó sẽ thua và ván đấu kết thúc. Mỗi thao tác bao gồm việc chọn một bịch \(i\) không rỗng và bỏ một số cục bạc và/hoặc cục vàng ra khỏi bịch đó. Theo luật, một người chơi có thể bỏ \(x\) cục bạc và \(y\) cục vàng trong một bịch, biết rằng bắt buộc phải bỏ ít nhất một cục bất kì \((0 \le x \le f_i, 0 \le y \le g_i)\). Tuy nhiên, mỗi cục bạc bị bỏ ra khỏi bịch thì bắt buộc phải bổ sung thêm ít nhất \(c\) cục vàng vô bịch (số cục vàng được bổ sung là bao nhiêu cũng được miễn là số đó lớn hơn hoặc bằng \(c\) với \(c\) là một số nguyên không âm cho trước). Vì vậy bất kì thao tác loại bỏ cục bạc nào (nghĩa là thao tác loại bỏ nào có \(x \ge 1\)) thì trước tiên \(y\) cục vàng sẽ bị bỏ ra và sau đó người chơi đang thực hiện thao tác sẽ phải bỏ lại \(z\) cục vàng vô lại (với \(z \ge c \times x\)). Biết rằng ban tổ chức có số lượng cục vàng là vô hạn.

Giả sử bạn tham gia trò chơi này với \(Q\) ván đấu, mỗi ván đấu bạn chơi với một đối thủ bất kì và bạn được đi trước, trước khi chơi thì bạn cần tính xem liệu bạn có thể thắng được trò chơi này hay không nếu bạn chơi một cách tối ưu nhất có thể.

Yêu cầu: Bạn hãy tính xem mỗi ván đấu liệu bạn có thể chiến thắng hay không.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(c\) và \(Q\) \((0 \le c \le 3000,1 \le Q \le 10)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(N\) \((1 \le N \le 10^4)\) là số bịch trong ván đấu đó và \(N\) dòng đó mỗi dòng sẽ chứa hai số nguyên lần lượt là \(f_i\) và \(g_i\) \((0 \le f_i \le 3000, 0 \le g_i \le 10^7)\). Biết rằng tất cả trận đấu đều sẽ tính theo hằng số \(c\).

Output

• In ra Yes nếu bạn có thể chiến thắng, nếu không thể thắng thì hãy in ra No.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(c = 0\) và \(f_i = 0\).
• Subtask \(2\) (\(10\%\) số điểm): Có \(c = 0\) và \(f_i \le 1\) và nếu \(f_i = 1\) thì \(g_i = 0\).
• Subtask \(3\) (\(10\%\) số điểm): Có \(c = 0\) và \(f_i \le 300\).
• Subtask \(4\) (\(10\%\) số điểm): Có \(c = 1\) và \(f_i \le 5\).
• Subtask \(5\) (\(10\%\) số điểm): Có \(c \le 20\) và \(f_i \le 20\).
• Subtask \(6\) (\(10\%\) số điểm): Có \(c \le 100\) và \(f_i \le 100\).
• Subtask \(7\) (\(20\%\) số điểm): Có \(c \le 300\) và \(f_i \le 300\).
• Subtask \(8\) (\(20\%\) số điểm): Không có ràng buộc gì thêm

Example

3 2
2
2 1
3 2
3
2 1
3 2
0 3

Yes
No