Tin học trẻ 2023 - Vòng Khu vực miền Bắc và miền Nam - Bảng B
Bảng màu
Nộp bàiAlice có một bảng màu kích thước \(m \times n\), các hàng được đánh số từ \(1\) đến \(m\) theo chiều từ trên xuống, các hàng được đánh số từ \(1\) đến \(n\) theo chiều từ trái qua phải. Ô nằm giao giữa hàng \(i\) (\(1 \le i \le m\)) và cột \(j\) (\(1 \le j \le n\)) gọi là ô \((i,j)\). Ban đầu, toàn bộ bảng là màu trắng (màu \(0\)), Alice thực hiện \(k\) thao tác tô màu như sau:
- Chọn một hình chữ nhật nằm trong bảng chiếm nguyên các ô và một màu \(c\) (\(1 \le c \le 100\)).
- Tô đè tất cả các ô trong hình chữ nhật vừa chọn thành màu \(c\).
Yêu cầu: Cho \(m,n\) là kích thước bảng và dãy gồm \(k\) thao tác tô màu, hãy xác định bảng màu mà Alice nhận được.
Input
- Dòng đầu tiên gồm ba số nguyên \(m,n,k\) (\(m,n,k \le 100\)).
- Dòng thứ \(s\) (\(1 \le s \le k\)) chứa năm số nguyên \(x_s,y_s,u_s,v_s,c_s\) trong đó (\(x_s,y_s\)) và (\(u_s,v_s\)) tương ứng là ô góc trái trên và ô góc phải dưới của hình chữ nhật được chọn ở thao tác tô màu thứ \(s\), \(c_s\) là màu sẽ tô cho hình chữ nhật đó.
Output
- Dòng thứ \(i\) (\(1 \le i\ le m\)) trong \(m\) dòng sau chứa \(n\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,n}\) mô tả màu trên hàng \(i\) của bảng màu Alice.
Example
Test 1
Input
3 3 2
1 1 2 2 2
2 2 3 3 1
Output
2 2 0
2 1 1
0 1 1
Tổng chữ số
Nộp bàiAn và Bình đang có một số nguyên dương \(X\) và muốn tách nó thành tổng hai số nguyên dương \(A\) và \(B\). Giá trị thực sự của một số nguyên dương không nằm ở độ lớn mà được quyết định bởi tổng chữ số. Hai bạn sẽ cảm thấy vui nếu \(A\) và \(B\) có tổng chữ số giống nhau.
Yêu cầu: Có \(T\) giả định, mỗi giả định cung cấp số nguyên dương \(X\). Với mỗi giả định, hãy giúp An và Bình tìm hai số nguyên dương \(A\) và \(B\) có tổng bằng \(X\) và tổng chữ số của hai số bằng nhau.
Input
- Dòng đầu tiên chứa một số nguyên dương \(T\) (\(1 \le T \le 10000\)).
- Mỗi dòng trong \(T\) dòng tiếp theo chứa một số nguyên dương \(X\) (\(X \ge 2\)).
Output
- VỚi mỗi giả định, in ra hai số nguyên \(A\) và \(B\) bất kì thỏa mãn đề bài trên một dòng. Nếu không tồn tại đáp án, in ra
-1.
Scoring
Gọi \(C(X)\) và \(S(X)\) là số chữ số và tổng chữ số của số nguyên dương \(X\).
- Subtask \(1\) (\(20\%\) số điểm): \(X \le 10000\) với mọi giả định.
- Subtask \(2\) (\(30\%\) số điểm): Tổng \(C(X)\) của các giả định không vượt quá \(1000\).
- Subtask \(3\) (\(20\%\) số điểm): Tổng \(C(X)\) của các giả định không vượt quá \(10^6\) và \(S(X)\) chẵn với mọi giả định.
- Subtask \(4\) (\(30\%\) số điểm): Tổng \(C(X)\) của các giả định không vượt quá \(10^6\).
Example
Test 1
Input
4
4
33
243
29
Output
2 2
12 21
117 126
-1
Dãy số tổng k
Nộp bàiCho dãy \(a\) gồm \(n\) số \(1\) và \(-1\), các phần tử được đánh số từ \(1\) đến \(n\).
Cho \(q\) thao tác gồm một trong hai dạng
- Thao tác loại \(1\) có dạng "\(1\) \(i\) \(v\)" (\(1 \le i \le n\) và \(v \in \{1,-1\}\)), thao tác này sẽ gán \(a_i = v\).
- Thao tác loại \(2\) có dạng "\(2\) \(l\) \(r\) \(k\)" (\(1 \le l \le r\ le n\) và \(|k| \le n\)), thao tác này cần tìm hai số nguyên \(x,y\) thỏa mãn \(l \le x \le y \le r\) và tổng các phần tử từ \(x\) đến \(y\) của dãy \(a\) đúng bằng \(k\).
Input
- Dòng đầu tiên chứa hai số nguyên \(n,q\) (\(1 \le n,q \le 10^5\)).
- Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(a_i \in \{1,-1\}\)).
- Mỗi dòng trong \(q\) dòng tiếp theo chứa một thao tác theo định dạng như trên đề bài.
Output
- Với mỗi thao tác loại \(2\), in ra hai số \(x,y\) bất kì thỏa mãn điều kiện. Nếu không tồn tại đáp án, in ra
-1.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(k = 0\) với mọi thao tác loại \(2\).
- Subtask \(2\) (\(20\%\) số điểm): \(n,q \le 5000\).
- Subtask \(3\) (\(30\%\) số điểm): không có thao tác loại \(1\).
- Subtask \(4\) (\(30\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
5 8
1 -1 -1 1 1
2 1 4 0
2 1 4 -3
1 4 -1
2 1 5 -3
1 3 1
1 1 -1
1 5 -1
2 1 5 -3
Output
3 4
-1
2 4
1 5