+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک جدول $ n \times m $ داریم که در هر خانه‌اش عددی نوشته شده است. یک برنامه نویس معمولی به یک خانه از جدول زینی می‌گوید اگر بتوان روی آن نشست! اما یک برنامه نویس نیمبو به یک خانه از جدول زینی می‌گوید اگر ۴ همسایه مجاور ضلعی‌اش موجود باشند و عددش از اعداد خانه های مجاور چپ و راستش بزرگ‌تر، و از اعداد خانه های مجاور بالا و پایینش کوچک‌تر باشد، و یا بالعکس (یعنی عددش از اعداد خانه‌های مجاور چپ و راستش کوچک‌تر و از اعداد خانه‌های مجاور بالا و پایینش بزرگ‌تر باشد). شما به عنوان برنامه نویسی نیمبو باید تعداد خانه‌های زینی یک جدول را پیدا کنید. # ورودی خط اول ورودی شامل دو عدد $n$ و $m$ است. در $n$ خط بعدی برنامه، سطر های جدول آمده اند. به طوری که هر خط شامل $m$ عدد است که نشان‌دهنده اعداد یک سطر از جدول هستند. اعداد جدول طبیعی و کوچکتر مساوی $ 10^{9} $ اند. $$1 \le n, m \le 100$$ # خروجی خروجی شامل یک عدد است که تعداد خانه‌های زینی جدول از دیدگاه برنامه‌نویسی نیمبو را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 3 3 1 2 3 6 5 6 1 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` فقط خانه وسط جدول زینی است. دقت کنید که بقیه خانه‌ها هیچ‌کدام شرط داشتن ۴ همسایه را ندارند. ## ورودی نمونه ۲ ``` 4 4 1 2 4 1 7 4 1 1 1 3 2 4 1 4 1 1 ``` ## خروجی نمونه ۲ ``` 2 ``` خانه‌ای که در سطر سوم و ستون دوم قرار دارد، و هم‌چنین خانه‌ای که در سطر سوم و ستون سوم قرار دارد زینی‌اند.

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- صبا یه جدول $n \times m$ داره. درون هر خونه‌ی این جدول می‌تواند حداکثر یک قارچ وجود داشته باشد. قارچ‌ها به قوانین‌ای (شبیه به [بازی زندگی](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life)) زنده می‌شوند و می‌میرند. در هر لحظه: + اگر در لحظه‌ی قبل در این خانه قارچ وجود داشته باشد و در خانه‌های مجاور آن در لحظه قبل بین ۲ تا ۳ قارچ وجود داشته باشد، زنده می‌ماند و در غیر این صورت می‌میرد. + اگر در لحظه‌ی قبل در این خانه قارج وجود نداشته باشد و در خانه‌های مجاور آن در لحظه قبل دقیقا ۳ قارچ وجود داشته باشد، یک قارچ در این خانه به وجود می‌آید. دو خانه متفاوت $(a, b)$ و $(x, y)$ را مجاور می‌نامیم اگر حداکثر یک ستون و یک سطر با هم فاصله داشته‌باشند. (فرض می‌شود که سطر اول و آخر و هم‌چنین ستون اول و آخر با هم مجاور هستند.) بنابراین هر خانه دقیقا ۸ همسایه دارد. صبا قبلا یک جدول داشت و روی آن $l$ مرحله قوانین بازی زندگی را اجرا کرد. اما از آن‌جا که جدول اولیه را فراموش کرده به شما جدول نهایی را می‌دهد و از شما می‌خواهد جدول اولیه را به او بدهید و یا بگویید که همچین جدولی وجود ندارد. # ورودی در خط اول سه عدد $n$ و $m$ و $l$ آمده‌اند در $n$ خط بعدی رشته‌ای $m$ حرفی آمده است که یعنی اگر در خط $i$ام و حرف $j$ام حرف `*` باشد در خانه‌ی $(i, j)$ یک قارچ وجود دارد و در غیر این صورت آن خانه خالی است. $$ 9 \le n \times m \le 20 $$ $$ 3 \le n, m \le 6 $$ $$ 1 \le l \le 20 $$ # خروجی در خروجی یک جدول $n \times m$ از حروف باید چاپ شود که مانند ورودی اگر در خط $i$ام حرف $j$ام `*` باشد یعنی در خانه‌ی $(i, j)$ یک قارچ وجود داشته. اگر جدول اولیه‌ای وجود نداشت پیام `impossible` چاپ شود. # مثال ## ورودی نمونه ۱ ``` 4 5 10 ....* ..*.* .*..* ..*.* ``` ## خروجی نمونه ۱ ``` ..*.* ...** **.** *.... ``` توجه کنید که جواب‌های دیگری هم ممکن است وجود داشته باشد و شما باید تنها یکی از آن‌ها را چاپ کنید. ## ورودی نمونه ۲ ``` 3 3 10 *** *** *.. ``` ## خروجی نمونه ۲ ``` impossible ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- توی دوره نیمبو به تفریح کارآموزها اهمیت زیادی داده می‌شه و واسه همین تو زمان استراحت به کارآموزا می‌گن که بازی تتریس نیمبویی رو بازی کنن تا هم یه تفریحی واسشون باشه هم زمان استراحت یه جوری بگذره. در بازی تتریس نیمبویی $n$ ستون وجود دارند که از چپ به راست با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند و ستون $i$ ام از $a_{i}$ مربع واحد تشکیل شده‌است. هر بازیکن در هر حرکت می‌تواند یک بازه از ستون‌ها را انتخاب کند و به هرکدام یک مربع اضافه کند. (در واقع بازیکن اعداد $l$ و $r$ را انتخاب میکند و سپس به ازای هر $l \le j \le r$ ، مقدار $a_{j}$ را یکی زیاد می‌کند.) هدف بازی یکسان کردن طول تمام ستون ها در کم‌ترین تعداد مرحله است. حالا مهرداد که از این بازی خوشش نیومده ازتون می‌خواد تا بهش بگین که این کم‌ترین تعداد مرحله چندتاست تا بتونه سریع بازی رو تموم کنه و به بقیه کاراش برسه. # ورودی در خط اول ورودی عدد $n$ ، تعداد ستون‌ها می‌آید. در خط بعدی $n$ عدد آمده که عدد $i$ ام آن $a_{i}$ است که تعداد مربع‌های ستون $i$ ام را نشان می‌دهد. $$ 1 \le n \le 1\ 000\ 000$$ $$ 1 \le a_{i} \le 1\ 000\ 000\ 000$$ # خروجی در خروجی یک عدد که کم‌ترین تعداد مراحل برای رسیدن به هدف بازی است را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 3 2 ``` ## خروجی نمونه ۱ ``` 3 ``` دوبار مقدار ستون اول (بازه $[1,1]$ ) را، و یکبار مقدار ستون سوم (بازه $[3,3]$ ) را زیاد میکنیم. ## ورودی نمونه ۲ ``` 5 4 3 1 3 7 ``` ## خروجی نمونه ۲ ``` 6 ``` سه بار بازه $[1,4]$ را انتخاب میکنیم. سپس یکبار بازه $[2,4]$ و دو بار بازه $[3,3]$ را انتخاب میکنیم.

+ **در این سوال به هر بخش از سوال که پاسخ بدهید نمره همان قسمت را خواهید گرفت** + **این سوال را باید با زبان جاوا پاسخ دهید. دقت کنید که انتظار نمی‌رود که همه مفاهیم را از ابتدا بلد باشید و ممکن است بسته به توانایی خود نیاز به جست‌و‌جو کردن داشته باشید.** ---------- قرار است در نیمبو یک فضای ابری برای ذخیره سازی فایل‌ها به اسم *NimboDrive* بسازیم! کلاس‌ها و توابع اولیه این برنامه را نوشته ایم اما این وظیفه شماست که آن‌ها را پیاده‌سازی و کامل کنید. فایل‌های اولیه پروژه را از [اینجا](https://quera.ir/qbox/download/hgEs31dkYH/NimboDrive.zip) دانلود کنید. دقت کنید که نیازی نیست کل کارهای گفته شده در یک قسمت را انجام دهید تا نمره آن قسمت را بگیرید. در هر قسمت هر بخشی را که پیاده‌سازی کنید، نمره همان بخش را خواهیدگرفت. نحوه آپلود جواب در انتهای سوال آورده شده است. -------- ## قسمت اول در این قسمت شما باید کلاس `UserStorageRepository` را پیاده‌سازی کنید. این کلاس مدیریت می‌کند که هر کاربر چقدر حجم برای ذخیره سازی فایل در سیستم ما دارد. این کلاس برای این‌کار در داخل خود یک *Map* از اسم کاربر و حجم دارد. برای مثال در خود ذخیره می‌کند که کاربری به اسم `Ali` می‌تواند 125000 بایت دیگر در سیستم فایل آپلود کند. توابع گفته شده در زیر را پیاده‌سازی کنید. (**روی عنوان هر کار کلیک کنید تا توضیحات آن باز شود**.) <details> <summary> تابع increaseStorageOfUser </summary> این تابع اسم کاربر و یک عدد گرفته و میزان حجم کاربر را به اندازه عدد داده شده زیاد می‌کند. اگر کاربر از قبل در *Map* وجود نداشته باشد آن را اضافه می‌کند و حجم آن را برابر با مقدار داده شده قرار می‌دهد. </details> <details> <summary> تابع hasStorage </summary> این تابع اسم کاربر و یک عدد گرفته و بررسی می‌کند آیا کاربر به اندازه داده شده حجم دارد یا نه. اگر کاربر کلا وجود نداشته باشد باید `false‍` برگردانده شود. </details> <details> <summary> تابع decreaseStorageOfUser </summary> این تابع اسم کاربر و یک عدد گرفته و حجم کاربر را به آن اندازه کم می‌کند. اگر حجم کاربر به صفر رسید یا منفی شد، آن کاربر از *Map* حذف می‌شود. </details> -------- ## قسمت دوم کلاس `NimboFile` یک فایل را در سیستم ما مشخص می‌کند. این کلاس، زیرکلاس‌هایی(مثل `TextFile`) دارد که نوع فایل را مشخص می‌کنند. هر فایل یک اسم(مثلا `readme.txt`)، یک پوشه (مثلا `/user/ali/`) ، یک مالک (مثلا `Ali`) و یک عدد به عنوان حجم دارد که واحد آن بایت است. کلاس `FileRepository` کلاس اصلی برای مدیریت فایل‌هاست که در آن کل فایل‌ها و اطلاعات آنها ذخیره می‌شود. شما باید کارهای گفته شده در زیر را انجام دهید. <details> <summary> نوشتن متد `toString` برای `NimboFile` </summary> در کلاس `NimboFile` متد `toString` را override کنید به طوری که اسم کامل فایل(مثلا `a.txt`) را برگرداند. </details> <details> <summary> پیاده‌سازی تابع `addFile‍` در کلاس `FileRepository` </summary> این تابع یک فایل به عنوان ورودی می‌گیرد و اگر مالک فایل به اندازه کافی حجم داشته باشد، فایل را به مجموعه فایل‌های ذخیره شده اضافه می‌کند و به اندازه حجم فایل از فضای مالک کم می‌کند. اگر مالک فایل به اندازه کافی حجم نداشته باشد باید یک استنا از نوع *IllegalArgumentException* پرتاب کنید. درون این کلاس یک شی از جنس `UserStorageRepository` وجود دارد که برای کم‌کردن حجم از کاربر باید از آن استفاده کنید. </details> <details> <summary> پیاده‌سازی تابع `searchByName` در کلاس `FileRepository` </summary> این تابع یک رشته دریافت کرده و لیست تمام فایل‌هایی که رشته داده شده در اسم آن‌ها تکرار شده‌است را بر می‌گرداند. دقت کنید که فرمت فایل نباید در جست و جو در نظر گرفته شود. برای مثال اگر اسم فایل `a.txt` باشد و `xt` را سرچ کنیم، این فایل نباید برگرداننده شود. **جست و جو حساس به حروف بزرگ و کوچک نیست.** </details> <details> <summary> پیاده‌سازی تابع `scan` در کلاس `FileRepository` </summary> یک شئ در این کلاس به اسم `scanner` وجود دارد. این شئ یک تابع به اسم `scanFile` دارد که یک فایل ورودی میگیرد و اگر فایل ویروسی باشد یک اکسپشن پرت میکند. این تابع به کمک این شئ تمام فایل‌ها را اسکن می‌کند و فایل‌هایی که عادی نیستند را از مجموعه فایل‌ها حذف می‌کند و حجم آن‌ها را به مالکان فایل‌ها بر می‌گرداند. </details> -------- ## قسمت سوم برنامه ما این قابلیت را دارد که بعضی از انواع فایل‌ها را بدون دانلود به صورت پیش‌نمایش به کاربر نشان دهد. فایلی که این قابلیت را دارد واسط `hasPreview` را پیاده‌سازی می‌کند. <details> <summary> اضافه کردن پیش‌نمایش به کلاس `TextFile` </summary> کلاس `TextFile` را عوض کنید به گونه‌ای که اینترفیسِ `HasPreview<String>` را پیاده‌سازی کند.دقت کنید که نیازی نیست در این بخش تابع `preview‍` را هم پیاده‌سازی کنید. برای سادگی فعلاً می‌توانید در آن `return null;` بگذارید. </details> <details> <summary> پیاده‌سازی تابع `isPreviewable` در کلاس `FileRepository` </summary> این تابع یک فایل می‌گیرد و اگر فایل داده شده اینترفیسِ `HasPreview` را پیاده‌سازی کرده باشد (یا به عبارت دیگر از جنس `HasPreview` باشد ) `true` بر می‌گرداند. </details> <details> <summary> پیاده‌سازی تابع `sort‍` در کلاس `FileRepository` </summary> این تابع یک *Comparator* ‍به عنوان ورودی می‌گیرد و فایل‌ها را با توجه به آن مرتب کرده به صورت آرایه بر می‌گرداند. </details> -------- ## قسمت چهارم <details> <summary> پیاده‌سازی تابع `findLongestMediaInDirectory` در کلاس `FileRepository` </summary> این تابع آدرس یک پوشه را می‌گیرد(مثلا `/home/ali/`) و طولانی‌ترین فایل درون آن پوشه که از جنس `MediaFile` باشد را درون یک `Optional‍` گذاشته و برمی‌گرداند. طولانی‌ترین فایل، فایلی است که `duration` آن از همه بیش‌تر باشد. اگر در آن پوشه هیج فایل مدیایی وجود نداشته باشد ‍`Optional.empty()` برگردانده می‌شود. هم‌چنین اگر چندین فایل با طول یکسان وجود داشت یکی از آنها به دلخواه باید برگرداننده شود. </details> <details> <summary> پیاده‌سازی پیش‌نمایش برای کلاس `TextFile` </summary> در قسمت قبل کلاس `TextFile` را عوض کردید به گونه‌ای که اینترفیسِ `HasPreview<String>` را پیاده‌سازی کند. در این بخش باید تابع `preview` را در این کلاس پیاده‌سازی کنید. این تابع یک `InputStream` که مربوط به این فایل متنی است را دریافت می‌کند و باید خط اول آن را بخواند و رشته خوانده شده را در کلاس Preview قرار دهد و آن را برگرداند. </details> <details> <summary> پیاده‌سازی تابع `applyToAllByFilter` در کلاس `FileRepository` </summary> این تابع یک فیلتر و یک تابع به عنوان ورودی گرفته و تابع گرفته شده را روی تمامی فایل‌هایی که با فیلتر مطابقت دارند(فیلتر به ازای آنها true برمیگرداند) اعمال می‌کند. </details> -------------------------- ## نکات + یک فایل به اسم `SampleMain.java` به شما داده شده است تا با نحوه ی کارکردن کلاس‌ها آشنا شوید و استفاده دیگری ندارد. + به هیچ وجه امضای توابع داده شده یا متغیر های درونی هر کلاس را عوض نکنید. تغییر اسم تابع، نوع برگشتی، پارامترها و ... باعث می‌شود کد شما داوری نشود. + دقت کنید حتی اگر بعضی از فایل‌ها را هنوز دست نزده‌اید باز هم باید آنها را مطابق الگوی زیر آپلود کنید تا کد شما کامپایل شود و مورد داوری قرارگیرد. **چیزی که باید آپلود کنید:** یک فایل زیپ دقیقاً مشابه فایلی که دریافت کردید، یعنی وقتی آن را باز می‌کنیم پوشه in را ببینیم. داخل پوشه `in` باید پوشه `nimbo` قرار گرفته باشد. داخل پوشه `nimbo` هم باید پوشه‌های `file` و `preview` و فایل‌های `UserStorageRepository.java` و `FileRepository.java` و `FileScanner.java` قرار گرفته باشند. درون پوشه‌های `file` و `preview` نیز باید فایل‌های مرتبط موجود باشند. اسم فایل زیپ مهم نیست. ساختاری مشابه شکل زیر: ``` yourZipFileName.zip └── in └── nimbo ├── file │ ├── BinaryFile.java │ ├── MediaFile.java │ ├── NimboFile.java │ └── TextFile.java ├── FileRepository.java ├── FileScanner.java ├── preview │ ├── hasPreview.java │ └── Preview.java ├── SampleMain.java └── UserStorageRepository.java ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در این سوال می‌خواهیم دو دستور ساده از یک زبان برنامه نویسی را شبیه‌سازی کنیم. دستور اول، دستور `:=` است. در سمت چپ این دستور اسم متغیر و در سمت راست آن مقداری که می‌خواهیم به متغیر بدهیم می‌آید. اسم متغیر یک رشته از حروف کوچیک انگلیسی با حدکثر ۲۰ حرف است. مقدار متغیر می‌تواند به یکی از دو حالت زیر باشد. + یک لیست از اعداد باشد. شکل لیست این صورت است: ` [a_1, a_2, ..., a_n] ` هر عضو یک عدد حداکثر تا ۱۰۰ است و بین هر کاراکتر `,` و عدد بعدی یک فاصله وجود دارد. و بین بقیه حرفا فاصله‌ای وجود ندارد. لیست حداکثر ۲۰ عضو دارد. + یک لغت‌نامه از رشته‌های عددی به اعداد باشد. شکل لغت‌نامه به این صورت است: ` {"k_1": v_1, "k_2": v_2, ... "k_n": v_n} ` مقدار هر کلید (`k_i`) و هر مقدار (`v_i`) یک عدد حداکثر تا ۱۰۰ است. بعد هر حرف `:` و حرف `,` یک فاصله وجود دارد و جایی دیگری فاصله وجود ندارد. لغت‌نامه حداکثر شامل ۲۰ جفت می‌شود و همه‌ی مقدار‌های کلیدها متمایزند. دستور دوم، دستور `print` است. دستور متغیر به شکل مقابل استفاده می‌شود: `print var[id]` بین دستور `print` و کلمه `var` یک فاصله وجود دارد و `var` نام متغیر و `id` اگر متغیر لیست باشد اندیس خانه‌ایست که باید چاپ شود و اگر متغیر لغت‌نامه باشد کلید مقداریست که باید چاپ شود. تضمین می‌شود متغیر داده شده قبلا مقداردهی شده باشد. به شما یک برنامه که با دستورات توضیح داده نوشته شده، داده می‌شود. آن را اجرا کنید و خروجی را چاپ کنید. # ورودی در خط اول $n$ آمده که تعداد خطوط برنامه است و در ادامه یک برنامه $n$ خطی آمده‌است. $$ 1 \le n \le 200 $$ # خروجی خروجی برنامه را چاپ کنید. # مثال ## ورودی نمونه ``` 4 a := [1, 2, 3] b := {"2": 1, "1": 4, "4": 5} print a[1] print b["1"] ``` ## خروجی نمونه ``` 2 4 ```

+ محدودیت زمان: ۷ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شرکت سحاب به تازگی مقدار زیادی داده از خریدهایی که در بازار میوه‌فروشی انجام می‌شود، به دست آورده‌است. در این داده‌ها به ازای هر شخصی که به بازار میوه و تره‌بار رفته، میوه‌هایی که خریداری کرده، آمده‌است. علی که یکی از کارمندان شرکت است علاقه زیادی به میوه‌ها دارد و از طرفی هم به بررسی داده‌‌ها را کاری جذاب می‌داند، می‌خواهد بداند که چه زیرمجموعه‌هایی از میوه‌ها پرطرفدار هستند. علی به یک زیرمجموعه از میوه‌ها پرطرفدار می‌گوید اگر در حداقل $\lfloor \frac n{10} \rfloor$ تا از سبدها تکرار شده باشد و اندازه آن هم حداقل دو باشد. ($n$ تعداد کل سبدهاست.) حال ما از شما می‌خواهیم تا می‌توانید زیرمجموعه پرطرفدار پیدا کنید و هر چه قدر زیرمجموعه‌های بیشتری گزارش کنید، نمره بیشتری از این سوال می‌گیرید. توجه کنید که تست‌های این سوال طبق داده‌های واقعی هستند و سعی کنید از این قضیه در راه‌حل‌تان استفاده کنید. # ورودی در سطر اول ورودی $n$ آمده‌است که تعداد اشخاصی که خرید کرده‌اند را نشان می‌دهد. سپس در $n$ خط بعدی در ابتدا $k_i$ می‌آید که تعداد میوه‌هایی که است که شخص $i$ام خریداری کرده و در ادامه آن $k_i$تا عدد آمده که شماره میوه‌ها را مشخص می‌کند. $$1 \le n \le 300\ 000$$ $$1 \le k_i \le 80$$ تمام اعداد ورودی کم‌تر مساوی $10^6$ هستند. # خروجی در خروجی ابتدا در زیرمجموعه‌های پرطرفداری که پیدا کردید را چاپ کنید و سپس در خط‌های بعدی به ازای هر زیرمجموعه ابتدا اندازه و سپس اعضای آن را چاپ کنید. در نظر داشته‌باشید که هرچه قدر زیرمجموعه‌های بیشتری چاپ کنید نمره بیشتری می‌گیرید و اگر به ازای هر تست حداقل $2\ 000\ 000$ زیرمجموعه پرطرفدار چاپ‌کنید، نمره آن تست را می‌گیرید. # مثال # ورودی نمونه ۱ ``` 20 3 1 2 3 3 1 2 5 2 4 3 2 5 7 3 4 6 9 3 1 7 8 4 3 5 7 8 2 7 8 2 5 6 3 4 5 9 5 1 4 5 7 10 3 7 10 11 3 5 7 10 2 5 6 4 4 9 12 13 3 5 8 12 2 4 10 3 2 8 12 2 8 10 3 3 7 12 ``` # خروجی نمونه ۱ ``` 15 2 1 2 2 1 5 2 1 7 2 3 7 2 4 5 2 4 9 2 4 10 2 5 6 2 5 7 3 5 7 10 2 5 8 2 5 10 2 7 8 2 7 10 2 8 12 ``` دقت کنید که در این‌جا تمام زیرمجموعه‌های پرطرفدار خروجی داده شده‌اند و شما برای ردکردن بعضی از تست‌ها لازم نیست تا همه را چاپ کنید. # نکات + اگر از زبان پایتون برای حل این سوال استفاده می‌کنید پیشنهاد می‌کنیم از *Pypy 3* هنگام ارسال استفاده کنید. + اگر در خروجی زیرمجموعه‌ای را چاپ کنید که پرطرفدار نباشد از آن تست هیچ نمره‌ای نمی‌گیرید.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- سینا پس از سال‌ها تلاش، توانست پدرش را راضی کند تا برای او یک [درخت](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%28%D9%86%D8%B8%D8%B1%DB%8C%D9%87_%DA%AF%D8%B1%D8%A7%D9%81%29) (گرافی همبند و بدون دور) ریشه‌دار $n$ راسی بخرد. ریشه درخت سینا، راس شماره ۱ و پدر راس شماره $i$ $(2 \leq i \leq n)$ راس شماره $p_i$ است. او سپس درخت را به برادر کوچک‌ترش داد تا روی هر راس آن، یک عدد صحیح بنویسد. برادرش روی راس شماره $i$ عدد $a_i$ را نوشت. سپس از پدرش تقاضا کرد تا به او کمک کند درختش را **زیبا** کند. از نظر سینا و پدرش یک درخت ریشه‌دار **زیبا** است اگر به ازای هر $2 \leq v \leq n$ رابطه $a_v \geq a_{p_v}$ برقرار باشد. پدر سینا می‌تواند عملیات زیر را هر چند باری که دلش بخواهد انجام دهد: + یک یال مانند یال $v$ به $p_v$ در نظر بگیرد. سپس عدد نوشته شده روی راس $v$ را با عدد نوشته شده روی راس $p_v$ عوض کند. بعد از آن به عدد روی راس $p_v$ یکی اضافه کند و از عدد روی راس $v$ یکی کم کند. (برای درک بیشتر، توضیح نمونه ۱ را ببینید) آیا سینا و پدر سینا می‌توانند درخت سینا را زیبا کنند؟ # ورودی در خط اول ورودی عدد $n$، تعداد رئوس درخت سینا آمده است. در خط دوم $n - 1$ عدد $p_2, p_3, ..., p_n$ آمده است. در خط سوم نیز $n$ عدد $a_1, a_2, ..., a_n$ آمده است. $$ 2 \leq n \leq 200 \, 000 $$ $$ 1 \leq p_i < i $$ $$ -10^9 \leq a_i \leq 10^9 $$ # خروجی در تنها سطر خروجی، اگر سینا و پدر سینا می‌توانند درخت را زیبا کنند `Yes` و در غیر این صورت `No` چاپ کنید. # مثال # ورودی نمونه ۱ ``` 3 1 1 10 5 20 ``` # خروجی نمونه ۱ ``` Yes ``` \**توضیح نمونه ۱:** درخت اولیه این شکلی است:  اگر سینا و پدرش یال راس ۲ به پدرش را انتخاب کنند و عملیات را روی آن انجام دهند، به درخت زیبای زیر می‌رسند:  # ورودی نمونه ۲ ``` 2 1 2 1 ``` # خروجی نمونه ۲ ``` No ``` # ورودی نمونه ۳ ``` 6 1 1 2 4 4 7 4 8 4 1 10 ``` # خروجی نمونه ۳ ``` Yes ```

+ **در این سوال به هر بخش از سوال که پاسخ بدهید نمره همان قسمت را خواهید گرفت (توضیح نمره‌ی سوال در انتهای سوال قرار دارد)** + **این سوال را باید با bash پاسخ دهید. دقت کنید برای پاسخ به این سوال باید با مفاهیم مربوط به bash و لینوکس آشنا باشید و برای این کار نیاز به جستجو دارید.** ---------- یک پروسه‌ی مخرب روی کامپیوتر‌های سایت دانشکده مشاهده شده است و چند کامپیوتر سایت را که سیستم عامل *ubuntu* داشته اند را درگیر کرده است. یکی از بچه‌های سال بالایی ادعا کرده که توانسته اطلاعات زیر را از کامپیوتر‌های سایت جمع آوری کند: + شناسه‌ی پروسه‌ای که مخرب است. + یک قسمت از داده‌های موجود در شاخه‌ی `/proc` که به ازای هر `(pid (process id` شامل فایل‌ها و دایرکتوری‌هایی مشابه فایل‌های زیر است. ``` proc ├── 2 │ ├── fd/ │ │ ├── 0 │ │ ├── 1 │ │ └── 2 │ ├── fdinfo/ │ │ ├── 0 │ │ ├── 1 │ │ └── 2 │ ├── cmdline │ ├── gid_map │ ├── io │ └── status ├── 4 │ ├── fd/ │ ├── fdinfo/ │ ├── cmdline │ ├── gid_map │ ├── io │ └── status ``` از شما می‌خواهیم یک اسکریپت *bash* با نام `analyze.sh‍‍` بنویسید تا با آنالیز کردن اطلاعات موجود در `/proc` اطلاعاتی از این پروسه‌ی مخرب به ما بدهد. # توجه! + تقریبا همه‌ی افرادی که به حل این مساله می‌پردازند برای این که بتوانند به سوال پاسخ بدهند نیاز دارند تا در مورد proc در اینترنت جست‌وجو کنند. # جزئیات نحوه اجرای اسکریپت به این صورت است: ```bash bash analyze.sh malware_pid path/to/proc/snapshot ``` این اسکریپت باید به عنوان خروجی هر کدام از موارد زیر را در یک خط به ما ارائه بدهد. + آی‌دی کاربری که این پروسه را اجرا کرده است. + آی‌دی پروسه‌هایی که توسط این پروسه ایجاد شده اند (پروسه‌های بچه‌) که با فاصله از هم جدا شده‌اند. + آی‌دی پروسه‌ای که این پروسه را شروع کرده است. + آی‌دی پروسه‌هایی که با پروسه‌ی مخرب به صورت هم زمان روی یک فایل متنی مشترک با پسوند `txt` کار می‌کردند. # نکات + ممکن است برخی از اطلاعات خواسته شده برای برخی از `pid` ها وجود نداشته باشد. به طور مثال در صورتی که پروسه مخرب هیچ پروسه‌ی بچه‌ای نداشته باشد، شما باید در خروجی `not-found` چاپ کنید. همینطور در صورتی که پروسه با هیچ پروسه‌ی دیگری به فایل مشترک `txt` دسترسی نداشته باشد باید مقدار بخش چهارم را `not-found` بازگردانید. + توجه داشته باشید که اگر به جای `not-found` کلمه‌ی دیگری چاپ کنید،‌ تمام امتیاز سوال را از دست خواهید داد. + توجه داشته باشید در مورد آخر خواسته شده در پاسخ باید حتما فایلی که برروی آن کار می‌کنند پسوند `txt` باشد. + برای ارسال پاسخ خود یک فایل *Zip* شامل ‍‍`analyze.sh` آپلود کنید. # مثال برای مثال یک خروجی از *proc* به صورت tar.gz [در این آدرس](https://quera.ir/qbox/download/bjecbJhWTw/37829-example.tar.gz) پیوست شده است. شما می‌توانید آن را دانلود کرده، *extract* کنید و پس از نوشتن اسکریپت `analyze.sh` با دستور زیر خروجی خود را چک کنید. + توجه داشته باشید اگر این فایل را در ویندوز `extract` کنید فایل‌ها ناقص می‌شوند. پس باید حتما این کار را در linux انجام دهید. ```bash bash analyze.sh 37829 path/to/proc/snapshot ``` خروجی باید مشابه زیر باشد. ```bash 1000 37830 37831 7225 37832 37833 ``` # امتیاز دهی هر کدام از پاسخ‌ها به این سوال امتیاز خود را دارد. امتیاز بندی به شرح زیر است: + شما برای پیدا کردن `شناسه‌ی پروسه‌ی پدر` و `شناسه‌ی کاربر اجرا کننده` **۶۰** امتیاز خواهید گرفت. فقط توجه داشته باشید که این در صورتی است که برای سایر مقادیر `not-found` چاپ کنید. + در صورتی که به مقادیر بالا و مقدار `آی دی پروسه‌های بچه` جواب دهید. **۱۰۰** امتیاز دیگر خواهید گرفت. + در صورتی که همه‌ی مقادیر را درست به دست آورید **۳۰۰** امتیاز سوال را خواهید گرفت.