Limits 1s, 512 MB · Interactive

মিস্টার বিস্কিট পরে গেছে এক মহা ফাঁপরে। দুর্ঘটনাবশত সে তার সার্ভার এর সব প্রোগ্রাম ডিলিট করে দিয়েছে যার ফলে তার ডাটাবেস করাপ্টেড হয়ে গেছে। ওই ডাটাবেসে একটা গ্রাফ রাখা ছিল। গ্রাফ টার একটা সোর্স নোড ছিল যেখান থেকে গ্রাফের অন্য নোড গুলোতে যাবার নিকটতম দূরত্ব  নির্ণয় করা হয়েছিল একটা ফাংশন ব্যবহার করে যার নাম SSSH. মিস্টার বিস্কিট তার নোটবুকে এই ফাংশনটার সুডোকোড খুঁজে পেয়েছে। সুডোকোডটি নিচে দেয়া হলো:

Input: A non-empty weighted graph G with vertices V and edges E
procedure SSSP(G,source):
1  Let N ← number of nodes in G
2  Let D[] ← 100000000 // D is an one dimensional array of size N
3  D[source] = 0
4  for step from 1 to N
5      for all edges from (u,v) in E
6          if D[u] + cost[u][v] < D[v]
7              D[v] = D[u] + cost[u][v]
8          end if
9      end for
10 end for
11 return D

ফাংশনটি চলাকালীন সময়ে রেজাল্ট বের করার জন্য সুডোকেডের নম্বর লাইনের লুপটির প্রতি ইটারেশনের পর অ‍্যারে DD কে ডাটাবেস এ সেভ করে রাখা হয়েছে। সুতরাং যদি লুপটি XX বার চলে তাহলে অ‍্যারে DD এর XX টা কপি ডাটাবেস সেভ করে রাখবে। এভাবে প্রতি ইটারেশন পর সোর্স নোড থেকে প্রতিটা নোড এর নিকটতম দূরত্বের তথ্য  দিয়ে অ‍্যারে D আপডেট হতে পারে।

এখন ডাটাবেস করাপ্টেড হয়ে গেছে এবং মিস্টার বিস্কিট সোর্স থেকে নোডগুলোর নিকটতম দূরত্ব সম্পর্কিত তথ্যগুলো হারিয়ে ফেলেছে। সে আসলে মূল গ্রাফ টাও হারিয়ে ফেলেছে। কিন্তু তার মনে আছে গ্রাফটির কোন এজ এর পরম মান ১০০০১০০০ এর বেশি না। অনেকদিনের চেষ্টার পর সে প্রতিটা ইটারেশনের পর  অ‍্যারে DD এর সব ইনডেক্স এর ভ্যালু গুলো  উদ্ধার করতে পেরেছে। মিস্টার বিস্কুট এই উদ্ধারকৃত তথ্য গুলো একটা টেম্পোরারি ব্যাকআপ সার্ভার এ সেভ করে রেখে দিয়েছে। এই উদ্ধারকৃত ডাটা দিয়ে শর্টেস্ট পাথ গুলো বের করা সম্ভব  হতে পারে।


তোমাকে বের করতে হবে অরিজিনাল গ্রাফে  সোর্স নোড থেকে অন্য নোডগুলোতে যাবার শর্টেস্ট পাথ আছে কিনা। রেজাল্ট বের করার জন্য তুমি মিস্টার বিস্কুট এর উদ্ধার করা ডাটাগুলো থেকে কুয়েরি করতে পারো । যেহেতু ব্যাকআপ সার্ভার এর রিসোর্স সীমাবদ্ধ, তাই তোমার রেজাল্ট বের করার জন্য তুমি একটা নির্দিষ্ট সীমা পর্যন্তই কুয়েরি করতে পারবে।

ইন্টার-অ্যাকশন:

তুমি এই প্রব্লেম এ তিন ধরণের ইন্টার-অ্যাকশন করতে পারো

  1. 11: কনটেসটেন্ট ইন্টারএকশন স্টার্ট করবে একটি 11 প্রিন্ট করার মাধ্যমে এই ইন্টারএকশনের পর এর রেসপন্স হিসেবে কন্টেস্টেন্ট NN এর ভ্যালু পাবে। এই ধরণের ইন্টারএকশন কমিউনিকেশনের শুরুতে শুধুমাত্র একবার হবে।

  2. 2 t i j: কন্টেস্টেন্ট ইনডেক্স ii থেকে jj(i<=j,0<=i,j,<Ni<=j, 0 <= i, j, < N) পর্যন্ত একটা সাব অ‍্যারে চাইবে লুপের (1<=t<=N1 <= t <= N) তম ইটারেশনে পর। রেস্পন্স হিসেবে, কন্টেস্টেন্ট  SSSP নামক ফাংশন এর t তম ইটারেশনের পর অ‍্যারে DD এর ইনডেক্স ii থেকে jj পর্যন্ত ভ্যালু পাবে। একজন কন্টেস্টেন্ট এই ধরণের সর্বোচ্চ N২* N সংখ্যক ইন্টারএকশন করতে পারবে। প্রতিটা ইন্টারএকশন ভ্যালিড হতে হবে।

  3. 33 resultresult: টাইপ 11 এবং টাইপ 22 এর সব ইন্টারএকশনের পর, একজন কন্টেস্টেন্ট লাস্ট লাইনে রেজাল্ট প্রিন্ট করবে। যদি গ্রাফ এর সোর্স থেকে অন্য সবগুলো নোড এ যাবার শর্টেস্ট পাথ থাকে, তাহলে রেজাল্ট হতে হবে 11। অন্যথায় রেজাল্ট হতে হবে 00

ফলাফল:

টাইপ টু এর সর্বোচ্চ N২ * N কোয়েরির পরে উপরে উল্লিখিত পদ্ধতিতে তোমাকে 11 উত্তর দিতে হবে যদি আসল গ্রাফে সোর্স থেকে বাকি সব নোডে শর্টেস্ট পাথ থাকে, অন্যথায় প্রিন্ট করতে হবে। তুমি যদি কোন ভুল কোন কোয়েরি করো, তা হলে তুমি রং অ্যানসার ভার্ডিক্ট পাবে।

N=3N = 3 এর জন্য একটি ইন্টারঅ্যাকশন হতে পারে এমন:

input: 1

response: 3

input: 2 2 1 2

response: 7 12

input: 2 3 0 2

response: 0 7 12

input: 3 1

এটা যেহেতু ইন্টারেক্টিভ সমস্যা, তোমার আউটপুট ফ্লাশ(flush) করতে ভুলে যেও না! সি/সি++ -এ আউটপুট ফ্লাশ করার জন্য তুমি fflush(stdout) লিখতে পারো, এবং পাইথনে import sys এবং sys.stdout.flush() লিখতে পারো। তুমি যদি অন্য কোন ভাষায় কোড করে থাকো, তাহলে অনুগ্রহ করে সেটার ডকুমেন্টেশনটি দেখ।

ইন্টারেক্টিভ সমস্যা নিয়ে আরো জানতেঃ https://help.toph.co/toph/interactive-problems

Submit

Login to submit.

Statistics

41% Solution Ratio
mohanr7073Earliest, Jun '21
mbsabbirr127Fastest, 0.0s
Um_nikLightest, 131 kB
steinumShortest, 515B
Toph uses cookies. By continuing you agree to our Cookie Policy.