codeforces 337C Quiz
생각: 욕심 + 쾌속 멱
분석:
1 문 제 는 이 사람의 가장 작은 점 수 를 찾 는 것 이다.
2 문제 의 데 이 터 는 매우 크 고 O (1) 의 알고리즘, 즉 공식 이 있 음 이 분명 하 다.
3. 우 리 는 n 개의 수 를 연속 적 인 k 개의 나무 로 나 누 는 것 을 고려 하여 x = n / k 를 설정 합 니 다. 그러면 우 리 는 x 단 연속 구간 에서 모든 단락 이 하 나 를 틀 리 게 한다 면 우 리 는 적어도 x * (k - 1) 를 맞 출 수 있 습 니 다. 지금 우 리 는 x * (k - 1) > = m 를 판단 할 수 있 습 니 다. 그렇다면 답 안 은 m 입 니 다.그렇지 않 으 면 나머지 문 제 는 t = n - x * k 와 나머지 문제 의 개 수 는 z = m - x * (k - 1) 로 판단 한다. 만약 t > = z 라면 ans 는 x * (k - 1) + z 이다. 그렇지 않 으 면 우 리 는 뒤의 틀린 개 수 를 가 져 와 야 한 다 는 것 을 알 고 있다. 그러면 우 리 는 가 져 온 개 수 를 구 할 수 있다.그러면 다음 에 연속 적 인 t + (t - z) * k 개 수의 점 수 를 구하 고 뒤의 한 단락 을 더 하면 됩 니 다.
코드:
#include
#include
#include
#include
using namespace std;
const int MOD = 1e9+9;
int n , m , k;
long long Pow(long long m , long long n){
long long ans = 1;
while(n){
if(n&1)
ans = (ans*m)%MOD;
m = (m*m)%MOD;
n >>= 1;
}
return ans;
}
long long getAns(){
int numk = n/k;
//
if(numk*(k-1) >= m)
return m;
int rest_n = n-k*numk;
int rest_m = m-numk*(k-1);
//
if(rest_m <= rest_n)
return (numk*(k-1)+rest_m)%MOD;
//
int t = rest_m-rest_n;
int num = rest_n+t*k;
long long ans = (numk-t)*(k-1)%MOD;
numk = num/k;
ans = (ans+num-numk*k)%MOD;
ans = ans + 2*(k*(Pow(2 , numk)-1))%MOD;
return ans%MOD;
}
int main(){
while(scanf("%d%d%d" , &n , &m , &k) != EOF){
printf("%lld
" , getAns());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
