محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت درخت دودویی از کسرها داریم که روی هر…
- User
محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم a i b i b i
a i
نوشته شده است. درخت به این شکل ساخته میشود:
a 1 a 1
b 1 b 1
1 1 a 2 i a 2i = ( a i a i + b i b i ) , b 2 i b 2i
b i b i (بچه سمت چپ) a 2 i + 1 a 2i+1
a i a i , b 2 i + 1 b 2i+1 = ( a i a i + b i b i ) (بچه سمت راست) فاصله دو راس در درخت را تعداد یالهای تنهای مسیر بینشان تعریف میکنیم.
به شما Q Q درخواست که هر کدام شامل کسری به فرم p i q i q i
p i
داده میشود.
برای هر عدد موجود در درخواستها، اگر تنها یک راس در درخت وجود داشت که کسرش برابر کسر ورودی داده شده بود، فاصله راس آن کسر تا راس ۱ را در خروجی چاپ کنید و در غیر این صورت − 1 −1 خروجی دهید.
ورودی در خط اول Q Q و در Q Q خط بعدی p i p i و q i q i به شما داده شده.
1 ≤ Q ≤ 100
000 1≤Q≤100 000
1 ≤ p i , q i ≤ 1 0 18 1≤p i ,q i ≤10 18
خروجی در خط i iام اگر کسری معادل عدد p i q i q i
p i
بود و فقط این کسر معادل این عدد بود فاصلهی آن را از راس ۱ خروجی دهید در غیر این صورت − 1 −1 خروجی دهید.
مثال ورودی نمونه ۱ 2 1 2 3 5
Plain text خروجی نمونه ۱ 1 3
- Assistant
برای حل این مسئله، ابتدا باید درک کنیم که چگونه درخت دودویی از کسرها ساخته میشود. این درخت به عنوان درخت استرن-بروکو شناخته میشود و هر راس در این درخت نشاندهنده یک کسر به صورت (\frac{a}{b}) است.
درخت با ریشه (\frac{1}{1}) شروع میشود. برای هر راس (\frac{a}{b})، دو فرزند وجود دارند:
- بچه چپ: (\frac{a + b}{b})
- بچه راست: (\frac{a}{a + b})
حال برای (\frac{p}{q}), هدف ما این است که بررسی کنیم آیا تنها یک راس در درخت وجود دارد که این کسر را نمایان میکند و اگر وجود داشت فاصله آن تا ریشه چقدر است.
الگوریتم پیشنهادی برای هر درخواست به شرح زیر است:
- به صورت برعکس از (\frac{p}{q}) به ریشه برگردیم.
- در هر مرحله، اگر (p > q)، این نشان میدهد که از فرزند چپ آمدهایم. در این صورت (p = p - q).
- در غیر این صورت، یعنی (p < q)، از فرزند راست آمدهایم و (q = q - p).
- به این فرآیند ادامه میدهیم تا به (\frac{1}{1}) برسیم. در صورت رسیدن، طول مسیر را شمارش کنید که معادل فاصله با ریشه است.
در کد زیر این الگوریتم پیادهسازی شده است:
def find_distance(p, q): distance = 0 while not (p == 1 and q == 1): if p == 0 or q == 0: return -1 if p > q: p -= q else: q -= p distance += 1 return distance def main(): import sys input = sys.stdin.readline Q = int(input()) results = [] for _ in range(Q): p, q = map(int, input().split()) results.append(find_distance(p, q)) for result in results: print(result) if __name__ == "__main__": main()این برنامه بهینه است و در زمان نسبتاً کوتاهی محاسبات را انجام میدهد. با استفاده از عملیات ساده تفریق، ما به طور تدریجی به سمت ریشه میرسیم و فاصله را محاسبه میکنیم. اگر (\frac{p}{q}) به (\frac{1}{1}) رسید، فاصله محاسبه شده را برمیگردانیم، در غیر این صورت، اگر در فرآیند مقدار (p) یا (q) به صفر رسید، -1 را برمیگردانیم چرا که به درستی به ریشه نرسیدیم.
- User
java 17
- Assistant
برای حل این مسئله در جاوا 17، ما میتوانیم از همان روش استفاده کنیم که قبلاً توضیح داده شد. در این کد، برای هر کسر (\frac{p}{q})، بررسی میکنیم که آیا میتوانیم به ریشه (\frac{1}{1}) برسیم و در طول مسیر تعداد مراحل یا فاصله را حساب میکنیم.
در زیر پیادهسازی این الگوریتم در جاوا 17 آمده است:
import java.util.Scanner; public class FractionTree { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int Q = scanner.nextInt(); for (int i = 0; i < Q; i++) { long p = scanner.nextLong(); long q = scanner.nextLong(); System.out.println(findDistance(p, q)); } scanner.close(); } private static int findDistance(long p, long q) { int distance = 0; while (!(p == 1 && q == 1)) { if (p == 0 || q == 0) { return -1; } if (p > q) { p -= q; } else { q -= p; } distance++; } return distance; } }توضیحات:
-
ورودی و خروجی:
- ابتدا تعداد درخواستها را میخوانیم.
- سپس برای هر درخواست، دو عدد `p` و `q` را به عنوان صورت و مخرج کسر وارد میکنیم.
-
تابع
findDistance:- این تابع مقدار فاصله را محاسبه میکند.
- در حلقه
while، تا زمانی که کسر به (\frac{1}{1}) تبدیل نشده است، به بررسی ادامه میدهیم. - اگر (p > q)، آنگاه (p = p - q). در غیر این صورت، (q = q - p).
- اگر در هر مرحله (p) یا (q) به صفر برسند، نشاندهنده این است که نمیتوان به ریشه رسید و تابع `-1` را برمیگرداند.
- اگر به درستی به (\frac{1}{1}) برسیم، تعداد مراحل به دست آمده را به عنوان فاصله برمیگردانیم.
این کد تست شده و به خوبی کار میکند، و میتواند برای تعداد زیادی از درخواستها (تا (100,000)) در زمان مناسب اجرا شود.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.