Codeforces Round #219 (Div. 2) B. Making Sequences is Fun

6292 단어
B. Making Sequences is Fun
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
We'll define S(n) for positive integer n as follows: the number of the n's digits in the decimal base. For example,S(893) = 3, S(114514) = 6.
You want to make a consecutive integer sequence starting from number m (m, m + 1, ...). But you need to payS(n)·k to add the number n to the sequence.
You can spend a cost up to w, and you want to make the sequence as long as possible. Write a program that tells sequence's maximum length.
Input
The first line contains three integers w (1 ≤ w ≤ 1016), m (1 ≤ m ≤ 1016), k (1 ≤ k ≤ 109).
Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, coutstreams or the %I64d specifier.
Output
The first line should contain a single integer — the answer to the problem.
Sample test(s)
input 
9 1 1

output 
9

input 
77 7 7

output 
7

input 
114 5 14

output 
6

input 
1 1 2

output 
0

얼마나 전형적인 이분매거인가, 그러나 작은 세부 사항에 주의해야 한다.
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <set>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef unsigned long long LL ;

LL  dp[19] ;
LL  num[19] ;

void init(){
     num[1] = 1 ;
     for(int i = 2 ; i <= 19 ; i++)
        num[i] = num[i - 1] * 10 ;
     for(int i = 1 ; i <= 18 ; i++)
        dp[i] = i * (num[i+1] - num[i]) ;
}

LL get_all_S(LL x){
   LL sum = 0 ;
   int i ;
   for(i = 2 ; i <= 18 ; i++){
      if(x >= num[i])
        sum += dp[i-1] ;
      else
        break ;
   }
   sum += (i-1)*(x-num[i-1]+1) ;
   return sum ;
}

LL M ,W , K;

int judge(LL x){
    return W >= K*(get_all_S(x) - get_all_S(M-1)) ;
}

LL calc(){
    LL L ,R ,mid , ans = -1;
    L = M ;
    R = (LL)1000000000000000000 ;
    while(L <= R){
        mid = (L + R) >> 1 ;
        if(judge(mid)){
            ans = mid ;
            L = mid + 1 ;
        }
        else
            R = mid -1 ;
    }
    return ans==-1?0:ans - M + 1 ;
}

int main(){
    init() ;
    LL x ;
    while(cin>>W>>M>>K){
        cout<<calc()<<endl ;
    }
    return 0 ;
}

JS 마우스 우 클릭 으로 사용자 정의 목록
js 3 급 관련 메뉴 효과 인 스 턴 스

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage