زینی


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

یک جدول n×m n \times m داریم که در هر خانه‌اش عددی نوشته شده است.

یک برنامه نویس معمولی به یک خانه از جدول زینی می‌گوید اگر بتوان روی آن نشست! اما یک برنامه نویس نیمبو به یک خانه از جدول زینی می‌گوید اگر ۴ همسایه مجاور ضلعی‌اش موجود باشند و عددش از اعداد خانه های مجاور چپ و راستش بزرگ‌تر، و از اعداد خانه های مجاور بالا و پایینش کوچک‌تر باشد، و یا بالعکس (یعنی عددش از اعداد خانه‌های مجاور چپ و راستش کوچک‌تر و از اعداد خانه‌های مجاور بالا و پایینش بزرگ‌تر باشد).

شما به عنوان برنامه نویسی نیمبو باید تعداد خانه‌های زینی یک جدول را پیدا کنید.

ورودی🔗

خط اول ورودی شامل دو عدد nn و mm است.

در nn خط بعدی برنامه، سطر های جدول آمده اند. به طوری که هر خط شامل mm عدد است که نشان‌دهنده اعداد یک سطر از جدول هستند. اعداد جدول طبیعی و کوچکتر مساوی 109 10^{9} اند. 1n,m1001 \le n, m \le 100

خروجی🔗

خروجی شامل یک عدد است که تعداد خانه‌های زینی جدول از دیدگاه برنامه‌نویسی نیمبو را نشان می‌دهد.

مثال🔗

ورودی نمونه ۱🔗

3 3
1 2 3
6 5 6
1 1 1
Plain text

خروجی نمونه ۱🔗

1
Plain text

فقط خانه وسط جدول زینی است. دقت کنید که بقیه خانه‌ها هیچ‌کدام شرط داشتن ۴ همسایه را ندارند.

ورودی نمونه ۲🔗

4 4
1 2 4 1
7 4 1 1
1 3 2 4
1 4 1 1
Plain text

خروجی نمونه ۲🔗

2
Plain text

خانه‌ای که در سطر سوم و ستون دوم قرار دارد، و هم‌چنین خانه‌ای که در سطر سوم و ستون سوم قرار دارد زینی‌اند.

گال


  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

صبا یه جدول n×mn \times m داره. درون هر خونه‌ی این جدول می‌تواند حداکثر یک قارچ وجود داشته باشد. قارچ‌ها به قوانین‌ای (شبیه به بازی زندگی) زنده می‌شوند و می‌میرند. در هر لحظه:

  • اگر در لحظه‌ی قبل در این خانه قارچ وجود داشته باشد و در خانه‌های مجاور آن در لحظه قبل بین ۲ تا ۳ قارچ وجود داشته باشد، زنده می‌ماند و در غیر این صورت می‌میرد.
  • اگر در لحظه‌ی قبل در این خانه قارج وجود نداشته باشد و در خانه‌های مجاور آن در لحظه قبل دقیقا ۳ قارچ وجود داشته باشد، یک قارچ در این خانه به وجود می‌آید.

دو خانه متفاوت (a,b)(a, b) و (x,y)(x, y) را مجاور می‌نامیم اگر حداکثر یک ستون و یک سطر با هم فاصله داشته‌باشند. (فرض می‌شود که سطر اول و آخر و هم‌چنین ستون اول و آخر با هم مجاور هستند.) بنابراین هر خانه دقیقا ۸ همسایه دارد.

صبا قبلا یک جدول داشت و روی آن ll مرحله قوانین بازی زندگی را اجرا کرد. اما از آن‌جا که جدول اولیه را فراموش کرده به شما جدول نهایی را می‌دهد و از شما می‌خواهد جدول اولیه را به او بدهید و یا بگویید که همچین جدولی وجود ندارد.

ورودی🔗

در خط اول سه عدد nn و mm و ll آمده‌اند در nn خط بعدی رشته‌ای mm حرفی آمده است که یعنی اگر در خط iiام و حرف jjام حرف * باشد در خانه‌ی (i,j)(i, j) یک قارچ وجود دارد و در غیر این صورت آن خانه خالی است.

9n×m20 9 \le n \times m \le 20 3n,m6 3 \le n, m \le 6 1l20 1 \le l \le 20

خروجی🔗

در خروجی یک جدول n×mn \times m از حروف باید چاپ شود که مانند ورودی اگر در خط iiام حرف jjام * باشد یعنی در خانه‌ی (i,j)(i, j) یک قارچ وجود داشته. اگر جدول اولیه‌ای وجود نداشت پیام impossible چاپ شود.

مثال🔗

ورودی نمونه ۱🔗

4 5 10
....*
..*.*
.*..*
..*.*
Plain text

خروجی نمونه ۱🔗

..*.*
...**
**.**
*....
Plain text

توجه کنید که جواب‌های دیگری هم ممکن است وجود داشته باشد و شما باید تنها یکی از آن‌ها را چاپ کنید.

ورودی نمونه ۲🔗

3 3 10
***
***
*..
Plain text

خروجی نمونه ۲🔗

impossible
Plain text

تتریس


  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

توی دوره نیمبو به تفریح کارآموزها اهمیت زیادی داده می‌شه و واسه همین تو زمان استراحت به کارآموزا می‌گن که بازی تتریس نیمبویی رو بازی کنن تا هم یه تفریحی واسشون باشه هم زمان استراحت یه جوری بگذره.

در بازی تتریس نیمبویی nn ستون وجود دارند که از چپ به راست با اعداد ۱ تا nn شماره‌گذاری شده‌اند و ستون ii ام از aia_{i} مربع واحد تشکیل شده‌است.

هر بازیکن در هر حرکت می‌تواند یک بازه از ستون‌ها را انتخاب کند و به هرکدام یک مربع اضافه کند. (در واقع بازیکن اعداد ll و rr را انتخاب میکند و سپس به ازای هر ljrl \le j \le r ، مقدار aja_{j} را یکی زیاد می‌کند.)

هدف بازی یکسان کردن طول تمام ستون ها در کم‌ترین تعداد مرحله است.

حالا مهرداد که از این بازی خوشش نیومده ازتون می‌خواد تا بهش بگین که این کم‌ترین تعداد مرحله چندتاست تا بتونه سریع بازی رو تموم کنه و به بقیه کاراش برسه.

ورودی🔗

در خط اول ورودی عدد nn ، تعداد ستون‌ها می‌آید.

در خط بعدی nn عدد آمده که عدد ii ام آن aia_{i} است که تعداد مربع‌های ستون ii ام را نشان می‌دهد.

1n1 000 000 1 \le n \le 1\ 000\ 000 1ai1 000 000 000 1 \le a_{i} \le 1\ 000\ 000\ 000

خروجی🔗

در خروجی یک عدد که کم‌ترین تعداد مراحل برای رسیدن به هدف بازی است را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
1 3 2
Plain text

خروجی نمونه ۱🔗

3
Plain text

دوبار مقدار ستون اول (بازه [1,1][1,1] ) را، و یکبار مقدار ستون سوم (بازه [3,3][3,3] ) را زیاد میکنیم.

ورودی نمونه ۲🔗

5
4 3 1 3 7
Plain text

خروجی نمونه ۲🔗

6
Plain text

سه بار بازه [1,4][1,4] را انتخاب میکنیم. سپس یکبار بازه [2,4][2,4] و دو بار بازه [3,3][3,3] را انتخاب میکنیم.

نیمبو درایو


  • در این سوال به هر بخش از سوال که پاسخ بدهید نمره همان قسمت را خواهید گرفت
  • این سوال را باید با زبان جاوا پاسخ دهید. دقت کنید که انتظار نمی‌رود که همه مفاهیم را از ابتدا بلد باشید و ممکن است بسته به توانایی خود نیاز به جست‌و‌جو کردن داشته باشید.

قرار است در نیمبو یک فضای ابری برای ذخیره سازی فایل‌ها به اسم NimboDrive بسازیم! کلاس‌ها و توابع اولیه این برنامه را نوشته ایم اما این وظیفه شماست که آن‌ها را پیاده‌سازی و کامل کنید.

فایل‌های اولیه پروژه را از اینجا دانلود کنید.

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


قسمت اول🔗

در این قسمت شما باید کلاس UserStorageRepository را پیاده‌سازی کنید. این کلاس مدیریت می‌کند که هر کاربر چقدر حجم برای ذخیره سازی فایل در سیستم ما دارد. این کلاس برای این‌کار در داخل خود یک Map از اسم کاربر و حجم دارد. برای مثال در خود ذخیره می‌کند که کاربری به اسم Ali می‌تواند 125000 بایت دیگر در سیستم فایل آپلود کند.

توابع گفته شده در زیر را پیاده‌سازی کنید. (روی عنوان هر کار کلیک کنید تا توضیحات آن باز شود.)

تابع increaseStorageOfUser

این تابع اسم کاربر و یک عدد گرفته و میزان حجم کاربر را به اندازه عدد داده شده زیاد می‌کند. اگر کاربر از قبل در Map وجود نداشته باشد آن را اضافه می‌کند و حجم آن را برابر با مقدار داده شده قرار می‌دهد.

تابع hasStorage

این تابع اسم کاربر و یک عدد گرفته و بررسی می‌کند آیا کاربر به اندازه داده شده حجم دارد یا نه. اگر کاربر کلا وجود نداشته باشد باید false‍ برگردانده شود.

تابع decreaseStorageOfUser

این تابع اسم کاربر و یک عدد گرفته و حجم کاربر را به آن اندازه کم می‌کند. اگر حجم کاربر به صفر رسید یا منفی شد، آن کاربر از Map حذف می‌شود.


قسمت دوم🔗

کلاس NimboFile یک فایل را در سیستم ما مشخص می‌کند. این کلاس، زیرکلاس‌هایی(مثل TextFile) دارد که نوع فایل را مشخص می‌کنند. هر فایل یک اسم(مثلا readme.txt)، یک پوشه (مثلا /user/ali/) ، یک مالک (مثلا Ali) و یک عدد به عنوان حجم دارد که واحد آن بایت است.

کلاس FileRepository کلاس اصلی برای مدیریت فایل‌هاست که در آن کل فایل‌ها و اطلاعات آنها ذخیره می‌شود.

شما باید کارهای گفته شده در زیر را انجام دهید.

نوشتن متد toString برای NimboFile

در کلاس NimboFile متد toString را override کنید به طوری که اسم کامل فایل(مثلا a.txt) را برگرداند.

پیاده‌سازی تابع addFile‍ در کلاس FileRepository

این تابع یک فایل به عنوان ورودی می‌گیرد و اگر مالک فایل به اندازه کافی حجم داشته باشد، فایل را به مجموعه فایل‌های ذخیره شده اضافه می‌کند و به اندازه حجم فایل از فضای مالک کم می‌کند. اگر مالک فایل به اندازه کافی حجم نداشته باشد باید یک استنا از نوع IllegalArgumentException پرتاب کنید.

درون این کلاس یک شی از جنس UserStorageRepository وجود دارد که برای کم‌کردن حجم از کاربر باید از آن استفاده کنید.

پیاده‌سازی تابع searchByName در کلاس FileRepository

این تابع یک رشته دریافت کرده و لیست تمام فایل‌هایی که رشته داده شده در اسم آن‌ها تکرار شده‌است را بر می‌گرداند. دقت کنید که فرمت فایل نباید در جست و جو در نظر گرفته شود. برای مثال اگر اسم فایل a.txt باشد و xt را سرچ کنیم، این فایل نباید برگرداننده شود. جست و جو حساس به حروف بزرگ و کوچک نیست.

پیاده‌سازی تابع scan در کلاس FileRepository

یک شئ در این کلاس به اسم scanner وجود دارد. این شئ یک تابع به اسم scanFile دارد که یک فایل ورودی میگیرد و اگر فایل ویروسی باشد یک اکسپشن پرت میکند. این تابع به کمک این شئ تمام فایل‌ها را اسکن می‌کند و فایل‌هایی که عادی نیستند را از مجموعه فایل‌ها حذف می‌کند و حجم آن‌ها را به مالکان فایل‌ها بر می‌گرداند.


قسمت سوم🔗

برنامه ما این قابلیت را دارد که بعضی از انواع فایل‌ها را بدون دانلود به صورت پیش‌نمایش به کاربر نشان دهد. فایلی که این قابلیت را دارد واسط hasPreview را پیاده‌سازی می‌کند.

اضافه کردن پیش‌نمایش به کلاس TextFile

کلاس TextFile را عوض کنید به گونه‌ای که اینترفیسِ HasPreview<String> را پیاده‌سازی کند.دقت کنید که نیازی نیست در این بخش تابع preview‍ را هم پیاده‌سازی کنید. برای سادگی فعلاً می‌توانید در آن return null; بگذارید.

پیاده‌سازی تابع isPreviewable در کلاس FileRepository

این تابع یک فایل می‌گیرد و اگر فایل داده شده اینترفیسِ HasPreview را پیاده‌سازی کرده باشد (یا به عبارت دیگر از جنس HasPreview باشد ) true بر می‌گرداند.

پیاده‌سازی تابع sort‍ در کلاس FileRepository

این تابع یک Comparator ‍به عنوان ورودی می‌گیرد و فایل‌ها را با توجه به آن مرتب کرده به صورت آرایه بر می‌گرداند.


قسمت چهارم🔗

پیاده‌سازی تابع findLongestMediaInDirectory در کلاس FileRepository

این تابع آدرس یک پوشه را می‌گیرد(مثلا /home/ali/) و طولانی‌ترین فایل درون آن پوشه که از جنس MediaFile باشد را درون یک Optional‍ گذاشته و برمی‌گرداند. طولانی‌ترین فایل، فایلی است که duration آن از همه بیش‌تر باشد. اگر در آن پوشه هیج فایل مدیایی وجود نداشته باشد ‍Optional.empty() برگردانده می‌شود. هم‌چنین اگر چندین فایل با طول یکسان وجود داشت یکی از آنها به دلخواه باید برگرداننده شود.

پیاده‌سازی پیش‌نمایش برای کلاس TextFile

در قسمت قبل کلاس TextFile را عوض کردید به گونه‌ای که اینترفیسِ HasPreview<String> را پیاده‌سازی کند. در این بخش باید تابع preview را در این کلاس پیاده‌سازی کنید. این تابع یک InputStream که مربوط به این فایل متنی است را دریافت می‌کند و باید خط اول آن را بخواند و رشته خوانده شده را در کلاس Preview قرار دهد و آن را برگرداند.

پیاده‌سازی تابع applyToAllByFilter در کلاس FileRepository

این تابع یک فیلتر و یک تابع به عنوان ورودی گرفته و تابع گرفته شده را روی تمامی فایل‌هایی که با فیلتر مطابقت دارند(فیلتر به ازای آنها true برمیگرداند) اعمال می‌کند.


نکات🔗

  • یک فایل به اسم 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
Plain text

چی‌سون؟


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

در این سوال می‌خواهیم دو دستور ساده از یک زبان برنامه نویسی را شبیه‌سازی کنیم.

دستور اول، دستور := است. در سمت چپ این دستور اسم متغیر و در سمت راست آن مقداری که می‌خواهیم به متغیر بدهیم می‌آید. اسم متغیر یک رشته از حروف کوچیک انگلیسی با حدکثر ۲۰ حرف است. مقدار متغیر می‌تواند به یکی از دو حالت زیر باشد.

  • یک لیست از اعداد باشد. شکل لیست این صورت است:

    [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 اگر متغیر لیست باشد اندیس خانه‌ایست که باید چاپ شود و اگر متغیر لغت‌نامه باشد کلید مقداریست که باید چاپ شود. تضمین می‌شود متغیر داده شده قبلا مقداردهی شده باشد.

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

ورودی🔗

در خط اول nn آمده که تعداد خطوط برنامه است و در ادامه یک برنامه nn خطی آمده‌است. 1n200 1 \le n \le 200

خروجی🔗

خروجی برنامه را چاپ کنید.

مثال🔗

ورودی نمونه🔗

4
a := [1, 2, 3]
b := {"2": 1, "1": 4, "4": 5}
print a[1]
print b["1"]
Plain text

خروجی نمونه🔗

2
4
Plain text

دیتای‌ بزرگ


  • محدودیت زمان: ۷ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

شرکت سحاب به تازگی مقدار زیادی داده از خریدهایی که در بازار میوه‌فروشی انجام می‌شود، به دست آورده‌است. در این داده‌ها به ازای هر شخصی که به بازار میوه و تره‌بار رفته، میوه‌هایی که خریداری کرده، آمده‌است. علی که یکی از کارمندان شرکت است علاقه زیادی به میوه‌ها دارد و از طرفی هم به بررسی داده‌‌ها را کاری جذاب می‌داند، می‌خواهد بداند که چه زیرمجموعه‌هایی از میوه‌ها پرطرفدار هستند.

علی به یک زیرمجموعه از میوه‌ها پرطرفدار می‌گوید اگر در حداقل n10\lfloor \frac n{10} \rfloor تا از سبدها تکرار شده باشد و اندازه آن هم حداقل دو باشد. (nn تعداد کل سبدهاست.) حال ما از شما می‌خواهیم تا می‌توانید زیرمجموعه پرطرفدار پیدا کنید و هر چه قدر زیرمجموعه‌های بیشتری گزارش کنید، نمره بیشتری از این سوال می‌گیرید.

توجه کنید که تست‌های این سوال طبق داده‌های واقعی هستند و سعی کنید از این قضیه در راه‌حل‌تان استفاده کنید.

ورودی🔗

در سطر اول ورودی nn آمده‌است که تعداد اشخاصی که خرید کرده‌اند را نشان می‌دهد. سپس در nn خط بعدی در ابتدا kik_i می‌آید که تعداد میوه‌هایی که است که شخص iiام خریداری کرده و در ادامه آن kik_iتا عدد آمده که شماره میوه‌ها را مشخص می‌کند.

1n300 0001 \le n \le 300\ 000 1ki801 \le k_i \le 80

تمام اعداد ورودی کم‌تر مساوی 10610^6 هستند.

خروجی🔗

در خروجی ابتدا در زیرمجموعه‌های پرطرفداری که پیدا کردید را چاپ کنید و سپس در خط‌های بعدی به ازای هر زیرمجموعه ابتدا اندازه و سپس اعضای آن را چاپ کنید.

در نظر داشته‌باشید که هرچه قدر زیرمجموعه‌های بیشتری چاپ کنید نمره بیشتری می‌گیرید و اگر به ازای هر تست حداقل 2 000 0002\ 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
Plain text

خروجی نمونه ۱🔗

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 
Plain text

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

نکات🔗

  • اگر از زبان پایتون برای حل این سوال استفاده می‌کنید پیشنهاد می‌کنیم از Pypy 3 هنگام ارسال استفاده کنید.
  • اگر در خروجی زیرمجموعه‌ای را چاپ کنید که پرطرفدار نباشد از آن تست هیچ نمره‌ای نمی‌گیرید.

درخت سینا


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

سینا پس از سال‌ها تلاش، توانست پدرش را راضی کند تا برای او یک درخت (گرافی همبند و بدون دور) ریشه‌دار nn راسی بخرد. ریشه درخت سینا، راس شماره ۱ و پدر راس شماره ii (2in)(2 \leq i \leq n) راس شماره pip_i است. او سپس درخت را به برادر کوچک‌ترش داد تا روی هر راس آن، یک عدد صحیح بنویسد. برادرش روی راس شماره ii عدد aia_i را نوشت. سپس از پدرش تقاضا کرد تا به او کمک کند درختش را زیبا کند.

از نظر سینا و پدرش یک درخت ریشه‌دار زیبا است اگر به ازای هر 2vn2 \leq v \leq n رابطه avapva_v \geq a_{p_v} برقرار باشد.

پدر سینا می‌تواند عملیات زیر را هر چند باری که دلش بخواهد انجام دهد:

  • یک یال مانند یال vv به pvp_v در نظر بگیرد. سپس عدد نوشته شده روی راس vv را با عدد نوشته شده روی راس pvp_v عوض کند. بعد از آن به عدد روی راس pvp_v یکی اضافه کند و از عدد روی راس vv یکی کم کند. (برای درک بیشتر، توضیح نمونه ۱ را ببینید)

آیا سینا و پدر سینا می‌توانند درخت سینا را زیبا کنند؟

ورودی🔗

در خط اول ورودی عدد nn، تعداد رئوس درخت سینا آمده است.

در خط دوم n1n - 1 عدد p2,p3,...,pnp_2, p_3, ..., p_n آمده است.

در خط سوم نیز nn عدد a1,a2,...,ana_1, a_2, ..., a_n آمده است.

2n200000 2 \leq n \leq 200 \, 000 1pi<i 1 \leq p_i < i 109ai109 -10^9 \leq a_i \leq 10^9

خروجی🔗

در تنها سطر خروجی، اگر سینا و پدر سینا می‌توانند درخت را زیبا کنند Yes و در غیر این صورت No چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
1 1
10 5 20
Plain text

خروجی نمونه ۱🔗

Yes
Plain text

*توضیح نمونه ۱:* درخت اولیه این شکلی است: درخت اولیه

اگر سینا و پدرش یال راس ۲ به پدرش را انتخاب کنند و عملیات را روی آن انجام دهند، به درخت زیبای زیر می‌رسند: درخت ثانویه

ورودی نمونه ۲🔗

2
1
2 1
Plain text

خروجی نمونه ۲🔗

No
Plain text

ورودی نمونه ۳🔗

6
1 1 2 4 4
7 4 8 4 1 10
Plain text

خروجی نمونه ۳🔗

Yes
Plain text

پروسه‌ی بد


  • در این سوال به هر بخش از سوال که پاسخ بدهید نمره همان قسمت را خواهید گرفت (توضیح نمره‌ی سوال در انتهای سوال قرار دارد)
  • این سوال را باید با 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
    Plain text

    از شما می‌خواهیم یک اسکریپت bash با نام analyze.sh‍‍ بنویسید تا با آنالیز کردن اطلاعات موجود در /proc اطلاعاتی از این پروسه‌ی مخرب به ما بدهد.

    توجه!🔗

  • تقریبا همه‌ی افرادی که به حل این مساله می‌پردازند برای این که بتوانند به سوال پاسخ بدهند نیاز دارند تا در مورد proc در اینترنت جست‌وجو کنند.

    جزئیات🔗

نحوه اجرای اسکریپت به این صورت است:

bash analyze.sh malware_pid path/to/proc/snapshot
Bash

این اسکریپت باید به عنوان خروجی هر کدام از موارد زیر را در یک خط به ما ارائه بدهد.

  • آی‌دی کاربری که این پروسه را اجرا کرده است.
  • آی‌دی پروسه‌هایی که توسط این پروسه ایجاد شده اند (پروسه‌های بچه‌) که با فاصله از هم جدا شده‌اند.
  • آی‌دی پروسه‌ای که این پروسه را شروع کرده است.
  • آی‌دی پروسه‌هایی که با پروسه‌ی مخرب به صورت هم زمان روی یک فایل متنی مشترک با پسوند txt کار می‌کردند.

نکات🔗

  • ممکن است برخی از اطلاعات خواسته شده برای برخی از pid ها وجود نداشته باشد. به طور مثال در صورتی که پروسه مخرب هیچ پروسه‌ی بچه‌ای نداشته باشد، شما باید در خروجی not-found چاپ کنید. همینطور در صورتی که پروسه با هیچ پروسه‌ی دیگری به فایل مشترک txt دسترسی نداشته باشد باید مقدار بخش چهارم را not-found بازگردانید.
  • توجه داشته باشید که اگر به جای not-found کلمه‌ی دیگری چاپ کنید،‌ تمام امتیاز سوال را از دست خواهید داد.
  • توجه داشته باشید در مورد آخر خواسته شده در پاسخ باید حتما فایلی که برروی آن کار می‌کنند پسوند txt باشد.
  • برای ارسال پاسخ خود یک فایل Zip شامل ‍‍analyze.sh آپلود کنید.

مثال🔗

برای مثال یک خروجی از proc به صورت tar.gz در این آدرس پیوست شده است. شما می‌توانید آن را دانلود کرده، extract کنید و پس از نوشتن اسکریپت analyze.sh با دستور زیر خروجی خود را چک کنید.

  • توجه داشته باشید اگر این فایل را در ویندوز extract کنید فایل‌ها ناقص می‌شوند. پس باید حتما این کار را در linux انجام دهید.
bash analyze.sh 37829 path/to/proc/snapshot
Bash

خروجی باید مشابه زیر باشد.

1000
37830 37831
7225
37832 37833
Bash

امتیاز دهی🔗

هر کدام از پاسخ‌ها به این سوال امتیاز خود را دارد. امتیاز بندی به شرح زیر است:

  • شما برای پیدا کردن شناسه‌ی پروسه‌ی پدر و شناسه‌ی کاربر اجرا کننده ۶۰ امتیاز خواهید گرفت. فقط توجه داشته باشید که این در صورتی است که برای سایر مقادیر not-found چاپ کنید.
  • در صورتی که به مقادیر بالا و مقدار آی دی پروسه‌های بچه جواب دهید. ۱۰۰ امتیاز دیگر خواهید گرفت.
  • در صورتی که همه‌ی مقادیر را درست به دست آورید ۳۰۰ امتیاز سوال را خواهید گرفت.