algorithm bee maja - andstudy/forge GitHub Wiki

CynicJJ

ModuleMain.vb

    Public Module ModuleMain
    
    	Sub Main()
    		While True
    			Console.WriteLine(Run(Console.ReadLine()))
    		End While
    	End Sub
    
    	Function Run(ByVal input As String) As String
    		Dim willi As Integer
    		Try
    			willi = Integer.Parse(input)
    		Catch ex As Exception
    
    		End Try
    
    		If willi <= 0 Or willi >= 100000 Then Return Nothing
    
    		Dim hive As New BeeHive()
    		Dim maja() As Integer = hive.GetMaja(willi)
    
    		Return maja(0).ToString() + " " + maja(1).ToString
    	End Function
    
    End Module

!BeeHive.vb

    Public Class BeeHive
    
    	Sub New()
    		CreateConvertTable()
    	End Sub
    
    	Private _table As New List(Of List(Of Integer))
    	Private _willi As Integer
    
    	Sub CreateConvertTable()
    		_table.Clear()
    		_willi = 0
    
    		AddToTable(-1, -1)	 ' dummy
    
    		Dim level = 0
    
    		Dim x As Integer = 0
    		Dim y As Integer = 0
    		AddToTable(x, y)
    
    		While _willi < 100000
    			level += 1
    
    			y += 1
    			AddToTable(x, y)
    
    			While x > 0
    				x -= 1
    				y += 1
    				AddToTable(x, y)
    			End While
    
    			While x > -level
    				x -= 1
    				AddToTable(x, y)
    			End While
    
    			While y > 0
    				y -= 1
    				AddToTable(x, y)
    			End While
    
    			While y > -level
    				x += 1
    				y -= 1
    				AddToTable(x, y)
    			End While
    
    			While x < level
    				x += 1
    				AddToTable(x, y)
    			End While
    
    			While y < 0
    				y += 1
    				AddToTable(x, y)
    			End While
    		End While
    	End Sub
    
    	Sub AddToTable(ByVal x As Integer, ByVal y As Integer)
    		Dim maja() As Integer = {x, y}
    		_table.Add(New List(Of Integer)(maja))
    
    		_willi += 1
    	End Sub
    
    	Function GetMaja(ByVal willi As Integer) As Integer()
    		Dim maja(1) As Integer
    
    		maja(0) = _table(willi)(0)
    		maja(1) = _table(willi)(1)
    
    		Return maja
    	End Function
    
    End Class

!BeeHiveTest.vb

    <TestClass()> _
    Public Class BeeHiveTest
    
    	<TestMethod()> _
    	Public Sub GetMajaTest()
    		Dim hive As BeeHive = New BeeHive()
    
    		Dim expected(1) As Integer
    		Dim actual() As Integer
    
    		expected(0) = 1
    		expected(1) = 1
    		actual = hive.GetMaja(8)
    		CollectionAssert.AreEqual(expected, actual)
    
    		expected(0) = 0
    		expected(1) = 2
    		actual = hive.GetMaja(9)
    		CollectionAssert.AreEqual(expected, actual)
    
    		expected(0) = 1
    		expected(1) = 2
    		CollectionAssert.AreEqual(expected, hive.GetMaja(21))
    
    		expected(0) = -1
    		expected(1) = 3
    		CollectionAssert.AreEqual(expected, hive.GetMaja(23))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub InputOutputTest()
    		Dim input As String
    
    		input = "1"
    		Assert.AreEqual("0 0", ModuleMain.Run(input))
    		input = "8"
    		Assert.AreEqual("1 1", ModuleMain.Run(input))
    		input = "23"
    		Assert.AreEqual("-1 3", ModuleMain.Run(input))
    	End Sub
    
    End Class

Mastojun

문제 풀이

O(1)에 구해지는 알고리즘이 없을까?
if문이 덕지덕지 들어갔지만 어쨋든 O(1) .....

소스

    #include <stdio.h>
    #include <math.h>
    
    int n;	///< 입력 받는 값!
    
    int GetLine()
    {
    	return (int)floor( 0.5 + sqrt( 9.0 - 12.0*(2.0-n))/6.0);
    }
    
    int GetNum(int line)
    {
    	return 3*line*line - 3 * line + 2 ;
    }
    
    void GetXY(int &x, int &y)
    {
    	int Line = GetLine();
    	int Num = GetNum(Line) - 1;
    	int diff = n - Num;
    
    	if( diff <= Line*3 )		x = -diff +   Line;
    	else				x =  diff - 4*Line;
    
    
    	if( diff <= Line*2 )		y =  diff;
    	else if( diff <= Line*4 )		y = -diff + 3*Line ;
    	else				y =  diff - 6*Line ;
    
    	if( x > Line )			x =  Line;
    	else if( x < -Line )		x = -Line;
    
    	if( y > Line )			y =  Line;
    	else if( y < -Line )		y = -Line;
    }
    
    void PrintResult()
    {
    	int x, y;
    	
    	if( n == 1 )
    	{
    		x = y = 0;
    	}
    	else
    	{
    		GetXY(x, y);		
    	}
    
    	printf("%d %d\n", x, y);
    }
    
    int main()
    {
    	while( scanf("%d", &n) >= 1 )
    	{
    		PrintResult();
    	}
    
    	return 0;
    }

itmentor

C++ Accept버전

한 라인의 끝점부터 순회하여 좌표를 계산함.

  /* @JUDGE_ID:itmentor 110401 Cpp "Bee maja" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <string>
  #include <algorithm>
  
  #ifdef _UNIT_TEST
  	#include <UnitTest++.h>
  #endif
  
  using namespace std;
  
  class SearchRange
  {
  public:
  	struct Coord
  	{
  		int begin;
  		int end;
  	};
  
  	typedef vector<Coord> LineInfoList;
  
  	LineInfoList coord;
  	int X;
  	int Y;
  
  	SearchRange()
  	{
  	}
  
  	void initializeCoordArray(int limit)
  	{
  		coord.clear();
  
  		Coord c;
  		c.begin = 1;
  		c.end = 1;
  
  		coord.push_back(c);
  		int sum = 1;
  		int i = 1;
  		while (sum < limit)
  		{
  			sum += (i * 6);
  
  			c.begin = coord[i-1].end + 1;
  			c.end = sum;
  
  			coord.push_back(c);
  			if (sum >= 100000)
  			{
  				break;
  			}
  			i++;
  		}
  	}
  
  	SearchRange(int coordinate)
  	{
  		X = 0;
  		Y = 0;
  	}
  
  	void convert2(int searchTarget, int& xCoordinate, int& yCoordinate)
  	{
  		if( searchTarget == 1 )
  		{
  			xCoordinate = 0;
  			yCoordinate = 0;
  		}
  
  		int lineDistance = this->calcLineDistance( searchTarget );
  		
  		int seed1DPoint = coord[lineDistance].end;
  		
  		int base2DPointX = lineDistance;
  		int base2DPointY = 0;
  
  		if( searchTarget == seed1DPoint )
  		{
  			xCoordinate = base2DPointX;
  			yCoordinate = base2DPointY;
  			return;
  		}
  
  		int current2DPointX = base2DPointX;
  		int current2DPointY = base2DPointY;
  		int current1DPoint = seed1DPoint;
  
  		int directionX[6] = { 0,-1,-1,0,1,1 };
  		int directionY[6] = { -1,0,1,1,0,-1 };
  
  		for(int dir = 0 ; dir < 6 ; dir++)
  		{
  			for(int i = 0 ; i < lineDistance ; i++)
  			{
  				current2DPointX += directionX[dir];
  				current2DPointY += directionY[dir];
  				current1DPoint--;						//끝점에서 시작점으로 역순으로 순회
  
  				if( current1DPoint == searchTarget )
  				{
  					xCoordinate = current2DPointX;
  					yCoordinate = current2DPointY;
  					return;
  				}
  
  				if( current1DPoint == coord[lineDistance].begin )
  				{
  					xCoordinate = -1;
  					yCoordinate = -1;
  					return;
  				}
  			}
  		}
  	}
  
  	int getBasePositionX(int searchTarget)
  	{
  		if( searchTarget == 1 )
  		{
  			return 0;
  		}
  
  		return this->calcLineDistance( searchTarget );
  	}
  
  	int getBasePositionY(int searchTarget)
  	{
  		return 0;
  	}
  
  	int getChangingDirectionCount(int searchTarget )
  	{
  		int lineDistance = this->calcLineDistance( searchTarget );
  
  		int beginNum = coord[lineDistance].begin;
  
  		float retVal = 0.0f;
  		
  		if( searchTarget != beginNum )
  		{
  			retVal = (float)(searchTarget - beginNum) / lineDistance;
  
  			if( lineDistance < retVal )
  				retVal += 0.5;
  		}
  
  		return (int)(retVal);
  	}
  
  	int getChangingDirectionOffset(int searchTarget )
  	{
  		int lineDistance = this->calcLineDistance( searchTarget );
  		int beginNum = coord[lineDistance].begin;
  
  		int offset = 0;
  		if( searchTarget != beginNum && lineDistance != 1)
  		{
  			offset = (searchTarget - beginNum+1) % (lineDistance);
  		}
  		else if( searchTarget == beginNum && searchTarget != 1 && lineDistance > 1)
  		{
  			offset = 1;
  		}
  
  		return offset;
  	}
  
  	int calcLineDistance(int searchTarget)
  	{
  		if( searchTarget == 1 )
  			return 0;
  
  		int retVal = 0;
  
  		int i = 0;
  		for(LineInfoList::iterator iter = coord.begin() ; iter != coord.end() ; ++iter, ++i)
  		{
  			if( searchTarget >= iter->begin && searchTarget <= iter->end )
  			{
  				retVal = i;
  				break;
  			}
  		}
  
  		return retVal;
  	}
  };
  
  
  int main()
  {
  #ifdef _UNIT_TEST
  	UnitTest::RunAllTests();
  #endif
  
  	SearchRange range;
  	range.initializeCoordArray(100000);
  
  	int value1D = 0;
  	
  
  	while(true)
  	{
  		char ln[512];
  		cin.getline(ln,512);
  
  		if( ln[0] == 0 )
  			break;
  		value1D = atoi(ln);
  		int x = -1,y = -1;
  		range.convert2( value1D, x, y );
  		std::cout << x << " " << y << std::endl;
  	}
  	return 0;
  }
  
  #ifdef _UNIT_TEST
  
  TEST(LineDistance)
  {
  	SearchRange range;
  	range.initializeCoordArray(100000);
  
  	CHECK_EQUAL( 0, range.calcLineDistance(1));
  	CHECK_EQUAL( 1, range.calcLineDistance(2));
  	CHECK_EQUAL( 1, range.calcLineDistance(7));
  	CHECK_EQUAL( 2, range.calcLineDistance(8));
  	CHECK_EQUAL( 3, range.calcLineDistance(22));
  	CHECK_EQUAL( 3, range.calcLineDistance(23));
  }
  
  TEST(LineRangeDiv)
  {
  	SearchRange range;
  	range.initializeCoordArray(100000);
  
  	CHECK_EQUAL( 0, range.getChangingDirectionCount( 1 ) );
  	CHECK_EQUAL( 0, range.getChangingDirectionOffset( 1 ) );
  
  	CHECK_EQUAL( 0, range.getChangingDirectionCount( 2 ) );
  	CHECK_EQUAL( 0, range.getChangingDirectionOffset( 2 ) );
  
  	CHECK_EQUAL( 1, range.getChangingDirectionCount( 3 ) );
  	CHECK_EQUAL( 0, range.getChangingDirectionOffset( 3 ) );
  
  	CHECK_EQUAL( 1, range.getChangingDirectionOffset( 8 ) );
  
  	CHECK_EQUAL( 2, range.getChangingDirectionCount( 12 ) );
  	CHECK_EQUAL( 1, range.getChangingDirectionOffset( 12 ) );
  	
  	CHECK_EQUAL( 3, range.getChangingDirectionCount( 13 ) );
  	CHECK_EQUAL( 0, range.getChangingDirectionOffset( 13 ) );
  
  	CHECK_EQUAL( 0, range.getChangingDirectionCount( 22 ) );
  	CHECK_EQUAL( 0, range.getChangingDirectionOffset( 22 ) );
  
  	CHECK_EQUAL( 1, range.getChangingDirectionCount( 23 ) );
  	CHECK_EQUAL( 1, range.getChangingDirectionOffset( 23 ) );
  }
  
  TEST(BasePosition)
  {
  	SearchRange range;
  	range.initializeCoordArray(100000);
  
  	CHECK_EQUAL(0, range.getBasePositionX(1) );
  	CHECK_EQUAL(0, range.getBasePositionY(1) );
  
  	CHECK_EQUAL(1, range.getBasePositionX(2) );
  	CHECK_EQUAL(0, range.getBasePositionY(2) );
  
  	CHECK_EQUAL(1, range.getBasePositionX(7) );
  	CHECK_EQUAL(0, range.getBasePositionY(7) );
  
  	CHECK_EQUAL(2, range.getBasePositionX(8) );
  	CHECK_EQUAL(0, range.getBasePositionY(8) );
  
  	CHECK_EQUAL(3, range.getBasePositionX(22) );
  	CHECK_EQUAL(0, range.getBasePositionY(22) );
  }
  
  TEST(Final)
  {
  	SearchRange range;
  	range.initializeCoordArray(100000);
  
  	int x,y;
  
  	range.convert2(1, x, y);
  	CHECK_EQUAL(0, x);
  	CHECK_EQUAL(0, y);
  
  	range.convert2(2, x, y);
  	CHECK_EQUAL(0, x);
  	CHECK_EQUAL(1, y);		
  	
  	range.convert2(3, x, y);
  	CHECK_EQUAL(-1, x);
  	CHECK_EQUAL(1, y);	
  
  	range.convert2(5, x, y);
  	CHECK_EQUAL(0, x);
  	CHECK_EQUAL(-1, y);	
  	
  	range.convert2(7, x, y);
  	CHECK_EQUAL(1, x);
  	CHECK_EQUAL(0, y);
  
  	range.convert2(16, x, y);
  	CHECK_EQUAL(1, x);
  	CHECK_EQUAL(-2, y);
  
  	range.convert2(22, x, y);
  	CHECK_EQUAL(0, x);
  	CHECK_EQUAL(3, y);
  }
  #endif
  
  /* @END_OF_SOURCE_CODE */

ParkPD

아이큐 테스트 같은 문제군요.

  /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <deque>
  #include <list>
  #include <stack>
  #include <string>
  #include <algorithm>
  #include <map>
  #include <limits>
  #include <assert.h>
  #include <iomanip>
  #include <math.h>
  
  //#define _UNIT_TEST
  
  #ifdef _UNIT_TEST
  #include <Windows.h>
  #endif
  
  using namespace std;
  
  // Minimum Spanning Tree -> Prim Algorithm 을 생각하며 풀었음.
  
  namespace ATUtil
  {
  	bool IsInRange(int value, int from, int to)
  	{
  		return (from <= value) && (value <= to);
  	}
  
  	int ConvertToIndex(char c)
  	{
  		if ('a' <= c && c <= 'z')
  		{
  			return c - 'a';
  		}
  		else
  		{
  			return -1;
  		}
  	}
  
  	char ConvertToChar(int i)
  	{
  		return (char)i + 'a';
  	}
  
  #ifdef _UNIT_TEST
  	class CStopWatch
  	{
  	public:
  		CStopWatch()
  		{
  			m_StartTick = GetTickCount();		// gcc 에서 안 될 수 있으니까
  		}
  
  		~CStopWatch()
  		{
  			cout << "Time passed : " << GetTickCount() - m_StartTick << " milisec.\n";
  		}
  
  		int m_StartTick;
  	};
  #endif
  
  	typedef map<int, int> IntDB;
  	typedef vector<int> Ints;
  	typedef list<int> IntList;
  
  };
  
  using namespace ATUtil;
  
  #ifdef _UNIT_TEST
  
  #include "../UnitTest++/src/UnitTest++.h"
  
  #ifdef max
  #undef max
  #endif
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  // code implement
  
  namespace ATCode
  {
  	///////////////////////////////////////////////////////////////
  	// CSolver
  	class CSolver
  	{
  	public:
  		enum { MAX_COMB = 100001 };
  
  		struct OffsetData
  		{
  			OffsetData() {}
  			OffsetData(int x, int y) : m_X(x), m_Y(y) {}
  			int m_X;
  			int m_Y;
  		};
  
  		CSolver()
  		{
  			Init();
  		}
  
  		void Init()
  		{
  			// 6:00  ( 0,  1)
  			// 7:30  (-1,  1) (한 개 작게), 
  			// 10:30 (-1,  0)
  			// 12:00 ( 0, -1)
  			// 1:30  ( 1, -1)
  			// 4:30  ( 1,  0)
  			int direction[6][3] = {
  				{0,  0,  1},
  				{1, -1,  1},
  				{0, -1,  0},
  				{0,  0, -1},
  				{0,  1, -1},
  				{0,  1,  0}
  			};
  
  			int index = 1;
  			int iter = 1;
  
  			int x = 0;
  			int y = 0;
  			m_Data[index++] = OffsetData(x, y);
  
  			while (1)
  			{
  				for (int d = 0; d < 6; ++d)
  				{
  					for (int i = 0; i < iter - direction[d][0]; ++i)
  					{
  						if (MAX_COMB <= index)
  						{
  							return;
  						}
  
  						x += direction[d][1];
  						y += direction[d][2];
  						m_Data[index++] = OffsetData(x, y);
  					}
  				}
  
  				++iter;
  			}
  		}
  
  		void Input(int num, int& x, int& y)
  		{
  			x = m_Data[num].m_X;	
  			y = m_Data[num].m_Y;
  		}
  
  		OffsetData m_Data[MAX_COMB];
  	};
  
  	///////////////////////////////////////////////////////////////
  	// CConsole
  	class CConsole
  	{
  	public:
  		static void ConsoleTest(istream& input, ostream& output);
  	};
  
  	void CConsole::ConsoleTest(istream& input, ostream& output)
  	{
  		CSolver s;
  		int num, x, y;
  		while (input >> num)
  		{
  			s.Input(num, x, y);
  			output << x << " " << y << '\n';
  		}
  	};
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureBase
  {
  	FixtureBase()
  	{
  	}
  
  	int x, y;
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureBase, Input)
  {
  	CSolver g;
  	int tests[] = {1, 0, 0, 2, 0, 1};
  	for (int i = 0; i < sizeof(tests) / sizeof(int); i += 3)
  	{
  		g.Input(tests[i], x, y);
  		CHECK_EQUAL(tests[i + 1], x);
  		CHECK_EQUAL(tests[i + 2], y);
  	}
  }
  
  TEST_FIXTURE(FixtureBase, ConsoleTest)
  {
  	input << 
  		"1\n"
  		"2\n"
  		"3\n"
  		"4\n"
  		"5\n"
  		;
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL( 
  		"0 0\n"
  		"0 1\n"
  		"-1 1\n"
  		"-1 0\n"
  		"0 -1\n",
  		output.str());
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

soomong

ㅜㅜ 무지막지한 if 문의 향연

  public class BeeMaja {
  
  	int x,y;	// Maja's System
  	int index;	// Willi's System
  	int result;
  	
  	public BeeMaja() {
  		x = 0;
  		y = 0;
  		index = 1;
  	}
  
  	public void moveCycle(int number) {
  		
  		int depth = 1;
  		
  		while(true)
  		{
  			moveDown();
  			if( index == number )
  				return;			
  			
  			if( depth != 1 )
  			{
  				for(int i=0;i<depth-1; i++){
  					moveLeftDown();
  					if( index == number )
  						return;
  				}
  			}
  			
  			for(int i=0;i<depth; i++)	{
  				moveLeftUp();
  				if( index == number )
  					return;
  			}
  			for(int i=0;i<depth; i++)	{
  				moveUp();
  				if( index == number )
  					return;
  			}
  			
  			for(int i=0;i<depth; i++)	{
  				moveRightUp();
  				if( index == number )
  					return;
  			}
  			
  			for(int i=0;i<depth; i++)	{
  				moveRightDown();
  				if( index == number )
  					return;
  			}
  			
  			for(int i=0;i<depth; i++)	{
  				moveDown();
  				if( index == number )
  					return;
  			}
  		
  			depth++;
  		}
  		
  	}
  
  	public void moveUp() {
  		y--;	// (0,-1)
  		index++;
  	}
  
  	public void moveLeftUp() {
  		x--;	// (-1,0)
  		index++;
  	}
  
  	public void moveLeftDown() {
  		x--;	// (-1,1)
  		y++;
  		index++;
  	}
  
  	public void moveRightUp() {
  		x++;	// (1,-1)
  		y--;
  		index++;
  	}
  
  	public void moveRightDown() {
  		x++;	// (1,0)
  		index++;
  	}
  
  	public void moveDown() {
  		y++;	// (0,1)
  		index++;
  	}
  
  	public static void main(String args[])	{
  		BeeMaja b = new BeeMaja();
  	}
  	
  }

  import junit.framework.TestCase;
  
  public class BeeMajaTest extends TestCase {
  
  	BeeMaja b = new BeeMaja();
  	
  	public void testMove()
  	{		
  		b.moveUp();
  		assertEquals(0,b.x);
  		assertEquals(-1,b.y);
  		
  		b.moveLeftUp();
  		assertEquals(-1,b.x);
  		assertEquals(-1,b.y);
  		
  		b.moveLeftDown();
  		assertEquals(-2,b.x);
  		assertEquals(0,b.y);
  		
  		for(int i=0; i<3; i++)
  			b.moveRightUp();
  		assertEquals(1,b.x);
  		assertEquals(-3,b.y);
  		
  		for(int i=0; i<5; i++)
  			b.moveRightDown();
  		assertEquals(6,b.x);
  		assertEquals(-3,b.y);
  		
  		for(int i=0; i<2; i++)
  			b.moveDown();
  		assertEquals(6,b.x);
  		assertEquals(-1,b.y);		
  	}
  	
  	public void testMoveCycle()
  	{
  		b.moveCycle(2);
  		assertEquals(0,b.x);
  		assertEquals(1,b.y);
  
  		b.x = 0;
  		b.y = 0;
  		b.index = 1;
  		b.moveCycle(22);
  		assertEquals(0,b.x);
  		assertEquals(3,b.y);
  
  		b.x = 0;
  		b.y = 0;
  		b.index = 1;
  		b.moveCycle(8);
  		assertEquals(1,b.x);
  		assertEquals(1,b.y);
  		
  		b.x = 0;
  		b.y = 0;
  		b.index = 1;
  		b.moveCycle(12);
  		assertEquals(-2,b.x);
  		assertEquals(1,b.y);
  
  		b.x = 0;
  		b.y = 0;
  		b.index = 1;
  		b.moveCycle(99999);
  		assertEquals(103,b.x);
  		assertEquals(80,b.y);
  	}
  }

algorithm bee maja - andstudy/forge GitHub Wiki

CynicJJ

ModuleMain.vb

!BeeHive.vb

!BeeHiveTest.vb

Mastojun

문제 풀이

소스

itmentor

C++ Accept버전

ParkPD

soomong

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️