시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 275 | 48 | 39 | 17.890% |
남규나라의 공주 Acka가 마왕한테 납치당했다. 남규나라의 왕 zych는 전설의 쌍검 용사 nein에게 공주를 구해 달라고 부탁하였다. nein은 마왕성에 쳐들어가기 위해 준비를 하고 있는데, nein은 평소에 여러 길이의 검들을 들고 다니며, 상대에 따라 그 중 두가지의 검을 한 손에 하나씩 들어 쌍검으로 싸운다.
nein은 남규나라의 정보부로부터 마왕성의 적들에 대한 정보들을 받았다. nein은 전설의 쌍검 용사답게 오랜 경험을 통해 각각의 적들을 어떤 검들로 상대를 하면 이길 수 있을지 알 수 있었는데, 그 정보는 다음과 같다.
오른손에는 정확히 A길이의 검을 사용하고, 왼손에는 B와 C 사이 길이의 검을 사용하면 적을 이길 수 있다.
nein은 공주 Acka를 구하기 위하여, 마왕성의 모든 적을 이길 수 있도록 검을 챙겨가려고 한다. 하지만, 모든 길이의 검을 가져간다면 너무 무거움으로 모든 적을 이길 수 있는 최소 개수의 검만 챙겨가려고 한다. 하지만 그 최소개수를 모르기 때문에 nein은 당신에게 부탁하였다. nein이 공주 Acka를 구할 수 있는 최소 검의 개수를 구하여라.
첫째 줄에는 마왕성의 적 n명이 주어진다.(1≤n≤100,000)
다음 n줄에는 적들을 쓰러트리기 위한 값 A,B,C가 주어진다.(1≤A≤1,000,000 , 1≤B≤C≤1,000,000)
마왕성의 적을 모두 쓰러트릴 수 있는 최소 검의 개수를 구하시오.
3 3 5 10 6 11 15 3 13 15
3
4 1 10 20 3 50 60 2 30 40 4 70 80
8