Problem:


Score : 400 points

Problem Statement

Given are integers A, B, and N.

Find the maximum possible value of floor(Ax/B) - A × floor(x/B) for a non-negative integer x not greater than N.

Here floor(t) denotes the greatest integer not greater than the real number t.

Constraints

1 ≤ A ≤ 10^{6}

1 ≤ B ≤ 10^{12}

1 ≤ N ≤ 10^{12}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B N

Output

Print the maximum possible value of floor(Ax/B) - A × floor(x/B) for a non-negative integer x not greater than N, as an integer.

Sample Input 1

5 7 4

Sample Output 1

2

When x=3, floor(Ax/B)-A×floor(x/B) = floor(15/7) - 5×floor(3/7) = 2. This is the maximum value possible.

Sample Input 2

11 10 9

Sample Output 2

9



Sample input:
5 7 4


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	A,B,N = inputMap()

	maxs = 0
	conts = 0
	for x in range(N,0,-1):
		tmp = math.floor(A * x / B) - A * math.floor(x / B)
		conts += 1
		if maxs < tmp:
			maxs = tmp
		if conts == 30000000:
			break

	print(maxs)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import heapq
    input = sys.stdin.readline
    A,B,N=map(int,input().split())
    Z=[]
    heapq.heapify(Z)
    for x in range(N+1):
        Y=int(A*x/B)-A*int(x/B)
        heapq.heappush(Z,-1*Y)
    
    result=-1*heapq.heappop(Z)
    print(result)    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

a,b,n= map(int, input().split())

c = a/b
p = []

for x in range(n + 1):
    d = math.floor(c * x) - a * math.floor(x / b)
    p.append(d)

p.sort()
print(p[n])

Submission status: Time Limit Exceeded

Solution code:
a, b, n = map(int, input().split())
 
tmp = 0
for x in (range(1, b+1, 2) if b<=n else range(1, n+1, n-1)):
#for x in range(1, n+1):
    calc = a*x//b - a*(x//b)
    if calc > tmp:
        tmp = calc
 
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
a, b, n = map(int, input().split())
if n < b:
    print((a*n)//b)
else:
    ans = -1
    for x in range(b//a, b*2+1):
        tmp = (a*x)//b - a*(x//b)
        if tmp > ans:
            ans = tmp
        elif tmp < ans:
            break
    print(ans)

Submission status: Time Limit Exceeded

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

import math

a = [math.floor(A*i/B) - A*math.floor(i/B) for i in range(N+1)]

print(max(a))

Submission status: Time Limit Exceeded

Solution code:
A,B,N = input().split()
A = int(A)
B = int(B)
N = int(N)
ans = 0
for x in range(N+1):
    if x < B:
        ans_2 = int((A * x)/B)
    else:
        ans_2 = int((A * x)/B) - (A * int(x/B))
    if ans < ans_2:
        ans = ans_2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b, n = [int(x) for x in input().split()]

x = 2
answer = (a*1//b) - a*(1//b)
while x <= n:
    if (a*x//b) - a*(x//b) > answer:
        answer = (a*x//b) - a*(x//b)
    x += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
N = list(map(int, input().split()))
ans = []
for i in range(N[2] + 1):
    f_1 = (N[0]*i)//N[1]
    f_2 = N[0] * (i//N[1])
    ans.append(f_1 - f_2)
ans.sort()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
a,b,n=map(int,input().split())
ans=0
for x in range(n+1):
  test_ans=int(a*x/b)-a*int(x/b)
  if test_ans>ans:
    ans=test_ans
print(ans)

Submission status: Time Limit Exceeded

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

if B>N:
  print(A*N//B)
  exit()
list=0
for i in range((9*N//10),N+1):
  if i>B:
    list=A*i//B
  else:
    c=((A*i)//B)-(A*(i//B))
    if list<c:
      list=c
print(list)

Submission status: Time Limit Exceeded

Solution code:
import math
A, B, N = map(int, input().split())
ans = []
for x in range(N//10**7, N+1):
    cal = math.floor((A*x)/B) - (int(A) * math.floor(x/B))
    ans.append(cal)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
A, B, N = input().split()
max = 0

for x in range(int(N) +1):
    num = (math.floor(int(A) * x / int(B)) - int(A) * math.floor(x / int(B)))
    if max < num:
        max = num

print(max)

Submission status: Time Limit Exceeded

Solution code:
import math
 
a, b, n = map(int, input().split(" "))
 
print(max([math.floor(a * i / b) - a * math.floor(i / b) for i in range(1, n + 1)]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	A,B,N = inputMap()

	maxs = 0
	conts = 0
	for x in range(N,0,-1):
		tmp = math.floor(A * x / B) - A * math.floor(x / B)
		conts += 1
		if maxs < tmp:
			maxs = tmp
		if conts == 40000000:
			break

	print(maxs)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
a,b,n=map(int,input().split())
mx=-100000000000
for i in range(1,n+1):
    k=(a*i//b)-a*(i//b)
    mx= max(k,mx)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
a, b, n = map(int, input().split())
ans = 0
for x in range(1, min(n+1, b)):
    tmp = (a*x // b) - a * (x//b)
    ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

A, B, N = map(int, input().split())

ans = 0
tmp = 0

for x in range(1, N + 1):
    tmp = math.floor(A * x / B) - A * (math.floor(x / B))
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import random
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math
A, B, N = MII_split()

def f(x):
    """最小値を求めたい関数"""
    return math.floor(A * x / B) - A * math.floor(x / B)

def numerical_diff(f, x):
    """中央差分を元に数値微分する関数"""
    h = 1e-4
    return (f(x + h) - f(x - h)) / (2 * h)

def gradient_descent(f, initial, learning_rate=1, steps=10**5):
    """一階導関数から勾配法で最小値を求める関数"""
    # 現在地を示すカーソル
    x = initial

    # 所定の回数を繰り返す
    for _ in range(steps):
        # 現在地の勾配 (どちらにどれだけ進むべきか) を得る
        grad = numerical_diff(f, x)
        # 勾配を元にして現在地を移動する
        x -= learning_rate * grad

    # 最終的な位置を返す
    return f(x)

ma = 0
for _ in range(100):
    ini = random.randrange(N + 1)
    tmp = gradient_descent(f, ini)
    # tmp = f(ini)
    if ma < tmp:
        ma = tmp


print(ma)

Submission status: Time Limit Exceeded

Solution code:
a,b,n = map(int,input().split())

import heapq
import math

list=[]
heapq.heapify(list)
for x in range(n+1):
    value = math.floor(a*x//b)-a*math.floor(x//b)
    heapq.heappush(list,-1*value)


print(heapq.heappop(list)*(-1))  #最大値の取得と表示

Submission status: Time Limit Exceeded

Solution code:
import math

a, b, n = map(int, input().split(" "))

_max = 0
i = 0
while i <= n:
    val = math.floor((a * i) / b) - (a * math.floor(i / b))
    _max = max(_max, val)
    i += 1

print(_max)

Submission status: Time Limit Exceeded

Solution code:
import math
A,B,N =list(map(int,input().split()))
def floor(a):
  if a.is_integer():
    return(int(a))
  else:
  	return(int(math.ceil(a)-1))
_che = 0
x=0
while x<=N:
  if A*x > B:
    y = floor((A*x)/B) - A*floor(x/B)
    if _che < y:
      _che = y
  if x == B:
    break
  x+=1
print(_che)

Submission status: Time Limit Exceeded

Solution code:
A,B,N = map(int,input().split())
j = 0
if N < B:
  print(int(A*N/B))
else:
  for i in range(1,N+1):
    k = int(A*i/B) - A*int(i/B)
    if k > j:
      j = k
  print(j)

Submission status: Time Limit Exceeded

Solution code:
a, b, n = map(int, input().split())
print(max({(i*a//b) - a*(i//b) for i in range(n+1)}))

Submission status: Time Limit Exceeded

Solution code:
import math
a,b,n=map(int,input().split())
max=-2
lim=min(n,b)
for i in range(1,lim+1):
    s=math.floor(a*i/b)-a*math.floor(i/b)
    if s>max:
        max=s
print(int(max))

Submission status: Time Limit Exceeded

Solution code:
a,b,n=map(int,input().split())
import math
x=b-1
m=[math.floor(a*n/b)-a*(math.floor(n/b))]
while x<=n:
    f=math.floor(a*x/b)-a*(math.floor(x/b))
    m.append(f)
    x+=b
print(max(m))

Submission status: Time Limit Exceeded

Solution code:
import math

arr = list(map(int, input().split()))

a = arr[0]
b = arr[1]
n = arr[2]


for x in range(0,n+1):
    answer = math.floor(a*x/b) - a*math.floor(x/b)
    if x==0:
        max_answer = answer
    elif max_answer<answer:
        max_answer = answer

print(max_answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math

a, b, n = map(int, input().split())

if b >= n:
    if n%b != 0:
        x = n 
        ans = math.floor(a*x/b) - a*math.floor(x/b)
        print(ans)
        exit(0)
    else:
        x = n-1 
        ans = math.floor(a*x/b) - a*math.floor(x/b)
        print(ans)
        exit(0)

f = [-1 for _ in range(b)]
for x in range(1, b+1):
    f[x-1] = math.floor(a*x/b) - a*math.floor(x/b)
print(max(f))

Submission status: Time Limit Exceeded

Solution code:
a,b,N = map(int, input().split())

Ansermax = 0

if b < N :
    N = b

for x in range(N+1):

    Anser = 0

    Anser = int((a*x)//b)-a*int(x//b)
    
    if Ansermax < Anser:
        Ansermax = Anser

print(Ansermax)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	A,B,N = inputMap()

	maxs = 0
	conts = 0
	for x in range(N,0,-1):
		tmp = math.floor(A * x / B) - A * math.floor(x / B)
		conts += 1
		if maxs < tmp:
			maxs = tmp
		if conts == 50000000:
			break

	print(maxs)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
A,B,N=(int(x) for x in input().split())
p=0
for i in range (N+1):
    j=(math.floor((A*i)/B))-(math.floor(i/B))*A
    if p<j:p=j
print(p)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,n=LI()

  # right=n
  # ans=math.floor(a*right/b)-a*math.floor(right/b)
  # left=0
  # while left<=right:
  #   half=(left+right)//2
  #   _ans=math.floor(a*half/b)-a*math.floor(half/b)
  #   if _ans==ans:
  #     return ans
  #   elif _ans>ans:
  #     right=half-1
  #     ans=_ans
  #   else:
  #     left=half+1

  ans=int(a*1/b)-a*int(1/b)
  x=int(math.sqrt(n))
  for i in range(max(0,n-x-100000000),n+1):
    ans=max(ans,int(a*i//b)-a*int(i//b))
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    a,b,n = inpm()
    ans = 0
    for i in range(min(b+1,n+1)):
        ans = max(ans,int(a*i/b)-a*int(i/b))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if B>N:
  print(A*N//B)
  exit()
list=0
for i in range((4*N//5),N+1):
  if i>B:
    list=A*i//B
  else:
    c=((A*i)//B)-(A*(i//B))
    if list<c:
      list=c
print(list)

Submission status: Time Limit Exceeded

Solution code:
A,B,N=map(int,input().split())
ans=[]
for x in range(1,N+1):
  l=A*x/B
  r=x/B
  ans.append(int(l)-A*int(r))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import math

A,B,N = list(map(int, input().split()))
ans = 0

for i in range(N):
    temp = math.floor(A*(i+1)/B) - A * math.floor((i+1)/B)
    if ans < temp:
        ans = temp

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from numba import jit


@jit
def solve(A, B, N):
    ans = 0
    for x in range(N + 1):
        calc = math.floor(A * x / B) - A * math.floor(x / B)
        ans = max(ans, calc)
    return ans


def main():
    A, B, N = map(int, input().split())

    print(solve(A, B, N))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split(' ')
a = int(inputs[0])
b = int(inputs[1])
n = int(inputs[2]) + 1

output = 0
loop_cnt = n if n < b else b
for x in range(1, loop_cnt):
    buf = (a*x//b)
    if buf > output:
        output = buf

print(output)

Submission status: Time Limit Exceeded

Solution code:
a, b, n = [int(x) for x in input().split()]
l = []
for i in range(1, n+1):
    l.append((a*i)//b - a*(i//b))
s = sorted(l)
print(s[len(s)-1])

Submission status: Time Limit Exceeded

Solution code:
import math
a, b, n = map(int, input().split())

result = 0
base_num = 0
for x in range(1, n+1):
    if x % b == 0:
        base_num += 1
        continue
    result_child = math.floor((a*x)/b) - a * base_num
    if result_child > result:
        result = result_child
print(result)

Submission status: Time Limit Exceeded

Solution code:
a, b, n = map(int, input().split())

cnt = 1
buf = []
while True:
    x = cnt * b - 1
    if n < x:
        break
    calc = int(a * x / b) - a * (int(x / b))
    buf.append(calc)
    cnt += 1
    
buf.append(int(a * n / b) - a * (int(n / b)))

ans = max(buf)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B,N=map(int,input().split())
count=0
for i in range(N+1):
    result=int(A*i/B)-(A*int(i/B))
#     print(result)
    if count<result:
        count=result
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
 
A, B, N = map(int, input().split())
list1 = []
for x in range(0, N+1):
    value = math.floor(A*x/B) - (A * math.floor(x/B))
    list1.append(value)
print(max(list1))

Submission status: Time Limit Exceeded

Solution code:
import math

A, B, N = map(int, input().split())
max = 0
temp = 0
bk_temp = 0

for i in range(1, N + 1):
    temp = math.floor(A*i/B) - (A * math.floor(i/B))
    if bk_temp > temp:
        max = bk_temp
        break
    if max < temp:
        max = temp
    bk_temp = temp

print(max)

Submission status: Time Limit Exceeded

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

answer=0

for i in range(1,N+1):
    f=int(A*i/B)-A*int(i/B)
    if f>answer:
        answer=f
    #print(f)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
a, b, n = map(int, input().split())
count = 0
ans = 0

for x in range(int(n), int(n/4), -1):
    n = math.floor(a*x/b) - a * math.floor(x/b)
    # print(n)
    if ans <= n:
      ans = n
  
print(ans)

Submission status: Time Limit Exceeded

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

def g(t):
    return int(A*t/B)-A*int(t/B)

Max_x=0

for i in range(N):
    if g(i)<g(i+1):
        Max_x=i+1
        
print(g(Max_x))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    a, b, n = map(int, input().split())
    ans = 0
    if n > 10 ** 10:
        for x in range(n, 10 ** 8, -1):
            fx = math.floor(a/b * x) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass

    elif n > 10 ** 8:
        for x in range(n, 10**6 , -1):
            fx = math.floor(a/b * x) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass

    elif n > 10 ** 6:
        for x in range(n, 10**4 , -1):
            fx = math.floor(a/b * x) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass

    elif n > 10 ** 4:
        for x in range(n, 10**2 , -1):
            fx = math.floor(a/b * x) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass
    else: 
        for x in range(n, 0, -1):
            fx = math.floor(a * x / b) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import floor
a,b,n = map(int,input().split())
if a == 1:
    print(0)
    exit()

prev = 0
for x in range(min(b-1,n),n+1, b):
    val = floor(a*x/b) - a*floor(x/b)
    if val < prev:
        print(prev)
        exit()
    prev = val

val = floor(a*n/b) - a*floor(n/b)
print(max(prev,val))

Submission status: Time Limit Exceeded

Solution code:
import math


a,b,n = map(int,input().split())
max=0
ans=0
n_2=int(n/2)
for i in range(n_2,n+1):
    ans=math.floor(i*a/b)-a*math.floor(i/b)
    if max<ans:
        max=ans

print(max)

Submission status: Time Limit Exceeded

Solution code:
a,b,n = map(int,input().split())

x = list()
if n<=b:
  for i in range(n+1):
    y = int(a*i/b) - a*int(i/b)
    x.append(y)
else:
  for i in range(b):
    y = int(a*i/b) - a*int(i/b)
    x.append(y)
x = sorted(x)
print(x[-1])

Submission status: Time Limit Exceeded

Solution code:
import math
a,b,n=(int(x) for x in input().split())
k =0
for x in range(0,n+1):
    c = math.floor((a*x)/b)
    d = a*math.floor(x/b)
    if c -d > k:
        k = c-d
print(k)

Submission status: Time Limit Exceeded

Solution code:
def calc(A, B, N):
    return max(map(lambda x: int(A * x / B) - A * int(x / B), range(1, N + 1)))


def main():
    A, B, X = list(map(int, input().split(' ')))
    print(calc(A, B, X))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
A,B,N=map(int,input().split())
y=0
for i in range(1,N+1):
    z=int(A*i/B)-A*int(i/B)
    if z>y:
        y=z

print(y)

Submission status: Time Limit Exceeded

Solution code:
a,b,c=map(int,input().split())
d=[]
for i in range(c+1):
    e=(a*i)//b-a*(i//b)
    d.append(e)
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
import math
a,b,n = map(int,input().split())
c = 0
for i in range(1,n+1):
    # tmp = (math.floor(a*i/b)-a*math.floor(i/b))
    if c < (math.floor(a*i/b)-a*math.floor(i/b)):
        c = (math.floor(a*i/b)-a*math.floor(i/b))
    elif c > 0 and c > (math.floor(a*i/b)-a*math.floor(i/b)):
        print(c)
        exit()
print(c)

Submission status: Time Limit Exceeded

Solution code:
import math

a, b, n = map(int, input().split(" "))

print(max([math.floor(a * i / b) - a * math.floor(i / b) for i in range(1, n + 1)]))

Submission status: Time Limit Exceeded

Solution code:
import math
a, b, n = map(int, input().split())
n1 = 0
n2 = 0
for i in range(n+1):
  n1 = math.floor(a*i/b)-5*math.floor(i/b)
  if n1 >= n2:
    n2 = n1
print(n2)