s.c.i.t

science of computer and infomation technology

s.c.i.t

science of computer and infomation technology

s.c.i.t
تبلیغات
Blog.ir بلاگ، رسانه متخصصین و اهل قلم، استفاده آسان از امکانات وبلاگ نویسی حرفه‌ای، در محیطی نوین، امن و پایدار bayanbox.ir صندوق بیان - تجربه‌ای متفاوت در نشر و نگهداری فایل‌ها، ۳ گیگا بایت فضای پیشرفته رایگان Bayan.ir - بیان، پیشرو در فناوری‌های فضای مجازی ایران
طبقه بندی موضوعی

 


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



۱) برنامه ای بنویسید که از ورودی n را دریافت کرده٬ n خط بعدی که هر کدام n کاراکتر دارند را دریافت کرده٬ هر کاراکتر یا یک حرف انگلیسی است یا نقطه٬ هر حرف انگلیسی هم حد اکثر یک بار در جدول می آید٬ خب حالا برنامه چی رو باید حساب کنه؟! ... ما به هر مجموعه ای از سه کاراکتر که روی یک خط قرار دارند تریپلت می گوییم٬ برنامه ی شما باید تعداد تریپلت های موجود در این جدول n در n را به ما بدهد!

مثال :
ورودی :
4
a...
.b..
..c.
...d
خروجی :
4

۲) برنامه ی بنویسید که به گروه زیر کمک کند!
جریان از این قرار است که در این نقشه که r سطر و c ستون دارد٬ نقطه ها نمایانگر فضای آزاد هستند٬ * نمایانگر سیلاب و x نمایانگر صخره هست٬ s نمایانگر گروه ماست که قرار است خود را به نقطه ی d برساند! اکنون می دانیم که گروه ما در هر دقیقه به یکی از خانه های مجاور که در نقشه وجود دارند می تواند برود به جز جاهایی که سیلاب و صخره حضور دارد٬ از طرفی در هر دقیقه سیلاب نیز خود را گسترش می دهد و به خانه ی های همسایه ای که در نقشه وجود دارند می رود به جز در صخره ها و نقطه ی d ٬ اکنون بگویید حداقل در چند حرکت گروه ما می تواند خود را به d برساند٬ اگر ممکن نیست نیز برنامه کلمه ی KAKTUS را چاپ کند!
در ورودی ابتدا تعداد سطر ها و ستون ها می آید و در خطوط بعدی متناسب با تعداد سطر ها و ستون ها نقشه چاپ می شود٬ فرض کنید هر کدام از سطر و ستون ها کم تر از ۵۰ تا هستند!

مثال :
ورودی:
۳ ۳
* . d
. . .
. s .
خروجی :
۳

ورودی :
* . d
. . .
s . .
خروجی :
KAKTUS

۳) در این مسئله باید برنامه ای بنویسید تا به سرپرست این ماموران کمک کند!
n عدد مامور داریم که قرار است هر کدام یک ماموریت انجام دهند (که در مجموع n ماموریت انجام می دهند!) از قرار معلوم می دانیم هر مامور چند درصد احتمال دارد که هر ماموریتی را درست انجام دهد٬ اکنون باید بتوانید به سرپرست این گروه بگویید که حد اکثر چند درصد احتمال دارد همه ی ماموران بتوانند ماموریت ها را درست انجام دهند! در ورودی ابتدا تعداد ماموران و ماموریت ها آمده است که کمتر از ۲۰ است٬ در بیست خط بعدی در هر سطر بیست عدد آمده با این شرط که عدد j ام در خط i ام بیانگر احتمال درست انجام دادن ماموریت j توسط مامور شماره ی i است! در خروجی نیز باید حد اکثر احتمال را با ۰.۰۰۰۰۰۱ رقم اعشاری بگویید، در ضمن هر عدد در ورودی عددی بین ۰ و ۱۰۰ است که بیانگر درصد می باشد!

مثال :
ورودی :
۳
۱۰۰ ۶۰ ۲۵
۵۰ ۰ ۱۳
۹۰ ۷۰ ۱۲
خروجی :
۹.۱۰۰۰۰۰

توضیح در مورد این مثال : اگر مامور شماره ی ۱ ماموریت ۳ را و مامور شماره ی ۲ ماموریت ۱ را و مامور شماره ی ۳ ماموریت ۲ را بردارد این احتمال می شود :
٪ ۹.۱ = ۰.۷ * ۰.۱۳ * ۱

خب موفق باشید امیدوارم بتونید حل کنید٬ در ضمن لازم نیست که برنامه رو بنویسید٬ الگوریتم رو هم بتونید بیابید کافی است!
توضیح در مورد مسائل : مسئله ی یک آسان است و با یک تجربه ی کافی از برنامه نویسی حل می شود٬ مسئله ی دو کمی سخت است و با دانستن bfs حل می شود و مسئله ی سوم که سخت است با دانستن dynamic programming حل می شود! اگر این دو را نمی دانید توضیحاتش را در پست های آتی می آورم٬ به نظر می رسد مسئله ی دو برای دانش آموزان دوم دبیرستان (حد اقل به دست آوردن الگوریتم آن) خوب باشد و برای کسانی که برای مرحله دو کار می کنند مسئله ی سه خوب است و برای آنان که دوره رفته اند این مسائل جمعاْ آسان است! این ها را با این حساب گفتم که در دوره ی دبیرستان غالبا دانش آموزان دوم دبیرستانی گراف به حدی خوانده اند که بی اف اس و دی اف اس را بفهمند و آنان که برای مرحله دو کار می کنند احتمالاْ از شباهت بعضی از سوالات مرحله دو با داینامیک آن را خوانده باشند و مورد سوم برای بر و بچ دوره بدیهی است!
منبع سوالات مسابقات آزاد برنامه نویسی دبیرستانی کرواسی است که می توانید آن را در لینک زیر بیابید
http://www.hsin.hr/



نظر یادتون نره!


  • امیر محمد یوسفی

نظرات  (۱)

quisiera saber si se podrían juntar las letras como pa formar un nombre e imprimirlas el nombre es Vietncecualquier cosa a mi mail porfaaa.. es que no las puedo juntar y no me quedan iguales