아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

기념품

시간 제한1초메모리 제한256 MB

요약
금화와 은화로 상인을 순서대로 방문해 기념품을 사며 거스름 규칙에 맞게 지불 방식을 골라 구매 개수를 최대화합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

금화(gg 은화 가치)와 은화로 순서대로 기념품을 산다. 상인은 탐욕, 정직, 관대 방식으로 은화 패키지 거스름을 준다. 관대 상인은 가능하면 정확히 은화로, 나머지는 금화 1개로 지불한다. 최대 구매 수를 출력한다.

입력

gg, cc, nn, 이후 상인 정보.

출력

살 수 있는 기념품 최대 개수.

예제4

  1. 예제 1

    입력
    42 1 2
generous 21 41
honest 6 21
    예상 출력
    2

  2. 예제 2

    입력
    42 1 2
honest 21 11
generous 6 23
    예상 출력
    1

  3. 예제 3

    입력
    12 2 6
greedy 1 5
greedy 1 6
generous 4 7
greedy 4 6
greedy 6 6
honest 2 2
    예상 출력
    5

  4. 예제 4

    입력
    10 1 1
greedy 2 3
    예상 출력
    1