카드 오버행

면접 대비

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

요약
각 목표 오버행 c에 대해 조화합 1/2 + 1/3 + ... + 1/(n+1)이 c 이상이 되는 최소 카드 수 n을 구해 보고한다.
난이도

쉬움10점 중 3점

유형
수학, 구현, 누적 합, 완전 탐색
정답자
아직 제출이 없습니다

문제

책상 위에 카드를 겹쳐 쌓을 때, 카드 더미를 책상 끝 밖으로 얼마나 멀리 내밀 수 있을까요? 카드가 한 장이라면 카드 길이의 절반만큼 내밀 수 있습니다(모든 카드는 책상과 수직을 이룬다고 가정합니다). 카드가 두 장이라면 위 카드를 아래 카드보다 카드 길이의 12\frac{1}{2}만큼, 아래 카드를 책상 끝보다 13\frac{1}{3}만큼 내밀어, 최대 12+13=56\frac{1}{2} + \frac{1}{3} = \frac{5}{6} 카드 길이만큼 내밀 수 있습니다.

일반적으로 카드가 nn장이면

12+13+14+⋯+1n+1\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{n+1}

카드 길이만큼 내밀 수 있습니다. 맨 위 카드는 두 번째 카드보다 12\frac{1}{2}만큼, 두 번째 카드는 세 번째 카드보다 13\frac{1}{3}만큼, 세 번째 카드는 네 번째 카드보다 14\frac{1}{4}만큼 내밀며, 맨 아래 카드는 책상 끝보다 1n+1\frac{1}{n+1}만큼 내밉니다. 아래 그림은 이를 나타냅니다.

입력

입력은 하나 이상의 테스트 케이스로 이루어지며, 마지막에는 입력의 끝을 알리는 0.00 한 줄이 옵니다. 각 테스트 케이스는 양의 실수 cc 하나가 적힌 한 줄이며, cc의 값은 0.010.01 이상 5.205.20 이하이고 항상 유효숫자 세 자리(X.YZ 형태)를 가집니다.

출력

각 테스트 케이스마다, 내민 길이가 cc 카드 길이 이상이 되도록 하는 데 필요한 최소 카드 수를 출력합니다. 테스트 케이스마다 한 줄씩, 정확히 N card(s) 형태로 출력하세요. 여기서 N은 그 최소 카드 수입니다.

예제1

  1. 예제 1

    입력
    1.00
    3.71
    0.04
    5.19
    0.00
    
    예상 출력
    3 card(s)
    61 card(s)
    1 card(s)
    273 card(s)