비폭력 시위
시간 제한2초메모리 제한512 MB
각 사람의 임계치가 주어질 때 다른 사람이 이미 폭동 중이면 자신도 참여하는 규칙으로 최종 폭동 인원을 구합니다.
문제
1968년의 또 다른 역사적 사건은 마틴 루서 킹 주니어의 암살이었다. 그는 민권 운동의 지도자였고, 그의 "I have a dream" 연설은 미국 역사상 가장 중요한 연설 중 하나로 꼽힌다. 마틴 루서 킹 주니어는 비폭력 시위를 흔들림 없이 옹호했다. 비폭력 시위가 더 효과적인 경향이 있는 이유는 시위의 목표가 보통 인식을 높이고 여론을 움직이는 것이기 때문이다. 폭력적으로 보이면 여론을 자기 편으로 움직이기가 훨씬 어렵다. 그래서일까, 경찰과 다른 조직들은 공격적인 도발로, 또 폭력적인 시위자들을 잠입시켜 그들이 전체 시위를 따라오게 하고 대규모 폭동을 일으키기를 바라는 방식으로 민권 운동을 약화시키려 했다. 여기서 중요한 점은 긴장된 환경의 시위에서 평화로운 시위와 폭동 사이의 경계가 흔히 매우 얇다는 것이다. 미디어(그리고 역사책)의 보도는 보통 집단 전체의 성격을 "획일적"으로 다루지만, 실제로는 특정 상황에 반응하는 개인들이고, 상황의 아주 미묘한 변화가 다른 결과로 이어질 수 있다.
이를 다음과 같은 단순화한 모델로 살펴본다. n명의 개인이 시위에 참여한다. 각 개인은 정수 임계값 ti ≥ 0을 가진다. 개인 i는 자신보다 먼저 시위에 가담한 사람이 적어도 ti명 있으면 폭동에 가담한다. 그러면 그는 다른 사람들도 폭동에 가담하게 만들 수 있다. 아무도 폭동에 가담하지 않은 상태에서 시작할 때, 끝에 몇 명이 폭동에 가담하는지 계산하라.
입력
첫 줄은 입력 데이터 세트의 수 K이고, 그다음 K개의 데이터 세트가 각각 다음 형태로 주어진다.
첫 줄은 개인의 수 0 ≤ n ≤ 1000000이다. 다음 줄에는 n명의 임계값 ti가 특별한 순서 없이 주어진다.
출력
각 데이터 세트마다 "Data Set x:"를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호다. 그다음 끝에 폭동에 가담하는 사람의 수를 출력한다.
각 데이터 세트 뒤에는 빈 줄을 출력한다.