인터넷 서비스 제공업체

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

요약
N과 C가 주어질 때 이차식 N*T*(C-T*N)의 총 이익을 최대화하는 가장 작은 정수 T를 구합니다 (N=0인 경우 예외 처리 포함).
난이도

쉬움10점 중 3점

유형
수학, 구현, 이분 탐색
정답자
아직 제출이 없습니다

문제

NN개의 인터넷 서비스 제공업체(ISP)가 초당 최대 용량이 CC 트래픽 단위인 전용 통신 채널을 함께 사용합니다. 모든 ISP는 채널을 통해 동일하게 초당 TT 트래픽 단위를 보내며, 각 ISP는 T (C−T N)T\,(C - T\,N)에 정비례하는 이익을 얻습니다. 따라서 NN개 ISP 전체의 총 이익은 N T (C−T N)N\,T\,(C - T\,N)에 비례합니다.

이 총 이익을 최대로 만드는 가장 작은 정수 TT의 값 ToptimT_{optim}을 구하세요. 여기서 NN, CC, TT, ToptimT_{optim}은 모두 정수입니다.

ISP가 하나도 없는 경우(N=0N = 0)에는 모든 TT에 대해 총 이익이 00이 되어 Toptim=0T_{optim} = 0입니다.

입력

입력은 여러 개의 독립적인 데이터 집합으로 이루어지며, 파일의 끝(EOF)까지 읽습니다. 각 데이터 집합은 공백으로 구분된 두 정수 NN과 CC (0≤N,C≤1090 \le N, C \le 10^9)로 이루어지며, 각각 ISP의 수와 채널 용량을 나타냅니다. 입력 데이터는 항상 올바릅니다.

출력

각 데이터 집합에 대해 입력과 같은 순서로 ToptimT_{optim}을 한 줄에 하나씩 출력합니다. 빈 줄은 출력하지 않습니다.

예제4

  1. 예제 1

    입력
    1 0
    0 1
    4 3
    2 8
    3 27
    25 1000000000
    
    예상 출력
    0
    0
    0
    2
    4
    20000000
    
  2. 예제 2

    입력
    0 0
    
    예상 출력
    0
    
  3. 예제 3

    입력
    1 1
    
    예상 출력
    0
    
  4. 예제 4

    입력
    1 3
    
    예상 출력
    1