Google Code Jam (GCJ) 2018

目前过了Practice Session 和 Qualification Round

2018-04-13 11:00 ::

Round 1A 爆炸??Round 1B仍然需要参加。三题AC了一题,TLE了一题,最后被另一题吓跑。

2018-04-07 21:16 ::

第二题当然会爆炸。。。当时想着Qualification肯定是简单的算法就可以过了,然后就用了两遍排序+一边检查=O(n log n) + O(n^2) + O(n).
标答给的是一个O(n log n)的,这题TLE并不奇怪。

2018-04-07 21:07 ::

更新:最终QR得分64…第二题的附加测试TLE,第四题XZ轴旋转OJ认为我是Wrong Answer,这个有时间我再研究一下。

反正25分就过了

2018-04-07 14:25 ::

先把代码放上来,解释什么的有空再说。
前三题用普通的解法应该可以过掉几乎所有测试点,最后一题不确定用二分迭代能不能不超时:(

前三题用的C++,可以看到第一题有竞赛专用秘制输入输出优化,最后一题采用Go语言编写.


以下是代码

标准程序模板代码

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    return 0;
}

Saving the universe again

#include <iostream>
#include <string>
using namespace std;

static const auto __________ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

string instr;

int strength()
{
    int res=0, cur=1;
    for (unsigned int i=0; i<instr.length(); i++) {
        if (instr[i] == 'S') res += cur;
        else cur*=2;
    }
    return res;
}

int switchlastcs()
{
    size_t pos;
    if ((pos = instr.rfind("CS"))!=string::npos) {
        instr[pos] = 'S';
        instr[pos+1] = 'C';
        return 0;
    } else {
        return 1; // not found
    }

}

string hack(int d)
{
    int s = strength();
    int res = 0;
    if (s <= d) {
        return "0";
    } else {
        while (s > d) {
            if (switchlastcs() != 1) {
                s = strength();
                res++;
            }
            else
                return "IMPOSSIBLE";
        }
    }
    return to_string(res);
}

int main()
{
    int t, d;
    string p, res;
    cin >> t; // t test cases
    for (int i=0; i<t; i++) {
        cin >> d >> instr;
        cout << "Case #" << i+1 << ": " << hack(d) << endl;
    }
}

Trouble Sort

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void TroubleSort(int arr[], int n)
{
    bool done = false;
    while (!done) {
        done = true;
        for (int i=0; i< n-2; i++) {
            if (arr[i] > arr[i+2]) {
                done = false;
                swap(&arr[i], &arr[i+2]);
            }
        }
    }
}

int main ()
{
    int t,n,tmp;
    cin >> t;
    for (int i=0; i<t; i++) {
        cin >> n;
        vector<int> v1, v2;
        bool ok = 1;
        for (int j=0; j<n; j++) {
            cin >> tmp;
            v1.push_back(tmp);
        }
        v2 = v1;
        std::sort(v1.begin(), v1.end());
        TroubleSort(v2.data(), n);
        for (int j=0; j<n; j++) {
            if (v1[j] != v2[j]) {
                cout << "Case #" << i+1 << ": " << j << endl;
                ok =0;
                break;
            }
        }
        if (ok == 1) cout << "Case #" << i+1 << ": OK" << endl;
    }
}

Go, Gopher!

#include <iostream>
#include <string>
#include <string.h>
using namespace std;
const int sx = 500;
const int sy = 500;
const int bounds20[4] = {498, 502, 497, 502};
const int bounds200[4] = {480, 520, 497, 502};
int bounds[4];
int gmap[41][6][2];
int trials = 0;

int trytgt(int cx, int cy)
{

    if(trials < 1000) {
        //cerr << "trial #" << trials << endl;
        cout << cx << " " << cy << endl;
        //cerr << "want " << cx << " " << cy << endl;
        cin >> cx >> cy;
        //cerr << "get " << cx << " " << cy << endl;
        if (cx == 0 && cy == 0) {
            return 0;
        }
        if (cx == -1 && cy == -1) {
            return -1;
        }
        if (gmap[cx-480][cy-497][0] == 0) {
            //cerr << "originally 0, processing" << endl;
            gmap[cx-480][cy-497][0] = 1;
            for (int i=-1; i<2; i++) {
                for (int j=-1; j<2; j++) {
                    if (cx+i < bounds[0] || cx+i >= bounds[1] || cy+j < bounds[2] || cy+j >= bounds[3]) {continue;}
                    gmap[cx-480+i][cy-497+j][1]++;
                }
            }
        }
        trials ++;
        return 1;
    } else {
        //cerr << "trials exceeded." << endl;
        return -1;
    }
}

int main()
{
    int t, a, cx, cy;
    cin >> t;
    for (int s=0; s<t; s++) {
        cin >> a;
        for (int i=0; i<4; i++) {
            if (a == 20) bounds[i] = bounds20[i];
            else if (a == 200) bounds[i] = bounds200[i];
            else cerr << "I was told a is just 20 or 200" << endl;
        }
        //fill(&gmap[0][0][0], &gmap[0][0][0] + sizeof(gmap), 0);
        memset(gmap, 0, sizeof(gmap));
        int bf = 0;
        trials = 0;
        for (cy=bounds[2]+1; cy<bounds[3]-1; cy+=2) {
            for (cx=bounds[0]+1; cx <bounds[1]-1; cx+= (cx == bounds[1]-3 ? 1 : 2)) {
                while(gmap[cx-480][cy-497][1] < 9) {
                    //cerr << "current value: " << gmap[cx-480][cy-497][1] << endl;
                    int ret = trytgt(cx, cy);
                    if (ret == 0) {
                        //cerr << "passed" << endl;
                        bf = 1;
                        break;
                    }
                    else if (ret == -1) {
                        bf = 1;
                        break;
                    }
                }
            }
            if (bf == 1) break;
        }

        //for (int i=0; i<5; i++) {
            //for (int j=0; j<40; j++) {
                //cerr << gmap[j][i][0] << " ";
            //}
            //cerr << endl;
        //}
    }
    return 0;
}

Cubic UFO

package main

import (
    "fmt"
    "math"
)

func turnz(area float64) []float64 {
    r := math.Asin(area/math.Sqrt2) - math.Pi/4
    return []float64{math.Cos(r) / 2, -math.Sin(r) / 2, 0, math.Sin(r) / 2, math.Cos(r) / 2, 0, 0, 0, 0.5}
}

// Point represent point in 3d space
type Point struct {
    x, y, z float64
}

// NewPoint initializer
func NewPoint(x, y, z float64) *Point {
    p := new(Point)
    p.x = x
    p.y = y
    p.z = z
    return p
}

func (p *Point) rotateX(angle float64) {
    if p.z == 0 && p.y == 0 {
        return
    }
    m := math.Sqrt(p.z*p.z + p.y*p.y)
    a := math.Atan2(p.z, p.y) + angle
    p.y = math.Cos(a) * m
    p.z = math.Sin(a) * m
}

func (p *Point) rotateZ(angle float64) {
    if p.x == 0 && p.y == 0 {
        return
    }
    m := math.Sqrt(p.y*p.y + p.x*p.x)
    a := math.Atan2(p.y, p.x) + angle
    p.x = math.Cos(a) * m
    p.y = math.Sin(a) * m
}

// Cube represents the unit 3d cube
type Cube struct {
    v [11]*Point
}

// NewCube initializer
func NewCube() *Cube {
    c := new(Cube)
    s := 0.5

    c.v[0] = NewPoint(-s, -s, -s)
    c.v[1] = NewPoint(+s, -s, -s)
    c.v[2] = NewPoint(+s, -s, +s)
    c.v[3] = NewPoint(-s, -s, +s)

    c.v[4] = NewPoint(-s, +s, -s)
    c.v[5] = NewPoint(+s, +s, -s)
    c.v[6] = NewPoint(+s, +s, +s)
    c.v[7] = NewPoint(-s, +s, +s)

    c.v[8] = NewPoint(s, 0, 0)
    c.v[9] = NewPoint(0, s, 0)
    c.v[10] = NewPoint(0, 0, s)

    return c
}

func (c *Cube) rotateX(angle float64) {
    for i := 0; i < 11; i++ {
        c.v[i].rotateX(angle)
    }
}

func (c *Cube) rotateZ(angle float64) {
    for i := 0; i < 11; i++ {
        c.v[i].rotateZ(angle)
    }
}

func (c *Cube) areaXZ() float64 {
    return math.Sqrt2 * (math.Abs(c.v[0].x-c.v[1].x) + math.Abs(c.v[5].x-c.v[2].x))
}

func iterapproach(area float64) *Cube {
    c := NewCube()
    c.rotateX(math.Pi / 4)

    min := 0.0
    max := math.Pi / 4

    carea := c.areaXZ()
    for math.Abs(carea-area) > 0.0000000001 {
        mid := (min + max) / 2
        c = NewCube()
        c.rotateX(math.Pi / 4)
        c.rotateZ(mid)
        carea = c.areaXZ()
        if carea < area {
            min = mid
        } else {
            max = mid
        }
    }
    return c
}

func main() {
    var t int
    fmt.Scanf("%d", &t)
    for s := 1; s <= t; s++ {
        var a float64
        fmt.Scanf("%f", &a)
        //fmt.Printf("%v\n", turn2d(a))
        if a < math.Sqrt2 && a >= 1 {
            res := turnz(a)
            fmt.Printf("Case #%d:\n%.9f %.9f %.9f\n%.9f %.9f %.9f\n%.9f %.9f %.9f\n", s, res[0], res[1], res[2], res[3], res[4], res[5], res[6], res[7], res[8])
        } else {
            res := iterapproach(a)
            fmt.Printf("Case #%d:\n%.9f %.9f %.9f\n%.9f %.9f %.9f\n%.9f %.9f %.9f\n", s, res.v[8].x, res.v[8].y, res.v[8].z, res.v[9].x, res.v[9].y, res.v[9].z, res.v[10].x, res.v[10].y, res.v[10].z)
        }
    }
}