تبلیغات


  • محدودیت زمان:‌ ۱ ثانیه
  • محدودیت حافظه: ۱۰۲۴ مگابایت

قصد تبلیغ در تعدادی سایت برای جذب کاربران را داریم. nn کاربر و mm سایت و kk نوع تبلیغ داریم. سایت شماره‌ی ii پنلی به طول lil_i برای تبلیغ دارد. طول تبلیغ iiاُم sis_i است. هر کاربر تعدادی سایت را بازدید خواهد کرد. هم‌چنین ما میزان احتمال کلیک کردن هر کاربر بر روی هر تبلیغ (در صورت مشاهده‌ی آن در یک سایت) را می‌دانیم. ما قرار است تبلیغ‌ها را در سایت‌ها بچینیم. هدف ما بیشینه کردن امیدریاضی تعداد کلیک‌های کاربران بر روی تبلیغ‌هاست. بدیهی‌ست یک کاربر روی یک تبلیغ حداکثر یک بار کلیک می‌کند.

توجه‌کنید که در این مساله به دنبال این نیستیم که کمینه امیدریاضی را به دست آوریم و برنامه شما هر چه قدر راه حل بهتری را پیشنهاد بدهد نمره بیشتری دریافت خواهیدکرد.

ورودی🔗

در خط اول ورودی nn و mm و kk آمده است.

در خط دوم mm عدد آمده است که iiاُمین آنها lil_i است.

در خط سوم kk عدد آمده است که iiاُمین آنها sis_i است.

در iiامین خط از nn خط بعدی ابتدا numinum_i آمده‌ست که تعداد سایت‌هایی‌ست که نفر iiام از آن‌ها بازدید می‌کند. سپس در ادامه numinum_i عدد می‌آید که شماره‌ی سایت‌هایی که نفر iiام از آن‌ها بازدید می‌کند را نشان می‌دهد.

در iiامین خط از nn خط بعدی kk عدد آمده‌است که jjامین آن‌ها احتمال کلیک کردن فرد iiام بر روی تبلیغ jjام است. این اعداد با دقت دقیقاً ۶ رقم اعشار داده می‌شوند.

1n,m,k5001 \le n, m, k \le 500 1numim1 \le num_i \le m 1li,si1091 \le l_i, s_i \le 10^9

تضمین می‌شود یک کاربر حداکثر یک‌بار از هر سایت بازدید می‌کند.

خروجی🔗

در خروجی kk خط چاپ کنید که در خط iiام ابتدا xix_i بیاید که تعداد سایت‌هایی‌ست که تبلیغ iiام باید در آن‌ها قرار بگیرد. سپس xix_i عدد چاپ کنید، شماره‌ی سایت‌هایی که باید تبلیغ iiام در آن‌ها قرار بگیرد.

مثال🔗

ورودی نمونه🔗

3 3 3
4 10 2
10 9 4
2 2 3
2 1 2
1 3
0.735807 0.437574 0.041877
0.878751 0.535907 0.056048
0.412099 0.997380 0.834622
Plain text

خروجی نمونه🔗

1 2 
0 
1 1 
Plain text

در این نمونه تبلیغ اول در سایت دوم و تبلیغ سوم در سایت اول نمایش داده می‌شود. تبلیغ دوم هم در هیچ سایتی قرار نمی‌گیرد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.