เฉลยโจทย์ hyperhackathon ครั้งที่ 2

เนื่องจาก ในวันที่ 25 พฤษภาคม 2557 ที่ผ่ามมา มีการแข่งขัน เขียนโปรแกรม hyperhackathon ที่โรงแรม Swissôtel Le Concorde รัชดา ผมจึงขอเฉลยโจทย์ Part แรก ในส่วนของ Algorithm ครับ ไม่ถูกต้องยังไง บอกกล่าวได้นะครับ http://www.hyperhackathon.com/

โจทย์ชุดที่ 1

ข้อ 1.1 - 1.2

for(int i=2;i< MAX_NUM ; i ++)
{
	boolean isPrime = true;
	for(int j=0;j< prime.size() ; j ++)
	{
		if(i % prime.get(j) == 0)
		{
			isPrime= false;
			break;
		}
	}
	if(isPrime)
	{
		prime.add(i);
	}
}

ข้อ 1.3 - 1.4

int n = INPUT;
BigInteger x = BigInteger.ONE;
for (int i = 1; i <= n; i++)
{
	x = x.multiply(new BigInteger("" + i));
}
String s = x.toString(10);
int sum = 0;
for (int i = 0; i < s.length(); i++)
{
	int xx =  (int)(s.charAt(i)-48);
	sum += xx;
}
System.out.println(sum);

ข้อ 2.1-2.2

for (int j = 0; j < prime.size(); j++)
{
	int k = prime.get(j);
	if (prime.contains(n - k))
	{
		System.out.println(n + " = " + k + "+" + (n - k));
		return;
	}
}
System.out.println("Sorry !!!!!");

n=3

--x--
-x-x-
x-x-x
-x-x-
--x--

n=4

---x---
--x-x--
-x---x-
x--x--x
-x---x-
--x-x--
---x---

n=5

----x----
---x-x---
--x---x--
-x-----x-
x---x---x
-x-----x-
--x---x--
---x-x---
----x----

ข้อ 3

Scanner sc = new Scanner(new File("grid/grid_x_" + testcase_count + ".txt"));
			PrintWriter pw = new PrintWriter(new File("grid/grid_x_out_" + testcase_count + ".txt"));
			int T = sc.nextInt();
			sc.nextLine();

			for (int innerCase = 0; innerCase < T; innerCase++)
			{
				int N = sc.nextInt();
				sc.nextLine();
				int[][] g = new int[N][N];
				int i = 0;
				while (sc.hasNext() && i < N)
				{
					String s = sc.nextLine();
					String ss[] = s.split(" ");
					for (int j = 0; j < N; j++)
					{
						g[i][j] = Integer.parseInt(ss[j]);
					}

					i++;
				}
				
				
				
				 System.out.println(52 + 68 + 60 + 06);
				int max = 0;
				int min = Integer.MAX_VALUE;
				for (i = 0; i < N; i++)
				{
					for (int j = 0; j < N - 3; j++)
					{
						int n = g[i][j] + g[i][j + 1] + g[i][j + 2] + g[i][j + 3];
						if (n > max)
						{
							max = n;
						}
						if (n < min)
						{
							min = n;
						}
					}
				}

				for (int j = 0; j < N; j++)
				{
					for (i = 0; i < N - 3; i++)
					{

						int n = g[i][j] + g[i + 1][j] + g[i + 2][j] + g[i + 3][j];
						if (n > max)
						{
							max = n;
						}
						if (n < min)
						{
							min = n;
						}
					}
				}

				for (int j = 0; j < N - 3; j++)
				{
					for (i = 0; i < N - 3; i++)
					{

						int n = g[i][j] + g[i + 1][j + 1] + g[i + 2][j + 2] + g[i + 3][j + 3];
						if (n > max)
						{
							max = n;
						}
						if (n < min)
						{
							min = n;
						}
					}
				}

				for (int j = 3; j < N; j++)
				{
					for (i = 0; i < N - 3; i++)
					{

						int n = g[i][j] + g[i + 1][j - 1] + g[i + 2][j - 2] + g[i + 3][j - 3];
						if (n > max)
						{
							max = n;
						}
						if (n < min)
						{
							min = n;
						}
					}
				}

				System.out.print("max = " + max + "\t");
				System.out.println("min = " + min);

				
				pw.println("testcase " + (innerCase + 1) + " : " + "max = " + max + "\t" + "min = " + min);
			}
			pw.close();
			sc.close();

ข้อ 4

xxxxxxxxxxxxxxxxxxxx
x       x x        x
x       x x        x
x       x x        x
x    xxxx x        x
x    x    xxxxxxxxxx
x    x    x        x
x    x    x        x
x    xxxxxxxxxxxxxxx
x    x     x       x
x  xxx     x       x
xxxx       x       x
x          x       x
xxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxx
x       x x        x
x       x x        x
x       x x    32  x
x    xxxx x        x
x 47 x    xxxxxxxxxx
x    x 16 x  16    x
x    x    x        x
x    xxxxxxxxxxxxxxx
x    x     x       x
x  xxx     x       x
xxxx   27  x  28   x
x          x       x
xxxxxxxxxxxxxxxxxxxx

ตัวอย่าง 2
xxxxxxxxxx
x   x  x x
x   x  x x
x   x  x x
x        x
xxxxxxxxxx

มี 1 ห้อง ขนาดใหญ่ สุด คือ 26

ตัวอย่าง

2
14 20
xxxxxxxxxxxxxxxxxxxx
x       x x        x
x       x x        x
x       x x        x
x    xxxx x        x
x    x    xxxxxxxxxx
x    x    x        x
x    x    x        x
x    xxxxxxxxxxxxxxx
x    x     x       x
x  xxx     x       x
xxxx       x       x
x          x       x
xxxxxxxxxxxxxxxxxxxx
5 5
xxxxx
x   x
x xxx
x x x
xxxxx

ตอบ
case 1 : 6 47
case 2 : 2 5

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class mazeSolver
{

	public static void main(String[] args) throws FileNotFoundException
	{
		for (int count_x = 1; count_x <= 4; count_x++)
		{
			int number_test = count_x;
			PrintWriter pw = new PrintWriter(new File("maze/maze_" + number_test + "_out.txt"));
			ArrayList<Integer[][]> allInput = readFile("maze/maze_" + number_test + ".txt");
			for (int i = 0; i < allInput.size(); i++)
			{
				int result[] = new int[2];
				solver(allInput.get(i), result);
				System.out.println("number_test "+
				number_test+"num = " + result[0] + " max = " + result[1]);
				pw.println("case " + (i + 1) + " : " + "num = " + result[0] + " max = " + result[1]);
			}
			pw.close();
		}
	}

	public static void solver(Integer[][] maze, int[] result)
	{
		ArrayList<Integer> countList = new ArrayList<Integer>();
		for (int i = 0; i < maze.length; i++)
		{
			for (int j = 0; j < maze[i].length; j++)
			{
				if (maze[i][j] == 0)
				{
					int r = countRoomSize(maze, new MazePoint(j, i), countList.size() + 1);
					countList.add(r);
				}
			}
		}

		int max = 0;
		for (int i = 0; i < countList.size(); i++)
		{
			if (countList.get(i) > max)
			{
				max = countList.get(i);
			}
		}
		result[0] = countList.size();
		result[1] = max;

	}

	public static int countRoomSize(Integer[][] maze, MazePoint start, int num)
	{
		int count = 0;
		Queue<MazePoint> q = new LinkedList<MazePoint>();
		q.add(start);

		while (q.size() > 0)
		{
			MazePoint p = q.poll();
			count++;
			maze[p.y][p.x] = num;

			if (p.y > 0 && maze[p.y - 1][p.x] == 0)
			{
				q.add(new MazePoint(p.x, p.y - 1));
				maze[p.y - 1][p.x] = -100;
			}

			if (p.x > 0 && maze[p.y][p.x - 1] == 0)
			{
				q.add(new MazePoint(p.x - 1, p.y));
				maze[p.y][p.x - 1] = -100;
			}

			if (p.x < maze[0].length - 1 && maze[p.y][p.x + 1] == 0)
			{
				q.add(new MazePoint(p.x + 1, p.y));
				maze[p.y][p.x + 1] = -100;
			}

			if (p.y < maze.length - 1 && maze[p.y + 1][p.x] == 0)
			{
				q.add(new MazePoint(p.x, p.y + 1));
				maze[p.y + 1][p.x] = -100;
			}
		}
		return count;
	}

	public static ArrayList<Integer[][]> readFile(String path) throws FileNotFoundException
	{
		Scanner sc = new Scanner(new File(path));
		ArrayList<Integer[][]> allInput = new ArrayList<Integer[][]>();
		sc.nextLine();
		for (; sc.hasNext();)
		{
			int n = sc.nextInt();
			int m = sc.nextInt();
			sc.nextLine();
			Integer[][] maze = new Integer[n][m];

			for (int i = 0; i < n; i++)
			{
				String l = sc.nextLine();
				for (int j = 0; j < m; j++)
				{
					if (l.charAt(j) == 'x')
						maze[i][j] = -1;
					else
						maze[i][j] = 0;
				}
			}
			allInput.add(maze);
		}

		sc.close();
		return allInput;
	}
}

class MazePoint
{
	public int x, y;

	public MazePoint()
	{
	}

	public MazePoint(int xx, int yy)
	{
		x = xx;
		y = yy;
	}
}

			int a[];
			int b[];
			boolean visited[];
			int T;
			int t = 0;
			// Scanner sc = new Scanner(new File("sillysort_in.txt"));
			// PrintWriter out = new PrintWriter(new File("sillysort_out.txt"));
			//

			Scanner sc = new Scanner(new File("cat/in_" + count_x + ".txt"));
			PrintWriter out = new PrintWriter(new File("cat/out_" + count_x + ".txt"));
			T = sc.nextInt();
			sc.nextLine();
			for (t = 1; t <= T; t++)
			{
				int N = sc.nextInt();
				sc.nextLine();
				a = new int[N];
				b = new int[N];
				visited = new boolean[N];

				String s = sc.nextLine();
				String ss[] = s.split(" ");

				for (int i = 0; i < N; i++)
				{
					a[i] = Integer.parseInt(ss[i]);
					b[i] = a[i];
					visited[i] = false;
				}

				Arrays.sort(b);
				HashMap<Integer, Integer> place = new HashMap<Integer, Integer>();

				for (int i = 0; i < N; ++i)
				{
					place.put(b[i], i);
				}

				int res = 0;
				for (int i = 0; i < N; ++i)
				{
					if (visited[i] == false)
					{
						if (place.get(a[i]) == i)
						{
							visited[i] = true;
							continue;
						}
						// 
						int min_val = a[i];
						int num = 0;
						int sum = 0;
						int j = i;

						while (visited[j] == false)
						{
							sum += a[j];
							num++;
							if (a[j] < min_val)
							{
								min_val = a[j];
							}
							visited[j] = true;
							j = place.get(a[j]);
						}
						sum -= min_val;
						res += sum + min_val * (num - 1);

						if (2 * (b[0] + min_val) < (min_val - b[0]) * (num - 1))
						{
							res -= (min_val - b[0]) * (num - 1) - 2 * (b[0] + min_val);
						}
					}
				}
				out.printf("Case %d: %d\n", t, res);

			}

			out.close();
			sc.close();