یک جدول داریم که در هر خانهاش عددی نوشته شده است.
یک برنامه نویس معمولی به یک خانه از جدول زینی میگوید اگر بتوان روی آن نشست! اما یک برنامه نویس نیمبو به یک خانه از جدول زینی میگوید اگر ۴ همسایه مجاور ضلعیاش موجود باشند و عددش از اعداد خانه های مجاور چپ و راستش بزرگتر، و از اعداد خانه های مجاور بالا و پایینش کوچکتر باشد، و یا بالعکس (یعنی عددش از اعداد خانههای مجاور چپ و راستش کوچکتر و از اعداد خانههای مجاور بالا و پایینش بزرگتر باشد).
شما به عنوان برنامه نویسی نیمبو باید تعداد خانههای زینی یک جدول را پیدا کنید.
خط اول ورودی شامل دو عدد و است.
در خط بعدی برنامه، سطر های جدول آمده اند. به طوری که هر خط شامل عدد است که نشاندهنده اعداد یک سطر از جدول هستند. اعداد جدول طبیعی و کوچکتر مساوی اند.
خروجی شامل یک عدد است که تعداد خانههای زینی جدول از دیدگاه برنامهنویسی نیمبو را نشان میدهد.
فقط خانه وسط جدول زینی است. دقت کنید که بقیه خانهها هیچکدام شرط داشتن ۴ همسایه را ندارند.
خانهای که در سطر سوم و ستون دوم قرار دارد، و همچنین خانهای که در سطر سوم و ستون سوم قرار دارد زینیاند.
صبا یه جدول داره. درون هر خونهی این جدول میتواند حداکثر یک قارچ وجود داشته باشد. قارچها به قوانینای (شبیه به بازی زندگی) زنده میشوند و میمیرند. در هر لحظه:
دو خانه متفاوت و را مجاور مینامیم اگر حداکثر یک ستون و یک سطر با هم فاصله داشتهباشند. (فرض میشود که سطر اول و آخر و همچنین ستون اول و آخر با هم مجاور هستند.) بنابراین هر خانه دقیقا ۸ همسایه دارد.
صبا قبلا یک جدول داشت و روی آن مرحله قوانین بازی زندگی را اجرا کرد. اما از آنجا که جدول اولیه را فراموش کرده به شما جدول نهایی را میدهد و از شما میخواهد جدول اولیه را به او بدهید و یا بگویید که همچین جدولی وجود ندارد.
در خط اول سه عدد و و آمدهاند در خط بعدی رشتهای حرفی آمده است که یعنی اگر در خط ام و حرف ام حرف *
باشد در خانهی یک قارچ وجود دارد و در غیر این صورت آن خانه خالی است.
در خروجی یک جدول از حروف باید چاپ شود که مانند ورودی اگر در خط ام حرف ام *
باشد یعنی در خانهی یک قارچ وجود داشته. اگر جدول اولیهای وجود نداشت پیام impossible
چاپ شود.
توجه کنید که جوابهای دیگری هم ممکن است وجود داشته باشد و شما باید تنها یکی از آنها را چاپ کنید.
توی دوره نیمبو به تفریح کارآموزها اهمیت زیادی داده میشه و واسه همین تو زمان استراحت به کارآموزا میگن که بازی تتریس نیمبویی رو بازی کنن تا هم یه تفریحی واسشون باشه هم زمان استراحت یه جوری بگذره.
در بازی تتریس نیمبویی ستون وجود دارند که از چپ به راست با اعداد ۱ تا شمارهگذاری شدهاند و ستون ام از مربع واحد تشکیل شدهاست.
هر بازیکن در هر حرکت میتواند یک بازه از ستونها را انتخاب کند و به هرکدام یک مربع اضافه کند. (در واقع بازیکن اعداد و را انتخاب میکند و سپس به ازای هر ، مقدار را یکی زیاد میکند.)
هدف بازی یکسان کردن طول تمام ستون ها در کمترین تعداد مرحله است.
حالا مهرداد که از این بازی خوشش نیومده ازتون میخواد تا بهش بگین که این کمترین تعداد مرحله چندتاست تا بتونه سریع بازی رو تموم کنه و به بقیه کاراش برسه.
در خط اول ورودی عدد ، تعداد ستونها میآید.
در خط بعدی عدد آمده که عدد ام آن است که تعداد مربعهای ستون ام را نشان میدهد.
در خروجی یک عدد که کمترین تعداد مراحل برای رسیدن به هدف بازی است را چاپ کنید.
دوبار مقدار ستون اول (بازه ) را، و یکبار مقدار ستون سوم (بازه ) را زیاد میکنیم.
سه بار بازه را انتخاب میکنیم. سپس یکبار بازه و دو بار بازه را انتخاب میکنیم.
قرار است در نیمبو یک فضای ابری برای ذخیره سازی فایلها به اسم NimboDrive بسازیم! کلاسها و توابع اولیه این برنامه را نوشته ایم اما این وظیفه شماست که آنها را پیادهسازی و کامل کنید.
فایلهای اولیه پروژه را از اینجا دانلود کنید.
دقت کنید که نیازی نیست کل کارهای گفته شده در یک قسمت را انجام دهید تا نمره آن قسمت را بگیرید. در هر قسمت هر بخشی را که پیادهسازی کنید، نمره همان بخش را خواهیدگرفت. نحوه آپلود جواب در انتهای سوال آورده شده است.
در این قسمت شما باید کلاس UserStorageRepository
را پیادهسازی کنید. این کلاس مدیریت میکند که هر کاربر چقدر حجم برای ذخیره سازی فایل در سیستم ما دارد. این کلاس برای اینکار در داخل خود یک Map از اسم کاربر و حجم دارد.
برای مثال در خود ذخیره میکند که کاربری به اسم Ali
میتواند 125000 بایت دیگر در سیستم فایل آپلود کند.
توابع گفته شده در زیر را پیادهسازی کنید. (روی عنوان هر کار کلیک کنید تا توضیحات آن باز شود.)
این تابع اسم کاربر و یک عدد گرفته و میزان حجم کاربر را به اندازه عدد داده شده زیاد میکند. اگر کاربر از قبل در Map وجود نداشته باشد آن را اضافه میکند و حجم آن را برابر با مقدار داده شده قرار میدهد.
این تابع اسم کاربر و یک عدد گرفته و بررسی میکند آیا کاربر به اندازه داده شده حجم دارد یا نه. اگر کاربر کلا وجود نداشته باشد باید false
برگردانده شود.
این تابع اسم کاربر و یک عدد گرفته و حجم کاربر را به آن اندازه کم میکند. اگر حجم کاربر به صفر رسید یا منفی شد، آن کاربر از 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
نیز باید فایلهای مرتبط موجود باشند. اسم فایل زیپ مهم نیست. ساختاری مشابه شکل زیر:
در این سوال میخواهیم دو دستور ساده از یک زبان برنامه نویسی را شبیهسازی کنیم.
دستور اول، دستور :=
است. در سمت چپ این دستور اسم متغیر و در سمت راست آن مقداری که میخواهیم به متغیر بدهیم میآید. اسم متغیر یک رشته از حروف کوچیک انگلیسی با حدکثر ۲۰ حرف است. مقدار متغیر میتواند به یکی از دو حالت زیر باشد.
یک لیست از اعداد باشد. شکل لیست این صورت است:
[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
اگر متغیر لیست باشد اندیس خانهایست که باید چاپ شود و اگر متغیر لغتنامه باشد کلید مقداریست که باید چاپ شود. تضمین میشود متغیر داده شده قبلا مقداردهی شده باشد.
به شما یک برنامه که با دستورات توضیح داده نوشته شده، داده میشود. آن را اجرا کنید و خروجی را چاپ کنید.
در خط اول آمده که تعداد خطوط برنامه است و در ادامه یک برنامه خطی آمدهاست.
خروجی برنامه را چاپ کنید.
شرکت سحاب به تازگی مقدار زیادی داده از خریدهایی که در بازار میوهفروشی انجام میشود، به دست آوردهاست. در این دادهها به ازای هر شخصی که به بازار میوه و ترهبار رفته، میوههایی که خریداری کرده، آمدهاست. علی که یکی از کارمندان شرکت است علاقه زیادی به میوهها دارد و از طرفی هم به بررسی دادهها را کاری جذاب میداند، میخواهد بداند که چه زیرمجموعههایی از میوهها پرطرفدار هستند.
علی به یک زیرمجموعه از میوهها پرطرفدار میگوید اگر در حداقل تا از سبدها تکرار شده باشد و اندازه آن هم حداقل دو باشد. ( تعداد کل سبدهاست.) حال ما از شما میخواهیم تا میتوانید زیرمجموعه پرطرفدار پیدا کنید و هر چه قدر زیرمجموعههای بیشتری گزارش کنید، نمره بیشتری از این سوال میگیرید.
توجه کنید که تستهای این سوال طبق دادههای واقعی هستند و سعی کنید از این قضیه در راهحلتان استفاده کنید.
در سطر اول ورودی آمدهاست که تعداد اشخاصی که خرید کردهاند را نشان میدهد. سپس در خط بعدی در ابتدا میآید که تعداد میوههایی که است که شخص ام خریداری کرده و در ادامه آن تا عدد آمده که شماره میوهها را مشخص میکند.
تمام اعداد ورودی کمتر مساوی هستند.
در خروجی ابتدا در زیرمجموعههای پرطرفداری که پیدا کردید را چاپ کنید و سپس در خطهای بعدی به ازای هر زیرمجموعه ابتدا اندازه و سپس اعضای آن را چاپ کنید.
در نظر داشتهباشید که هرچه قدر زیرمجموعههای بیشتری چاپ کنید نمره بیشتری میگیرید و اگر به ازای هر تست حداقل زیرمجموعه پرطرفدار چاپکنید، نمره آن تست را میگیرید.
دقت کنید که در اینجا تمام زیرمجموعههای پرطرفدار خروجی داده شدهاند و شما برای ردکردن بعضی از تستها لازم نیست تا همه را چاپ کنید.
سینا پس از سالها تلاش، توانست پدرش را راضی کند تا برای او یک درخت (گرافی همبند و بدون دور) ریشهدار راسی بخرد. ریشه درخت سینا، راس شماره ۱ و پدر راس شماره راس شماره است. او سپس درخت را به برادر کوچکترش داد تا روی هر راس آن، یک عدد صحیح بنویسد. برادرش روی راس شماره عدد را نوشت. سپس از پدرش تقاضا کرد تا به او کمک کند درختش را زیبا کند.
از نظر سینا و پدرش یک درخت ریشهدار زیبا است اگر به ازای هر رابطه برقرار باشد.
پدر سینا میتواند عملیات زیر را هر چند باری که دلش بخواهد انجام دهد:
آیا سینا و پدر سینا میتوانند درخت سینا را زیبا کنند؟
در خط اول ورودی عدد ، تعداد رئوس درخت سینا آمده است.
در خط دوم عدد آمده است.
در خط سوم نیز عدد آمده است.
در تنها سطر خروجی، اگر سینا و پدر سینا میتوانند درخت را زیبا کنند Yes
و در غیر این صورت No
چاپ کنید.
*توضیح نمونه ۱:* درخت اولیه این شکلی است:
اگر سینا و پدرش یال راس ۲ به پدرش را انتخاب کنند و عملیات را روی آن انجام دهند، به درخت زیبای زیر میرسند:
یک پروسهی مخرب روی کامپیوترهای سایت دانشکده مشاهده شده است و چند کامپیوتر سایت را که سیستم عامل ubuntu داشته اند را درگیر کرده است. یکی از بچههای سال بالایی ادعا کرده که توانسته اطلاعات زیر را از کامپیوترهای سایت جمع آوری کند:
شناسهی پروسهای که مخرب است.
یک قسمت از دادههای موجود در شاخهی /proc
که به ازای هر (pid (process id
شامل فایلها و دایرکتوریهایی مشابه فایلهای زیر است.
از شما میخواهیم یک اسکریپت bash با نام analyze.sh
بنویسید تا با آنالیز کردن اطلاعات موجود در /proc
اطلاعاتی از این پروسهی مخرب به ما بدهد.
تقریبا همهی افرادی که به حل این مساله میپردازند برای این که بتوانند به سوال پاسخ بدهند نیاز دارند تا در مورد proc در اینترنت جستوجو کنند.
نحوه اجرای اسکریپت به این صورت است:
این اسکریپت باید به عنوان خروجی هر کدام از موارد زیر را در یک خط به ما ارائه بدهد.
txt
کار میکردند.pid
ها وجود نداشته باشد. به طور مثال در صورتی که پروسه مخرب هیچ پروسهی بچهای نداشته باشد، شما باید در خروجی not-found
چاپ کنید. همینطور در صورتی که پروسه با هیچ پروسهی دیگری به فایل مشترک txt
دسترسی نداشته باشد باید مقدار بخش چهارم را not-found
بازگردانید.not-found
کلمهی دیگری چاپ کنید، تمام امتیاز سوال را از دست خواهید داد.txt
باشد.analyze.sh
آپلود کنید.برای مثال یک خروجی از proc به صورت tar.gz در این آدرس پیوست شده است. شما میتوانید آن را دانلود کرده، extract کنید و پس از نوشتن اسکریپت analyze.sh
با دستور زیر خروجی خود را چک کنید.
extract
کنید فایلها ناقص میشوند. پس باید حتما این کار را در linux انجام دهید.خروجی باید مشابه زیر باشد.
هر کدام از پاسخها به این سوال امتیاز خود را دارد. امتیاز بندی به شرح زیر است:
شناسهی پروسهی پدر
و شناسهی کاربر اجرا کننده
۶۰ امتیاز خواهید گرفت. فقط توجه داشته باشید که این در صورتی است که برای سایر مقادیر not-found
چاپ کنید. آی دی پروسههای بچه
جواب دهید. ۱۰۰ امتیاز دیگر خواهید گرفت.