ACM-ICPC国际大学生程序设计竞赛北京赛区(2015)网络赛H题2015-9-20

青旅半醒 2022-08-08 15:58 123阅读 0赞

\[PKu H题\] ([http://hihocoder.com/contest/acmicpc2015beijingonline/problem/8][http_hihocoder.com_contest_acmicpc2015beijingonline_problem_8])  
题目描述：  
题目8 : Fractal  
时间限制:1000ms  
单点时限:1000ms  
内存限制:256MB  
描述  
h.png

This is the logo of PKUACM 2016. More specifically, the logo is generated as follows:

1.  Put four points A0(0,0), B0(0,1), C0(1,1), D0(1,0) on a cartesian coordinate system.
2.  Link A0B0, B0C0, C0D0, D0A0 separately, forming square A0B0C0D0.
3.  Assume we have already generated square AiBiCiDi, then square Ai+1Bi+1Ci+1Di+1 is generated by linking the midpoints of AiBi, BiCi, CiDi and DiAi successively.
4.  Repeat step three 1000 times.

![这里写图片描述][14426600132859.png]  
Now the designer decides to add a vertical line x=k to this logo( 0<= k < 0.5, and for k, there will be at most 8 digits after the decimal point). He wants to know the number of common points between the new line and the original logo.

输入  
In the first line there’s an integer T( T < 10,000), indicating the number of test cases.

Then T lines follow, each describing a test case. Each line contains an float number k, meaning that you should calculate the number of common points between line x = k and the logo.

输出  
For each test case, print a line containing one integer indicating the answer. If there are infinity common points, print -1.

样例输入  
3  
0.375  
0.001  
0.478  
样例输出  
\-1  
4  
20  
此题为水题，正确率一直是百分之九十以上，飙高不下，主要就是体用数学的方法来实现，当用x=k这条直线去截一个由1000个正方形的”枚绿“图案，并计算交点问题，特别的1：当交点有n多个时，直接输出“-1”，则可以把所有的正方形分成奇数个和偶数个，打表记录下来与y轴平行的交点可能有n多个的偶数个正方形边界的坐标，并用k和其比较即可；特别的2：表中第999个正方形为奇数个，按正常应该是不用管，但是，k有等于0.5的情况，所以经过计算k=0.5时，交点恰为1000个，特殊处理一下即可。  
代码实现如下：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    int main()
    {
        double a[1005];
        int T;
        double k;
        memset(a,0,sizeof(a));
        a[0]=0.0;
        a[999]=0.5;
        for(int i=2; i<1000; i+=2)
        {
            a[i]=(a[i-2]+0.5)/2;
        }
        scanf("%d",&T);
        while(T--)
        {
            scanf("%lf",&k);
            if(k==0.5) printf("1000\n");
            else
            {
                for(int i=0; i<999; i+=2)
                {
                    if(k>a[i]&&k<a[i+2])
                    {
                        printf("%d\n",(i+2)*2);
                        break;
                    }
                    if(k==a[i])
                    {
                        printf("-1\n");
                        break;
                    }
                }
            }
        }
        return 0;
    }

[http_hihocoder.com_contest_acmicpc2015beijingonline_problem_8]: http://hihocoder.com/contest/acmicpc2015beijingonline/problem/8
[14426600132859.png]: /images/20220731/c6a96569bcfb4e30b6f9989b58a176a4.png