Google Code Jam 2018: Qualification Round

曾经终败给现在 2022-05-27 00:59 171阅读 0赞

资格赛，除了最后一题比较有趣以外，其他都比较简单

## Saving The Universe Again ##

贪心  
一开始想着尽可能将S往前移，但是想了想觉得这样移动好多次，可能才等于后面的S往前移一位的成果。  
所以就变成尽可能地将C往末尾移（末尾一段连续的C就不用考虑了），即，每一次移动减少的伤害最大。

int T,n;
    vi a1,a2;
    
    int main()
    {
        cin>>T;
        int cases = 1;
        while(T--)
        {
            cin>>n;
            a1.clear();
            a2.clear();
            for(int i = 0, x; i < n; i++)
            {
                cin>>x;
                if(i&1)
                    a2.pb(x);
                else
                    a1.pb(x);
            }
            sort(a1.begin(),a1.end());
            sort(a2.begin(),a2.end());
            int ans = -1;
            for(int i = 0; i < n-1; i++)
            {
                if(i&1)
                {
                    if(a2[i/2]>a1[i/2+1] && ans==-1)
                    {
                        ans = i;
                        break;
                    }
                }
                else
                {
                    if(a1[i/2]>a2[i/2] && ans==-1)
                    {
                        ans = i;
                        break;
                    }
                }
            }
            if(ans == -1)
                printf("Case #%d: OK\n", cases);
            else
                printf("Case #%d: %d\n", cases, ans);
            cases++;
        }
        return 0;
    }

## Trouble Sort ##

想法一：

实现两种排序，比较，复杂度O(N2)  O ( N 2 )

想法二：

因为Trouble Sort仅会在奇数位和奇数位或偶数位和偶数位交换，所以将奇偶分开来排序，按顺序比较大小即可。

int main()
    {
        speed
        int T, cases = 1;
        ll D, a[33];
        string str;
        cin >> T;
        while (T--)
        {
            cin >> D >> str;
            int n = str.size();
            ll sum = 0;
            int c = 0;
            ll tot = 0;
            for(int i = 0; i < n; i++)
            {
                a[i] = -1;
                if(str[i] == 'C')
                    c++;
                else
                {
                    a[i] = (1ll << c);
                    sum += a[i];
                    tot++;
                }
            }
            cout << "Case #" << cases++ << ": ";
            if(tot > D)
            {
                cout << "IMPOSSIBLE" << endl;
            }
            else
            {
                int ans = 0;
                while(sum > D)
                {
                    for(int i = n-1; i > 0; i--)
                    {
                        if (a[i-1] == -1 && a[i] > -1)
                        {
                            a[i] >>= 1;
                            sum -= a[i];
                            swap(a[i - 1], a[i]);
                            break;
                        }
                    }
                    ans++;
                }
                cout << ans << endl;
            }
        }
        return 0;
    }

## Go, Gopher! ##

除了题目长一些，就是乱搞题

方法就是以3∗3  3 ∗ 3 的正方形，构造大矩形。

可以按标的方法，做一个3∗3×23  3 ∗ 3 × 23 的一行矩形。也可以像这里一样做一个15×15  15 × 15 的矩形。

按照200个可以投1000次，命中率是20%  20 % ，所以每一个3∗3  3 ∗ 3 的正方形只要投8次就行。最后再补缺补漏一下即可。

const int MAXN = 1010;
    
    bool p[MAXN][MAXN];
    int num[MAXN][MAXN];
    int dx[3] = {
       1, 0, -1};
    int dy[3] = {
       1, 0, -1};
    
    int main()
    {
        int T, a, n, x, y;
        read(T);
        while(T--)
        {
            CLR(p, 0);
            CLR(num, 0);
            read(a);
            if(a == 20)
                n = 6;
            else
                n = 15;
            printf("%d %d\n", 2, 2);
            fflush(stdout);
            while(read(x) && read(y))
            {
                if((x == 0 && y == 0) || (x == -1 && y == -1))
                    break;
                x--, y--;
                if(!p[x][y])
                {
                    p[x][y] = true;
                    num[x / 3][y / 3]++;
                }
                bool flag = true;
                for(int i = 0; i < n / 3 && flag; i++)
                    for(int j = 0; j < n / 3 && flag; j++)
                        if(num[i][j] < 8)
                        {
                            printf("%d %d\n", i * 3 + 2, j * 3 + 2);
                            flag = false;
                        }
                for(int i = 1; i < n - 1 && flag; i++)
                    for(int j = 1; j < n - 1 && flag; j++)
                    {
                        int c = 0;
                        for(int k = 0; k < 3; k++)
                            for(int d = 0; d < 3; d++)
                            {
                                int xx = i + dx[k], yy = j + dy[d];
                                c += p[xx][yy];
                            }
                        if(c < 9)
                        {
                            printf("%d %d\n", i + 1, j + 1);
                            flag = false;
                        }
                    }
                fflush(stdout);
            }
        }
        return 0;
    }

## Cubic UFO ##

超级有意思的题目

首先，你先在Y轴旋转45°  45 ° ，然后再二分求出X轴如何旋转能够使得投影面积最大。之后就可以二分了。

一开始觉得是暴力枚举精度，但是最后没卡过去；后来用了三分套三分，应该是找不到投影面积最大的点，也挂了。

投影面积就是用线性代数算一下投影的点坐标，然后用凸包求面积。

但是最有意思的就是[The cube shadow theorem (pt.1): Prince Rupert’s paradox][The cube shadow theorem _pt.1_ Prince Rupert_s paradox]：unit cube的垂直投影面积和它的上下高度差相等。

这样就可以忽略一大堆代码，直接得出结论，美滋滋啊。

typedef long double Double;
    typedef pair<Double,Double> dd;
    #define Dsin sinl
    #define Dcos cosl
    #define Datan2 atan2l
    #define Dhypot hypotl
    #define Dfabs fabsl
    
    typedef vector<Double> Coord;
    
    vector<Coord> corners(8, Coord(3));
    
    const Double PI = 3.14159265358979323846;
    
    inline Double deg2rad(Double deg)
    {
        return deg * PI / 180.0;
    }
    inline Double rad2deg(Double rad)
    {
        return rad / PI * 180.0;
    }
    
    void _init()
    {
        int _corners[8][3] =
        {
            {
       1, 1, 1}, {
       1, -1, 1}, {-1, -1, 1}, {-1, 1, 1},
            {
       1, 1, -1}, {
       1, -1, -1}, {-1, -1, -1}, {-1, 1, -1}
        };
    
        for(int c = 0; c < 8; c++)
            for(int i = 0; i < 3; i++)
                corners[c][i] = 0.5 * _corners[c][i];
    }
    
    inline Coord dot(Double R[][3], Coord& x)
    {
        Coord y(3, 0.0);
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                y[i] += R[i][j] * x[j];
        return y;
    }
    
    Coord _rx(Coord& p, Double th)
    {
        Double R[3][3];
        R[0][0] = 1;
        R[0][1] = 0;
        R[0][2] =  0;
        R[1][0] = 0;
        R[1][1] = Dcos(th);
        R[1][2] = -Dsin(th);
        R[2][0] = 0;
        R[2][1] = Dsin(th);
        R[2][2] =  Dcos(th);
        return dot(R, p);
    }
    
    Coord _ry(Coord& p, Double th)
    {
        Double R[3][3];
        R[0][0] =  Dcos(th);
        R[0][1] = 0;
        R[0][2] = Dsin(th);
        R[1][0] =  0;
        R[1][1] = 1;
        R[1][2] = 0;
        R[2][0] = -Dsin(th);
        R[2][1] = 0;
        R[2][2] = Dcos(th);
        return dot(R, p);
    }
    
    Coord _rz(Coord& p, Double th)
    {
        Double R[3][3];
        R[0][0] = Dcos(th);
        R[0][1] = -Dsin(th);
        R[0][2] = 0;
        R[1][0] = Dsin(th);
        R[1][1] =  Dcos(th);
        R[1][2] = 0;
        R[2][0] = 0;
        R[2][1] =  0;
        R[2][2] = 1;
        return dot(R, p);
    }
    
    inline dd vec(dd& a, dd& b)
    {
        return dd(b.first - a.first, b.second - a.second);
    }
    inline Double outer(dd& u, dd& v)
    {
        return u.first * v.second - v.first * u.second;
    }
    inline Double vlen(dd& v)
    {
        return Dhypot(v.first, v.second);
    }
    
    inline Double ccw(dd& p1, dd& p2, dd& p3)
    {
        return (p2.first - p1.first)*(p3.second - p1.second)
               - (p2.second - p1.second)*(p3.first - p1.first);
    }
    
    template<typename T>
    vector<T> _uniq(vector<T>& v)
    {
        set<T> tmp(ALL(v));
        return vector<T>(ALL(tmp));
    }
    
    inline bool dd_eq(dd& p, dd& q)
    {
        dd pq = vec(p, q);
        return vlen(pq) < eps;
    }
    
    vector<dd> uniq(vector<dd>& v)
    {
        sort(v.begin(), v.end());
        vector<dd> res;
        res.pb(v[0]);
        for (int i=1; i<v.size(); ++i)
        {
            if (!dd_eq(v[i], res.back()))
            {
                res.pb(v[i]);
            }
        }
        return res;
    }
    
    vector<dd> convex_hull(vector<dd>& points_orig)
    {
        vector<dd> points = uniq(points_orig);
        int N = points.size();
    
        Double ymin = 1e9, xmin = 1e9;
        int at = -1;
        for(int i = 0; i < N; i++) ymin = min(ymin, points[i].second);
        for(int i = 0; i < N; i++)
        {
            if (points[i].second == ymin)
            {
                if (points[i].first < xmin)
                {
                    xmin = points[i].first;
                    at = i;
                }
            }
        }
        vector<pair<Double, dd>> tmp(N);
        for(int i = 0; i < N; i++)
        {
            Double th;
            if (i != at)
                th = Datan2(points[i].second - ymin, points[i].first - xmin);
            else
                th = -1e9;
            tmp[i] = make_pair(th, points[i]);
        }
        sort(tmp.begin(), tmp.end());
        assert(tmp[0].second == dd(xmin, ymin));
    
        vector<dd> pts(N+1);
        for(int i = 0; i < N; i++) pts[1+i] = tmp[i].second;
        pts[0] = pts[N];
    
        int M = 1;
        for (int i=2; i<=N; ++i)
        {
            while (ccw(pts[M-1], pts[M], pts[i]) <= 0)
            {
                if (M > 1)
                {
                    --M;
                    continue;
                }
                else if (i == N)
                {
                    break;
                }
                else
                {
                    ++i;
                }
            }
            ++M;
            swap(pts[M], pts[i]);
        }
    
        if (M < pts.size())
        {
            pts.erase(pts.begin()+M, pts.end());
        }
    
        return pts;
    }
    
    Double convex_hull_area(vector<dd>& hull)
    {
        int N = hull.size();
        dd m(0, 0);
    
        Double area = 0;
        for(int i = 0; i < N; i++)
        {
            dd p = hull[i], q = hull[(i+1)%N];
            area += 0.5 * Dfabs(outer(p, q));
        }
        return area;
    }
    
    void render_ans(Double th_x, Double th_z)
    {
        for(int c = 0; c < 3; c++)
        {
            Coord p(3, 0);
            p[c] = 0.5;
            Coord r1 = _rx(p, th_x);
            Coord r2 = _rz(r1, th_z);
            printf("%.16Lf %.16Lf %.16Lf\n", r2[0], r2[1], r2[2]);
        }
    }
    
    Double rotated_shadow_area(Double th_x, Double th_z)
    {
        vector<dd> points;
    
        for(int c = 0; c < 8; c++)
        {
            Coord r1 = _rx(corners[c], th_x);
            Coord r2 = _rz(r1, th_z);
            points.pb( dd(r2[0], r2[2]) );
        }
    
        vector<dd> hull = convex_hull(points);
        Double area = convex_hull_area(hull);
    
        return area;
    }
    
    void solve(double A)
    {
        Double alpha, beta_min, beta_max;
        if (A < 1.0)
        {
            assert(false);
        }
        else if (A <= sqrt(2.0))
        {
            alpha = 0;
            beta_min = 0;
            beta_max = deg2rad(45);
        }
        else
        {
            alpha = deg2rad(45);
            beta_min = 0;
            beta_max = deg2rad(35.26438902);
        }
    
        Double lo = beta_min, hi = beta_max, mi;
        Double f_lo = rotated_shadow_area(alpha, lo);
        Double f_hi = rotated_shadow_area(alpha, hi);
        Double f_mi;
        for(int i = 0; i < 100; i++)
        {
            mi = (lo + hi) / 2;
            f_mi = rotated_shadow_area(alpha, mi);
            if (A < f_mi)
            {
                hi = mi;
            }
            else
            {
                lo = mi;
            }
        }
    
        render_ans(alpha, mi);
    
    }
    
    int main()
    {
        _init();
    
        int T;
        cin >> T;
        for (int t=1; t<=T; ++t)
        {
            double A;
            cin >> A;
            printf("Case #%d:\n", t);
            solve(A);
        }
        return 0;
    }

[The cube shadow theorem _pt.1_ Prince Rupert_s paradox]: https://www.youtube.com/watch?v=rAHcZGjKVvg