개미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


거리 = 속력 * 시간


출처 : cscandkswon




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.