מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מסלולים זולים לכלל הזוגות/תרגילים/זיהוי ארביטראג'/שאלה

יחסי המרה

	שקל	דולר	דינאר	דונג
שקל	1	0.2		100
דולר	4.5	1	3	10000
דינאר		0.2	1	1000
דונג	0.001	0.00009	0.0009	1

נתונה טבלת יחסי המרה $\displaystyle W$ בין מטבעות שונים, לדוגמה הטבלה שמצד שמאל. הטבלה מציינת כמה יחידות ממטבע כלשהו אפשר לקבל עבור 1 יחידת מטבע.

דוגמה: בטבלה שמשמאל: ניתן להמיר $\displaystyle 1$ שקל ל$\displaystyle 0.2$ דולר. ניתן להמיר $\displaystyle 1$ דולר ל$\displaystyle 4.5$ שקל. אי אפשר להמיר ישירות שקל לדינאר.

הגדרה: נאמר שקיים ארביטראז' אם קיימת סדרת המרות שמסתיימת ברווח חד-משמעי.

דוגמה: בטבלה שמשמאל, נניח שאנו מתחילים עם $\displaystyle 1$ שקל. נמיר את השקל ל $\displaystyle 0.2$ דולר. נמיר את $\displaystyle 0.2$הדולר ל$\displaystyle 0.2\cdot 10000=2000$ דונג. נמיר את $\displaystyle 2000$ הדונג ל$\displaystyle 2$ שקלים. הכפלנו את כספנו!

אנא מצא אלגוריתם יעיל המוצא האם בטבלת המרות כלשהי קיים ארביטראז'.

רמז: השתמש בזהות הידועה $\displaystyle \log(p_{1}\cdot p_{2}\cdots p_{k})=\log(p_{1})+\log(p_{2})+\cdots +\log(p_{k})$.