Interactive GCD
এটি একটি ইন্টার একটিভ প্রবলেম।
ইন্টার একটিভ প্রবলেম হলো এমন প্রবলেম যেখানে তোমার প্রোগ্রাম এর আউটপুট এর উপর ভিত্তি করে পরবর্তী ইনপুট নির্ধারিত হয়।
Alice এবং Bob ইন্টার একটিভ গসাগু গেমটি খেলেছিলো।
গেম টির বৈশিষ্ট হলো, গেম ইঞ্জিন এ একটি লুকানো পূর্ণসংখ্যার অ্যারে রয়েছে। প্রতি খেলোয়াড় একজন এর পর আরেকজন এইভাবে ক্রমান্বয়ে খেলে।
একজন নিজের পালায় একটি Index এর সাবসেট নির্বাচন করে যেই সাব সেট আগে নির্বাচন করা হয় নি। যদি তার সাব সেট এর Index গুলোর সংখ্যার গসাগু 1 হয় তবে সে এক পয়েন্ট পায়ো। নাহলে কোনো পয়েন্ট পায় না । খেলা তখন ই শেষ হয় যখন সকল Index এর সাব সেট নিয়ে খেলা হয়ে গেছেে। যেহেতু n টি সংখ্যার অ্যারে এর জন্যে 2n-1 গুলো index এর subset রয়েছে তাই বলা যায় যে সর্বমোট 2n-1 বারের পর খেলা শেষ হয়ে যাবেে।
যার বেশি পয়েন্ট আছে সে জিতবে। দুজনের পয়েন্ট সমান হলে খেলা অমীমাংসিত থেকে যায়।
যেহেতু Alice আর Bob ঘনিষ্ঠ বন্ধু, ওরা কেউই চায় না নিজের বন্ধু কে হারাতে। দুজনেই চায় যেনো খেলা অমীমাংসিত থাকে।
কিন্তু কিছু গেম ইঞ্জিন এ খেলা অমীমাংসিত থাকা সম্ভব ই না। তাই ওরা তোমাকে দায়িত্ব দিয়েছে ইঞ্জিন টি পরীক্ষা করে বলার জন্য যে এই ইঞ্জিন এ গেম খেললে এইটা আদৌ সম্ভব কি না যে খেলা অমীমাংসিত থেকে যাবে।
ইঞ্জিন পরীক্ষা করার জন্যে তুমি মালিক কে সর্বোচ্চ 26 টি প্রশ্ন করবে। প্রতিটি প্রশ্নে তুমি 1 থেকে 100 এর মধ্যে একটি পূর্ণসংখ্যা বলবে এবং মালিক উত্তর এ তোমাকে বলবে যে ওই লুকানো অ্যারে এর কতগুলো সংখ্যা তোমার দেয়া সংখ্যা দ্বারা নিঃশেষে বিভাজ্য।
উদাহরণ হিসেবে ধর লুকানো অ্যারে যদি [2,3,4,5,6] হয় আর তুমি যদি 2 এর জন্যে প্রশ্ন করো তবে মালিক তোমাকে উত্তরে 3 বলবে।
Input
Interaction Details:
শুরুতে তোমাকে একটা পূর্ণসংখ্যা T(0 < T ≤ 100 ) দেয়া হবে. যা টেস্ট কেস এর সংখ্যার নির্দেশক।
প্রতিটি টেস্ট কেস এ তুমি শুরু তে "Start" লিখবেে। তার উত্তরে মালিক তোমাকে n(1 ≤ n ≤ 500), অ্যারে তে কতগুলো সংখ্যা থাকবে তা বলবে।
তারপরের সর্বোচ্চ 26 গুলো প্রশ্নে তুমি একটা পূর্ণ সংখ্যা বলবে আর মালিক উত্তরে বলবে লুকানো অ্যারে এর কতগুলো সংখ্যা তোমার দেয়া সংখ্যা দ্বারা নিঃশেষে বিভাজ্য।
যখন তুমি মনে করো যে তুমি উত্তর নিয়ে নিশ্চিত তখন তুমি তোমার উত্তর "Yes" / "No" প্রিন্ট করবে। উত্তরে তুমি পাবে যে তোমার উত্তর ঠিক হয়েছে নাকি ভুল।
তোমার উত্তর ঠিক হলে "Correct" আর ভুল হলে "Incorrect" লেখা থাকবে।
যদি তুমি ভুল উত্তর দাও তবে তোমার প্রোগ্রাম ওখানেই শেষ করো। আর ঠিক হলে পরের টেস্ট কেস নিয়ে কাজ শুরু করো।
Note:
প্রতিটা প্রশ্ন নতুন লাইন এ প্রিন্ট করো আর প্রশ্নের শেষে আউটপুট Flush করতে ভুল না।
Flush করার জন্যে ব্যবহার করতে পারো,
-fflush(stdout) in C/C++
-stdout.flush() in Python
Subtask Details :
Subtask 1, 5% পয়েন্ট এর জন্যে: n=1, গোপন অ্যারে এর সংখ্যা গুলো 1 এবং 10 এর মধ্যে
Subtask 2, 15% পয়েন্ট এর জন্যে: n ≤ 2, গোপন অ্যারে এর সংখ্যা গুলো 1 এবং 10 এর মধ্যে
Subtask 3, 50% পয়েন্ট এর জন্যে: n ≤ 20, গোপন অ্যারে এর সংখ্যা গুলো 1 এবং 32 এর মধ্যে
Subtask 4, 100% পয়েন্ট এর জন্যে, original constraints.
Output
নিচে একটি প্রশ্নোত্তর এর চিত্র তুলে ধরা হলো।
এখানে লুকানো অ্যারে টি [2,4,2,3,1]।
> 1
< Start
> 5
< 1
> 5
< 2
> 3
< 3
> 2
< 4
> 1
< Yes
> Incorrect
উপরের চিত্রে '<' এর মানে হলো তোমার প্রোগ্রাম আউটপুট দিচ্ছে , আর '>' এর মানে হলো তোমার প্রোগ্রাম ইনপুট নিচ্ছে.। এই চিহ্ন গুলো শুধু বুঝার সুবিধার্থে এখানে দেয়া হয়েছে। তোমার প্রোগ্রাম যেনো এই চিহ্ন গুলো প্রিন্ট না করে।
আরেকটা নমুনা প্রশ্নোত্তর নিচে দেয়া হয়েছে যেখানে লুকানো অ্যারে টি হলো [2,5,4,3]।
> 1
< Start
> 4
< 1
> 4
< 2
> 2
< 3
> 1
< 4
> 1
< 5
> 1
< Yes
> Correct
