algorithm how many fibs - andstudy/forge GitHub Wiki

CynicJJ

Solved. 우왕ㅋ굳ㅋ
- 온라인 판정에는 신경 끄려고 해도 잘 안됨
- 자바에서 너무 지나치게 편의를 제공하는 class는 사용 못하도록 만들었다는 규정을 본적이 있는데.. BigInteger는 아니였군요 no....대회가 아니여서 풀어준건가;;
BigInteger 클래스 없었다면 그냥 GG 했을 듯

Main.java

    import java.math.BigInteger;
    import java.io.*;
    
    class Main implements Runnable{
        static String ReadLn(int maxLength){  // utility function to read from stdin,
                                              // Provided by Programming-challenges, edit for style only
            byte line[] = new byte [maxLength];
            int length = 0;
            int input = -1;
            try{
                while (length < maxLength){//Read untill maxlength
                    input = System.in.read();
                    if ((input < 0) || (input == '\n')) break; //or untill end of line ninput
                    line [length++] += input;
                }
    
                if ((input < 0) && (length == 0)) return null;  // eof
                return new String(line, 0, length);
            }catch (IOException e){
                return null;
            }
        }
    
        public static void main(String args[])  // entry point from OS
        {
            Main myWork = new Main();  // Construct the bootloader
            myWork.run();            // execute
        }
    
        public void run() {
            new myStuff().run();
        }
    }
    class myStuff implements Runnable{
        public void run() {
        	HowManyFibs fibs = new HowManyFibs();
        	
        	while(true) {
        		String input = Main.ReadLn(99999).trim();
        		String first = input.split(" ")[0];
        		String second = input.split(" ")[1];
        		
        		if (first.equals("0") && second.equals("0")) {
        			break;
        		}
        		
        		int count = fibs.getFibsCount(first, second);
        		System.out.println(count);
        	}
        }
    }
    
    class HowManyFibs {
    	public int getFibsCount(String begin, String end) {
    		BigInteger beginBig = new BigInteger(begin);
    		BigInteger endBig = new BigInteger(end);
    		
    		BigInteger before = new BigInteger("1");
    		BigInteger fib = new BigInteger("1");
    		BigInteger newFib;
    		
    		int count = 0;
    		
    		while(fib.compareTo(endBig) <= 0) {
    			if( (fib.compareTo(beginBig) >= 0)&& fib.compareTo(endBig) <= 0) {
    				count++;
    			}
    			newFib = fib.add(before);
    			before = fib;
    			fib = newFib;
    		}
    		
    		return count;
    	}
    }

HowManyFibsTest.java

    import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class HowManyFibsTest {
    	@Test
    	public void getFibsCountTest() {
    		HowManyFibs fibs = new HowManyFibs();
    		assertEquals(1, fibs.getFibsCount("1", "1"));
    		assertEquals(2, fibs.getFibsCount("1", "2"));
    		assertEquals(5, fibs.getFibsCount("10", "100"));
    	}
    	
    	@Test
    	public void getFibsCountTestLarge() {
    		HowManyFibs fibs = new HowManyFibs();
    		assertEquals(4, fibs.getFibsCount("1234567890", "9876543210"));		
    	}
    
    	@Test
    	public void getFibsCountTestHuge() {
    		HowManyFibs fibs = new HowManyFibs();
    		
    		StringBuilder strHugeNumber = new StringBuilder();
    		strHugeNumber.append("1");
    		for(int i=0 ; i<100 ; i++) {
    			strHugeNumber.append("0");
    		}
    
    		assertEquals(435, fibs.getFibsCount("1234567890", strHugeNumber.toString()));		
    	}
    }

Mastojun

문제 풀이

작년과 같은 문제로 Wrong Answer를 여럿 찍었습니다. ㅠㅠ
programming-challenges에서는 RTE를 Wrong answer라고 알려주네요.;;
입력의 최대값이 10^100 이므로 총 101 자리숫자, Null문자 포함 102개의 char배열에 입력 받아야 하는데 101개로 설정해서 Wrong Answer를 받았었어요, 경계값 테스트의 중요성을 다시 한번 느꼈습니다.
BigNumber 클래스를 보다더 클래스 답게 만들려고 했지만 그게 쉽진 않네요 결국 Solved받기에만 급급해서 후다닥 작성해 버렸습니다;

소스 코드

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    
    #define MAXLEN 103
    #define max(x,y) ((x)>(y)?(x):(y))
    
    using namespace std;
    
    class BigNumber
    {
    public:
    	BigNumber()
    	{
    		length = 0;
    		for(int i = 0; i < MAXLEN; i++ )
    		{
    			Number[i] = 0;
    		}
    	}
    
    	BigNumber(char* in)
    	{
    		BigNumber();
    		length = strlen(in);
    		for(int i = length-1; i >= 0; i-- )
    		{
    			Number[i] = in[length-i-1] - '0';
    		}
    	}
    
    	char GetAt(int i) const
    	{
    		if( i >= length ) return 0;
    		return Number[i];
    	}
    
    	const BigNumber& operator+=(const BigNumber& rhs)
    	{
    		int i;
    		int carry = 0;
    		int MaxLen = max(rhs.length, length);
    
    		for( i = 0; i < MaxLen; i++ )
    		{
    			Number[i] = rhs.GetAt(i) + Number[i] + carry;
    
    			if( Number[i] >= 10 )
    			{
    				Number[i] -= 10;
    				carry = 1;
    			}
    			else
    			{
    				carry = 0;
    			}						
    		}
    
    		if( carry )
    		{
    			length = MaxLen+1;
    			Number[i] = carry;
    		}
    		else
    		{
    			length = MaxLen;
    		}
    
    		return *this;
    	}
    
    	bool operator>=(const BigNumber& rhs)
    	{
    		if( length > rhs.length ) return true;
    		if( length < rhs.length) return false;
    
    		for( int i = length-1; i >= 0; i-- )
    		{
    			if( Number[i] > rhs.Number[i] ) return true;
    			if( Number[i] < rhs.Number[i] ) return false;
    		}
    
    		return true;	
    	}
    
    	bool operator>(const BigNumber& rhs)
    	{
    		if( length > rhs.length ) return true;
    		if( length < rhs.length) return false;
    
    		for( int i = length-1; i >= 0; i-- )
    		{
    			if( Number[i] > rhs.Number[i] ) return true;
    			if( Number[i] < rhs.Number[i] ) return false;
    		}
    
    		return false;	
    	}
    	
    
    private:
    	char Number[MAXLEN];
    	int  length;
    };
    
    BigNumber operator+(const BigNumber& lhs, const BigNumber& rhs)
    {
    	BigNumber temp;
    
    	temp += lhs;
    	temp += rhs;
    
    	return temp;
    }
    
    int main()
    {
    	char Input1[102];
    	char Input2[102];
    	
    	while( scanf("%s %s", Input1, Input2) == 2 )
    	{
    		if(Input1[0] == '0' && Input2[0] == '0')
    		{
    			break;
    		}
    
    		BigNumber Start(Input1), End(Input2);
    
    		BigNumber fibo1("1"), fibo2("2");
    		
    		int result = 0;
    
    		while(true)
    		{
    			if( fibo1 > End ) break;
    			if( fibo1 >= Start ) result++;
    			BigNumber Temp(fibo2);
    			fibo2 = fibo1 + fibo2;
    			fibo1 = Temp;
    		}
    
    		printf("%d\n", result);
    	}
    
    	return 0;
    }

ParkPD

Lua 로 풀어보았습니다. 스크립트로 풀었는데 어째 코드량이 이렇게 많은 것인지...

그나저나 온라인 판정을 못 해 보는 게 아쉽군요. :(

  -- Library
  
  function fwrite(fmt, ...)
  	return io.write(string.format(fmt, unpack(arg)))
  end
  
  function swrite(fmt, ...)
  	return string.format(fmt, unpack(arg))
  end
  
  function SwapBySize(i1, i2)
  	if (i2 < i1) then
  		return i2, i1
  	end	
  	return i1, i2
  end
  
  function IsBetween(i, i1, i2)
  	i1, i2 = SwapBySize(i1, i2)
  	return i1 <= i and i <= i2
  end
  
  function PrintTable(t)	
  	fwrite("%s\n", ConvertTableToString(t))
  end
  
  function ConvertTableToString(t)
  	s = "["
  	for _, k in pairs(t) do
  		s = s..tostring(k)..' '
  	end
  	s = s .. "]"
  	return s
  end
  
  function pack(...)
  	return arg
  end
  
  -- UnitTest
  UnitTest = {test = 0, success = 0, failed = 0}
  
  function UnitTest:new(o)
  	o = o or {}
  	setmetatable(o, self)
  	self.__index = self
  	return o
  end
  
  function UnitTest:ShowResult()
  	if UnitTest.failed == 0 then
  		fwrite("Success : %d tests passed\n", UnitTest.success)
  	else
  		fwrite("Failed : %d in tests %d\n", UnitTest.failed, UnitTest.test)
  	end
  end
  
  function Check(name, actual)
  	UnitTest.test = UnitTest.test + 1
  	if not actual then
  		fwrite("Check Failed in %s\n", name)
  		UnitTest.failed = UnitTest.failed + 1
  	else
  		UnitTest.success = UnitTest.success + 1
  	end
  end
  
  function CheckEqual(name, expect, actual)
  	UnitTest.test = UnitTest.test + 1
  	if (expect ~= actual) then
  		fwrite("CheckEqual Failed in %s. %s expected but actual is %s\n", name, tostring(expect), tostring(actual))
  		UnitTest.failed = UnitTest.failed + 1
  	else
  		UnitTest.success = UnitTest.success + 1
  	end
  end
  
  function CheckArrayEqual(name, expect, actual)
  	UnitTest.test = UnitTest.test + 1
  	
  	local fail = false
  	if (#expect == #actual) then
  		for k, v in pairs(expect) do
  			if (actual[k] ~= v) then
  				fail = true
  				break
  			end			
  		end		
  	else
  		fail = true
  	end
  		
  	if (fail) then
  		fwrite("CheckArrayEqual Failed in %s. %s expected but actual is %s\n", name, ConvertTableToString(expect), ConvertTableToString(actual))
  		UnitTest.failed = UnitTest.failed + 1
  	else
  		UnitTest.success = UnitTest.success + 1
  	end
  end
  
  -- Algorithm
  
  ------------------------------- BigInt
  BigInt = {}
  
  function BigInt:new(o)
  	o = o or {Nums = {}}
  	setmetatable(o, self)
  	self.__index = self
  	return o
  end
  
  function BigInt:HighLow(o)
  	local low = o % 1000000
  	local high = math.max(0, o - low) / 1000000
  	return high, low
  end
  
  function BigInt:SetZero()
  	self.Nums = {}
  end
  
  function BigInt:SetInt(o)
  	self:SetZero()
  	
  	-- litte endian 처럼 역순으로 저장	
  	local high = 0
  	high, self.Nums[1] = self:HighLow(o)
  	if high > 0 then
  		self.Nums[2] = high
  	end
  	
  	--print("SetInt ", self.Nums[1], self.Nums[2])
  end
  
  function BigInt:SetSubString(o, i)
  	-- o 길이가 6 초과임을 보장.
  	local num = string.sub(o, #o - 5, #o)
  	self.Nums[i] = tonumber(num)	
  	return string.sub(o, 1, #o - 6)
  end
  
  function BigInt:SetString(o)
  	self:SetZero()
  	
  	local i = 1
  
  	while (6 < #o) do
  		-- 하위 6 자리씩 뜯어낸다.
  		local num = string.sub(o, #o - 5, #o)
  		
  		self.Nums[i] = tonumber(num)	
  		o = string.sub(o, 1, #o - 6)
  		i = i + 1		
  	end	
  	
  	self.Nums[i] = tonumber(o)
  end
  
  function BigInt:Print(o)
  	local s = ""
  	for i = 1, #self.Nums - 1 do
  		s = swrite("%06d", self.Nums[i])..s
  	end
  	
  	s = tonumber(self.Nums[#self.Nums])..s
  	return s
  end
  
  function BigInt:Add(a, b)
  	local c = BigInt:new()
  
  	local carry = 0
  	
  	local maxNum = math.max(#a.Nums, #b.Nums)
  	for i = 1, maxNum do
  		if (a.Nums[i] ~= nil and b.Nums[i] ~= nil) then
  			--print (a.Nums[i], b.Nums[i], carry)
  			carry, c.Nums[i] = self:HighLow(a.Nums[i] + b.Nums[i] + carry)
  		elseif (a.Nums[i] ~= nil) then
  			carry, c.Nums[i] = self:HighLow(a.Nums[i] + carry)
  		elseif (b.Nums[i] ~= nil) then
  			carry, c.Nums[i] = self:HighLow(b.Nums[i] + carry)
  		else
  			assert(nil, "Can't come here")
  		end
  	end
  	
  	if (carry > 0) then
  		c.Nums[maxNum + 1] = carry
  	end
  	
  	return c
  end
  
  function BigInt:Equal(a)
  	if #a.Nums ~= #self.Nums then
  		return false
  	end
  	
  	for i = 1, #a.Nums do
  		if a.Nums[i] ~= self.Nums[i] then
  			return false
  		end
  	end
  	
  	return true
  end
  
  -- 1 : self is bigger than a, 
  -- 0 : equal, 
  -- -1 : self is less than a
  function BigInt:Compare(a)
  	if #a.Nums ~= #self.Nums then
  		if #a.Nums < #self.Nums then
  			return 1
  		else
  			return -1
  		end
  	else
  		for i = #a.Nums, 1, -1 do
  			if a.Nums[i] < self.Nums[i] then
  				return 1
  			elseif self.Nums[i] < a.Nums[i] then
  				return -1
  			else
  				-- do nothing
  			end
  		end
  	end
  	
  	return 0	-- equal
  end
  
  ------------------------------- Fib
  Fib = {Nums = {BigInt:new(), BigInt:new()}}
  Fib.Nums[1]:SetString("1")	-- Fib 의 1 번 값은 "1"이다.
  Fib.Nums[2]:SetString("2")
  
  function Fib:new(o)
  	o = o or {Count = 0}
  	setmetatable(o, self)
  	self.__index = self
  	return o
  end
  
  -- from 보다 크거나 같은 피보나치 수열이 나타나는 인덱스를 리턴한다.
  function Fib:FindFirstFib(from)
  	self.count = 1
  	while 1 do
  		local it = self.Nums[self.count]
  		if it ~= nil then
  			if (0 <= it:Compare(from)) then	-- from 보다 크거나 같은 첫 번째 숫자
  				return self.count, it
  			end		
  		else
  			local it1 = BigInt:Add(self.Nums[self.count - 1], self.Nums[self.count - 2])
  			self.Nums[self.count] = it1	
  			if (0 <= it1:Compare(from)) then	-- from 보다 크거나 같은 첫 번째 숫자
  				return self.count, it1
  			end	
  		end
  		
  		self.count = self.count + 1
  	end	
  end
  
  -- test part
  do
  	local testSet = 
  		{10, 100, 5,
  		 1234567890, 9876543210, 4
  		}
  		
  	for i = 1, #testSet, 3 do
  		local a = BigInt:new()
  		local b = BigInt:new()
  		a:SetInt(testSet[i])
  		b:SetInt(testSet[i + 1])
  		
  		local f = Fib:new()
  		local countA, itA = f:FindFirstFib(a)
  		local countB, itB = f:FindFirstFib(b)
  		--print(countA, itA:Print(), countB, itB:Print())
  		
  		CheckEqual("How many "..math.ceil(i / 3), testSet[i + 2], countB - countA)
  	end
  end
  
  do
  	local testSet = 
  		{"1234", "1233", 1,
  		 "1233", "1234", -1,
  		 "1233", "1233", 0,
  		 "1234567890", "1234567891", -1,
  		 "98765432109876543210", "98765432109876543210", 0,
  		 "98765432109876543210", "98765432009876543210", 1,
  		 "10", "98765432009876543210", -1,
  		 "1000001", "1000001", 0
  		}
  		
  	for i = 1, #testSet, 3 do
  		local a = BigInt:new()
  		local b = BigInt:new()
  		a:SetString(testSet[i])
  		b:SetString(testSet[i + 1])
  		CheckEqual("Compare "..math.ceil(i / 3), testSet[i + 2], a:Compare(b))
  	end	
  end
  
  do
  	local testSet = 
  		{10, 6, "13",
  		 1234567890, 45, "1836311903",
  		 9876543210, 49, "12586269025",
  		 12345678901234567890, 59, "1548008755920"
  		}
  		
  	for i = 1, #testSet, 3 do
  		local b = BigInt:new()
  		b:SetInt(testSet[i])
  		
  		local f = Fib:new()
  		local count, it = f:FindFirstFib(b)
  		
  		CheckEqual("MakeFibTable 1 "..math.ceil(i / 3), testSet[i + 1], count)
  		CheckEqual("MakeFibTable 2 "..math.ceil(i / 3), testSet[i + 2], it:Print())
  	end
  end
  
  do
  	local testSet = 
  		{"1234", "1234", true,
  		 "1234567890", "1234567890", true,
  		 "1234567890", "1234567891", false,
  		 "98765432109876543210", "98765432109876543210", true,
  		 "98765432109876543210", "98765432009876543210", false,
  		 "1000001", "1000001", true
  		}
  		
  	for i = 1, #testSet, 3 do
  		local a = BigInt:new()
  		local b = BigInt:new()
  		a:SetString(testSet[i])
  		b:SetString(testSet[i + 1])
  		
  		CheckEqual("Print a "..math.ceil(i / 3), testSet[i], a:Print())
  		CheckEqual("Print b "..math.ceil(i / 3), testSet[i + 1], b:Print())
  		CheckEqual("Equal "..math.ceil(i / 3), testSet[i + 2], a:Equal(b))
  	end
  end
  
  do
  	local testSet = 
  		{1111111111, {1111, 111111}, 
  		 0xffffffff, {4294, 967295}, 
  		 12345678, {12, 345678}
  		}
  	
  	local b = BigInt:new()
  	for i = 1, #testSet, 2 do
  		local t = pack(b:HighLow(testSet[i]))
  		CheckArrayEqual("HighLow", testSet[i + 1], t)
  	end	
  end
  
  do
  	local testSet = 
  		{10, "10", 
  		 0xffffffff, "4294967295", 
  		 12345678, "12345678",
  		 1234567890123456, "1234567890123456"
  		}
  		
  	for i = 1, #testSet, 2 do
  		local b = BigInt:new()	
  		b:SetInt(testSet[i])
  		CheckEqual("Print "..math.ceil(i / 2), testSet[i + 1], b:Print())
  	end	
  end
  
  do
  	local testSet = 
  		{10, 20, "30", 
  		 0xffffffff, 1, "4294967296", 
  		 0xffffffff, 0xffffffff, "8589934590"
  		}
  
  	for i = 1, #testSet, 3 do
  		local a = BigInt:new()
  		local b = BigInt:new()
  		a:SetInt(testSet[i])
  		b:SetInt(testSet[i + 1])
  		
  		local c = BigInt:Add(a, b)
  		CheckEqual("BigInt:Add"..math.ceil(i / 3), testSet[i + 2], c:Print())
  	end
  end
  
  UnitTest:ShowResult()
  
  -- input part
  
  while 1 do
  	local count = io.read("*number")
  	if count == nil then 
  		break 
  	end
  end

algorithm how many fibs - andstudy/forge GitHub Wiki

CynicJJ

Main.java

HowManyFibsTest.java

Mastojun

문제 풀이

소스 코드

ParkPD

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

⚠️ GitHub.com Fallback ⚠️