Thí nghiệm hạt bốc đồng
Đề bài
Mô tả
Các nhà khoa học đã phát hiện ra một loại hạt mới có thể tạo ra cuộc cách mạng trong giao thông. Trong môi trường lý tưởng, nếu có một vật phẳng ở gần, hạt sẽ tự bắn mình theo hướng tới điểm gần nhất trên vật đó, gần như tức thời. Sau đó hạt ổn định lại và đứng yên. Các nhà khoa học gọi vật phẳng đó là gương phản xạ, và tùy theo chất liệu của gương mà hạt dừng lại ở vị trí khác nhau:
- nếu gương làm bằng vàng, hạt sẽ dừng lại ngay trên gương (tại hình chiếu vuông góc của nó lên gương);
- nếu gương làm bằng kim cương, hạt sẽ dừng lại ở phía đối diện của gương, cách gương đúng bằng khoảng cách vuông góc ban đầu (tại điểm đối xứng của nó qua gương).
Các nhà khoa học nhận ra rằng điều này có thể biến dịch chuyển tức thời thành hiện thực. Tuy nhiên, cần thử nghiệm thêm để đảm bảo an toàn cho mọi người và tối ưu chi phí cho cách di chuyển này. Vì vậy, họ tiến hành một số thí nghiệm.
Môi trường thí nghiệm được xem như mặt phẳng tọa độ . Các nhà khoa học chuẩn bị gương phản xạ, gương thứ làm bằng chất liệu (vàng hoặc kim cương) và được mô hình hóa bằng đường thẳng . Sau đó họ thực hiện thao tác thuộc các loại sau:
- 1 j m a b c: thay gương thứ bằng một gương khác, làm bằng chất liệu , nằm trên đường thẳng .
- 2 x y l r: đặt một hạt tại vị trí . Lần lượt với mỗi từ đến , các nhà khoa học bắn hạt tới gương thứ , đưa hạt tới vị trí dừng mới.
Với mỗi thao tác loại thứ hai, hãy giúp các nhà khoa học tìm vị trí dừng cuối cùng của hạt.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (): số gương và số thao tác.
Dòng thứ trong dòng tiếp theo chứa một ký tự và ba số nguyên (, , ): chất liệu của gương thứ (G là vàng, D là kim cương) và các hệ số của đường thẳng chứa gương.
Mỗi dòng trong dòng tiếp theo mô tả một thao tác theo dạng:
- 1 j m a b c (, , , ): thao tác loại 1.
- 2 x y l r (, ): thao tác loại 2.
Dữ liệu ra
Với mỗi thao tác loại thứ hai, in ra hai số nguyên (): tọa độ vị trí dừng cuối cùng của hạt, lấy theo modulo .
Chính thức, gọi . Có thể chứng minh mọi tọa độ đều biểu diễn được dưới dạng phân số tối giản , với là số nguyên và . Hãy in ra số nguyên bằng , nói cách khác là số nguyên sao cho và .
Ràng buộc
- .
- , với mọi gương.
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 G 1 0 -1 D 0 1 -1 2 3 5 1 1 2 3 5 1 2 1 2 D 1 1 0 2 3 5 1 2 2 6 9 2 2 |
1 5 1 998244350 998244348 998244352 998244344 998244347 |
Gương 1 (vàng) là đường , gương 2 (kim cương) là đường . Thao tác 1: hạt tại chiếu lên được . Thao tác 2: tiếp tục đối xứng qua được . Thao tác 3 thay gương 2 bằng gương kim cương trên đường . Thao tác 4: . Thao tác 5: đối xứng qua được . |
| 3 4 D 1 -1 0 G 0 1 0 D 1 0 -2 2 4 1 1 1 2 4 1 1 3 1 2 G 1 1 -1 2 0 0 2 3 |
1 4 3 0 499122180 499122177 |
Ví dụ bổ sung (không có trong đề gốc). Thao tác 2: . Thao tác 4: chiếu lên được , đối xứng qua được . |
Bình luận