using System; using System.Collections; using System.Collections.Generic; using System.Drawing; namespace PaperFoldingLargestRegion { class Program { static void Main(string[] args) { long[] a = new long[1 + 2 * N]; for (int x = 0; x < Max; x++) { for (int y = 0; y < Max; y++) { if (!visited[x][y]) { Point p = new Point(x, y); long t = 0; Queue<Point> visiting = new Queue<Point>(); visiting.Enqueue(p); visited[p.X][p.Y] = true; while (visiting.Count > 0) { t++; foreach (Point q in SquareNeighbours(visiting.Dequeue())) { if (!visited[q.X][q.Y]) { visiting.Enqueue(q); visited[q.X][q.Y] = true; } } } int r = Rank(p); a[r] = Math.Max(a[r], t); } } } for (int n = 0; n < a.Length; n++) { Console.WriteLine($"{n} {a[n]}"); } } static int Rank(Point p) { return 2 * Math.Max(bits[p.X], bits[p.Y]) - (bits[p.X] < bits[p.Y] ? 1 : 0); } static IEnumerable<Point> SquareNeighbours(Point p) { if (RightSquare(p)) { yield return new Point(p.X + 1, p.Y); } if (UpSquare(p)) { yield return new Point(p.X, p.Y + 1); } if (LeftSquare(p)) { yield return new Point(p.X - 1, p.Y); } if (DownSquare(p)) { yield return new Point(p.X, p.Y - 1); } } // Right - left - up - down square connected to square at p? static bool RightSquare(Point p) { return !Up(new Point(p.X + 1, p.Y)); } static bool LeftSquare(Point p) { return !Up(p); } static bool UpSquare(Point p) { return !Right(new Point(p.X, p.Y + 1)); } static bool DownSquare(Point p) { return !Right(p); } // Right - left - up - down point connected to point at p? static bool Right(Point p) { if (p.X < 0 || p.Y < 0) { return false; } else if (p.Y == 0) { return true; } else { return (p.X >> val2[p.Y]) % 2 != pf[p.Y]; } } static bool Left(Point p) { return Right(new Point(p.X - 1, p.Y)); } static bool Up(Point p) { if (p.X < 0 || p.Y < 0) { return false; } else if (p.X == 0) { return true; } else { return (p.Y >> (val2[p.X] + 1)) % 2 != pf[p.X]; } } static bool Down(Point p) { return Up(new Point(p.X, p.Y - 1)); } const int N = 14; // maximum number of double-folds const int Max = 1 << N; static readonly int[] val2 = new int[Max + 1]; // 2-adic valuation ~ A007814 static readonly int[] pf = new int[Max + 1]; // regular paper-folding sequence ~ A014577 with a leading 0 static readonly int[] bits = new int[Max + 1]; // number of bits ~ A070939 with a(0) = 0 static readonly BitArray[] visited = new BitArray[Max]; static Program() { val2[0] = int.MaxValue; pf[0] = 0; bits[0] = 0; for (int n = 1; n <= Max; n++) { int m = n; while (m % 2 == 0) { val2[n]++; m /= 2; } if ((m & 2) == 0) { pf[n] = 1; } if (n == 1) { bits[n] = 1; } else { bits[n] = 1 + bits[n / 2]; } } for (int x = 0; x < Max; x++) { visited[x] = new BitArray(Max); } } } }