일방통행 블럭 도배해서 임의의 어마챌 맵 만들기 (아님)
정해진 값 V (0 ≤ V ≤ 2025)를 아래 질문으로 찾는 문제. 단, 질문은 처음에 몰아서 해야 하고, (1번 질문의 결과를 토대로 2번 질문을 만들 수 없음) 최대 한 개의 질문에 대해 잘못된 값이 반환될 수 있음.
이때, 질문을 15개 이하로 사용해서 알아내야 한다.
2025 ⇒ 비트 11개로 구성되어 있음.
먼저, 각 비트를 포함하는지를 묻는 질문 11개를 구성 ⇒ 0~10
그 후, V의 비트 개수가 홀수인지를 묻는 질문 2개를 구성 ⇒ 반환값이 다르다면 나머지 11개 질문이 참이므로 ok, 같다면 11개의 질문 중 거짓인 것이 존재하는지 판단 가능
다음으로 이분 탐색을 통해 거짓인 비트를 찾는다. (비트 개수 홀짝성 판별로 범위 내에 존재하는지 판단 가능)
이러면 17개로, 부분 점수 70점을 받는다.
만점 풀이는 1~2025에 이진 문자열을 잘 할당하는 풀이
삼각형, 사각형, 나비, 전갈 모양 그래프를 찾는 문제
백준에 있는 문제임 (21620. Math Homework)
[l..r] 범위의 수의 gcd가 X(≤16)라는 정보가 주어졌을 때, 모든 정보를 만족하는 수열이 있는지 판단하고 있다면 가능한 것 중 하나를 반환하는 문제