알고리즘 훈련 원숭이 사과 나 누 기
가을 이 되자 n 마리 의 원숭이 가 사 과 를 한 무더기 따 서 동굴 에 넣 고 다음날 똑 같이 나 누 기로 약속 했다.이 원숭이 들 은 원숭이 왕 손오공 을 매우 숭배 하기 때문에 모두 그 에 게 사 과 를 좀 남 겨 주 고 싶 어한 다.첫 번 째 원숭이 는 몰래 동굴 로 와 서 사 과 를 평균 n 개 로 나 누 어 남 은 m 개의 사 과 를 먹고 한 개 를 숨 겼 다가 남 은 사 과 를 다시 합 쳤 다.이 원숭이 들 은 차례대로 동굴 로 몰래 와 서 똑 같은 조작 을 하 는데 마침 매번 사과 m 개가 남 았 다.다음날 이 원숭이 들 은 동굴 에 와 서 남 은 사 과 를 n 으로 나 누 었 는데 공교롭게도 m 개가 남 았 다.원래 이 원숭이 들 은 적어도 몇 개의 사 과 를 땄 느 냐 고 물 었 다.
입력 형식
두 개의 정수, n m
출력 형식
하나의 정수 는 원래 사과 의 수 를 나타 낸다.
샘플 입력
5 1
샘플 출력
15621
데이터 규모 와 약정
0
사과 총 수 를 x 로 설정 할 수 있 고 전체 수량 에 (n - 1) * m 개의 사과 로 y = x + (n - 1) * m 를 추가 할 수 있 습 니 다.첫 번 째 원숭이 는 m 개의 사 과 를 먹고 (x - m) * (1 / n) 개 를 숨 겼 다. 즉, 첫 번 째 원숭이 는 모두 y * (1 / n) 개의 사 과 를 가 져 갔 고 사 과 는 남 았 다 (n - 1) / n * y 를 남 겼 다.(스스로 머리 를 써 서 먹고 입 는 것 이 풍족 하 다.) 원숭이 한 마 리 를 추가 했다 고 가정 할 수 있다.
공식: x = (n ^ n+1) - ((n - 1) * m)
#include <stdio.h>
int main()
{
int n,m, p, t, sum;
scanf("%d%d", &n, &m);
t = n+1;
p = 1;
while(t -- > 0){
p *= n;
}
sum = p - ((n - 1 ) * m);
printf("%d", sum);
return 0;
}
그러나 OJ 의 첫 번 째 테스트 데이터 가 잘못 되 어 다음 날 원숭이 들 이 사 과 를 n 부 로 나 눌 때 1 부 는 적어도 1 개 이기 때문에 이 문 제 는 100% 정확 하지 않다.
정정 후 공식 은 x = k (n ^ n + 1) - (n - 1) * m)
정정 후 해제
#include <stdio.h>
int main()
{
int n,m, o, p, k, t, sum;
scanf("%d%d", &n, &m);
t = n+1;
p = 1;
o = 1;
k = 1;
while(t -- > 0){
p *= n;
o *= (n-1);
}
o /= (n-1);
while(o < m+1){
k ++;
p *= k;
o *= k;
}
sum = p - ((n - 1 ) * m);
printf("%d", sum);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.