개미2 > 문제은행



1448 : 개미2

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
33 회   
시도횟수
90 회   

문제

개미들이 직선으로 이루어진 길을 걷고 있다. 개미들은 시작점에서 일정한 속력으로 왼쪽 또는 오른쪽으로 이동한다. 이들이 걷다 보면 부딪히는 경우가 있는데, 이때에는 다음과 같이 처리한다.

 

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

Hint!

거리 = 속력 * 시간



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP