왔다 갔다

면접 대비

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

요약
두 헛간에 각각 열 개씩 있는 양동이 크기가 주어질 때, 네 번 번갈아 옮긴 뒤 첫 번째 헛간 탱크에 남을 수 있는 서로 다른 우유 양의 가짓수를 센다.
난이도

보통10점 중 4점

유형
완전 탐색, 시뮬레이션, 구현, 해시맵
정답자
아직 제출이 없습니다

문제

농부 존에게는 두 개의 착유 헛간이 있고, 각 헛간에는 큰 우유 탱크와 크기가 다양한 1010개의 양동이가 들어 있는 보관함이 있다. 그는 운동 삼아 두 헛간 사이를 오가며 우유를 나른다.

월요일에 농부 존은 첫 번째 헛간의 탱크에서 정확히 10001000갤런의 우유를, 두 번째 헛간의 탱크에서도 정확히 10001000갤런의 우유를 잰다.

화요일에 그는 첫 번째 헛간에서 양동이 하나를 가져와 가득 채우고, 그 우유를 두 번째 헛간으로 가져가 탱크에 붓는다. 양동이는 두 번째 헛간에 두고 온다.

수요일에 그는 두 번째 헛간에서 양동이 하나를 가져와(화요일에 두고 온 것일 수도 있다) 가득 채우고, 그 우유를 첫 번째 헛간으로 가져가 탱크에 붓는다. 양동이는 첫 번째 헛간에 두고 온다.

목요일에 그는 첫 번째 헛간에서 양동이 하나를 가져와(수요일에 두고 온 것일 수도 있다) 가득 채우고, 그 우유를 두 번째 헛간으로 가져가 탱크에 붓는다. 양동이는 두 번째 헛간에 두고 온다.

금요일에 그는 두 번째 헛간에서 양동이 하나를 가져와(화요일이나 목요일에 두고 온 것일 수도 있다) 가득 채우고, 그 우유를 첫 번째 헛간으로 가져가 탱크에 붓는다. 양동이는 첫 번째 헛간에 두고 온다.

그런 다음 농부 존은 첫 번째 헛간의 탱크에 있는 우유를 잰다. 그가 볼 수 있는 서로 다른 눈금은 몇 가지인가?

입력

첫 번째 줄에는 처음에 첫 번째 헛간에 있는 양동이의 크기를 나타내는 1010개의 정수가 주어진다. 두 번째 줄에는 처음에 두 번째 헛간에 있는 양동이의 크기를 나타내는 1010개의 정수가 주어진다. 모든 양동이의 크기는 1…1001 \dots 100 범위이다.

출력

금요일 이후에 농부 존이 첫 번째 헛간의 탱크에 있는 우유를 재서 얻을 수 있는 눈금의 가짓수를 출력한다.

힌트

이 예시에서 첫 번째 헛간 탱크의 최종 우유 양은 55가지가 나올 수 있다:

  • 10001000: FJ가 매번 같은 양동이로 왔다 갔다 하면 첫 번째 헛간 탱크의 총량은 변하지 않는다.
  • 10031003: FJ가 화요일에 22단위, 수요일에 55단위, 목요일에 11단위, 금요일에 11단위를 나를 수 있다.
  • 10041004: FJ가 화요일에 11단위, 수요일에 55단위, 목요일에 11단위, 금요일에 11단위를 나를 수 있다.
  • 10071007: FJ가 화요일에 11단위, 수요일에 55단위, 목요일에 22단위, 금요일에 55단위를 나를 수 있다.
  • 10081008: FJ가 화요일에 11단위, 수요일에 55단위, 목요일에 11단위, 금요일에 55단위를 나를 수 있다.

예제1

  1. 예제 1

    입력
    1 1 1 1 1 1 1 1 1 2
    5 5 5 5 5 5 5 5 5 5
    
    예상 출력
    5