행복

X 나라의 화폐 체계는 조금 이상하다. 1부터 M까지의 모든 정수 값을 가지는 지폐가 있다. X 나라의 상점에는 또 다른 이상한 규칙이 있다. 손님은 거스름돈을 받을 수 없고, 팁을 남길 수도 없다. 즉 손님은 항상 구매 금액과 정확히 같은 값을 지불해야 한다. 가지고 있는 돈으로 정확한 금액을 만들 수 없다면 그 물건을 살 수 없다. 이 규칙이 손님들에게 얼마나 큰 불편을 주는지 상상해 보라.

Niya는 X 나라에서 온 소녀이다. 다른 모든 사람들과 마찬가지로 그녀도 위에서 설명한 규칙들과 끊임없이 싸운다. 그녀는 항상 자신의 지폐 집합을 알고 있다. 그 값이 a1, a2, ..., aN이라고 하자. 이 값들은 모두 1과 M 사이이고, 같은 값의 지폐를 여러 장 가지고 있을 수도 있다. 또한 값의 수열 a1, a2, ..., aN은 어떤 순서로도 정렬되어 있지 않다. Niya는 상점에 들어갔을 때, 총 가격이 1부터 자신이 가진 지폐 값의 합 a1 + a2 + ... + aN 사이의 어떤 수와도 같아지도록 상품을 임의로 조합하여 살 수 있다면 행복을 느낀다. 이 경우 쇼핑할 때 자신의 지폐로 살 수 있는지 없는지 복잡하게 계산할 필요 없이 전체 금액만 생각하면 된다.

비고: a1, a2, ..., aN을 오름차순으로 정렬하자. Si = 1 + a1 + a2 + ... + ai라고 하자. 1부터 a1 + a2 + ... + aN 사이의 모든 수를 중복 집합 a1, a2, ..., aN의 원소들의 합으로 나타낼 수 있기 위한 필요충분조건은 각 i > 1에 대해 부등식 Si ≥ ai+1이 성립하고 a1 = 1이라는 것이다.

예상대로 Niya의 지폐 집합은 구매할 때마다 그리고 월급을 받을 때마다 바뀐다. 그래서 그녀의 행복도 변한다. 이 소녀를 위해 프로그램을 하나 만들어 줄 수 있다. 프로그램은 Niya의 초기 지폐 집합과 일어나는 모든 사건(구매와 월급)을 입력으로 받는다. 프로그램은 처음에 그리고 각 사건 이후에 Niya가 행복한지 판별할 수 있어야 한다.

Niya는 돈이 하나도 없을 때도 행복을 느낀다는 점을 밝혀 둔다. 그럴 때는 쇼핑을 건너뛰고 조깅을 하러 가기 때문이다.

심사위원의 그레이더와 함께 컴파일될 함수 init()과 is_happy()를 작성하라. 이 함수들은 처음과 각 사건 이후에 Niya의 행복을 판별하는 데 쓰인다. 함수들은 매개변수로 Niya의 초기 지폐 집합과, 집합에서 제거되는(구매 시) 지폐 집합, 집합에 추가되는(월급 수령 시) 지폐 집합을 받는다.

채점 시스템에는 다음 함수들을 포함하는 파일 happiness.cpp를 제출해야 한다.

• bool init(int coinsCount, long long maxCoinSize, long long coins[]).
• bool is_happy(int event, int coinsCount, long long coins[]).

매개변수 설명:

• coinsCount – 받거나(초기 집합 또는 월급) 버리는(쇼핑) 지폐의 수.

• maxCoinSize – 지폐 한 장의 최댓값.

• coins[] – 지폐의 값들이 임의의 순서로 주어지는 배열(인덱스는 0부터 시작).

• event – 사건의 종류:

  • -1 – 쇼핑;
  • 1 – 월급 수령.

함수 init은 그레이더가 처음에 Niya의 초기 지폐 집합을 설정하기 위해 한 번 호출하고, 그다음 그레이더는 event = -1(쇼핑) 또는 event = 1(월급)로 is_happy를 Q번 호출한다. 각 호출 후 호출된 함수는 Niya가 현재 지폐 집합으로 행복하면 true, 그렇지 않으면 false를 반환해야 한다.

파일 happiness.cpp에는 함수 main()이 있어서는 안 되지만, 함수 init과 is_happy가 올바르게 동작하는 데 필요한 다른 선언과 함수는 있어도 된다. 프로그램 맨 처음에 #include "happiness.h"가 있어야 한다.

Nc를 어느 순간의 Niya의 지폐 수, K를 어느 구매나 월급에 사용되는 지폐의 수라고 하자. 그러면 다음이 성립한다.

• 0 ≤ Nc ≤ 200 000
• 0 ≤ Q ≤ 100 000
• 1 ≤ M ≤ 1012
• 1 ≤ K ≤ 5

event = −1(쇼핑)인 is_happy의 모든 호출에서 coins[]에 주어지는 지폐 집합은 현재 Niya의 지폐 집합의 부분집합임이 보장된다.