progheal

#!/usr/bin/env python3
# encoding=UTF-8

# Minecraft CJK-IME patchfile generator (Minecraft 中文輸入更新檔產生程式) by LPH66 @ PTT (Minecraft IGN: proghealer)
#
# Version 0.6 probably final (2015/10/22)
#
# 適用範圍：Minecraft 1.6.4 ~ 1.8.8；但 snapshot/prerelease 版本不一定適用。
#
# 系統需求: python 3.x 執行環境。(關於 python 環境安裝等事項可至 python 官方網站查詢：https://www.python.org/ )

progheal

We'll prove that the number of color needed for input n is ceiling((n-1)^2/2), ie. this OEIS sequence with offset 1.

First we prove that this number is needed. To satisfy the condition, a square color should be different from all other squares in a specific range related to n. This range is the union of all retangles containing the initial square, and is a diamond shape centered at this square. For example, n=5 corresponding to this diamond shape:

progheal

For odd number of students, it's easy to construct a situation that all of them are king chicken:
Label them from 1 to n, every one pecks the (n-1)/2 students numbered after him (labels wrap around from n to 1).
In this case, for every people, those (n-1)/2 students pecked him is pecked by the last people he pecked.
For example, for 7 students (Test 4),
Student 1 pecks Student 2,3,4, and Student 4 pecks Student 5,6,7, make Student 1 king chicken;
Student 2 pecks Student 3,4,5, and Student 5 pecks Student 6,7,1, make Student 2 king chicken;
etc.

For even number of students, things get interesting:
n=2 is impossible for both of them to be king; one must peck the other.

progheal

Let's classify all the possible equilateral triangles of interest. As there are more equilateral triangles in the proof, let's call those we want to count the counting triangles.

For each of the counting triangle asked, define its enclosing triangle be the minimal upright equilateral triangle that goes alone the network. Here, upright means the triangle has one side being horizontal, and the third vertex is above the horizontal side. Later in the text, the term upside-down will appear, meaning the opposite of upright, ie. one side being horizontal but the third vertex is below the horizontal side.

For example, here are some counting triangles (red) and their enclosing triangle (blue). The second counting triangle is upside-down.

We classify counting triangles by the side length of its enclosing triangle, as this directly related to how many these triangles are there in the original network. If the network has side N, we can find the number of ways

progheal

Let's analyze all these digits. We classify the appearing position within the number it begins, with the rightmost being 1. For example, the 111 in 41118 is said to be at position 4, while the cross-number 777 between 72977 and 72978 is said to be at position 2. The input size is n.

000

Because 000 cannot cross number (no number starts with 0), the position of 000 is at least 3. For position p, the other digits of the number can be combined to count them; for example, numbers for n=5 and p=4 are 10000, 10001, 10002, ..., 90009, 100000; there are 100 - 10 + 1 = 91 of them.

It is easy to deduct that there's ways to have 000 in position p. Adds up all of these for p from 3 to n, we have
![(n-2)\times10^{n-3}-\sum_{p=3}^n 10^{p-3}+(n-2)=(n-2)\times10^{n-3}-\underset{n-2}{\underbrace{111\dots1}}+(n-2)](http://latex.codecogs.com/gif.latex?%28n-2%29%5

progheal

#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <tuple>
using namespace std;

// switch the comment below to see log printed to stderr
//#define LOGERR(x) x
#define LOGERR(x) 

progheal

為了讓 gist 的標題有點意義所以加的檔案

progheal

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <iterator>
#include <algorithm>
using namespace std;

progheal

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

struct Op
{
	int xm, xM, ym, yM, zm, zM, sw;
};

progheal

Let's start from our designated starting point, the "top left" of the first cube face, going right. This means we are going clockwise along the edge of the net.

We want to trace the edge and trying to match the "edge cells", which is represented by a cell, and its direction when we traversed them clockwisely. Using the sample as example, the first edge is (1,9,>). If the current edge does not match other edge, we simply push that into a stack.

We go along the edge, stopping every N times to determine which turn do we take on the net. This is done by going one step out and check myself and my left.