Problem:

D: 貪欲が最適？

物語

1, 5, 10, 50, 100, 500 円玉がある日本では、ある金額を支払う時、大きい金額の硬貨をできるだけ多く使うという方法で支払うと、硬貨の枚数を最小化できることが知られている。

硬貨の金額が日本とは異なる場合、貪欲に支払うと必ずしも最小化できるとは限らない。

貪欲に支払うのが最適になるために、硬貨の金額が満たすべき条件は何なのだろうか。

問題

TAB 君は上のことが気になったので、まずは硬貨が 1, A, B の 3 種類しかない場合について考えることにした。

A, B が与えられるので、貪欲に支払った場合枚数が最小にならないような金額のうち、最小のものを出力せよ。

また、どんな金額でも貪欲法が最適な場合は、-1 を出力せよ。

入力形式

A B

制約

1 < A \leq 10^5

A < B \leq 10^9

入力例 1

4 6

出力例 1

8

8 円を貪欲に支払うと、 6 + 1 \times 2 で支払うことになり、合計 3 枚必要だが、4 \times 2 で合計 2 枚で支払うことができる。

入力例 2

2 1000000000

出力例 2

-1

どんな金額であっても貪欲に支払うのが最適である。



Sample input:
4 6


Sample output:
8

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
d=e=-(-b//a)*a
c=0
while d>=b:
    d-=b
    c+=1
while d>=a:
    d-=a
    c+=1
c+=d
if c>e//a:
    print(e)
else:
    print(-1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
ans = -1
for i in range(B//A+1,A):
    P = A*i
    if (P//B) + (P%B)%A > i:
        ans = P
        break 
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    p = LI()
    t = LI()
    dp = [inf] * (10**5)
    dp[0] = 0
    for i in range(10**5):
        for num,ti in enumerate(t):
            if i - ti >= 0:
                dp[i] = min(dp[i], dp[i - ti] + p[num])
    for i in range(10**5-1, 0, -1):
        dp[i - 1] = min(dp[i], dp[i - 1])
    print(dp[n])
    return

#B
def B():
    def yaku(n):
        res = 0
        if n == 0:
            return 0
        for i in range(1, int(math.sqrt(n-1)) + 1):
            if n % i == 0:
                res += 2
        if float.is_integer(math.sqrt(n)):
            res += 1
        return res
    q = II()
    ya = [yaku(i) for i in range(10 ** 5 + 1)]
    ya[0] = 0
    for i in range(1,10 ** 5 + 1):
        if ya[i] >= 5:
            ya[i] = 1
        else:
            ya[i] = 0
        ya[i] += ya[i - 1]
    for i in range(q):
        n = II()
        print(ya[n])
    return

#C
def C():
    return

#D
def D():
    a, b = LI()
    if b % a == 0 or a == 2:
        print(-1)
    else:
        x = b // a + 1
        c = a * x
        if x < c // b + c % b:
            print(c)
        else:
            print(-1)

#E
def E():
    return

#F
def F():
    return

#G  
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
A,B=map(int,input().split())

if A>B:
    A,B=B,A

if B%A==0:
    print(-1)

else:
    for i in range(((B//A+1)*A),B+A*2,A):
        if i//A < i//B+(i-i//B*B)//A+(i-i//B*B)%A:
            print(i)
            break

    else:
        print(-1)

Submission status: Accepted

Solution code:
from math import ceil, floor
A, B = map(int, input().split())

ans = 10**10
for b in range(1, A+1):
    a = ceil(b*B/A)
    c = a*A - b*B
    
    if b + c > a > 0:
        ans = min(ans, a*A)
        
if ans == 10**10:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    a, b = map( int, input().split())
    if max((b-1+a-2)//(a-1), (b+a-1)//a) < (a+b)/a:
        print(max((b-1+a-2)//(a-1), (b+a-1)//a)*a)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

A, B = inpl()

def calca(x):
    return x//A + x%A

X = -(-B//A)*A
Y = calca(X - X//B*B) + X//B
if -(-B//A) < Y:
    print(X)
else:
    print(-1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())

if B%A == 0:
    print(-1)
    exit()

_k = -(-B//A)

for k in range(_k, _k+10**7):
    bn, rem = divmod(k*A, B)
    an, rem = divmod(rem, A)
    n = bn + an + rem
    if n > k:
        print(k*A)
        exit()
print(-1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())

#初めてBより大きくなるaの枚数をカウント
a = (B + A -1) //A

#その値は A * a
ans = A * a

# この時貧浴で支払う
b = ans//B
ans -= B * b
b += ans//A
ans -= A * (ans //A)
b += ans%A

if b >= a:
    print (A * a)
else:
    print (-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template




def main():
    """
    6 7
6 8
6 9
6 10
6 13
6 14
6 15
6 19
6 20
6 25
    """
    A, B = mi()
    if B > (A - 1) ** 2:
        print(-1)
        sys.exit()
    if B % (A - 1) == 0:
        print(A * ceil(B / A))
    else:
        a = B // (A - 1)
        b = B % (A - 1)
        if a < b:
            print(A * ceil(B / A))
        else:
            print(-1)
    # dp1 = [float('inf')] * 100
    # dp2 = [float('inf')] * 100
    # dp1[0] = dp2[0] = 0
    # for i in range(1, 100):
    #     dp1[i] = min(dp1[i], dp1[i - 1] + 1)
    #     if i >= A:
    #         dp1[i] = min(dp1[i], dp1[i - A] + 1)
    #     if i >= B:
    #         dp1[i] = min(dp1[i], dp1[i - B] + 1)
    # for i in range(1, 100):
    #     if i >= B:
    #         dp2[i] = dp2[i - B] + 1
    #     elif i >= A:
    #         dp2[i] = dp2[i - A] + 1
    #     else:
    #         dp2[i] = dp2[i - 1] + 1
    # for i in range(100):
    #     if dp1[i] != dp2[i]:
    #         print(A, B)
    #         break
    # for i in range(100):
    #     if dp1[i] != dp2[i]:
    #         debug(i, dp1[i], dp2[i], "?")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    p = LI()
    t = LI()
    ans = float("inf")
    for i in range(n+1):
        x0 = t[0]*i
        m0 = p[0]*i
        for j in range(n+1):
            x1 = x0+t[1]*j
            m1 = m0+p[1]*j
            for k in range(n+1):
                x2 = x1+t[2]*k
                m2 = m1+p[2]*k
                rest = max(0,math.ceil((n-x2)/t[3]))
                m3 = m2+p[3]*rest
                if m3 < ans:
                    ans = m3
    print(ans)
    return

#B
def B():
    def f(n):
        if n < 4:
            return 1
        m = n
        res = 1
        i = 2
        while i**2 <= n:
            if m%i == 0:
                if m//i != i:
                    res *= m//i
                res *= i
            i += 1
        return res
    MA = 100000
    d = [0]*(MA+1)
    for i in range(12,MA+1):
        if not d[i]:
            if f(i) >= (i<<1):
                j = i
                while j <= MA:
                    d[j] = 1
                    j += i
    for i in range(MA):
        d[i+1] += d[i]
    q = I()
    for i in range(q):
        print(d[I()])
    return

#C
def C():
    n = I()

    return

#D
def D():
    a,b = LI()
    for i in range(b+1,b+a):
        x = i//b
        j = i%b
        x += j//a
        j = j%a
        x += j
        y = i//a+i%a
        if y < x:
            print(i)
            break
    else:
        print(-1)
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#Solve
if __name__ == "__main__":
    D()