مسابقات ACM

[sin2x=2sinxcosx]

سلام بر همه .
نمی دونم کدوم یکی از شما ها تا حالا به این مسابقات رفتین و نمی دونم چند نفرتون با سایت acm.sharif.edu آشنا هستین . این یه سایت هست که برای مسابقات اینترنتی ACM طراحی شده و این مسابقات تو این پورتال برگزار می شن . بعد از اینکه تو این سایت ثبت نام کردین وارد سایت می شین . یه قسمت هست به نام "محیط" که اگه وارد اون بشین تعدادی محیط مسابقه مشاهده می کنین که همه شون زمانش به اتمام رسیده به جز یکی که اون باز هست . اسم محیط ACM_Training هستش . که تقریبا اکثر سوال های این سری مسابقات تو این محیط هست . وقتی وارد این محیط شدین میرین سراغ فهرست مسئله ها ، یه مسئله رو انتخاب می کنین ، روی مسئله رو می خونین ، جوابشو به زبان ++C یا Java می نویسین و ارسال می کنین . موقع ارسال نام مسئله رو مشخص می کنین و فایل رو از هاردتون Browse می کنین و کامپایلر رو انتخاب می کنین که برای سی پلاس پلاسی ها ، ++g و برای جاوا ای ها sun jdk هست . بعد برنامه تونو ارسال می کنین . چندین حالت ممکنه رخ بده .
خوش بینانه ترین حالت : صحیح
برنامه شما تمامی test case های خفن اونا رو با موفقیت و بدون باگ گذرونده و جواب شما درسته .
نادرست
جواب شما به ازای یکی یا تمامی test case ها جواب نادرست میده و یا شکل خروجی شما ایده آل آن ها نیست و ...
خطای زمان اجرا
همون Run_Time Error خودمون
حطای زمان کامپایل
همون Compilation Error
زمان غیرمجاز
زمانی که برنامه شما صرف یافتن جواب مسئله می کند از حد مجاز بیشتر است . باید برنامه سریع تر بشه .

حالا که چی ؟
هیچی اینا رو گذاشتم تا کسایی که علاقه مند به برنامه نویسی هست و می خوان خودشونو به قول بعضی ها Challenge کنن می تونن برن و مسئله های ریز و درشت این سایت رو حل کنن و اگه accept گرفتن ، جواب مسئله رو به همراه نام مسئله تو این سایت بذارن تا بقیه هم استفاده کنن .

[ali zi zeperto]

علاقمندان مسابقات می تونن تو این گروه (acm-icpc-tehran ) توی گوگل عضو بشن و مباحث رو درباره مسابقات دنبال کنن.

[sin2x=2sinxcosx]

راستی دوستان یه توضیح برای اونایی که می خوان تو این سایت فعالیت کنن .
برنامه هاتون باید حتما کنسولی باشه و با int main شروع بشه و آخرش هم return 0 داشته باشه . با کامپایلرهای جدید که اون h. رو برداشتن استفاده کنین. هر خروجی که تو روی سوال گفته شده دقیقا چاپ کنین . حتی یه نقطه رو هم جا نذارین .
امسال تو مسابقات منطقه ای تو دانشگاه شریف ، تیم تایوان تو 3ساعت تونست هر 10 سوال رو حل کنه و دو تیم دانشگاه شریف هم تو 4 ساعت هر 10 تا رو حل کردن . کارشون خیلی درسته . تو بهمن ماه مسابقات جهانی تو چین برگذار میشه .

[sin2x=2sinxcosx]

سلام دوستان . تصمیم گرفتم روی ترجمه شده سوال های ACM رو تو این تاپیک بذارم و با هم حل کنیم .
مثلا یه سوال رو می ذاریم و اسم مسئله رو هم می گیم. دوستان بنویسن و تو acm.sharif.edu بذارن . اگه accept گرفتن جواب مسئله رو همین جا هم بذارن تا بقیه هم استفاده کنن . بعضی حالت ها هم هست که شما برنامه رو تو کامپیوتر خودتون کامپایل می کنین و به ازای تمامی test case ها جواب درست رو می گیرین ولی از acm.sharif.edu پاسخ نادرست می گیرین . این برنامه ها رو هم این جا بذارین تا ببینیم مشکلشون چی هست .
از پست بعدی من شروع می کنم .

[sin2x=2sinxcosx]

مسئله StringLD ( که LD مخفف Left Delete هست)
تابع stringld یه تابعی هست که یک رشته رو می گیره و سمت چپ ترین کاراکترشو حذف می کنه .
مثلا "acm" میشه "cm" .
به شما لیستی از کلمه های مجزا داده میشه و در هر مرحله ما تابع stringld رو روی این کلمه اعمال می کنیم . وظیفه ما اینه که برنامه ای بنویسیم که تعداد مراحلی که لازم است طی بشه (توسط تابع Stringld ) تا حداقل یکی از وضعیت های زیر صادق بشه :
1- یکی از کلمات empty بشه . یعنی "" بشه
2- دو کلمه یکسان حاصل بشه .
مثلا کلمات aab ، abac و caac رو داریم . برای اولین بار تابع رو روی هر کدوم اعمال می کنیم . نتیجه میشه :
bac - ab - aac
می بینیم که هیچ کدوم از شرط های فوق صادق نشدن . پس برای دومین بار تابع رو اعمال می کنیم :
ac - b - ac
می بینیم که کلمه ac دو تا شد . پس شرط 2 صادقه . بنابراین برنامه ما 1 رو به عنوان نتیجه چاپ می کنه . حالا چرا 1 و 2 نه ؟ دلیلش اینه که ما مرحله آخر رو که باعث میشه یکی از شرط ها true بشه لحاظ نمی کنیم .

ورودی برنامه :
اولین خط از ورودی شامل یک عدد n است که بین 1 تا 100 هست . (خود 1 و 100 هم هستن ) بعد از این خط ، n تا کلمه باید وارد بشه . ورودی تا زمانی ادامه داره که به جای n صفر وارد بشه .

خروجی برنامه :
بیشترین تعداد فراخوانی تابع stringld رو چاپ می کنیم . طبق شرایطی که قبلا گفته شد .

مثلا فرض کنین ورودی به شکل زیر هست :
4
aaba
aaca
baabcd
dcba
3
aaa
bbbb
ccccc
0

خروجی باید این طوری باشه :
1
2

مسئله به نسبت راحتیه برای شروع کار ...

[hoax3r]

این خطای زمان اجرا رو چطوری باید رفع کرد، من الان برای مساله faverage هر کاری می کنم میگه خطای زمان اجرا داری
ولی تو کامپیوتر خودم درسته، یعنی به نظر درست میاد. نمیدونم چه تستی روش انجام میشه این ایرادو میگیره
این کدی گه نوشتم، البته یکم قرقاطیه :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

راستی این مساله جدید که ترجمه کردی هم بریم روش کار کنیم بنظر جالب میاد.

[sin2x=2sinxcosx]

من اینو نوشتم و accept گرفتم :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[sin2x=2sinxcosx]

این خطای زمان اجرا رو چطوری باید رفع کرد، من الان برای مساله faverage هر کاری می کنم میگه خطای زمان اجرا داری
ولی تو کامپیوتر خودم درسته، یعنی به نظر درست میاد. نمیدونم چه تستی روش انجام میشه این ایرادو میگیره
این کدی گه نوشتم، البته یکم قرقاطیه :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

راستی این مساله جدید که ترجمه کردی هم بریم روش کار کنیم بنظر جالب میاد.

راستی یه چیزی در مورد برنامه شما بگم . اصلا در مورد نوع ورودی نگران نباشین . لازم نیست که تست کنین که آیا عدد وارد شده در range مورد نظر هست یا نه . اون میگه به ازای standard input شما خروجی استاندارد رو چاپ کنین . نه هر ورودی . برای همین لازم نیست ورودی رو رشته بگیرین . کاربر خودش اعداد رو با فاصله وارد می کنه . مثلا اگه گفته 5 عدد با فاصله وارد می کنیم شما کافیه دستور زیر رو بنویسین :
cin >> a >> b >> c >> d >> e

[sin2x=2sinxcosx]

روی این مسئله faverage رو هم من می ذارم :
n عدد صحیح گرفته میشه
میانگین آن ها محاسبه می شه و تو A1 قرار داده میشه
اون عدد هایی که کمتر از این A1 هستند دور انداخته میشه
بعد میانگین اعداد باقیمانده محاسبه میشه و تو A2 ذخیره میشه
اونایی که بزرگتر از این A2 هستن دور انداخته میشن
بعد میانگین این اعداد باقیمانده محاسبه میشه و تو A3 ذخیره میشه و .......... همین جوری می ره تا وقتی که جواب این میانگین بالاخره به عدد ثابتی برسه . یعنی با دور انداختن اعداد کوچکتر و بزرگتر از میانگین عدد میانگین تغییر نکنه .

ورودی :
یک عدد صحیح N میاد که نشان دهنده تعداد test case ها هست . هر test case شامل دو خط ورودی است که خط اول عددی بین 1 تا 30000 است که تعداد اعدادی که می خوایم میانگینشونو محاسبه کنیم نشون می ده . بعد تو خط دوم هم این اعداد میان با یک فاصله بین هر کدوم که هر عدد بین 30000- و 30000 است .

خروجی :
برای هر خط خروجی نتیجه رو چاپ میکنین که قبلش این عبارت ":case #i" میاد و بعد هم نتیجه مورد نظر که تا 3 رقم اعشار دقت داره .

مثلا این ورودی هامون هستن :

4
3
3 2 1
1
7
9
9 8 6 7 5 4 3 2 1
4
2 2 2 1

این هم خروجی :

Case #1: 2.000
Case #2: 7.000
Case #3: 6.000
Case #4: 2.000

[hoax3r]

کد جالبی بود اینجور که شما انجام دادی پس لزومی نداره حتما ما تمام ورودی رو بگیریم و نتیجه تمام ورودی ها رو به خروجی ببریم،
بعد از هر ورودی میتونیم نتیجه رو چاپ کنیم. درسته؟
باز برم رو کد خودم یکم کار کنم ببینم بهتر در میاد

ممنون بابت توضیحات