이번에 당신은 결국 일을 그르쳤습니다. "정사각형 타일을 좀 사 오게"라고 상사가 당신에게 말했습니다. 하지만 평소와 같이 당신은 메시지를 읽거나, 이메일에 답장하거나, 페이스북 담벼락 상태를 업데이트하느라 바빴을 것입니다. 당신이 기억할 수 있었던 것은 "타일을 좀 사 오게"라는 말뿐이었습니다.
이제 당신의 상사는 당신이 사 온 타일이 정사각형이 아니라고 불평하며, 당신이 이 문제를 해결하지 못하면 해고될 것이라고 합니다!
"해결? 이걸 어떻게 해결하라는 거지?" 당신은 혼잣말을 합니다. "나는 프로그래머야. 내가 아는 유일한 타일은 테트리스 게임의 타일뿐이라고!" 게다가 당신은 이대로 해고당할 수는 없습니다. 한 달도 안 되어 이번이 세 번째 직장입니다. "어떻게든 해결해야 해!" 당신은 계속 되뇌입니다.
당신은 타일을 산 가게에 전화하지만, 가게에서는 "상품이 가게를 떠난 후에는 주문 취소가 어렵습니다"라고 말하며 반품이나 교환조차 받지 않으려고 합니다.
당신은 타일을 살펴보니, 모두 직사각형 모양이고 크기가 모두 같습니다. 타일을 자르면 손해가 클 것이고, 애초에 완벽한 정사각형으로 자를 수도 없습니다. "잠깐!" 당신은 혼잣말을 합니다. 당신은 타일 몇 개를 집어, 어떤 배열로 배치했고, 짜잔, 그것이 정사각형이 되었습니다.
하지만 그것으로는 당신의 상사를 설득할 수 없습니다. 타일은 작아야 하는데, 당신이 생각해낸 것은 다소 큽니다. 배열을 다시 살펴보자 다시 무언가 떠오릅니다. "오늘 감이 좋군!" 당신은 자랑스럽게 혼잣말을 합니다. 가장 작은 가능한 정사각형을 만드는 데 필요한 가장 적은 타일의 수를 어떻게 찾을 수 있는지 방금 알아낸 것입니다.
당신은 서둘러 상사에게 달려가 당신의 발견을 보여줍니다. 그는 그다지 감명받지 않습니다. (알고리즘을 설명하느라 머리에 피가 몰려 있는 상태를 감안하면) 당신의 말이 어쨌든 말이 되지 않기 때문입니다. 계산이 당신이 말하는 것보다 훨씬 단순하다는 것을 알지만, 명확하게 생각할 수가 없습니다.
마침내 당신의 상사는 소리칩니다. "첫째, 타일은 같은 방향으로 놓여야만 해. 둘째, 나는 지금 건설 현장을 운영하고 있지, 소프트웨어 업체를 운영하는 게 아니야! 작업자들이 그 숫자를 어떻게 알아낼 거라고 생각하는 거야! 당신이 설명하는 그 계산을 수행할 프로그램을 작성하든지, 아니면 지금 당장 네 넷북, 휴대폰, 아이팟, 블랙베리를 챙겨서 여기서 나가!"
입력
당신의 프로그램은 하나 이상의 데이터 세트로 테스트될 것입니다.
각 테스트 세트는 하나의 줄에 두 개의 양수로 설명됩니다: 0 < W, H < 1,000,000 이것은 각 타일의 너비와 높이입니다.
blackbee4 1년 전 1
이번에 당신은 결국 일을 그르쳤습니다. "정사각형 타일을 좀 사 오게"라고 상사가 당신에게 말했습니다. 하지만 평소와 같이 당신은 메시지를 읽거나, 이메일에 답장하거나, 페이스북 담벼락 상태를 업데이트하느라 바빴을 것입니다. 당신이 기억할 수 있었던 것은 "타일을 좀 사 오게"라는 말뿐이었습니다.
이제 당신의 상사는 당신이 사 온 타일이 정사각형이 아니라고 불평하며, 당신이 이 문제를 해결하지 못하면 해고될 것이라고 합니다!
"해결? 이걸 어떻게 해결하라는 거지?" 당신은 혼잣말을 합니다. "나는 프로그래머야. 내가 아는 유일한 타일은 테트리스 게임의 타일뿐이라고!" 게다가 당신은 이대로 해고당할 수는 없습니다. 한 달도 안 되어 이번이 세 번째 직장입니다. "어떻게든 해결해야 해!" 당신은 계속 되뇌입니다.
당신은 타일을 산 가게에 전화하지만, 가게에서는 "상품이 가게를 떠난 후에는 주문 취소가 어렵습니다"라고 말하며 반품이나 교환조차 받지 않으려고 합니다.
당신은 타일을 살펴보니, 모두 직사각형 모양이고 크기가 모두 같습니다. 타일을 자르면 손해가 클 것이고, 애초에 완벽한 정사각형으로 자를 수도 없습니다. "잠깐!" 당신은 혼잣말을 합니다. 당신은 타일 몇 개를 집어, 어떤 배열로 배치했고, 짜잔, 그것이 정사각형이 되었습니다.
하지만 그것으로는 당신의 상사를 설득할 수 없습니다. 타일은 작아야 하는데, 당신이 생각해낸 것은 다소 큽니다. 배열을 다시 살펴보자 다시 무언가 떠오릅니다. "오늘 감이 좋군!" 당신은 자랑스럽게 혼잣말을 합니다. 가장 작은 가능한 정사각형을 만드는 데 필요한 가장 적은 타일의 수를 어떻게 찾을 수 있는지 방금 알아낸 것입니다.
당신은 서둘러 상사에게 달려가 당신의 발견을 보여줍니다. 그는 그다지 감명받지 않습니다. (알고리즘을 설명하느라 머리에 피가 몰려 있는 상태를 감안하면) 당신의 말이 어쨌든 말이 되지 않기 때문입니다. 계산이 당신이 말하는 것보다 훨씬 단순하다는 것을 알지만, 명확하게 생각할 수가 없습니다.
마침내 당신의 상사는 소리칩니다. "첫째, 타일은 같은 방향으로 놓여야만 해. 둘째, 나는 지금 건설 현장을 운영하고 있지, 소프트웨어 업체를 운영하는 게 아니야! 작업자들이 그 숫자를 어떻게 알아낼 거라고 생각하는 거야! 당신이 설명하는 그 계산을 수행할 프로그램을 작성하든지, 아니면 지금 당장 네 넷북, 휴대폰, 아이팟, 블랙베리를 챙겨서 여기서 나가!"
입력
당신의 프로그램은 하나 이상의 데이터 세트로 테스트될 것입니다.
각 테스트 세트는 하나의 줄에 두 개의 양수로 설명됩니다: 0 < W, H < 1,000,000 이것은 각 타일의 너비와 높이입니다.
마지막 줄은 두 개의 0으로 구성됩니다.
출력
각 테스트 케이스에 대해, 정답을 별도의 줄에 작성하십시오.