동전

시간 제한2초메모리 제한512 MB

요약

N개 동전의 앞면 확률이 M번 갱신될 때마다 앞면 개수가 홀수일 확률과 짝수일 확률 중 어느 쪽이 큰지 판정한다.

난이도: 보통10점 중 7점
유형: 수학, 확률, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

앞면이 나올 확률이 서로 다른 $N$ 개의 동전이 있다. $N$ 개의 동전을 모두 던졌을 때 앞면이 홀수 개이면 살고 짝수 개이면 죽는다.

처음 상태에 이어 확률을 바꾸는 작업이 $M$ 번 주어진다. 각 작업은 동전 번호와 바뀐 앞면 확률을 지정한다. 확률을 $0$ 번 바꾼 처음 상태부터 $M$ 번 바꾼 마지막 상태까지 총 $M+1$ 개의 상태에서 살 확률과 죽을 확률을 비교한다.

입력

첫 줄에 $N$ 과 $M$ 이 주어진다. $1 \le N \le 500000$ 이고 $0 \le M \le 500000$ 이다. 둘째 줄에 $N$ 개의 실수가 주어진다. $i$ 번째 수는 $i$ 번 동전의 앞면 확률이다. 이어지는 $M$ 줄에는 동전 번호와 바뀐 확률이 한 줄에 하나씩 주어진다.

모든 확률은 $0$ 이상 $1$ 이하이며 소수점 아래 $6$ 자리까지 주어진다.

출력

총 $M+1$ 줄을 출력한다. $i$ 번째 줄은 확률을 $i-1$ 번 바꾼 상태의 답이다.

살 확률이 더 높으면 "ALIVE"를 출력하고 죽을 확률이 더 높으면 "DEAD"를 출력한다. 두 확률이 같으면 "SAME"을 출력한다.

힌트

앞면 확률이 $0.3$ , $0.4$ , $0.7$ 인 세 동전이 있을 때 살 확률은 $0.516$ 이고 죽을 확률은 $0.484$ 이다. 따라서 살 확률이 더 높다.

예제2

예제 1

입력

2 3
1.000000 1.000000
1 0.000000
2 0.500000
2 0.000000

예상 출력

DEAD
ALIVE
SAME
DEAD

예제 2
입력
```
3 0
0.300000 0.400000 0.700000
```
예상 출력
```
ALIVE
```