레이팅 미적용소 베시는 수직선 위 어딘가에 숨어 있다. 농부 존의 다른 \(N\)마리 소(\(1\le N\le 1000\))는 각자 알려줄 정보를 하나씩 가지고 있다. \(i\)번째 소는 베시가 \(p_i\) 이하의 어떤 위치에 숨어 있다고 말하거나, \(p_i\) 이상의 어떤 위치에 숨어 있다고 말한다(\(0\le p_i\le 10^9\)).
안타깝게도, 모든 소의 답과 일치하는 숨은 위치가 존재하지 않을 수도 있다. 이는 모든 소가 진실을 말하고 있는 것은 아니라는 뜻이다. 거짓말을 하고 있어야 하는 소의 최소 수를 구하여라.
Problem credits: Jesse Choe
Problem credits: Jesse Choe
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 L 또는 G와 그 뒤에 정수 \(p_i\)가 주어진다. L은 \(i\)번째 소가 베시의 숨은 위치가 \(p_i\) 이하라고 말한다는 뜻이고, G는 \(i\)번째 소가 베시의 숨은 위치가 \(p_i\) 이상이라고 말한다는 뜻이다.
거짓말을 하고 있어야 하는 소의 최소 수를 출력한다.
2
G 3
L 50It is possible that no cow is lying.
2
G 3
L 21At least one of the cows must be lying.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Bronze