You are given three positive integers x, y, n. Your task is to find the nearest fraction to fraction [Image] whose denominator is no more than n. 

Formally, you should find such pair of integers a, b (1 ≤ b ≤ n; 0 ≤ a) that the value $|\frac{x}{y} - \frac{a}{b}|$ is as minimal as possible.

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.


-----Input-----

A single line contains three integers x, y, n (1 ≤ x, y, n ≤ 10^5).


-----Output-----

Print the required fraction in the format "a/b" (without quotes).


-----Examples-----
Input
3 7 6

Output
2/5

Input
7 2 4

Output
7/2

Difficulty: MEDIUM_HARD
Tags: Amortized analysis

Implementation

Complete search
Skill types: Amortized analysis

Complete search

Starter code:

Solutions:
import math, sys
import heapq
from fractions import Fraction
from collections import Counter, defaultdict

def li():
	return list(map(int, sys.stdin.readline().split()))

def ls():
	return list(map(int, list(input())))

def la():
	return list(input())

def ii():
	return int(input())

def dic(x):
	return defaultdict(lambda : x)

def isPrime(n):
	i = 2
	if n == 1:
		return False
	while i <= int(math.sqrt(n)):
		if n % i == 0:
			return False
		i = i + 1
	return True

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def binarySearch(arr, x):
	(l, r) = (0, len(arr) - 1)
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return True
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return False
minn = float('inf')
(x, y, n) = li()
a = Fraction(x, y).limit_denominator(n)
print('{}/{}'.format(a.numerator, a.denominator))


from fractions import Fraction
(x, y, n) = map(int, input().split())
z = Fraction(x, y).limit_denominator(n)
print(z.numerator, z.denominator, sep='/')


from fractions import Fraction
(x, y, d) = map(int, input().split())
f = Fraction(x, y).limit_denominator(d)
print(str(f.numerator) + '/' + str(f.denominator))


def main():
	from sys import stdin, stdout
	from math import ceil, floor
	(x, y, n) = list(map(int, stdin.readline().split()))
	ans = []
	n = min(n, y)
	ratio = x / y
	while n:
		a = floor(ratio * n)
		b = ceil(ratio * n)
		if abs(a / n - ratio) <= abs(b / n - ratio):
			ans.append((round(abs(a / n - ratio), 15), n, a))
		else:
			ans.append((round(abs(b / n - ratio), 15), n, b))
		n -= 1
	ans.sort()
	stdout.write(str(ans[0][2]) + '/' + str(ans[0][1]))

def __starting_point():
	main()
__starting_point()


(x, y, n) = map(int, input().split())
(best, mn, eps) = ([0, 0], 10 ** 9, 1e-15)
for i in range(1, n + 1):
	m1 = i * x // y
	m2 = (i * x + y - 1) // y
	a = abs(x / y - m1 / i)
	b = abs(x / y - m2 / i)
	if a < mn - eps:
		mn = a
		best = [m1, i]
	if b < mn - eps:
		mn = b
		best = [m2, i]
print(*best, sep='/')


from fractions import Fraction
(x, y, n) = map(int, input().split())
t = Fraction(x, y).limit_denominator(n)
print(str(t.numerator) + '/' + str(t.denominator))


class Fraction:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __sub__(self, a):
		return Fraction(self.x * a.y - a.x * self.y, self.y * a.y)

	def __lt__(self, a):
		return self.x * a.y < self.y * a.x

	def __abs__(self):
		if self.x < 0:
			return Fraction(-self.x, self.y)
		return self

	def __str__(self):
		return str(self.x) + '/' + str(self.y)
(x, y, n) = list(map(int, input().split()))
f = Fraction(x, y)
dif = None
for i in range(1, n + 1):
	m = x * i // y
	for d in [m, m + 1]:
		g = Fraction(d, i)
		if dif is None or abs(f - g) < dif:
			dif = abs(f - g)
			ans = g
print(ans)


from __future__ import division, print_function
from sys import stdin, stdout
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from math import ceil, floor, log, sqrt, factorial, pow, pi, gcd
from fractions import Fraction

def ii():
	return int(input())

def si():
	return str(input())

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

def li():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d.keys():
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = {}
	for i in range(n):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			s.add(i)
			n = n // i
	if n > 2:
		s.add(n)
	return s
(a, b, n) = mi()
a = Fraction(a, b).limit_denominator(n)
print(a.numerator, a.denominator, sep='/')


from fractions import Fraction
(x, y, n) = map(int, input().split())
val = Fraction(x, y)
ret = val.limit_denominator(n)
print('%d/%d' % (ret.numerator, ret.denominator))


from operator import itemgetter
import math
import fractions

def res(a, b, x, y, low):
	if low:
		return abs(fractions.Fraction(x, y) - fractions.Fraction(a, b))
	else:
		return abs(x / y - a / b)

class CodeforcesTask281BSolution:

	def __init__(self):
		self.result = ''
		self.x_y_n = []

	def read_input(self):
		self.x_y_n = [int(x) for x in input().split(' ')]

	def process_task(self):
		if self.x_y_n[2] >= self.x_y_n[1]:
			(a, b) = (self.x_y_n[0], self.x_y_n[1])
			while not math.gcd(a, b) == 1:
				g = math.gcd(a, b)
				a //= g
				b //= g
			self.result = '{0}/{1}'.format(a, b)
		else:
			results = []
			base = self.x_y_n[0] / self.x_y_n[1]
			l = self.x_y_n[2] < 100
			for den in range(1, self.x_y_n[2] + 1):
				a2 = int(base * den)
				a1 = a2 - 1
				a3 = a2 + 1
				results.append((res(a1, den, self.x_y_n[0], self.x_y_n[1], l), a1, den))
				results.append((res(a2, den, self.x_y_n[0], self.x_y_n[1], l), a2, den))
				results.append((res(a3, den, self.x_y_n[0], self.x_y_n[1], l), a3, den))
			results.sort(key=itemgetter(0))
			(a, b) = (results[0][1], results[0][2])
			while not math.gcd(a, b) == 1:
				g = math.gcd(a, b)
				a //= g
				b //= g
			self.result = '{0}/{1}'.format(a, b)

	def get_result(self):
		return self.result
Solution = CodeforcesTask281BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


from fractions import Fraction
(x, y, n) = input().split()
x = int(x)
y = int(y)
n = int(n)
if Fraction(x / y).limit_denominator(n) == 0:
	print('0/1')
elif Fraction(x / y).limit_denominator(n) == int(Fraction(x, y).limit_denominator(n)):
	print(str(Fraction(x, y).limit_denominator(n)) + '/1')
elif (2 * Fraction(x, y) - Fraction(x / y).limit_denominator(n)).denominator >= Fraction(x / y).limit_denominator(n).denominator:
	print(Fraction(x / y).limit_denominator(n))
else:
	a = 2 * Fraction(x, y) - Fraction(x / y).limit_denominator(n)
	print(str(a.numerator) + '/' + str(a.denominator))


from fractions import Fraction
(a, b, n) = map(int, input().split(' '))
f = Fraction(a, b).limit_denominator(n)
x = f.numerator
y = f.denominator
print(str(x) + '/' + str(y))


from fractions import Fraction as frac
(a, b, n) = map(int, input().split())
f = frac(a, b).limit_denominator(n)
print(str(f.numerator) + '/' + str(f.denominator))


def gcd(a, b):
	return gcd(b % a, a) if a else b
(x, y, n) = map(int, input().split())
z = gcd(x, y)
(x, y) = (x // z, y // z)
if n < y:
	d = [min(i, y - i) for i in (x * i % y for i in range(0, n + 1))]
	for i in range(n - 1, 0, -1):
		if d[i] < d[n] and n * d[i] <= i * d[n]:
			n = i
	print(str(x * n // y + int(2 * (x * n % y) > y)) + '/' + str(n))
else:
	print(str(x) + '/' + str(y))


import sys
from fractions import Fraction
data = [x.rstrip() for x in sys.stdin]
l = data[0].split()
x = int(l[0])
y = int(l[1])
n = int(l[2])
f = Fraction(x, y).limit_denominator(n)
x = f.numerator
y = f.denominator
print(str(x) + '/' + str(y))


from fractions import Fraction
(x, y, n) = map(int, input().split())
ans = Fraction(x, y).limit_denominator(n)
if ans == int(ans):
	ans = str(ans) + '/1'
print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest, _heapify_max, _heapreplace_max
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def outln(var):
	sys.stdout.write(str(var) + '\n')

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(x, y, n) = sp()
f = Fraction(x, y).limit_denominator(n)
outln(str(f.numerator) + '/' + str(f.denominator))


import sys
from fractions import Fraction

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = int(1000000000.0) + 7
(x, y, n) = rinput()
ans = Fraction(x, y).limit_denominator(n)
print(str(ans.numerator) + '/' + str(ans.denominator))


import math
(x, y, n) = map(int, input().split())
best = (0, 0)
mingap = 10 ** 9
eps = 1e-15
for i in range(1, n + 1):
	m = i * x / y
	m1 = math.floor(m)
	m2 = math.ceil(m)
	gap1 = abs(x / y - m1 / i)
	gap2 = abs(x / y - m2 / i)
	if gap1 < mingap - eps:
		mingap = gap1
		best = (m1, i)
	if gap2 < mingap - eps:
		mingap = gap2
		best = (m2, i)
print(*best, sep='/')


from sys import *
from bisect import *
from collections import *
from itertools import *
from fractions import *
Input = []

def Out(x):
	stdout.write(str(x) + '\n')

def In():
	return stdin.readline().strip()

def inputGrab():
	for line in stdin:
		Input.extend(map(str, line.strip().split()))

def Search(target, Y):
	low = 0
	hi = 100009
	Min = 1000000.0
	ANS = 0
	for i in range(80):
		X = (low + hi) // 2
		if abs(X / Y - target) <= Min:
			Min = abs(X / Y - target)
			ANS = X
		if X / Y <= target:
			low = X + 1
		else:
			hi = X - 1
	return ANS

def main():
	(x, y, n) = map(int, In().split())
	ansX = 0
	ansY = 0
	Min = Fraction(100000, 100000)
	for Y in range(1, n + 1):
		X = Search(x / y, Y)
		Dist = abs(Fraction(X, Y) - Fraction(x, y))
		if Dist < Min:
			ansX = X
			ansY = Y
			Min = Dist
	print(str(ansX) + '/' + str(ansY))
main()


from math import ceil, floor
(x, y, n) = map(int, input().split())
if 1 == 2:
	print('djgisf')
else:
	p = x / y
	now = []
	mini = 10 ** 9
	a = y - n
	for req in range(0, y + 1, 1):
		up = req * (x / y)
		x1 = x - up
		y1 = y - req
		if y1 <= 0 or y1 > n:
			now.append([-1, -1, 10 ** 10])
			continue
		a1 = x1 / y1
		a2 = floor(x1) / y1
		a3 = ceil(x1) / y1
		if abs(a2 - p) <= abs(a3 - p):
			now.append([floor(x1), y1, round(abs(a2 - p), 14)])
		else:
			now.append([ceil(x1), y1, round(abs(a3 - p), 14)])
	now = now[::-1]
	for i in range(len(now)):
		diff = now[i][2]
		if diff < mini:
			mini = diff
			a = now[i][0]
			b = now[i][1]
	print(str(a) + '/' + str(b))


from math import inf, floor, ceil
(x, y, n) = map(float, input().split())
m = inf
ans = ''
for b in range(1, int(n + 1)):
	a = floor(x * b / y)
	z = abs(x / y - a / b)
	if z < m - 1e-15:
		m = z
		ans = str(a) + '/' + str(b)
	a = ceil(x * b / y)
	z = abs(x / y - a / b)
	if z < m - 1e-15:
		m = z
		ans = str(a) + '/' + str(b)
print(ans)


(x, y, n) = map(int, input().split())
ansNum = -1
ansDenom = -1
for b in range(1, n + 1):
	a = x * b // y
	if x * b % y * 2 > y:
		a += 1
	if ansNum == -1 or abs(x / y - ansNum / ansDenom) > abs(x / y - a / b):
		ansNum = a
		ansDenom = b
print(ansNum, ansDenom, sep='/')


from fractions import Fraction as F
(x, y, n) = map(int, input().split())
a = F(x, y).limit_denominator(n)
print(a.numerator, '/', a.denominator, sep='')


def s():
	[x, y, n] = list(map(int, input().split()))
	res = (0, 1)
	for b in range(1, n + 1):
		a = int(round(b * x / y, 0) + 0.1)
		if abs(x * res[1] - y * res[0]) * b > abs(x * b - y * (a - 1)) * res[1]:
			res = (a - 1, b)
		if abs(x * res[1] - y * res[0]) * b > abs(x * b - y * a) * res[1]:
			res = (a, b)
	print(*res, sep='/')
s()


from math import gcd
(x, y, n) = map(int, input().split())
if y <= n:
	t = gcd(x, y)
	print(f'{x // t}/{y // t}')
else:
	ans = [0, n]
	ansdif = abs(x / y - ans[0] / ans[1])
	for b in range(1, n + 1):
		a = b * x // y
		t = a
		dif = abs(x * b - y * a) / (y * b)
		if dif < ansdif:
			ans[0] = a
			ans[1] = b
			ansdif = dif
		a = max(0, t - 1)
		dif = abs(x * b - y * a) / (y * b)
		if dif < ansdif:
			ans[0] = a
			ans[1] = b
			ansdif = dif
		a = t + 1
		dif = abs(x * b - y * a) / (y * b)
		if dif < ansdif:
			ans[0] = a
			ans[1] = b
			ansdif = dif
	print(f'{ans[0]}/{ans[1]}')


from fractions import Fraction
(a, b, c) = map(int, input().split())
print('{0.numerator}/{0.denominator}'.format(Fraction(a, b).limit_denominator(c)))


from fractions import Fraction
from ast import Try
from io import BytesIO, IOBase
import math
import time
import sys
import os
from math import gcd, floor, sqrt, log
input: lambda : sys.stdin.readline().rstrip()
start_time = time.time()

def iin():
	return int(input())

def sin():
	return input().strip()

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

def liststr():
	return list(map(str, input().strip().split()))

def ceill(x):
	return int(x) if x == int(x) else int(x) + 1

def ceilldiv(x, d):
	return x // d if x % d == 0 else x // d + 1

def LCM(a, b):
	return a * b // gcd(a, b)

def solve():
	(x, y, n) = listin()
	x = Fraction(x, y).limit_denominator(n)
	print(x.numerator, end='/')
	print(x.denominator)
ttt = 1
for hula in range(ttt):
	solve()


import sys
input = sys.stdin.buffer.readline
from math import *
(x, y, n) = map(int, input().split())
if n >= y:
	gc = gcd(x, y)
	print('%d/%d' % (x // gc, y // gc))
else:
	ans1 = 0
	ans2 = 1
	for i in range(1, n + 1):
		a = i * x // y
		if fabs(ans2 * x - ans1 * y) * i > fabs(i * x - a * y) * ans2:
			ans1 = a
			ans2 = i
		a += 1
		if fabs(ans2 * x - ans1 * y) * i > fabs(i * x - a * y) * ans2:
			ans1 = a
			ans2 = i
	print('%d/%d' % (ans1, ans2))


from fractions import *
(x, y, k) = list(map(int, input().split()))
ans = Fraction(x, y).limit_denominator(k)
print(str(ans.numerator) + '/' + str(ans.denominator))


from fractions import Fraction
(a, b, c) = map(int, input().split())
z = f'{Fraction(a, b).limit_denominator(c)}'
if '/' not in z:
	print(z + '/1')
else:
	print(z)


from fractions import Fraction
(x, y, n) = input().split()
x = int(x)
y = int(y)
n = int(n)
if (2 * Fraction(x, y) - Fraction(x / y).limit_denominator(n)).denominator >= Fraction(x / y).limit_denominator(n).denominator:
	b = Fraction(x / y).limit_denominator(n)
	print(str(b.numerator) + '/' + str(b.denominator))
else:
	a = 2 * Fraction(x, y) - Fraction(x / y).limit_denominator(n)
	print(str(a.numerator) + '/' + str(a.denominator))


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import stdin, stdout
from io import BytesIO, IOBase
from itertools import accumulate
from collections import deque

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a
l = []
for i in range(1, 20):
	l.append(2 ** i)

def main():
	(x, y, n) = sep()
	c = Fraction(x, y).limit_denominator(n)
	c = str(c)
	if '/' in c:
		print(c)
	else:
		print(c + '/' + '1')
main()


from fractions import Fraction
(a, b, d) = map(int, input().split(' '))
f = Fraction(a, b).limit_denominator(d)
num = f.numerator
den = f.denominator
print(str(num) + '/' + str(den))


from fractions import Fraction
(x, y, n) = map(int, input().split())
b = Fraction(x, y).limit_denominator(n)
print('{}/{}'.format(b.numerator, b.denominator))


from fractions import Fraction
(x, y, n) = map(int, input().split())
f = Fraction(x, y).limit_denominator(n)
if '/' not in str(f):
	print(str(f) + '/1')
else:
	print(f)


from __future__ import division, print_function
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 21)
mod = 10 ** 9 + 7

def bucketsort(order, seq):
	buckets = [0] * (max(seq) + 1)
	for x in seq:
		buckets[x] += 1
	for i in range(len(buckets) - 1):
		buckets[i + 1] += buckets[i]
	new_order = [-1] * len(seq)
	for i in reversed(order):
		x = seq[i]
		idx = buckets[x] = buckets[x] - 1
		new_order[idx] = i
	return new_order

def ordersort(order, seq, reverse=False):
	bit = max(seq).bit_length() >> 1
	mask = (1 << bit) - 1
	order = bucketsort(order, [x & mask for x in seq])
	order = bucketsort(order, [x >> bit for x in seq])
	if reverse:
		order.reverse()
	return order

def long_ordersort(order, seq):
	order = ordersort(order, [int(i & 2147483647) for i in seq])
	return ordersort(order, [int(i >> 31) for i in seq])

def multikey_ordersort(order, *seqs, sort=ordersort):
	for i in reversed(range(len(seqs))):
		order = sort(order, seqs[i])
	return order

def solve(case):
	(x, y, n) = sep()
	mn = inf
	for i in range(1, n + 1):
		temp = int(i * x / y)
		l = lcm(i, y)
		mn = min(mn, round(abs(x * (l // y) - temp * (l // i)) / l, 18))
		mn = min(mn, round(abs(x * (l // y) - (temp + 1) * (l // i)) / l, 18))
	ll = []
	rr = []
	for i in range(1, n + 1):
		temp = i * x // y
		l = lcm(i, y)
		if round(abs(x * (l // y) - temp * (l // i)) / l, 18) == mn:
			ll.append(i)
			rr.append(temp)
		if round(abs(x * (l // y) - (temp + 1) * (l // i)) / l, 18) == mn:
			ll.append(i)
			rr.append(temp + 1)
	order = multikey_ordersort(range(len(ll)), ll, rr)
	print(rr[order[0]], end='/')
	print(ll[order[0]])
testcase(1)


from fractions import Fraction
(x, y, n) = map(int, input().split())
ans = Fraction(x, y).limit_denominator(n)
num = ans.numerator
denom = ans.denominator
print(str(num) + '/' + str(denom))


import sys
s = input()
all = s.split()
ans = 'lol'
n = int(all[2])
x = float(all[0])
y = float(all[1])
a = 0
b = 1
dif = x / y
for i in range(1, n + 1):
	na = int(x * i / y)
	if dif > abs(x * i - na * y) / (y * i):
		a = na
		b = i
		dif = abs(x * i - na * y) / (y * i)
	na = na + 1
	if dif > abs(x * i - na * y) / (y * i):
		a = na
		b = i
		dif = abs(x * i - na * y) / (y * i)
ans = str(a) + '/' + str(b)
print(ans)


import os
import sys
from io import BytesIO, IOBase
import math

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)
(x, y, n) = map(int, input().split())
v = x / y
ans = [100000000000, 1]
ansv = 1000000000
for b in range(1, n + 1):
	a1 = int(v * b)
	a2 = a1 + 1
	ansa1 = round(abs(a1 / b - v), 15)
	ansa2 = round(abs(a2 / b - v), 15)
	if ansa1 < ansv:
		ansv = ansa1
		(ans[0], ans[1]) = (a1, b)
	if ansa2 < ansv:
		ansv = ansa2
		(ans[0], ans[1]) = (a2, b)
print(str(ans[0]) + '/' + str(ans[1]))