AlgoSec Battle 2 - Bảng đôi nam nữ
Dãy ngoặc kì bí
Nộp bàiPoint: 100
Trong một thị trấn nhỏ, có một cậu bé tên là Sơn đam mê khám phá về lập trình. Một ngày, cậu nhận được một cuốn sách kỳ lạ có tên Những Dãy Ngoặc Huyền Bí. Trong cuốn sách này, có một bí mật: cách kết hợp các dãy ngoặc để tạo ra những điều kỳ diệu. Sơn học được rằng một dãy ngoặc được gọi là kì bí khi nó tuân thủ các quy tắc sau:
- Dãy ngoặc rỗng là một dãy ngoặc kì bí.
- Nếu
là dãy ngoặc kì bí thì là một dãy ngoặc kì bí. - Nếu
và là 2 dãy ngoặc kì bí thì là 1 dãy ngoặc kì bí.
Từ đó, Sơn đã áp dụng những kiến thức này vào cuộc sống hàng ngày của mình, giúp anh trở thành một lập trình viên đẳng cấp. Sơn muốn đố bạn rằng: Cho một dãy ngoặc bất kì, kiểm tra xem đó có phải dãy ngoặc kì bí hay không?
Input
- Dòng đầu tiên là số lượng bộ test T (T ≤ 20).
- Mỗi test gồm 1 dãy ngoặc S có độ dài không vượt quá 10000.
- Dãy ngoặc S chỉ chứa các kí tự:
, , , , , , "" (rỗng)
Output
- Với mỗi test, in ra Yes nếu S là dãy ngoặc đúng, in ra No trong trường hợp ngược lại.
Chia độ khó
Độ khó | Điều kiện |
---|---|
Dễ (40% tổng số điểm) | 0 < T ≤ 3, S ≤ 10 |
Trung bình (30% tổng số điểm) | 0 < T ≤ 15, S ≤ 100 |
Khó (30% tổng số điểm) | 0 < T ≤ 20, S < 10^4 |
Sample Input:
2
[()]{}{[]()}
[(])
Sample Output:
Yes
No
Lũy thừa cao
Nộp bàiPoint: 100
Ta gọi một số có dạng
Cho một số
Input
- 1 dòng duy nhất chứa
Output
- 1 dòng duy nhất là kết quả
, nếu có hoặc nếu không
Sample Input 1
27
Sample output 1
3 3
Sample Input 2
10
Sample output 2
0
Ghép đôi
Nộp bàiPoint: 100
Để tăng số lượng thí sinh tham dự cho bảng thi đôi nam nữ kì thi AlgoSec Battle mùa 3 tới, CLB TAS quyết định tổ chức ghép đôi theo quy tắc như sau:
- Các thí sinh nam sẽ điền form đăng ký ghép đôi và trình bày các điểm mạnh cũng như mong muốn của bản thân
- Sau khi bước 1 hoàn tất, các thí sinh nữ sẽ chọn từ form số thứ tự của 2 bạn nam mà mình muốn được ghép đôi cùng
Vì không để ý nên tới hạn chót H mới đăng ký ghép đôi cho mình. Lúc này trong danh sách đã có
Vì viết mãi mà thuật toán chạy không đúng nên H quyết định nhờ sự giúp đỡ của bạn. Hãy giúp bạn ấy có thể ghép đôi suôn sẻ cho kì thi sắp tới nhé!
Input
- Dòng đầu chứa số nguyên
là số lượng bạn nữ đã đăng ký. dòng tiếp theo, dòng thứ chứa cặp số nguyên , là chỉ số của 2 bạn nam mà bạn nữ thứ mong muốn ghép đôi. .
Output
- Chứa một số duy nhất là đáp số bài toán.
Chia độ khó
Độ khó | Điều kiện |
---|---|
Dễ (25% tổng số điểm) | |
Trung bình (35% tổng số điểm) | |
Khó (40% tổng số điểm) |
Sample Input 1
2
2 3
2 3
Sample Output 1
2
Sample Input 2
3
1 2
1 2
1 2
Sample Output 2
0
Giải thích
Ví dụ 1: Do 2 bạn nữ 1 và 2 đều chọn 2 bạn nam 2 và 3 nên 2 bạn này sẽ được ghép cho 2 người. Hảo chỉ có thể chọn bạn Nam số 1, vì vậy 2 cách chọn hợp lý cho Hảo là (1,2) và (1,3).
Ví dụ 2: Do có 3 bạn nữ đều muốn chọn bạn nam 1 và 2 nên dù Hảo chọn như thế nào cũng không thể sắp xếp được.
Cây thu nhập
Nộp bàiPoint: 100
Công ty VTCorp có
Quan hệ cấp bậc trong công ty tạo thành một cấu trúc hình cây. Quan hệ này có tính bắc cầu: nếu nhân viên
Biết rằng nhân viên thứ
- Nhân viên thứ
là cấp trên của nhân viên và . - Thu nhập của nhân viên thứ
cao hơn thu nhập của nhân viên thứ và thứ . - Bộ ba
và được coi là giống nhau.
Input
- Dòng 1: Chứa số nguyên
thể hiện số nhân viên. - Dòng 2: Chứa một số nguyên dương
thể hiện tiền lương của CEO (nhân viên ). dòng tiếp theo: Dòng thứ chứa số nguyên dương và lần lượt thể hiện cấp trên trực tiếp và tiền lương của nhân viên thứ
Output
- Một số nguyên duy nhất là số lượng bộ ba thỏa mãn.
- Kết quả có thể vượt quá giới hạn số nguyên
bit.
Chia độ khó
Độ khó | Điều kiện |
---|---|
Dễ (20% tổng số điểm) | |
Trung bình (15% tổng số điểm) | |
Khó (65% tổng số điểm) |
Sample input
5
3
1 2
1 2
3 2
3 1
Sample output
6
Giải thích
Sơ đồ biểu diễn cấp bậc của các nhân viên sẽ như sau:
1
/ \
2 3
/ \
4 5
Ta có 6 bộ ba như sau:
- CEO có lương bằng lớn hơn nhân viên thứ và thứ với tiền lương của mỗi người là . CEO là cấp trên của cả nhân viên và . - Tiền lương của nhân viên thứ và thứ đều là và nhỏ hơn tiền lương của CEO và cả đều là cấp dưới.
Bộ