ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی i i و j j با فاصله از هم آمده است.…
- User
ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی i i و j j با فاصله از هم آمده است. 1 ≤ i , j ≤ 1
000
000 1≤i,j≤1 000 000
خروجی خروجی برنامهی شما باید شامل ۱ عدد صحیح باشد که برابر طول کوتاهترین مسیر بین دو کندوی i i و j j است.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۰۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 5 36 Plain text خروجی نمونه ۱ 3 Plain text ورودی نمونه ۲ 4 17 Plain text خروجی نمونه ۲ 4 java
- Assistant
به نظر میرسد که مسئلهای که مطرح کردهاید مربوط به یافتن کوتاهترین مسیر تبدیل عدد
iبه عددjبا استفاده از مجموعهای از عملیات مجاز باشد. بر اساس نمونههای ارائه شده، به نظر میرسد که عملیاتهای مجاز شامل:- اضافه کردن ۱ به عدد فعلی (
x + 1) - کم کردن ۱ از عدد فعلی (
x - 1) - ضرب عدد فعلی در ۲ (
x * 2) - ضرب عدد فعلی در ۳ (
x * 3)
میباشد. بنابراین، میتوان از الگوریتم جستجوی ابتدا-اول (BFS) برای یافتن کوتاهترین مسیر استفاده کرد. در اینجا پیادهسازی یک راهکار در زبان جاوا ارائه شده است:
import java.util.*; import java.io.*; public class ShortestPathBetweenHives { static class Node { int value; int steps; Node(int value, int steps) { this.value = value; this.steps = steps; } } public static void main(String[] args) throws IOException { // خواندن ورودی BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().trim().split("\\s+"); int start = Integer.parseInt(input[0]); int end = Integer.parseInt(input[1]); // اگر شروع و پایان یکسان هستند if (start == end) { System.out.println(0); return; } // محدوده اعداد int MAX = 1000000; boolean[] visited = new boolean[MAX + 1]; // ایجاد صف برای BFS Queue<Node> queue = new LinkedList<>(); queue.add(new Node(start, 0)); visited[start] = true; while (!queue.isEmpty()) { Node current = queue.poll(); // عملیات مختلف int[] operations = {current.value + 1, current.value - 1, current.value * 2, current.value * 3}; for (int next : operations) { // بررسی محدودیتها if (next == end) { System.out.println(current.steps + 1); return; } if (next >= 1 && next <= MAX && !visited[next]) { visited[next] = true; queue.add(new Node(next, current.steps + 1)); } } } // اگر نتوانستیم به j برسیم System.out.println(-1); } }توضیح کد:
- کلاس Node: برای نگهداری مقدار فعلی و تعداد مراحل طی شده تا به آن مقدار برسیم.
- خواندن ورودی: دو عدد
iوjاز ورودی خوانده میشوند. - بررسی شرایط پایه: اگر
iوjیکسان باشند، خروجی0خواهد بود. - الگوریتم BFS:
- از یک صف استفاده میکنیم تا به ترتیب مراحل مختلف را بررسی کنیم.
- برای هر عدد فعلی، تمام عملیاتهای مجاز را اعمال میکنیم و اگر به عدد
jرسیدیم، تعداد مراحل را چاپ میکنیم. - اگر به
jنرسیدیم، به عملیات بعدی ادامه میدهیم.
- در نهایت: اگر نتوانستیم به
jبرسیم،-1چاپ میشود (این حالت در مثالهای داده شده اتفاق نمیافتد).
بررسی نمونهها:
برای ورودی
5 36:- مسیر ممکن:
5 -> 6 -> 12 -> 36(3 مرحله)
برای ورودی
4 17:- مسیر ممکن:
4 -> 5 -> 15 -> 16 -> 17(4 مرحله)
این پیادهسازی با استفاده از BFS میتواند کوتاهترین مسیر را با توجه به عملیات مجاز تعیین کند.
- اضافه کردن ۱ به عدد فعلی (