BÀI TRẮC NGHIỆM VÒNG LOẠI 1 - Bài toán 1

Thông tin bài tập:

• Số lượng câu: 30 câu.
• Lưu ý quan trọng: Hệ thống đã kích hoạt chế độ One-shot (Nộp 1 lần). Bạn sẽ không thể sửa lại bài sau khi đã bấm nộp.

Yêu cầu:

1. Làm đủ các câu hỏi.
2. Bấm nộp bài và xem kết quả chấm tự động.

Bài toán 2

Có một con cua Hoàng Đế (King Crab), rất có thể chính là hero cấp S Mr. King trong manga One-Frame... à nhầm, One-Punch Man isekai sang thế giới của loài cua, đang ở trên sàn nhà tại điểm ~(a,b)~ của một căn phòng hình hộp chữ nhật có kích thước ~w\times d\times h~ và sàn nhà được gắn vào một hệ trục tọa độ 2D với 4 góc ở 4 điểm ~(0,0),(w,0),(0,d),(w,d)~.

Con cua, sau khi đã chán chê bài hát On The Floor do ca sĩ Jennifer Lopez và rapper Pitbull trình bày vì cảm thấy giai điệu quá hăng, khiến gạch cua trong người phân bố không đồng đều, sẽ tổn hao nguyên khí về lâu dài, liền đổi gu nhạc và đang chill theo bài hát Dancing On The Ceiling của ca sĩ Lionel Richie, nên muốn leo lên điểm ~(f,g)~ ở trên tầng nhà - chỗ của ca sĩ Lionel Richie đang biểu diễn.

Nhưng vì phận làm cua, dẫu là Hoàng Đế đi chăng nữa, con cua này chỉ có thể bò song song với các cạnh của căn phòng (i.e., dọc, ngang, hoặc thẳng đứng) trên sàn nhà, tường, và trần nhà, chứ không thể bò theo hướng chéo bất kỳ.

Yêu cầu: Tìm chiều dài của quãng đường ngắn nhất mà cua cần bò từ điểm ~(a,b)~ đến điểm ~(f,g)~.

Input

Mỗi test chứa nhiều test cases. Dòng đầu tiên chứa số test cases ~t~ (~1\le t\le10^4~). Mỗi test case gồm 2 dòng:

• Dòng 1 chứa 3 số ~w,d,h~ (~2\le w,d,h\le10^9~) mô tả kích thước của căn phòng.
• Dòng 2 chứa 4 số nguyên ~a,b,f,g~ (~0 < a,f < w, 0 < b,g < d~): con cua đang ở điểm ~(a,b)~ trên sàn nhà, và Lionel Richie đang ở điểm ~(f,g)~ trên trần nhà.

Output

Với mỗi test case, in ra một số nguyên duy nhất -- chiều dài của quãng đường ngắn nhất để cua có thể về với vòng tay của Lionel Richie bằng cách chỉ bò dọc theo các bức tường, sàn nhà, trần nhà, và song song với các cạnh của căn phòng.

Sample Input

5 
55 20 29 
23 10 18 3 
20 10 5 
1 5 2 5
15 15 4
7 13 10 10
2 1000 2
1 1 1 999
10 4 10
7 1 2 1

Sample Output

47
8
14
1002
17

Bài toán 3

Một chuỗi nhị phân (binary string) là một chuỗi chỉ chứa các ký tự ~0~ và ~1~. Với một chuỗi nhị phân ~t~ bất kỳ, gọi ~f(t)~ là số dãy con khác rỗng của ~t~ chỉ chứa ký tự ~0~, và gọi ~g(t)~ là số dãy con khác rỗng của ~t~ có chứa ít nhất ~1~ ký tự ~1~, e.g., ~f(000) = 7, g(100) = 4~. Định nghĩa "oneness" của chuỗi nhị phân ~t~ bởi ~O(t) := |f(t) - g(t)|~. Cho một số nguyên dương ~n~. Tìm chuỗi nhị phân nhỏ nhất và chuỗi nhị phân lớn nhất theo thứ tự từ điển có chiều dài ~n~ sao cho oneness của nó nhỏ nhất có thể.

Input. Dòng 1 chứa một số nguyên dương ~1 \le t \le 10^4~ là số bộ test. Mỗi bộ test gồm 1 dòng duy nhất chứa 1 số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) – chiều dài của chuỗi nhị phân ~s~.

Output. In ra giá trị nhỏ nhất của oneness, chuỗi nhị phân nhỏ nhất và chuỗi nhị phân lớn nhất theo thứ tự từ điển có chiều dài ~n~ ứng với giá trị nhỏ nhất đó, cách nhau bởi 1 khoảng trắng.

Sample Input

3 
1 
2
3

Sample Output

1 0 1
1 01 10
1 001 100

Bài toán 4

Với mỗi ~n \in \mathbb{N}~, đặt ~S_n := 4^n(\sin^{2n} 15^\circ + \cos^{2n} 15^\circ)~. Ta cần tính giá trị ~S_n \mod m~, i.e., số dư khi chia ~S_n~ cho ~m~ khi ~S_n~ có giá trị nguyên; quy ước giá trị này là ~-1~ nếu xảy ra trường hợp ~S_n~ không phải là số nguyên.

Input. Mỗi test chứa nhiều test cases. Dòng đầu tiên chứa số test cases ~t~ (~1 \le t \le 10^4~). Mỗi test case gồm 1 dòng chứa 2 số nguyên ~n, m~ cách nhau bởi 1 khoảng trắng (~1 \le m, n \le 10^8~).

Output. In ra kết quả ~S_n \mod m~.

Sample Input

5 
2 2 
3 4 
4 8 
5 2 
3 100

Sample Output

0
0
2
0
52

Lưu ý. Biết ~\sin 15^\circ~ và ~\cos 15^\circ~ là 2 số vô tỷ, nhưng ~S_n~ được thiết kế để tạo ra dãy số nguyên, i.e., ~S_n \in \mathbb{Z}, \forall n \in \mathbb{N}~. Các kiểu số thực thông thường của các ngôn ngữ lập trình hiện nay có hiệu ứng sai số không thể chấp nhận được khi làm tròn số thực thành số nguyên. Thuật toán của bạn cần nguyên hóa các công thức, bởi vì việc tính toán không chấp nhận sai sót dù chỉ 1-bit.