trang chủ / đề bài / icpcwf24_h

Con quỷ của Maxwell

Đề bài

Mô tả

Yên tâm: bài này không cần kiến thức nhiệt động lực học.

Con quỷ của Maxwell ngồi trong một bình chứa có chiều cao h và chiều rộng 2w. Bình được chia thành hai buồng kề nhau, mỗi buồng cao h và rộng w. Một bức tường không thể xuyên qua ngăn cách hai buồng, và con quỷ ngồi ở một vị trí cố định trên bức tường giữa này.

Trong các buồng có các hạt, mỗi hạt có một vị trí, một vận tốc và một màu. Khi một hạt chạm vào thành của buồng, nó phản xạ đàn hồi hoàn toàn. Ví dụ thứ nhất là một bình có hai hạt: một hạt xanh ở buồng trái và một hạt đỏ ở buồng phải.

Con quỷ của Maxwell muốn giảm entropy bằng cách phân loại các hạt: nó muốn mọi hạt đỏ ở buồng trái và mọi hạt xanh ở buồng phải. Để làm điều đó, nó có một năng lực đặc biệt: nó có thể cho các hạt đi xuyên qua bức tường giữa khi chúng chạm vào đúng vị trí của con quỷ.

Đáy hai buồng nằm trên trục x, bức tường giữa nằm dọc theo nửa dương của trục y. Như vậy buồng trái là hình chữ nhật [−w,0]×[0,h] và buồng phải là [0,w]×[0,h]. Vào bất kỳ thời điểm nào con quỷ chọn, mọi hạt đang ở vị trí của con quỷ (0,d) sẽ không phản xạ khỏi bức tường giữa mà đi xuyên qua sang buồng bên kia, giữ nguyên vận tốc. Con quỷ có thể làm việc này bất cứ khi nào và bao nhiêu lần tùy ý, và cũng có thể chọn không cho một hạt đi qua dù hạt đó chạm vào vị trí của con quỷ. Tuy nhiên, nếu có nhiều hạt cùng ở vị trí (0,d) tại cùng một thời điểm thì hoặc tất cả các hạt đó đi qua, hoặc tất cả đều bị phản xạ.

Hãy giúp con quỷ phân loại các hạt và giảm entropy! Thời điểm sớm nhất mà có thể làm cho mọi hạt đỏ ở buồng trái và mọi hạt xanh ở buồng phải là bao nhiêu?

Dữ liệu vào

Dòng đầu gồm năm số nguyên w, h, d, r, b: w và h là chiều rộng và chiều cao của mỗi buồng, d là tung độ của vị trí con quỷ trên bức tường giữa, r và b lần lượt là số hạt đỏ và số hạt xanh.

Tiếp theo là r+b dòng, mỗi dòng mô tả một hạt bằng bốn số nguyên px, py, vx, vy, trong đó (px,py) là vị trí ban đầu và (vx,vy) là vận tốc ban đầu của hạt. r hạt đầu tiên có màu đỏ, các hạt còn lại có màu xanh.

Dữ liệu ra

In ra thời gian ít nhất cần thiết để mọi hạt đỏ ở buồng trái và mọi hạt xanh ở buồng phải. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6. Nếu không thể làm cho mọi hạt đỏ ở buồng trái và mọi hạt xanh ở buồng phải trong một khoảng thời gian hữu hạn, in ra impossible.

Ràng buộc

  • 2≤w,h≤200.
  • 0≤d≤h.
  • 0≤r,b và 1≤r+b≤200.
  • 0<|px|<w, 0<py<h.
  • |vx|<w, |vy|<h, (vx,vy)≠(0,0).

Ví dụ

Input Output Giải thích
7 4 1 1 1
2 1 4 1
-3 1 2 0
24.0 Con quỷ ở (0,1). Hạt xanh xuất phát ở (−3,1) trong buồng trái, chạy ngang trên đường y=1 và chạm vị trí con quỷ lần đầu ở thời điểm 1,5: cho nó đi qua sang buồng phải. Hạt đỏ xuất phát ở (2,1) trong buồng phải và chạm vị trí con quỷ lần đầu ở thời điểm 24: cho nó đi qua sang buồng trái.
4 4 1 2 2
3 1 2 2
-2 3 -2 -1
3 2 1 -2
-2 2 2 2
impossible Không bao giờ có thể đồng thời đưa mọi hạt đỏ sang buồng trái và mọi hạt xanh sang buồng phải.

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