ماراتن ++C

[SABB]

من یه cout قبل و بعد push_back ئه گذاشتم معلوم شد سر همون سطر می پره بیرون!!
الگوریتمم اینطوریه:
به هر عدد باینریش رو نسبت می دیم و اگه باینریش تو مرتبه j ام برابر 1 بود اون عدد رو تو گروه j ام به کاربر نشون می دیم. بعد هم Y های کاربر و N هاشو با 0 و 1 متناظر می کنیم و اون عدد باینریه رو به دهدهی تبدیل می کنیم که همون عدد مورد نظر کاربر میشه.
درسته؟!!

 

[Goharshady]

من یه cout قبل و بعد push_back ئه گذاشتم معلوم شد سر همون سطر می پره بیرون!!
الگوریتمم اینطوریه:
به هر عدد باینریش رو نسبت می دیم و اگه باینریش تو مرتبه j ام برابر 1 بود اون عدد رو تو گروه j ام به کاربر نشون می دیم. بعد هم Y های کاربر و N هاشو با 0 و 1 متناظر می کنیم و اون عدد باینریه رو به دهدهی تبدیل می کنیم که همون عدد مورد نظر کاربر میشه.
درسته؟!!

احتمالا مشکل از push_back کردن زیاد است. vector محدودیت سایز دارد زیرا هیچ یک از تابعهای برنامه نمی تواند بیشتر از 16 مگابایت حافظه بگیرد. باید سعی کنید global بگیرید.<IMG src=modules/forums/images/smiles/53.gif>

</IMG src=modules/forums/images/smiles/53.gif>

 

[SABB]

من یه cout قبل و بعد push_back ئه گذاشتم معلوم شد سر همون سطر می پره بیرون!!
الگوریتمم اینطوریه:
به هر عدد باینریش رو نسبت می دیم و اگه باینریش تو مرتبه j ام برابر 1 بود اون عدد رو تو گروه j ام به کاربر نشون می دیم. بعد هم Y های کاربر و N هاشو با 0 و 1 متناظر می کنیم و اون عدد باینریه رو به دهدهی تبدیل می کنیم که همون عدد مورد نظر کاربر میشه.
درسته؟!!

احتمالا مشکل از push_back کردن زیاد است. vector محدودیت سایز دارد زیرا هیچ یک از تابعهای برنامه نمی تواند بیشتر از 16 مگابایت حافظه بگیرد. باید سعی کنید global بگیرید.<IMG src=modules/forums/images/smiles/53.gif>

</IMG src=modules/forums/images/smiles/53.gif>

یه متغیر هم برای شمارش تعداد push_back ها تعریف کردم. سر push_back اولی میپره بیرون

 

[Goharshady]

++g و gdb نصب کنید و ببینید مشکلش چیه!
http://www.horstmann.com/ccc/help/cygwin/install.html
http://hamsterrepublic.com/ohrrpgce/index.php/GDB_on_Windows.html

 

[rezashiri]

این سوال که ...

فعلا من سوال بعدی رو می ذارم!!؟

این چهار تا چون آسونن یک سوال محسوب می شن:

A

B

C

D


اینم کد های من:

http://snipt.net/rezashiri/ispc-1387-problemset-a

http://snipt.net/rezashiri/ispc-1387-problemset-b

http://snipt.net/rezashiri/ispc-1387-problemset-c

http://snipt.net/rezashiri/ispc-1387-problemset-d

 

[SABB]

برنامه ای برای یک بازی بین کامپیوتر و کاربر با شرایط زیر بنویسید:
ابتدا کاربر یک عدد طبیعی یک رقمی، n، به ماشین می دهد. سپس ماشین از کاربر میخواهد که یک عدد صحیح نامنفی کوچکتر از 2[SUP]n[/SUP] انتخاب کند و بعد با n سوال عدد مورد نظر کاربر را پیدا کند. هر سوال 2[SUP]n-1[/SUP] عدد روی صفحه نمایش می دهد و کاربر باید در صورت وجود عدد مورد نظرش در بین آن ها پاسخ Y و درغیر اینصورت پاسخ N دهد.
مثال: اگر n=3 و پاسخ های کاربر به صورت زیر باشد آنگاه عدد موردنظر کاربر 5 خواهد بود.
(مرحله دوم اولین المپیاد کامپیوتر ایران)

1 3 5 7 Y
2 3 6 7 N
4 5 6 7 Y

​

بالاخره درست شد!

مشکل از همون push_back بود، چون وقتی اون vector رو آرایه کردم درست شد.

http://snipt.net/SABB/inoi-1-2nd-round

 

[Olympiad]

يه سوال آسون بذاريد يكم روحيه بگيريم !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

[rezashiri]

یعنی اون سوالاتی که من گذاشتم سختن!؟!؟

 

[Olympiad]

یعنی اون سوالاتی که من گذاشتم سختن!؟!؟

نه اونا كه گلابي بودن !!!!!!
منظورم اينه يه سوال ديگه بذاريد.....

 

[rezashiri]

این سوال بدی نیست:

http://www.20upload.com/files/download/12826692921.pdf

 

[Goharshady]

این سوال بدی نیست:

http://www.20upload.com/files/download/12826692921.pdf

برای آشنایی با Dynamic Programming خیلی هم عالیه

 

[rezashiri]

کسی نظری نداره؟!

آقای گوهرشادی این کد من درسته؟!

http://snipt.net/rezashiri/ispc-1387-problemset-j

 

[Goharshady]

من که از این چیزی نفهمیدم. لطفا الگوریتمتان را بگویید

 

[rezashiri]

من که از این چیزی نفهمیدم. لطفا الگوریتمتان را بگویید

از طبقه ی H شروع می کنه یکی یکی میاد پایین اگه k از H کمتر یا مساوی بود آجر های طبقه ی H رو به طبقه ی H-K منتقل می کنه.

بعدشم چون آجر ها تو K طبقه اول جمع می شن میاد بزرگترینشون رو تو خروجی چاپ می کنه.

اگه بد توضیح دادم ببخشید چون کدشو چند روز پیش زدم.

 

[Goharshady]

من که از این چیزی نفهمیدم. لطفا الگوریتمتان را بگویید

از طبقه ی H شروع می کنه یکی یکی میاد پایین اگه k از H کمتر یا مساوی بود آجر های طبقه ی H رو به طبقه ی H-K منتقل می کنه.

بعدشم چون آجر ها تو K طبقه اول جمع می شن میاد بزرگترینشون رو تو خروجی چاپ می کنه.

اگه بد توضیح دادم ببخشید چون کدشو چند روز پیش زدم.

این شدیدا greedy هست. مطمئنید درسته؟ اثباتی برای درستی اش دارید؟ به نظر من می شه greedy حلش کرد ولی نه دیگه اینقدر greedy!!

 

[rezashiri]

من که از این چیزی نفهمیدم. لطفا الگوریتمتان را بگویید

از طبقه ی H شروع می کنه یکی یکی میاد پایین اگه k از H کمتر یا مساوی بود آجر های طبقه ی H رو به طبقه ی H-K منتقل می کنه.

بعدشم چون آجر ها تو K طبقه اول جمع می شن میاد بزرگترینشون رو تو خروجی چاپ می کنه.

اگه بد توضیح دادم ببخشید چون کدشو چند روز پیش زدم.

این شدیدا greedy هست. مطمئنید درسته؟ اثباتی برای درستی اش دارید؟ به نظر من می شه greedy حلش کرد ولی نه دیگه اینقدر greedy!!

مگه سوال همینو نگفته؟

کدوم قسمتش حریصانه است؟

 

[Goharshady]

در این مثال فرض کنید k=2

طبقه تعداد آجر
5 1
4 1
3 400
2 1
1 0
الآن از طبقه ی 5 یکی به 3 می دهد و کار 3 برابر با 401 می شود و کار کل هم همین 401 است
اما اگر 5 به 4 و 4 به 2 بدهد دیگر چنین مشکلی نداریم و کار کل 400 می شود

 

[rezashiri]

در این مثال فرض کنید k=2

طبقه تعداد آجر
5 1
4 1
3 400
2 1
1 0
الآن از طبقه ی 5 یکی به 3 می دهد و کار 3 برابر با 401 می شود و کار کل هم همین 401 است
اما اگر 5 به 4 و 4 به 2 بدهد دیگر چنین مشکلی نداریم و کار کل 400 می شود

من اصلا متوجه حداکثر K طبقه پایین تر نشده بودم.

 

[SABB]

اینقدر greedy خوبه؟:
اول مقدار همه ی طبقه ها از 1 تا k را برابر تعداد آجر های آن قرار می دهیم، بعد مقدار طبقه k+1 را بعلاوه ی مینیمم k تای پایینیش می کنیم، k+2 رو هم همینطور و...

البته باز مینیمم رو بدست نمی آریم...

 

[Goharshady]

فرض کنید می خواهیم از طبقه ی H تعدادی آجر را انتقال بدهیم. هر آجر را به یکی از k طبقه ی زیری که min تعداد آجر را دارد انتقال می دهیم. ــ توجه کنید که min بعد از انتقال آجرها update می شود ــ
حالا ثابت کنید این کار درسته. ــ اثباتش خیلی راحته ــ