algorithm light more light - andstudy/forge GitHub Wiki

문제보기 7장 Summit Pages

• 최초 풀이는 10줄 정도, 아니 뭐 이렇게 쉬운 문제가? 라고 생각

• 제출 해보니 시간 초과

• 풋~ 간단히 최적화

• 그래도 시간 초과

• 어쭈구리? 열심히 최적화, 최초구현에 비해 9배 정도의 성능

• 그래도 시간 초과, 씁숑구리

• 반나절간 삽질

• 마침내 깨닫게 되다. 현재 상태로는 이 문제를 풀지 못한다.

• 콜롬버스의 달걀이 필요하다.

• 해답은 어처구니 없을 정도로 간단하지 않을까?

• 마음을 비우고 맥반석 달걀이나 먹으면서 생각해보자.

    Public Class Light
    
    	Function GetLastBulbStatus(ByVal bulbCount As UInteger) As Boolean
    		Dim count As UInteger = 1		' 첫번째 반복에서 무조건 켜지기 때문
    
    		Dim loopLimit As UInteger = bulbCount \ 2
    
    		' 짝수 처리
    		While (bulbCount And 1) = 0
    			bulbCount >>= 1
    			count += 1
    			loopLimit >>= 1
    		End While
    
    		Dim n As UInteger = 3
    		While n <= loopLimit
    			If (bulbCount Mod n) = 0 Then
    				bulbCount \= n
    				count += 1
    				loopLimit = bulbCount
    			Else
    				n += 2
    			End If
    		End While
    
    		If count = 1 Then count += 1 ' count 가 여전히 1이면 자신이 소수라는 의미
    		Return ((count And 1) = 1)
    	End Function
    
    End Class
  

• 어처구니 없을정도로 간단 :D
• 문제의 요점은 제곱수인지를 묻는 것.

    #include <stdio.h>
    #include <math.h>
    #define ever (;;)
    
    int main()
    {
    	unsigned int n,t;
    
    	for ever
    	{
    		scanf("%u", &n);
    		if( n == 0 ) break;
    
    		t = (unsigned int)sqrt((double)n);
    
    		printf("%s\n", (t*t == n)?"yes":"no");
    	}
    
    	return 0;
    }

• 정답일 듯하나, never solved 문제라서 확인해 보지 못함.(wrong answer 로 나옴)

  • 입력 범위가 2^32-1 까지 입니다. int형의범위를 넘어서 Wrong answer 나오는 겁니다. [Mastojun]

    /* @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 <complex>
    #include <math.h>
    
    //#define _UNIT_TEST
    
    #ifdef _UNIT_TEST
    #include <Windows.h>
    #include "../UnitTest++/src/UnitTest++.h"
    #endif
    
    using namespace std;
    
    #ifdef max
    #undef max
    #endif
    
    #ifdef min
    #undef min
    #endif
    
    // 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
    
    int main()
    {
    	UnitTest::RunAllTests();
    
    	char temp;
    	cin >> temp;
    
    	return 0;
    }
    
    #endif
    
    // code implement
    
    namespace ATCode
    {
    	///////////////////////////////////////////////////////////////
    	// CSolver
    	class CSolver
    	{
    	public:
    		int GetDivisorNum(int num)
    		{
    			if (num == 1)
    			{
    				return 1;
    			}
    
    			int divisor = 2;	// 1 과 자기 자신.
    			int s = num;
    			for (int i = 2; i < s; ++i)
    			{
    				int remain = num % i;
    				if (0 == remain)
    				{
    					s = num / i;
    
    					if (i == s)	// 1, 2, 4 의 2와 같은 경우는 한 번만 더한다.
    					{
    						divisor++;
    					}
    					else
    					{
    						divisor += 2;
    					}
    				}
    			}
    
    			return divisor;
    		}
    
    		bool Input(int index)
    		{
    			// 최적화
    			//if (0 == GetDivisorNum(index) % 2)
    			//{
    			//	return false;
    			//}
    			//else
    			//{
    			//	return true;
    			//}
    			int s = (int)sqrt((double)index);
    			if (index == s * s)
    			{
    				return true;
    			}
    			else
    			{
    				return false;
    			}
    		}
    	};
    
    	///////////////////////////////////////////////////////////////
    	// CConsole
    	class CConsole
    	{
    	public:
    		static void ConsoleTest(istream& input, ostream& output);
    	};
    
    	void CConsole::ConsoleTest(istream& input, ostream& output)
    	{
    		CSolver s;
    		int index;
    		while (input >> index)
    		{
    			if (0 == index)
    			{
    				break;
    			}
    
    			if (s.Input(index))
    			{
    				output << "yes" << '\n';
    			}
    			else
    			{
    				output << "no" << '\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, GetDivisorNum)
    {
    	CSolver g;
    	int tests[] = {
    		1, 1,
    		2, 2, 
    		3, 2,
    		4, 3,
    		5, 2,
    		6, 4,
    		7, 2,
    		8, 4,
    		9, 3,
    		10, 4,
    		11, 2,
    		12, 6,
    		13, 2,
    		14, 4
    	};
    
    	for (int i = 0; i < sizeof(tests) / sizeof(int); i += 2)
    	{
    		cout << tests[i] << '\n';
    		CHECK_EQUAL(tests[i + 1], g.GetDivisorNum(tests[i]));
    	}
    }
    
    TEST_FIXTURE(FixtureBase, Input)
    {
    	CSolver g;
    	int tests[] = {
    		3, 0,
    		6241, 1,
    		8191, 0,
    		9, 1,
    		14, 0
    	};
    
    	for (int i = 0; i < sizeof(tests) / sizeof(int); i += 2)
    	{
    		//cout << i / 2 << '\n';
    		CHECK_EQUAL(tests[i + 1], g.Input(tests[i]) ? 1 : 0);
    	}
    }
    
    TEST_FIXTURE(FixtureBase, ConsoleTest)
    {
    	input << 
    		"3\n"
    		"6241\n"
    		"8191\n"
    		"0\n"
    		;
    	CConsole::ConsoleTest(input, output);
    	CHECK_EQUAL( 
    		"no\n"
    		"yes\n"
    		"no\n",
    		output.str());
    }
    
    #endif
    
    /* @END_OF_SOURCE_CODE */