sẽ kể các bạn nghe về hành trình vượt bao gian khó để đoạt được vũ khí tối thượng. Có tất cả 6 vũ khí, tương ứng với mỗi ải mà sẽ phải vượt qua.
Ải đầu tiên được trấn giữ bởi xạ thủ dê non . Ami sẽ phải chiến thằng trong ván cờ vua với dê non để đoạt được vũ khí là sừng dê siêu nhọn.
Dê non đã bố trí \(k\) con xe trên 1 bàn cờ \(m \times n\) (\(m\) hàng, \(n\) cột). sẽ phải đặt một con vua lên bàn cờ sao cho vua không bị chiếu. , với bản năng sát thủ của mình đã ngay lập tức chiến thắng thử thách này. Bây giờ, muốn hỏi các bạn, có bao nhiêu cách đặt con vua như vậy ?
Dòng đầu tiên chứa 3 số nguyên dương \(m, n, k \ (k \leq \min(mn, 10^5))\) lần lượt là kích cỡ bàn cờ và số con xe của
\(k\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(x, y \ (1 \leq x \leq m; 1 \leq y \leq n)\), tọa độ của một con xe.
\(k\) con xe nằm ở \(k\) vị trí khác nhau.
Subtask \(1\) (\(10\%\) số điểm): \(m, n \leq 20\)
Subtask \(2\) (\(10\%\) số điểm): \(m, n \leq 100\)
Subtask \(3\) (\(20\%\) số điểm): \(m, n \leq 1000\)
Subtask \(4\) (\(30\%\) số điểm): \(m, n \leq 100000\)
Subtask \(5\) (\(30\%\) số điểm): \(m, n \leq 10^9\)
Test 1
2 3 2
1 1
1 31Chỉ có 1 vị trí đặt vua là \((2, 2)\).
phải đối mặt với tiền đạo sứa xanh justys, sau khi đã đả bại một cách chóng vánh. sẽ đánh cờ tướng với sứa xanh justys để dành lấy vũ khí kim tiêm siêu dài.
Tuy đánh cờ tướng nhưng justys lại sử dụng bàn cờ vua \(n \times n\) và các quân cờ vua 🙂 . Sứa xanh justys quăng cho \(k\) quân tốt và \(1\) quân hậu. Một con tốt gọi là bị nhiễm độc nếu nó ở chung một hàng, hoặc một cột, hoặc một đường chéo với quân hậu.
cần đặt hết \(k\) quân tốt và \(1\) quân hậu lên bàn cờ, sao cho không có 2 quân bất kì ở chung một ô và tất cả mọi quân tốt đều bị nhiễm độc.
Với kĩ năng thượng thừa của mình, quá dễ dàng để vượt qua của ải này. Bây giờ, không cần các bạn phải đưa ra một phương án thích hợp, các bạn chỉ cần xác định xem có tồn tại một cách đặt các quân cờ để mọi con tốt đều bị nhiễm độc hay không.
Dòng đầu tiên chứa 1 số nguyên dương \(q\) là số lượng câu hỏi.
\(q\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(n, k\) là kích cỡ bàn cờ và số lượng con tốt.
Subtask \(1\) (\(10\%\) số điểm): \(q = 1\); \(n \leq 5, k \leq 50\)
Subtask \(2\) (\(20\%\) số điểm): \(q = 10^2\); \(n \leq 100, k \leq 1000\)
Subtask \(3\) (\(20\%\) số điểm): \(q = 10^2\); \(n \leq 10^5, k \leq 10^6\)
Subtask \(4\) (\(50\%\) số điểm): \(q = 10^5\); \(n \leq 10^9, k \leq 10^{10}\)
Test 1
3
2 2
2 1
3 1000000000YES
YES
NOVới trường hợp 2 1 và 2 2 ta có thể đặt các quân cờ ở bất kỳ vị trí nào.
Với trường hợp 3 1000000000 không thể đặt \(10^9\) quân cờ vào bàn cờ \(3 \times 3\)
Sau khi đả bại sứa xanh justys, hiện đang đối mặt với vua mật mã . cho tên người yêu cũ thứ 96 của mình, và muốn tìm một xâu kí tự có thứ tự từ điển nhỏ nhất và không nhỏ hơn tên người yêu cũ của . Tuy nhiên, vì căm ghét người yêu cũ, muốn chỉ sử dụng không quá \(cnt_{c}\) kí tự \(c\). Đương nhiên đã đưa ra câu trả lời trong 6ms. Các bạn hãy thử sức giải câu đố của vua mật mã nhé.
Dòng đầu tiên chứa 1 số nguyên dương \(n \ (n \leq 10^{3})\) là độ dài tên người yêu cũ của vua mật mã.
Dòng tiếp theo một xâu kí tự \(S\) là tên người yêu cũ của , tên chỉ chứa các kí tự la tinh thường.
Dòng tiếp theo chứa 26 số \(cnt_{c_{i}}\), \(c_{i}\) là kí tự la tinh thường thứ \(i\), \(cnt_{c}\) là số kí tự \(c\) tối đa mà được phép sử dụng.
Subtask \(1\) (\(10\%\) số điểm): \(n \leq 20\), \(cnt_{c_{i}} \leq 10^{5}\)
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 1000\), \(\Sigma cnt_{c_{i}} \leq 10\)
Subtask \(3\) (\(20\%\) số điểm): \(n \leq 1000\), \(cnt_{c_{i}} \leq 10^9\) và vua mật mã chỉ cho phép sử dụng tối đa 2 kí tự.
Subtask \(4\) (\(50\%\) số điểm): \(n \leq 10^{3}\), \(cnt_{c_{i}} \leq 10^{9}\)
Test 1
2
aa
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1abỞ ví dụ 1, mỗi kí tự chỉ được dùng 1 lần, riêng kí tự \(u\) được dùng 2 lần. Một số xâu thoả mãn là \(amisuper\), \(amibest\) , \(amiop\) , \(cuomngu\) , \(cuomnguthe\) , \(cuomgathiesu\), \(ab\). Xâu \(ab\) có thứ tự từ điển nhỏ nhất và lớn hơn xâu \(aa\).
Test 2
10
amideptrai
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1azỞ ví dụ 2, kí tự a được dùng 1 lần, kí tự z được dùng 1 lần. Các xâu thoả mãn là \(a\) , \(az\) , \(z\) , \(za\). Xâu \(az\) có thứ tự từ điển nhỏ nhất và lớn hơn xâu \(amideptrai\). Lưu ý rằng \(a\) có thứ tự từ điểm nhỏ hơn \(amideptrai\) nên không hợp lệ.
Test 3
10
amideptrai
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-1Ở ví dụ 3, kí tự a được dùng 1 lần, do đó chỉ có 1 xâu thoả mãn là \(a\). Xâu này có thứ tự từ điển nhỏ hơn \(amideptrai\), do đó không hợp lệ
Ải thứ 4 do kình ngư bò mộng thủ thành. cần chiến thắng trong cuộc thi tính toán với bò mộng để dành được vũ khí lông bò siêu bén.
Bò đã chuẩn bị sẵn 2 số tự nhiên \(l, r \ (0 \leq r - l \leq 10^6)\), chỉ việc tính \(LCM(l, l + 1, ..., r)\) trong 15 ms là giành chiền thắng, vì bò mộng cần tới tận \(15.69\) ms mới hoàn thành. Tính thôi chưa đủ độ khó với , còn muốn lấy kể quả này chia dư \(10^9+7\). Đương nhiên với trí tuệ siêu phàm, chỉ mất \(1.69\) ms để hoàn thành thử thách. Các bạn có nhanh tay như vậy không ?
Subtask \(1\) (\(10\%\) số điểm): \(l \leq r \leq 20\).
Subtask \(2\) (\(20\%\) số điểm): \(l \leq r \leq 10^5\).
Subtask \(3\) (\(20\%\) số điểm): \(l \leq r \leq 10^6\).
Subtask \(4\) (\(20\%\) số điểm): \(l \leq r \leq 10^7\).
Subtask \(5\) (\(30\%\) số điểm): \(l \leq r \leq 10^{14}\).
Test 1
3 560Test 2
1 102520càng ngày càng gần với việc thu thâp 6 vũ khí, và kẻ thù cũng ngày càng mạnh hơn. sẽ phải đối mặt với ma sa xét . Để dàng chiến thắng, cần vượt qua mê cung tử thần và dành lấy vũ khí áo choàng chống lửa.
Mê cung tử thần có \(n\) căn phòng và \(m\) cổng không gian. Để các bạn dễ hình dung, các căn phòng được đánh số từ \(1\) đến \(n\), các cổng không gian được đánh số từ \(1\) đến \(m\). Mỗi cây cầu không gian nối \(2\) phòng khác nhau theo một chiều, và có một con số ám ảnh là \(w_{i}\).
Tuy nhiên, chỉ việc vượt qua mê cung vẫn là chưa đủ. cần vượt qua mê cung với độ ám ảnh ít nhất. sẽ bắt đầu ở căn phòng \(a\) và đích đến là căn phòng \(b\). chỉ có thể di chuyển giữa \(2\) phòng nếu giữa chúng tồn tại một cồng không gian. Nếu dùng các cổng không gian \(w_{1}, w_{2}, w_{3}, \ldots, w_{k}\) thì độ ám ảnh sẽ là \(w_{1}\) OR \(w_{2}\) OR \(\ldots\) OR \(w_{k}\). có phép dịch chuyển, nên cậu đã đến cồng \(b\) một cách nhanh chóng. đố các bạn rằng đã đến đó với độ ám ảnh bao nhiêu?
Test 1
3 4 1 3
1 2 1
1 2 4
2 3 2
1 3 53Trong test ví dụ 1, ami đi theo con đường thứ \(1\) rồi qua con đường thứ \(3\). Giá trị cuối cùng là \(1\) OR \(2 = 3\).
Test 2
3 4 3 1
1 2 1
1 2 4
2 3 2
1 3 5-1Trong test ví dụ 2, không có con đường nào từ \(3\) đến \(1\) vì các con đường là đường \(1\) chiều.
Cho một bàn cờ \(m \times n\) và 1 con hậu trên bàn cờ. LN tưởng tượng mình là con hậu và muốn đặt \(k\) con vua lên bàn cờ. LN muốn \(k\) con vua ở các vị trí khác nhau và con hậu ngắm nhìn được nhiều con vua nhất. Một con vua nằm trong tầm ngắm của con hậu nếu nó 2 quân nằm trên cùng 1 hàng, cột hoặc đường chéo, đồng thời giữa chúng không có con vua nào cản đường. LN tự hỏi con hậu có thể ngắm được nhiều nhất bao nhiêu con vua. cảm thấy bài toán quá đơn giản nên thêm vào: Có bao nhiêu cách xếp để con hậu ngắm được nhiều con vua nhất?
Hai cách xếp được gọi là khác nhau nếu có một ô cờ mà trong cách xếp này có vua, và trong cách kia không có vua.
Dòng đầu tiên chứa 3 số nguyên dương \(m, n, k \ (1 \leq m, n \leq 1000; 1 \leq k < mn)\)
Dòng thứ hai chứa 2 số nguyên dương \(x, y \ (1 \leq x \leq m, 1 \leq y \leq n)\) - vị trí của con hậu
Subtask \(1\) (\(10\%\) số điểm): \(m = 1\)
Subtask \(2\) (\(10\%\) số điểm): \(m, n \leq 4\)
Subtask \(3\) (\(10\%\) số điểm): \(m, n \leq 20; k \leq 3\)
Subtask \(4\) (\(10\%\) số điểm): \(m, n \leq 20\)
Subtask \(5\) (\(10\%\) số điểm): \(m, n \leq 100\)
Subtask \(6\) (\(50\%\) số điểm): \(m, n \leq 1000\)
Test 1
2 2 2
1 12 3Trong test ví dụ đầu tiên, có 2 con vua và có thể đặt chúng vào 3 vị trí. Bất kể có đặt thế nào thì LN vẫn ngắm được 2 con vua. Số cách đặt là \(C^2_3=3\)
Test 2
3 3 4
1 13 28