https://atcoder.jp/contests/practice/tasks/practice_2
In testset 3, N=5<math style="box-sizing: border-box;" xmlns="http://www.w3.org/1998/Math/MathML">N=5</math> and Q=7<math style="box-sizing: border-box;" xmlns="http://www.w3.org/1998/Math/MathML">Q=7</math>.
2번셋까지는 풀었는데 3번셋에서 막히네요..
문제는 알파벳순으로 쓰여진 공 N개가 있는데, Q개의 질문으로 공 무게 비교를 할 수 있다는 조건에서 공을 무게 오름차순으로 정렬하는 겁니다
공이 N 개가 있으니까 답은 N! 가지중에 하나임. 질문을 Q개 할 수 있으니까, 우리가 얻을 수 있는 정보는 2^Q 가지임.
예를 들면, N=5 일 때, 6개의 질문만으로 답을 찾는 것은 불가능함. 6개의 질문만으로는 2^6 = 64 가지의 경우만을 구별할 수 있기 때문임.그러나 5! = 120임. 이 관찰을 잘 이용해서 답을 찾아야 함
각 원소를 a, b, c, d, e 라고 하자. 이제 a 와 b를 비교할거임. 그러면 총 5! = 120 가지의 경우중에 a { b 인 경우가 60개, b { a 인 경우가 60개임. 두 경우는 같으니까 a{b 라고 하자.
(부등호가 잘 표시가 안 되서 { 기호 사용... 대소비교임)
저 경우는 그냥 손으로 직접 해야돼요
이제 b와 c를 비교한다고 해보자. 그러면 b{c 이거나 c{b 인 결과가 나올테지. case b{c 일 때) 아까 60개의 [경우] 가 있다고 했는데, 그때 말한 60개 중 b{c인 경우는 오직 20개 뿐임.
반대로, c{b 인 경우는 60-20 = 40 개가 나옴. 그럼 이 상황에서 40개의 경우를 구분해야 함. 그런데 질문은 겨우 5개 쓸 수 있음. 질문 5개로는 고작 32가지의 경우만 구분할 수 있음.
그래서 이런 식의 전략으로는 모든 경우를 구분할 수 없음. a와 b를 비교한 후에 b와 c를 비교하는 전략은 좆망임. a와 b를 비교한 후에는 c와 d를 비교하는 방식을 쓰던지 해야 함.
이 아이디어를 써서, 어떤 원소와 어떤 원소를 비교해야 하는지, 그 전략을 찾을 수 있음. 물론 걍 노가다로 찾을 수도 있는데 그렇게 찾으면 잘 찾아지지도 않고 스트레스만 받고 머리만 아프고 시발 그렇게 찾으려면 스트레스 받아서 문제못품
이제야봤네요 답변 ㄳㄳ합니다