POJ 2661: AD HOC

POJ 2661: Factstone Benchmark

Description

Data

사고방식

AD HOC

구체적 분석

LOG2

AC!

Code

——AD HOC
원제 전송문
Description
Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word-size every ten years. (Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and a 4-bit computer, its first, in 1960.) Amtel will use a new benchmark - the Factstone - to advertise the vastly improved capacity of its new chips. The Factstone rating is defined to be the largest integer n such that n! can be represented as an unsigned integer in a computer word. Given a year y, what will be the Factstone rating of Amtel’s most recently released chip?
Data
Input There are several test cases. For each test case, there is one line of input containing y. A line containing 0 follows the last test case. Output For each test case, output a line giving the Factstone rating.

	Sample Input
	1960
	1981
	0
	Sample Output
	3
	8		

1960 <= y <= 2160
사고의 방향
좀 신기한 AD HOC 제목인 것 같은데?
AD HOC
잡문제(물문제)라고도 부르는데 사고방식(지능)을 시험하는 문제로 알고리즘과 구조는 스스로 고려해야 한다.이런 문제는 많이 하면 이해할 수 있으니 생각을 넓혀야 한다.
구체적 분석
이 문제는 2x와 y를 분석합시다!크기 관계.그중 4<=x<=212는 어색합니다.어쨌든 우리는 모두 총명하니까(lazy), 이 문제는 틀림없이 고정밀을 쓸 수 없을 거야!그렇지 않으면 정수 곱셈과 곱셈, 그리고 비교가 있다. 그래서 우리는 더블 유형으로 폭발 범위의 문제를 해결하는 것을 고려한다.
LOG2
설령 더블을 사용한다고 해도 우리는 직접 곱할 수 없다. 왜냐하면 더블의 정밀도는 개수를 보장할 수 없기 때문이다.그러나 본 문제는 정형(개위 이상의 부분)만 필요하다는 것을 알아차렸다.그래서 우리는 정밀도를 보장할 수 없는 부분을 소수로 옮길 수 있다.2x를 보면 바로 LOG2로 문제를 풀 수 있다!
AC!
여기까지 생각하니 확 트인다.우리는 2x를log(2x)=x로 바꾸어 2를 밑으로 대수를 얻는다.그래서 y!로그 (y!) =log(y)+log(y-1)+...+log(1)<=log(2x)=x 그래서 먼저 x를 계산한 다음에 i:1을 INF로 순환시키고 매번 S+=log(i)를 누적하면 S>x가 답이다.
Code

#include
#include
#include
using namespace std;
int main()
{
    int n;
    while (~scanf("%d",&n))
    {
        if (n==0) break;
        int i;
        double sum=0.,x;
        x=pow(2.,(n-1960)/10+2);
        for (i=1;x-sum>1e-5;i++) 
            sum+=log2(i);
        printf("%d
",i-2);
    }
    return 0;
    // Very Short
}

감사합니다.