問題
개미들이 직선으로 이루어진 길을 걷고 있다. 개미들은 시작점에서 일정한 속력으로 왼쪽 또는 오른쪽으로 이동한다. 이들이 걷다 보면 부딪히는 경우가 있는데, 이때에는 다음과 같이 처리한다.
1. 같은 방향으로 가다 부딪힌 경우는 두 개미의 속력이 서로 바뀌고 방향은 바뀌지 않은채 가던 방향 그대로 간다. 2. 다른 방향으로 가다 부딪힌 경우는 두 개미의 속력과 방향이 모두 서로 바뀐다. 3. 만약 3마리 이상의 개미가 부딪힌 경우는 개미의 번호가 작은 것들부터 부딪히고 부딪히지 않는 개미는 그대로 진행한다.
이와 같이 개미들이 길을 걷고 있을 때 모든 개미가 길의 끝(0 또는 N)에 도달하는 시간을 구하시오.
輸入
길의 길이 N(3 <= N <= 10^14), 개미의 수 M(1 <= M <= 10^6)이 첫줄에 입력된다.
그다움 줄부터 각각 개미의 정보가 입력된다.
개미 번호 n(1 <= n <= M), 개미 시작점 p(1 <= p < N, 정수), 개미가 움직이는 방향 a(1인 경우는 왼쪽, 2인 경우는 오른쪽), 개미의 속력 s(1 <= s <= 30000, 정수)가 입력된다.
데이터의 30%는 M <= 10^3 이다
輸出
모든 개미가 길의 끝에 도달했을 때의 시간을 소수 이하 7 자리에서 반올림하여 6 자리까지 출력한다.
範例
100 5
2 5 2 3
1 24 1 7
4 12 2 12
5 92 1 52
3 51 2 24
31.666667
提示
來源
cscandkswon
需要登入才能撰寫程式碼。