iChess

면접 대비

시간 제한2초메모리 제한64 MB

요약
흑백 타일 개수가 주어졌을 때 체크보드 패턴으로 채울 수 있는 가장 큰 정사각형의 한 변의 길이를 구하거나 불가능하면 그렇게 출력합니다.
난이도

쉬움10점 중 3점

유형
이분 탐색, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

체스 페이션스는 카드가 아니라 흑백 정사각형 타일로 하는 놀이다. 목표는 타일들을 평면 위에 놓아, 흑백이 체스판처럼 번갈아 칠해진 정사각형을 만드는 것이다. 이 정사각형은 빈 칸 없이 완전히 채워져야 하고, 가능한 한 크게 만들어야 한다. 정사각형에 들어가지 못한 타일은 남겨 두어도 된다.

이 놀이의 컴퓨터 버전인 iChess에서는 실제 타일 대신 타일의 개수만 주어진다. 또한 결과로 구하는 것은 실제 배치가 아니라, 만들어진 정사각형의 한 변의 길이(타일 개수 단위)이다.

흑색 타일 b개와 백색 타일 w개가 주어질 때, 이들 중 일부(또는 전부)를 사용해 체스판 무늬로 완전히 채울 수 있는 정사각형의 최대 한 변의 길이를 출력하는 프로그램을 작성하여라. 한 변의 길이가 s인 정사각형은 두 색을 번갈아 칠하므로 한 색은 ⌈s²/2⌉개, 다른 색은 ⌊s²/2⌋개가 필요하며, 어느 색을 더 많이 쓸지는 자유롭게 정할 수 있다.

입력

두 정수 b와 w가 주어진다. 각각 흑색 타일과 백색 타일의 개수이다 (0 ≤ b, w ≤ 10000).

출력

흑색 타일 b개와 백색 타일 w개로 만들 수 있는 체스판 무늬 정사각형의 최대 한 변의 길이 s를 한 줄에 출력한다. 어떤 정사각형도 만들 수 없으면 Impossible을 출력한다.

예제4

  1. 예제 1

    입력
    12 15
    
    예상 출력
    5
    
  2. 예제 2

    입력
    0 0
    
    예상 출력
    Impossible
    
  3. 예제 3

    입력
    1 0
    
    예상 출력
    1
    
  4. 예제 4

    입력
    2 2
    
    예상 출력
    2