Shopping Mania

Limits 1s, 256 MB · Interactive

শাপলা এবং জুই বার্ষিক কেনাকাটা পাগলামি প্রতিযোগীতায় অংশগ্রহণ করেছে। এই প্রতিযোগীতায় দুইজন একে অপরের বিপরীতে লড়াই করে। প্রতিযোগীতার নিয়মগুলি নিম্নে বর্ণিতঃ

1. $n$ টি বস্তু আছে যাদের দাম যথাক্রমে $p_1, p_2, \dots, p_n$। এছাড়াও একটি ধ্রুবক মান $k$ আছে, যেটাকে বলা হয় একটানা সর্বোচ্চ স্কিপ লিমিট। এই মানগুলি প্রতিযোগীতা শুরুর সময়েই প্রতিযোগীদের জানিয়ে দেয়া হয়।

2. উপস্থাপক একটি বস্তু উপস্থাপন করে। এই বস্তুগুলি একের পর এক উপস্থাপিত হয় এবং $i$ -তম বস্তুটি শুধুমাত্র তখনই উপস্থাপিত হয়, যদি এর আগের সব বস্তু অর্থাৎ $1, 2, \dots, i-1$ ক্রমিক সংখ্যার বস্তুগুলি প্রতিযোগীরা কিনে ফেলে।

3. এখন যে প্রতিযোগীর দান, সে উপস্থাপিত বস্তুটি কিনে ফেলতে পারে অথবা এই দানের জন্য না কিনে এড়িয়ে যেতে পারে, যেটাকে আমরা ইংরেজিতে skip বলছি। এই দানে বস্তুটি না কিনে এড়িয়ে যাওয়া যাবে শুধুমাত্র যদি শেষ $k$ দানে দুই প্রতিযোগীর কেউ একজন কোন একটি বস্তু কিনে থাকে অথবা প্রতিযোগীতায় এখনো $k$-টা দান সংঘটিত না হয়।

   • বস্তুটি কিনে ফেললে, সেটি প্রতিযোগীর থলে-তে যোগ হয়ে যায়।

     • যদি এটি শেষ বস্তু হয়ে থাকে অর্থাৎ $n$-তম বস্তু যদি হয়, তাহলে প্রতিযোগীতা শেষ হয়ে যায়।

     • নাহলে, উপস্থাপক এর পরের বস্তুটি উপস্থাপন করে। বর্তমান প্রতিযোগী থেকে দান বদলে অন্য প্রতিযোগীর কাছে দান যায়। এবং প্রতিযোগীতা-টি ৩-নং ধাপ থেকে আবার শুরু হয়।

   • যদি বর্তমান প্রতিযোগীর পক্ষে সম্ভবপর হয় এই দানে না কিনে এড়িয়ে যাওয়া এবং সে যদি এড়িয়েই যায়, তাহলে দান বদলে অন্য প্রতিযোগীর কাছে যায় এবং প্রতিযোগীতা আবার ৩-নং ধাপ থেকে শুরু হয়।

4. প্রতিযোগীতা যখন শেষ হয়, তখন উভয় প্রতিযোগীর থলের বস্তুগুলির দাম যোগ করা হয়। যে প্রতিযোগীর থলের বস্তুগুলির সর্বমোট দাম বেশি, তাকে বিজয়ী ঘোষণা করা হয়। যদি উভয়ের থলের বস্তুগুলির সর্বমোট দাম সমান হয়, তাহলে উভয় প্রতিযোগীকেই বিজয়ী ঘোষণা করা হয়।

শাপলা টস জিতেছে। সে এখন সিদ্ধান্ত নিবে প্রতিযোগীতার প্রথম দান কে শুরু করবে, সে নাকি জুই। তুমি কি শাপলাকে পরামর্শ দিতে পারবে তার কি প্রথম দানে শুরু করা উচিত নাকি দ্বিতীয় দানে, এবং শাপলার প্রতি দানে তার কি বর্তমান বস্তুটি কিনে ফেলা উচিত নাকি এড়িয়ে যাওয়া উচিত যেন শাপলা প্রতিযোগীতাটিতে জয়ী হতে পারে?

Interaction

এটি একটি ইন্টারেক্টিভ(interactive) সমস্যা। অনলাইন জাজ তোমার বিপরীতে জুই হিসেবে খেলবে। ইন্টারেক্টিভ প্রবলেম নিয়ে সাহায্যের জন্য Notes সেকশনটি দেখ।

ইনপুটের প্রথম লাইনে দুইটি পূর্ণসংখ্যা $n,k$ থাকবে। এর পরের লাইনে $n$ টি পূর্ণসংখ্যা $p_1, p_2, \dots, p_n$স্পেস দিয়ে আলাদা করা থাকবে।

এখন, তোমাকে অবশ্যই “first” অথবা “second” (উদ্ধৃতি বাদে) কোন একটি আউটপুট দিতে হবে, জাজকে এটা বলার জন্য যে শাপলা প্রথম দানে শুরু করতে চায় নাকি দ্বিতীয় দানে।

• শাপলার প্রতি দানে, তোমাকে “purchase” অথবা “skip” (উদ্ধৃতি বাদে) আউটপুট করতে হবে। এরা যথাক্রমে বর্তমান বস্তুটি কেনা এবং এড়িয়ে যাওয়া নির্দেশ করে। খেয়াল কর, তুমি শুধুমাত্র তখনই এড়িয়ে যেতে পারবে যদি প্রতিযোগীতার নিয়ম অনুযায়ী বৈধ হয়।

• জুইয়ের প্রতি দানে, জাজ একই রকম ভাবে “purchase” অথবা “skip” আউটপুট করবে একটি লাইনে। তোমাকে অবশ্যই এই লাইনটি ইনপুট নিতে হবে। তুমি নিশ্চিন্ত থাকতে পারো যে জাজের আউটপুট বৈধ হবে।

• যখন কোন প্রতিযোগী $x$ বর্তমান বস্তু $i$ কিনে ফেলে, তখন এক লাইন ইনপুট থাকবে এই ফরম্যাটেঃ “$x$ purchased item $i$” (উদ্ধৃতি ছাড়া)। তোমাকে অবশ্যই এই লাইনটি ইনপুট নিতে হবে। কিন্তু এই লাইনটি বোঝার সুবিধার জন্য এবং এটা নিয়ে তুমি কোন কিছু নাও করতে পারো।

প্রতিযোগীতা শেষ হবে যখন $n$ -টি বস্তু কেনা হয়ে যাবে। তোমার প্রোগ্রামকে তখনই কার্যক্রম শেষ করে ফেলতে হবে। তুমি “Accepted” রায়(verdict) পাবে যদি তুমি এবং শাপলা এই প্রতিযোগীতাটি জিতে যাও। অন্যথায়, না জিতলে “Wrong Answer” পাবে। প্রতিযোগীতা শেষে তোমার প্রোগ্রাম যদি কার্যক্রম শেষ না করে এবং আরো ইনপুটের জন্য বসে থাকে তাহলে “Accepted” ব্যতিত যেকোন রায় সে পেতে পারে, যার মধ্যে “Idleness Limit Exceeded” একটি।

খেয়াল কর, তোমার প্রোগ্রামের যেকোন অবৈধ আউটপুটের পরিণতি হবে “Wrong Answer” রায়ে। ইনপুট-আউটপুট আরো ভালো করে বোঝার জন্য নীচের নমুনা ইন্টারেকশনটি দেখ।

Sample Interaction

ইনপুটগুলি বামপাশে এবং তোমার আউটপুটগুলিকে ডানপাশে দেখানো হয়েছে বোঝার সুবিধার জন্য। খেয়াল কর যে, ১১ নং লাইনে জুই এর ৩-নং বস্তুটি কিনে ফেলা ছাড়া এড়িয়ে যাওয়ার কোন উপায় ছিল না যেহেতু শেষ $k = 3$ দানে কেউ কোন বস্তু কিনে নাই।

Constraints & Scoring

প্রতি সাবটাস্কের জন্যঃ

• $1 \le p_i \le 10^5$.

সাবটাস্কগুলিঃ

1. সাবটাস্ক ১ (১৪ পয়েন্ট)ঃ

   • $2 \le n \le 3$

   • $0 \le k \le 1$.

2. সাবটাস্ক ২ (৬ পয়েন্ট)ঃ

   • $2 \le n \le 10^4$

   • $k = 0$.

3. সাবটাস্ক ৩ (৮০ পয়েন্ট)ঃ

   • $2 \le n \le 10^4$

   • $0 \le k \le 50$.

Notes

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

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