+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + سوال پیاده‌سازی ---------- پس از اوج‌گیری دوباره شیوع ویروس کرونا، مسئولین تصمیم گرفتند تا با استفاده از داده‌های در دسترس، راهی برای مقابله با این ویروس پیدا کنند. در این سوال قصد داریم ابزاری طراحی کنیم که با تحلیل داده‌های در دسترس که شامل تردد‌ها، آزمایش‌های کرونا و اطلاعات خانوار ها می‌باشد؛ درخواست‌های موردنیاز مسئولین را مرتفع کند. برای ساده‌سازی مسئله، فرض‌های زیر را در نظر می‌گیریم. + شهر ها با `شناسه‌ی شهر‍‍` که عددی بین `1` تا `c`(که در ورودی داده می‌شود) مشخص می‌شوند. + افراد با `شناسه‌ی فرد` که عددی بین `1` تا `n`(که در ورودی داده می‌شود) مشخص می‌شوند. + هر فرد می‌تواند در هیچ، یک و یا بیشتر از یک خانواده قرار داشته‌باشد. (اگر یک فرد در دو خانواده باشد، اعضای آن خانواده با هم خویشاوند محسوب می‌شوند) + تاریخ تردد و تاریخ آزمایش به‌صورت عددی بین `1` تا `365` تعریف می‌شود. + تردد می‌تواند از یک شهر به شهر دیگر و یا از یک شهر به همان شهر باشد؛ که در حالت اول، شناسه‌ی شهر مبدا و مقصد متفاوت بوده و در حالت دوم شناسه‌ی مبدا و مقصد یکی می‌باشد. + در صورتی که آزمایش یک فرد در روز `i` ام `positive` شود؛ فرد موردنظر و تمام افرادی که با او در یک خانواده هستند (تمام خانواده‌هایی که فرد در آن‌ها قرار دارد) از روز ‍`i` ام تا روز `i+7` که شامل `8` روز می‌باشد؛ **مبتلا به کرونا** محسوب می‌شوند. + متخلف کسی است که در دوره‌ای که به کرونا مبتلا شده‌است؛ ترددی از یک شهر به شهر دیگر انجام دهد و هر تردد اینگونه‌ی او یک تخلف محسوب ‌می‌شود.(تردد از یک شهر به همان شهر تخلف محسوب نمی‌شود) # ورودی 1. در خط اول ورودی $n$ (تعداد افراد مورد بررسی) وارد می‌شود. شناسه‌ی افراد از `1` تا `n` می‌باشد. 2. در خط دوم، $m$ (تعداد خانواده‌ها) وارد می‌شود. 3. سپس در $m$ خط بعدی، اعضای خانواده $i$م با یک فاصله از هم وارد می‌شوند. 4. سپس $c$ (تعداد شهرها) وارد می‌شود. شناسه‌ی شهرها از `1` تا `c` می‌باشد. 5. سپس $p$ (تعداد تردد های ثبت‌شده) وارد می‌شود. 6. در $p$ خط بعدی، در هر خط شناسه‌ی فرد، شناسه‌ی شهر مبدا، شناسه‌ی شهر مقصد و تاریخ تردد با یک فاصله از هم به‌صورت زیر وارد می‌شوند. ``` personId srcCity dstCity date ``` 7. سپس $t$ (تعداد آزمایش‌های کرونا) وارد می‌شود. 8. در $t$ خط بعدی، در هر خط شناسه‌ی فرد، نتیجه‌ی آزمایش(که یا `positive` است یا `negative`)، شناسه‌ی شهر محل آزمایش و تاریخ آزمایش با یک فاصله از هم به‌صورت زیر وارد می‌شوند. ``` personId testResult testCity date ``` 9. سپس $q$ (تعداد درخواست‌ها) وارد می‌شود. 10. در $q$ خط بعدی، در هر خط یکی از درخواست‌های تعریف‌شده در بالا وارد می‌شود. $$ 0 < n \le 100 $$ $$ 0 < m , c , p , t, q\le 30 $$ ### درخواست ها **پیاده‌سازی هر یک از درخواست‌ها ‍‍۴۰ امتیاز دارد.** 1. درخواست `Q1` : این درخواست، افراد با بیشترین تخلف‌ها را به‌‌ترتیب نزولی خروجی می‌دهد و به‌صورت زیر وارد می‌شود. ``` Q1 count ``` که `count` تعداد افرادی که باید خروجی بدهد را نشان می‌دهد.(در صورت برابر بودن تخلف های دو فرد، فرد با شناسه‌ی کوچک‌تر، بالاتر قرار می‌گیرد.). این دستور به شکل دیگری نیز وارد می‌شود که دارای `تاریخ شروع` و `تاریخ پایان` است؛ که همانند حالت قبلی‌است با این تفاوت که بیشترین تخلف‌ها را از `تاریخ شروع` تا `تاریخ پایان` نشان می‌دهد. ``` Q1 count fromDate toDate ``` ---------- 2. درخواست `Q2` : این درخواست، افراد با بیشترین تعداد آزمایش مثبت خود (نه اعضای خانواده) را به‌ترتیب نزولی خروجی می‌دهد و به‌صورت زیر وارد می‌شود. ``` Q2 count ``` که `count` تعداد افرادی که باید خروجی بدهد را نشان می‌دهد.(در صورت برابر بودن تعداد آزمایش مثبت‌های دو فرد، فرد با شناسه‌ی کوچک‌تر، بالاتر قرار می‌گیرد.). این دستور به شکل دیگری نیز وارد می‌شود که دارای `تاریخ شروع` و `تاریخ پایان` است؛ که همانند حالت قبلی‌است با این تفاوت که بیشترین تعداد آزمایش مثبت را از `تاریخ شروع` تا `تاریخ پایان` نشان می‌دهد. ``` Q2 count fromDate toDate ``` ---------- 3. درخواست `Q3`: این درخواست، شهر هایی که بیشترین آزمایش مثبت را ثبت کرده‌اند؛ به‌ترتیب نزولی خروجی می دهد و به‌صورت زیر وارد می‌شود. ``` Q3 count ``` که `count` تعداد شهرهایی که باید خروجی بدهد را نشان می‌دهد.(در صورت برابر بودن آزمایش‌های مثبت دو شهر، شهر با شناسه‌ی کوچک‌تر، بالاتر قرار می‌گیرد.). این دستور به شکل دیگری نیز وارد می‌شود که دارای `تاریخ شروع` و `تاریخ پایان` است؛ که همانند حالت قبلی‌است با این تفاوت که شهر هایی که بیشترین آزمایش مثبت را از `تاریخ شروع` تا `تاریخ پایان` داشته‌اند؛ نشان می‌دهد. ``` Q3 count fromDate toDate ``` ---------- 4. درخواست `Q4`: این درخواست، با دریافت شناسه‌ی شهر، روزهایی که بیشترین تعداد آزمایش مثبت را داشته‌اند؛ به‌ترتیب نزولی خروجی می‌دهد و به‌صورت زیر وارد می‌شود.‌ ``` Q4 CityId count ``` که `count` تعداد روزهایی که باید خروجی بدهد را نشان می‌دهد.(در صورت برابر بودن تعداد آزمایش‌های مثبت دو روز، روز با عدد کوچک‌تر، بالاتر قرار می‌گیرد.) ---------- 5. درخواست `Q5`: این درخواست، روزهایی از سال با بیشترین آمار مبتلا به کرونا را به‌صورت نزولی خروجی می‌دهد(به این نکته توجه شود که هر فرد، از روز آزمایش مثبت تا ۷ روز بعد، مبتلا به کرونا محسوب می‌شود) و به‌صورت زیر وارد می‌شود. ``` Q5 count ``` که `count` تعداد روزهایی که باید خروجی بدهد را نشان می‌دهد.(در صورت برابر بودن تعداد مبتلایان دو روز، روز با عدد کوچک‌تر، بالاتر قرار می‌گیرد). # خروجی برای هر درخواست ابتدا در یک خط نوع درخواست که یکی از مقادیر `Q1`، `Q2`، `Q3`، `Q4`، یا `Q5` می‌باشد نمایش‌داده می‌شود و سپس نتیجه‌ی درخواست که متناسب با نوع درخواست به صورت زیر می‌باشد؛ در خروجی نمایش‌داده می‌شود. 1. درخواست `Q1` : خروجی شامل `count` خط است که در هر خط ابتدا شناسه‌ی فرد و سپس تعداد تخلف‌های فرد نمایش‌ داده می‌شود. 2. درخواست `Q2` : خروجی شامل `count` خط است که در هر خط ابتدا شناسه‌ی فرد و سپس تعداد آزمایش‌های مثبت شخص نمایش‌ داده می‌شود. 3. درخواست `Q3` : خروجی شامل `count` خط است که در هر خط ابتدا شناسه‌ی شهر و سپس تعداد آزمایش‌های مثبت نمایش‌ داده می‌شود. 4. درخواست `Q4` : خروجی شامل `count` خط است که در هر خط ابتدا روز و سپس تعداد آزمایش‌های مثبت نمایش‌ داده می‌شود. 5. درخوست `Q5` : خروجی شامل `count` خط است که در هر خط ابتدا روز و سپس تعداد مبتلایان نمایش‌ داده می‌شود. # مثال ## ورودی نمونه ۱ ``` 6 3 1 2 3 4 2 5 3 2 1 1 3 20 1 3 1 30 3 1 negative 1 20 1 positive 2 28 3 negative 1 360 1 Q1 3 ``` ## خروجی نمونه ۱ ``` Q1 1 1 2 0 3 0 ``` <details class="blue" > <summary>توضیحات نمونه‌ی ۱</summary> فرد با شناسه‌ی `1` در روز `28` ام یک آزمایش مثبت داشته و در تاریخ `30` ام ترددی از یک شهر به شهر دیگر انجام داده‌است که یک تخلف محسوب می ‌شود. با توجه به اینکه بقیه‌ی افراد تخلفی نکرده‌اند اما `3` درخواست شده‌اند؛ افراد به ترتیب صعودی شناسه، نمایش داده می‌شوند. </details> ## ورودی نمونه ۲ ``` 6 3 1 2 3 4 2 5 3 2 1 1 3 20 1 3 1 30 5 1 negative 1 20 1 positive 2 28 3 negative 1 35 2 positive 3 51 5 positive 1 28 4 Q2 4 Q3 2 Q4 2 1 Q5 3 ``` ## خروجی نمونه ۲ ``` Q2 1 1 2 1 5 1 3 0 Q3 1 1 2 1 Q4 28 1 Q5 28 3 29 3 30 3 ```