trang chủ / đề bài / icpc26_mn_a

Bromine chơi bi-a

Đề bài

Mô tả

Bromine đang chơi trên một bàn bi-a hình chữ nhật có các cạnh song song với các trục tọa độ. Góc dưới bên trái của bàn là (0,5;0,5) và góc trên bên phải là (n+0,5;m+0,5), nên bàn có kích thước n×m. Anh đặt một quả bi cái có đường kính 1 lên bàn, tâm bi ban đầu ở điểm (x,y).

Bromine đánh quả bi cái, truyền cho nó vectơ vận tốc ban đầu (vx,vy). Hai thành phần vx và vy là vận tốc ban đầu của tâm bi theo trục X và trục Y, tính bằng đơn vị tọa độ mỗi giây.

Ví dụ, trên bàn 8×4, tâm bi ban đầu ở (2,2) và vận tốc ban đầu là (1,1): bi chạy chéo lên phía trên bên phải.

Giả sử quả bi chuyển động mãi mãi mà không mất tốc độ. Mỗi khi chạm thành bàn, nó va chạm đàn hồi hoàn toàn. Quy tắc phản xạ như sau:

  • Khi tâm bi đạt tới X=1 hoặc X=n, bi chạm một thành dọc và thành phần X của vận tốc đổi dấu.
  • Khi tâm bi đạt tới Y=1 hoặc Y=m, bi chạm một thành ngang và thành phần Y của vận tốc đổi dấu.

Nếu bi chạm hai thành cùng lúc, cả hai thành phần vận tốc đều đổi dấu. Nếu lúc đầu bi đang chạm một thành và vận tốc hướng vào thành đó, bi phản xạ ngay tại thời điểm 0.

Bromine là một cơ thủ cực kỳ điêu luyện. Anh đánh trúng mọi cú và tính được vị trí của bi cái tới tận một tỷ giây sau.

Bromine đã chán vì không tìm được đối thủ, nên để thử xem ai đó có xứng đáng chơi với mình hay không, anh đặt cho họ câu hỏi kiểu sau: "Cho thời điểm t, hãy xác định chính xác tọa độ (X,Y) của tâm bi đúng t giây sau khi bi được đánh."

Bạn muốn được chơi một ván với Bromine. Vì thế anh hỏi bạn q câu hỏi, và bạn cần trả lời tất cả thật nhanh!

Dữ liệu vào

  • Dòng đầu tiên chứa sáu số nguyên n,m,x,y,vx,vy (2≤n,m≤109, 1≤x≤n, 1≤y≤m, −109≤vx,vy≤109): kích thước bàn, tọa độ ban đầu của tâm bi và vectơ vận tốc ban đầu.
  • Dòng thứ hai chứa một số nguyên q (1≤q≤105): số câu hỏi.
  • Mỗi dòng trong q dòng tiếp theo chứa một số nguyên t (0≤t≤109): thời điểm (tính bằng giây) của câu hỏi.

Dữ liệu ra

In ra q dòng. Dòng thứ i chứa hai số nguyên Xt và Yt: tọa độ tâm bi tại thời điểm t của câu hỏi thứ i. Có thể chứng minh rằng tại mọi thời điểm được hỏi, cả hai tọa độ của tâm bi đều là số nguyên.

Ràng buộc

  • 2≤n,m≤109.
  • 1≤x≤n, 1≤y≤m.
  • −109≤vx,vy≤109.
  • 1≤q≤105.
  • 0≤t≤109.

Ví dụ

Input Output Giải thích
8 4 2 2 1 1
5
0
1
2
3
4
2 2
3 3
4 4
5 3
6 2
Tâm bi lần lượt ở (2,2), (3,3), (4,4) tại t=0,1,2. Tại t=2 tâm bi đạt Y=4=m nên thành phần Y đổi dấu, sau đó bi ở (5,3) và (6,2).
5 3 5 1 3 -2
4
0
1
2
7
5 1
2 3
3 1
2 3
Ví dụ bổ sung (không có trong đề gốc). Lúc đầu bi chạm thành X=5 và thành Y=1, vận tốc hướng vào cả hai thành nên bi phản xạ ngay tại thời điểm 0 với vận tốc (−3,2). Tại t=1 bi ở (2,3). Từ t=1 đến t=2, theo trục X bi đi 1 đơn vị tới X=1, phản xạ rồi đi tiếp 2 đơn vị tới X=3; theo trục Y bi đang ở Y=3=m nên phản xạ và đi xuống Y=1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0