آرشیو - گفت و گو ها پیرمون مراحل مختلف ، دوران مختلف

وضعیت
موضوع بسته شده است.

ArtmisSoR

کاربر حرفه‌ای
ارسال‌ها
292
امتیاز
3,448
نام مرکز سمپاد
فرزانگان‎امین
شهر
Isf
دانشگاه
پلی‌پیکنیک
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات مرحله 2 - تشریحی

به نقل از MeC :
مهمان نواز افراطی ! هنوز در درک این سوال مشکل دارم من ، بیاید بگذریم از این سوال :-"

اینو حل کنید ، سخته یکم : مسئله 5 - دوره بیست - دنباله - قسمت ب

برای این که تعداد مراحل به اندازه ی n-1 بشه باید در هر دوره از اجراهای الگوریتم، تعداد اعداد متمایز نصف شود:
n/2 + n/4 + n/8 +...+ n/n = n-1
اگر مرحله ی 3 الگوریتم رو بررسی کنیم؛ می فهمیم که ماکزیمم مقداری که به B در ادامه ی این مرحله اضافه میشه، وقتی ایجاد میشه که f(ax) برابر با f(ay) باشه. چون اگر برابر نباشند، در مرحله ی 4 یا 7 الگوریتم، مقدار f کمتر به B اضافه میشه.
پس در دور اول تعداد n/2 عدد 1 به B اضافه میشه. در دور بعد تعداد n/4 عدد 2، و دور بعدش n/8 عدد 4 و همین طور ادامه پیدا میکنه تا زمانی که کلّ nتا عدد به دو دسته عدد تقسیم شدن که عدد هر دسته با دسته ی دیگه متفاوت ـه ولی تعداد اعداد در هر دسته برابر n/2 هست؛ پس 1 عدد n/2 به B اضافه میشه. در مجموع n-1 مرحله اجرای الگوریتم، B این طور بدست میاد: (n=2^k)

xn0nq9t4jg7lchxgtdi2.jpg



من اصلاً اثبات کردن بلد نیستم و میدونم اینی که نوشتم احتمالاً بررسی یه حالت خآص هست؛ و مشکل عمده ام با این اثبات اینه که در نهایت به جواب k * 2^k-1 می رسم در حالی که مسئله k * 2^k رو خواسته...

خولا3 منتظر اثبات صحیــ ـحِ این سوال میباشیــ ـم :D
 

عمو ژپتو

کاربر خاک‌انجمن‌خورده
ارسال‌ها
1,710
امتیاز
5,696
نام مرکز سمپاد
علامه حلی 1
شهر
کرمان
سال فارغ التحصیلی
93
مدال المپیاد
قبولی در مرحله دوم المپیاد کامپیوتر
دانشگاه
شهید باهنر کرمان / شریف
رشته دانشگاه
ریاضی :x
پاسخ : سوالات مرحله 2 - تستی

آقا من میگم اینجا هم بیایم مشکل بپرسیم بهتره ها :-"
من تو سوال آخر دوره 21 مشکل دارم :-" من میگم برا هر 4 تا میشه :-"
برا همم اثبات کردم :-"
شما گفتید کدوم یکی نمیشه :-" ؟؟؟
 

Aimoi

کاربر فوق‌فعال
ارسال‌ها
80
امتیاز
609
نام مرکز سمپاد
شهید بهشتی
مدال المپیاد
برای المپیاد کامپیوتر مطالعاتی داشتم.
دانشگاه
دانشگاه تبریز
رشته دانشگاه
مهندسی کامپیوتر
پاسخ : سوال های مرحله 2 تستی

به نقل از MeC :
5-


اثبات کمینه بودن عدد 10
فرض کنید می خوایم بزاریمشون تو دو دسته A و B ! پس اولش 20^2 حالت داریم
خب واضحه با هر نتیجه ای که به دست بیارید ، تعداد جواب مسئله رو تقسیم به 4 کردید
یعنی قدرت تفکیکمون 4 هست
پس واضحه برای اینکه به 1 حالت درست مسئله برسیم باید 10 مرحله حداقل کارمون رو انجام بدیم !

و میمونه راهی با 10 مرحله : اولش 6 دسته 3 تایی درست می کنیم و یک دسته 2 تایی
حالا تو 6 مرحله هر کدوم از اون 6 دسته رو از هم جدا میکنیم و در 3 مرحله با هم ادغام
حالا هم اون 2 تای بیرونی رو با یکی از 18 تای بقیه در نظر میگیریم و 2 دستمون درست میشه #S-:
خب آخه اینجا یه مسئله ای نمی مونه؟ : این که از کجا معلوم سیستم اون دو تا سکه ی آخری چی بوده؛ ینی هر دو تاشون از یه نوع بودن یا فرق می کردن؟ اگه با هم دیگه فرق کنن دیگه نمیشه آخرش با یه حرکت تکلیف دسته ها رو روشن کرد... اِنی آیدیا؟
 

niloofar.l

کاربر نیمه‌حرفه‌ای
ارسال‌ها
170
امتیاز
1,313
نام مرکز سمپاد
فرزانگان امین1
شهر
اصفهان
پاسخ : سوالات مرحله 2 - تشریحی

سلام!
سوال 2 دوره هیجدهم قسمت ب، اثباتش رو میدونم اما جواب آخرو نمیدونم درسته یا نه :-" اگه میشه جوابشو بگید دوستان!
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تشریحی

اینم نظر من ، x رو تعداد ai هایی که برابر یک هستند و y رو ai هایی که برابر 2 هستند در نظر میگیریم !
دو معادله زیر را داریم
x+y=(n^2)-1​
x+2y=2n(n-1)​

پس

x=(n^2)-2n+1​
y=2n-2​

هر عدد 2 هم حاصل ما رو 4 تا افزایش میده و هر عدد 1 ، یدونه افزایش میده
پس جواب آخر برابر :
4n^2 - 6n + 2
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تستی

ببین مشکلی نیست #S-:
اگه با اونی که از ببین 18 تا انتخاب کرده بودیم تو یه گروه باشن ، می میره تو گروه 18 امین و اگه تو یه گروه نباشند میره تو اون گروه دیگری #-o
 

Aimoi

کاربر فوق‌فعال
ارسال‌ها
80
امتیاز
609
نام مرکز سمپاد
شهید بهشتی
مدال المپیاد
برای المپیاد کامپیوتر مطالعاتی داشتم.
دانشگاه
دانشگاه تبریز
رشته دانشگاه
مهندسی کامپیوتر
پاسخ : سوالات مرحله 2 - تستی

:-? :-? :-?
خب آقا یه مثال شیک و مجلسی می زنم تا منظورم رو دقیق تر برسونم. اصن فرض کنید بعد از این که 6 تا سه تایی رو بررسی کردیم و ادغامشون کردیم همه شون بیفتن تو یه دسته. حالا 18 تا سکه داریم تو یه دسته و 2 تا سکه هم داریم که تکلیفشون معلوم نیست. خب طبق گفته ی شما این دو تا رو با یه سکه ی دیگه میندازیم تو دستگاه. اگه هر سه تا رو تو یه خروجی بده که کار تمومه اما اگه دو تا رو تو یه خروجی بده، یکی رو تو خروجی دیگه مسئله مشکل دار میشه. قضیه اینه که این دو تا سکه ی باقی مونده می تونن جزو دسته ی مخالف اون 18 تا باشن و سکه ی تویه خروجی دیگه همون متعلق به 18 تایی ها باشه؛ ولی تو حالت دیگه ممکنه یکی از اون دو تا سکه ی باقی مونده جزو دسته ی 18 تایی ها باشه و با اون سکه که از 18 تایی ها برداشتیم تو یه خروجی قرار بگیره و سکه ی دیگه جزو دسته ی مخالفشون باشه. اینجا دیگه نمی تونیم تصمیم بگیریم که دسته ی 2 تایی رو باید کجا بذاریمش. به این نکته هم توجه کنید که سکه ها از لحاظ ظاهری هیچ تفاوتی ندارن و بعد از این رفتن تو دستگاه دیگه نمی تونیم تشخیص بدیم سکه ای که از 18تایی ها برداشتیم کدوم بوده...
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تستی

به این نکته هم توجه کن که سکه ها با شماره های 1 تا 20 نامگذاری شدند :|
وقتی میرن تو دستگاه می تونیم تشخیص بدیم
 
  • لایک
امتیازات: Aimoi

Aimoi

کاربر فوق‌فعال
ارسال‌ها
80
امتیاز
609
نام مرکز سمپاد
شهید بهشتی
مدال المپیاد
برای المپیاد کامپیوتر مطالعاتی داشتم.
دانشگاه
دانشگاه تبریز
رشته دانشگاه
مهندسی کامپیوتر
پاسخ : سوالات مرحله 2 - تستی

به نقل از MeC :
به این نکته هم توجه کن که سکه ها با شماره های 1 تا 20 نامگذاری شدند :|
وقتی میرن تو دستگاه می تونیم تشخیص بدیم
#-o #-o عجب گافی دادم! ممنون از شما دوست عزیز... اگه میشه یه آدم خیری سوال 13 دوره ی بیستم رو حل کنه: من بین گزینه های "الف" و "ه" می مونم... ولی بیشتر به نظر گزینه ی "ه" می رسه. چون از راه حلم مطمئن نیستم نمی نویسمش.
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تستی

خب همون ه میشه دیگه !
با اعداد الف به هدفشون میرسند ، ببین 199 * 7 از 1389 بزرگ تره ، پس میرسن به هدفشون
 

Aimoi

کاربر فوق‌فعال
ارسال‌ها
80
امتیاز
609
نام مرکز سمپاد
شهید بهشتی
مدال المپیاد
برای المپیاد کامپیوتر مطالعاتی داشتم.
دانشگاه
دانشگاه تبریز
رشته دانشگاه
مهندسی کامپیوتر
پاسخ : سوالات مرحله 2 - تستی

چرا 7؟ مگه نباید از طول کل خیابون M-1+L)*n) رو کم کنیم بعدش عدد به دست اومده رو با M مقایسه کنیم؟ مثلن برای این که گزینه ی ب رو رد کنیم می گیم چون 14*99=1386 و 3=1386-1389 و 3 از 12 کمتره می تونن به هدفشون برسن ولی توی الف و ه هر دوشون عددی که از تفاضل به دست میاد بیشتر از M میشه... احتمالا مشکلم تو m-1 باشه ولی به نظرم باید همین باشه چون حداقل حالتی که توش نمیشه یه ماشین رو پارک کرد m-1ه که با L جمع می کنیم تا حداکثر تعداد خونه هایی که به ازای هر ماشین می تونیم اشغال کنیم به دست بیاد...
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تستی

خب می دونی مشکل راه حلت چیه ؟
اینکه فک می کنی همه فاصله ها باید عدد صحیح باشن
تو اون عبارتت منهای 1 لازم نیست ، یه چُسه هم از 6 فاصلشون کمتر باشه ماشین جدید جاش نمیشه ولی تو واسه اینکه ماشین جدید جاش نشه میای فاصله ها رو 5 تایی میزاری ! فهمیدی آیا ؟ :D
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تستی

10. گزینه ه - 36 دقیقه

اگه مجموع فاصله ها رو حساب کنید میبینید که در ایده آل ترین راه هم از 36 کمتر نمیشه (;

اینم راه واسه 36


11. گزینه ج - 6

اگه دقت کنید در مرحله i ام در دست استاد دوم ، دومین کارت از لحاظ کوچک بودن بین 1 تا i-1 است ، پس جواب برابر 6 است :-"

12. گزینه ه
سارق 2 کار زیر رو می تونه انجام بده و گزینه ه بین این دو گزینه ماکسیمم میگیره ، پس درسته :D
1- تابلو i ام رو بدزده و ارزش این تابلو رو با بیشترین حالت تا i-2 تابلو جمع کنه.
2- تابلو i ام رو ندزده و بیشترین حالت تا i-1 تابلو رو به دست بیاره.
 

most wanted

کاربر نیمه‌حرفه‌ای
ارسال‌ها
215
امتیاز
669
نام مرکز سمپاد
علامه حلی2
شهر
تهران
پاسخ : سوالات مرحله 2 - تستی

13)ادعا می کنم اگر :
(n+1)*M + n * L > 1389
در این صورت آنها به هدف خود می رسند چون در واقع n+1جایگاه بین ماشین ها و دیوار ها قرار دارد که همه را حداکثر M (فعلا) قرار می دهیم و این مقدار را با ضرب تعداد ماشین ها در اندازه شان جمع میکنیم اگر این مقدار حتی یکی بزرگ تر از 1389 باشد میتوان اندازه بین ماشین ها را با مقدارهایی (لازم نیست مقدار طبیعی باشند ) قرار داد که ماشینی دیگر قرار نگیرد.
که اگر این مقدار را برای همه گزینه ها بنویسیم گزینه آخر جواب می شود.
14)5
1: 1تا10
2: 11تا20
3: 6تا 10 و 16 تا 20
4: 1تا 5 و 11 تا 15
5: 6 تا 15
با مراحل 1و2و3 5 تای بزرگتر سر جای خود قرار میگیرند. با مراحل 1و2و4 5 تای کوچیکتر سر جای خود قرار گرفته اند و با مرحله آخر 10 تای وسط نیز مرتب میشوند.

16)الگوریتم در واقع عدد را به مبنای دو می برد سپس اگر دو عدد پشت سر هم متفاوت باشند مقدار s یکی اضافه میشود(یکی بیشتر از تعداد گفته شده است چون یک بار هم عدد 0 با بیت اول عدد ما سنجیده میشود که مقدارش یک است).
1010101 و این عدد هم حداکثر مقدار را به ما میدهد چون بیشترین تعداد جفت های متوالی متفاوت را دارد. که این عدد مقدار 7 را می دهد.
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 - تستی

17.گزینه ب - 26
این سوال رو با حالت بندی روی عدد سمت راست دنباله حل می کنیم.
اگه عدد سمت راست یک باشه ، 11 تا به s اضافه میشه
اگه 2 باشه ، 9 تا به s اضافه میشه
اگه 3 باشه ، 6 تا به s اضافه میشه
اگه 4 باشه ، هیچی اضافه نمیشه

پس در مجموع 26 تا به s اضافه میشه
 

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
660
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : سوالات مرحله 2 - تستی

18-هر لامپ را جدا گانه بررسی می کنیم که اگر روشن باشد چه مقدار امتیاز در اعمال فوق دارد و اگر خا موش باشد چقدر.........
سپس به صورت یکتا آن ها را تعیین می کنیم.
1=6::::::::::::خاموش.
2=6::::::::::::روشن.
3=5::::::::::::روشن.
4=4::::::::::::خاموش.
5=4::::::::::::خاموش.
6=4::::::::::::خاموش.
فک کنم بشه 29 تا.
:-?
 

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
660
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : سوالات مرحله 2 - تشریحی

7 لیوان روی میز قرار دارند و همگی وارونه اند در هر حرکت می توانیم هر4 تا از آن ها را که بخواهیم سر و ته کنیم آیا می توانیم به وضعیتی برسیم که تمام لیوان ها رو به بالا قرار گرفته باشند ؟؟؟
;;)

راهنمایی:
از زوجیت تعداد لیوان هایی که وارونه اند به عنوان ناوردا استفاده کنید.
:-"

دانته ×× پست های متوالی ترکیب شدند .
نیما ×× دفه آخرت باشه.
 

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
660
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
سوالات مرحله 3

بعد از مرحله 2 بهتره بریم سراغ کد زدن و حل سوالای متشبه با مرحله 3.........................
یه کتاب هس اسمش مسیله های الگوریتمی اهــ سوالاش مثل سوالای مرحله 3 اهــ.................
بهتره حل سوالای اونو شروع کنیم................
هر کسی هر سوالی رو که حل کرد خواهشا کدش رو هم بزاره.............
اگه سوالارو قبلا حل کردید نیاین بعد از گذاشتن سوال سریع جوابشو بزارید...........
به بقیه هم وقت بدید رو سوال فکر کنن...........
سوال 1:محاسبه ی مقدار تابع
تابع F این ویژگی ها را دارد.
1=(f(1
دنباله ی .....(f(4و(f(3و(f(2و(f(1 دنباله ای صعودی است که عدد n در آن (f(n بار آمده است.
به عنوان مثال چند جمله ی اول این دنباله به صورت زیر است:
....6 6 6 6 5 5 5 4 4 4 3 3 2 2 1
برنامه ای بنویسید که با گرفتن n از صفحه کلید (f(n را چاپ کند.
(سوال کاملا درسته ولی فهمیدنش یکم سخته با دقت بخونید)
با آرزوی موفقیت شما در مرحله 3 .
B-)
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 3

این طوری سوال ها رو بزاری ، بیشتر می فهمن ملت . :D

اینم کد من واسه این سوال

کد:
#include<iostream>
#include<conio.h>
using namespace std;
int main ()
{
	int n;
	cin>>n;
	int a[1000+1];
	for(int i=0;i<1001;i++)
	{
		a[i]=0;
	} 
	a[1]=1;
	a[2]=2;
	a[3]=2;
	int j=4;
	for(int i=3;i<1000;i++)
	{
		for(int z=1;z<=a[i];z++)
		{
			a[j]=i;
			j++;
			if(j==1001)
			{
				cout<<a[n];
				getch();
				return 0;
			}
		}
	}
}
 

kia.celever

کاربر حرفه‌ای
ارسال‌ها
338
امتیاز
1,367
نام مرکز سمپاد
دبیرستان علامه حلی ۳
شهر
تهران
پاسخ : سوالات مرحله 3

این کتاب سوالات برنامه نویسی دوره رو جمع کرده. برای مرحله ۳ بهتر نیست پروجکت اویلر بزنیم؟
+ اینکه کدمونو بذاریم اینجا هم از نظر آموزشی جالب نیست. چون اینطوری یکی که می‌خواد سؤال رو حل کنه یه بار تلاش می‌کنه. بار دوم میاد کد رو می‌خونه و دیگه ارزش سؤال براش از بین می‌ره.
 
وضعیت
موضوع بسته شده است.
بالا