Lớp Đội tuyển Olympic Tin học & ICPC 2023 - Buổi 02
Gặp phải thằng liều
Nộp bàiPoint: 100
Gần đây anh Việt Thảo, phó chủ nhiệm CLB TAS rất đam mê với cờ vua. Tối ngày cứ lúc nào rảnh là anh lại mở kênh Youtube để xem các ván cờ vua đặc sắc. "Không ngờ lại gặp phải thằng liều", "chiếu hết trong sự ngỡ ngàng của đối thủ", không biết từ khi nào đã trở thành những câu nói cửa miệng của anh. Tuy nhiên, không ai ngờ anh lại liều tới mức học đánh cờ mà tọa độ bàn cờ cũng không thuộc. Cơ mà chẳng hề nao núng, anh Thảo ra cho TAS một đề bài như sau:
- Giả sử bàn cờ vua được đánh số từ trên xuống dưới, từ trái sang phải, ô trên cùng bên trái là ô ~(1, 1)~
- Cho một tọa độ ~(r, c)~, với r là chỉ số hàng, c là chỉ số cột trên bàn cờ vua. Hãy cho biết vị trí ô vuông đó trên bàn cờ là ô đen hay ô trắng.
- P/s: Bàn cờ vua của anh Thảo cũng không phải loại thường. Chiều dài, rộng của nó có thể lên tới ~10^{12}~ ô
Hình ảnh mô phỏng tọa độ bàn cờ
Input:
- Dòng đầu tiên chứa 2 số r, c ~(1 <= r, c <= 10^{12})~
Output:
- In ra
WHITE
nếu đó là ô trắng,BLACK
nếu là ô đen
Sample Input 1
1 1
Sample Output 1
WHITE
Sample Input 2
4 5
Sample Output 2
BLACK
Cấp số nhân
Nộp bàiPoint: 100
Dãy số ~A = (a_{0}, a_{1}, a_{2}, a_{3},…)~ gọi là dãy cấp số nhân nếu với mọi cặp số liên tiếp trong A thì tỉ lệ giữa chúng không thay đổi.
Ví dụ:
- ~A = (1, 2, 4, 8, 16, 32)~ là dãy cấp số nhân vì số đứng sau luôn gấp ~2~ số đứng trước.
- ~A = (108, 36, 12, 4)~ là dãy cấp số nhân vì số đứng sau luôn bằng ~\frac{1}{3}~ số đứng trước.
Như vậy, ta có thể suy ra mọi phần tử của A nếu biết trước hai phần tử đầu tiên và độ dài của dãy.
Input
- 3 số nguyên mỗi số trên một dòng, là hai phần tử đầu tiên và độ dài của A
- Tuy dãy cấp số nhân tổng quát nên là dữ liệu số thực, nhưng dữ liệu của bài đảm bảo tất cả các phần tử của A đều nguyên (có thể âm).
Output:
- In ra các phần tử của A, mỗi phần tử trên một dòng
- Số dòng không quá 10000.
- Nếu giá trị phần tử in ra cần 10 vị trí trở lên (tức giá trị từ 1 tỉ trở lên hoặc -100 triệu trở xuống), chỉ cần in ra 3 chữ số đầu tiên và tiếp sau là ba dấu chấm (xem test ví dụ).
Vài test ví dụ:
Sample input 1
3
12
10
Sample output 1
3
12
48
192
768
3072
12288
49152
196608
786432
Sample input 2
1
1234
20
Sample output 2
1
1234
1522756
187...
231...
286...
353...
435...
537...
663...
818...
101...
124...
153...
189...
234...
289...
356...
440...
543...
Mật mã Caesar
Nộp bàiPoint: 100
Trong mật mã học, mật mã Ceasar, hay còn gọi là mật mã dịch chuyển, là một trong những hệ mật mã đơn giản và được biết đến nhiều nhất.
Hệ mã Ceasar hoạt động trên bảng chữ cái tiếng Anh 26 kí tự. Cho một đoạn văn bản rõ ~m~ và một khóa ~k~, mật mã sẽ tạo ra bản mã ~c~ bằng cách thay thế mỗi chữ cái trong bản rõ ~m~ bằng một chữ cái nằm trong bảng chữ cái cách nó ~k~ kí tự.
Ví dụ với đoạn văn bản m="ATTACKATDAWN"
và một khóa k=3
, mỗi chứ cái trong văn bản sẽ được thay thế bằng chữ cái cách nó 3 kí tự trong bảng chữ cái:
A
sẽ được thay thế bằngD
T
sẽ được thay thế bằngW
C
sẽ được thay thế bằngF
- ...
Sau khi thay thế xong ta được bản mã c="DWWDFNDWGDZQ"
Ngoài ra, khi gặp các kí tự không nằm trong bảng chữ cái như khoảng trắng, chữ số, kí tự đặc biệt,...ta để nguyên kí tự đó như ban đầu.
Ví dụ m="I LOVE TLU 2023 <3", k=7
-> c="P SVCL ASB 2023 <3"
Nếu trong quá trình dịch chuyển chữ cái đang xét vượt ra khỏi bảng chữ cái thì nó sẽ được dịch chuyển kí tự đầu tiên trong bảng chữ cái (chữ A). Ví dụ m="XYZ", k=3
-> c="ABC"
Chủ nhiệm TAS Nguyễn Văn Hiếu nhận được 1 xâu mã hóa ~c~ và key ~k~ từ thầy cố vấn Trương Xuân Nam, tuy nhiên anh ấy quá bận nên không kịp giải mã xem xâu này có ý nghĩa gì. Vì vậy anh ấy đặt niềm tin vào bạn - một người đam mê lập trình sẽ giúp anh ấy kịp giải mã thông điệp bí ẩn này.
Cho bản mã ~c~ (gồm toàn các chữ cái viết hoa, các kí tự đặc biệt, khoảng trắng và số) và khóa ~k~, hãy tìm ra bản rõ ~m~
Input:
- Dòng đầu tiên gồm 2 số nguyên ~n~ (~n <= 10^6~) và ~k~ (~1 <= k <= 10^{12}~) là độ dài của bản mã và giá trị khóa ~k~
- Dòng thứ là bản mã ~c~
Output:
- Bản rõ ~m~
Sample Input 1
13 100
PDWK ZAL PNWE
Sample Output 1
THAO DEP TRAI
Sample Input 2
13 123456
Q_TWDM_BIA :v
Sample Output 2
I_LOVE_TAS :v
Sum of x
Nộp bàiPoint: 100
Chúng ta hãy gọi hàm ~f(x)~ là tổng các chữ số của số nguyên dương ~x~ . Các bạn hãy tìm 2 số nguyên dương a và b sao cho:
~f(a) >= N~
~f(b) >= N~
~f(a+b) <= M~
Ví dụ ~f(123)=6~
Với ~N~ và ~M~ là 2 số nguyên dương cho trước
Input:
- Dòng duy nhất của input chứa 2 số nguyên dương ~N~ và ~M~ ~(1 \leq n,m \leq 5000)~
Output:
Hãy in ra ~a~ và ~b~ bạn tìm được, mỗi số trên 1 dòng. Nếu có nhiều kết quả, hãy in ra 1 trong số đó. Dữ liệu đảm bảo có đầu ra.
Hãy lưu ý, độ dài của ~a~ hoặc ~b~ không vượt quá 2250
Sample Input 1
8 16
Sample Output 1
35
53