مسابقات برنامه نويسي دانش آموزي ايران (ISPC )

[Olympiad]

سلام و درود .....

مسابقه ي آبان تموم شد ..... از اين به بعد ، بعد از هر مسابقه بياييد اينجا و هر كي اشكال داشت بگه تا اشكالش رفع بشه ...... و در اينجا كدهامون رو به اشتراك بذاريم ( هم در مورد قسمت پيشرفته و هم مقدماتي )

خوب الان ميتونيم در مورد اولين مسابقه كه گذشت بحث كنيم و اشكالاتمون رومطرح كنيم .....

 

[rezashiri]

سلام

من تو قسمت پیشرفته شرکت نکردم(اصلا وقتشو نداشتم روی سوالاتش فکر کنم)

این کد هام برای سوال های مقدماتیاگه مشکلی توی هرکدوم دیدید بگید)

مثل این که سوال سوم رو 800 امتیاز و سوال اول رو 200 امتیاز گرفتم یکی میگه اشتباهم کجا بود؟!؟

سوال اول

سوال دوم

سوال سوم

 

[navidjalalmanesh]

سوال اول رو 200 امتیاز گرفتم یکی میگه اشتباهم کجا بود؟!؟

سوال اول

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

اولا نیازی نبود آرایه کاراکتریتون رو دو بعدی در نظر بگیرید. می تونستید همون 1 بعدی در نظر بگیرید و هر دفعه روی قبلی ها اطلاعات جدید رو بریزید که در حافظه مصرفی به صرفه تر بود .

علت Wrong خوردن کدتون اینه که for یی که متغیر حلقه اش j هستش رو اشتباه نوشته اید . شما نوشتید :

for(int j=0;j<s[j];j++)

خوب , می دونیم s[j] a یا کاراکتر '(' یا ')' هستن که به int می شن 40 یا 41 . پس این for حداکثر تا 41 پیش می ره و بعد از اون رو بررسی نمی کنه و خوب توی ورودی ها ممکنه رشته به طول 50 هم به کدتون داده بشه .

کلا کدتون رو می تونستید با یه for ساده جمع کنید . (فرض کنید s همون string ورودی باشه)

int tc = 0; //tc yani tedad parantez haye baz shode. sharte lazem va kafi baraye 2rost budan javab Ene ke hamishe tc > 0 bashe
for(int i = 0; i < s.size(); i++)
{
    if (s[I] == '(')
	   tc++;
    else tc--;

    if (tc < 0)
    {
	   cout << "FALSE" << endl;
	   goto end;
    }
}
if ( !tc )
cout << "TRUE" << endl;
else cout << "FALSE" << endl;
end: ;

ویرایش : اضافه کردن if به آخر کد!







[/I]

 

[SABB]

سلام

من هر چی میگردم اشکال کد دومم رو نمیتونم پیدا کنم!
میشه یکی لطفا بگه کجا اشتباهه...

کد 1
کد 2
کد 3

 

[Sepehrmousavi]

کلا کدتون رو می تونستید با یه for ساده جمع کنید . (فرض کنید s همون string ورودی باشه)

int tc = 0; //tc yani tedad parantez haye baz shode. sharte lazem va kafi baraye 2rost budan javab Ene ke hamishe tc > 0 bashe
for(int i = 0; i < s.size(); i++)
{
    if (s[I] == '(')
	   tc++;
    else tc--;

    if (tc < 0)
    {
	   cout << "FALSE" << endl;
	   goto end;
    }
}
cout << "TRUE" << endl;
end: ;

[/I]
کد شما هم ناقص است. برای مثال، اگر ورودی یک پرانتز باز باشد آنگاه کد شما True بر می گرداند در حالی که باید False بدهد زیرا عبارت غلط است و پرانتز بسته وجود ندارد! در کل باید در نهایت ، TC مساوی صفر هم باشد تا این مفهوم را برساند که به ازای هر پرانتز باز ، یک پرانتز بسته نیز در عبارت وجود داشته و تعدادشان با هم برابر است!

 

[navidjalalmanesh]

کد شما هم ناقص است. برای مثال، اگر ورودی یک پرانتز باز باشد آنگاه کد شما True بر می گرداند در حالی که باید False بدهد زیرا عبارت غلط است و پرانتز بسته وجود ندارد! در کل باید در نهایت ، TC مساوی صفر هم باشد تا این مفهوم را برساند که به ازای هر پرانتز باز ، یک پرانتز بسته نیز در عبارت وجود داشته و تعدادشان با هم برابر است!

بله , کاملا درسته . خیلی سریع کد رو نوشتم اصلا دقت نکردم. یه if باید به اون قسمت آخر اضافه می کردم.

 

[navidjalalmanesh]

سلام

من هر چی میگردم اشکال کد دومم رو نمیتونم پیدا کنم!
میشه یکی لطفا بگه کجا اشتباهه...

کد 1
کد 2
کد 3

دقت دقت دقت! صورت سوال رو همیشه دقیق بخونید.

ساختار خروجی:

در خط اول درجه‌ی چند جمله‌ای حاصل را بنویسید. در خط بعدی ضرایب چندجمله‌ای حاصل را به ترتیب با شروع از ضریب جمله‌ای که بیشترین توان x را دارد، بنوسید.

 

[SABB]

سلام

من هر چی میگردم اشکال کد دومم رو نمیتونم پیدا کنم!
میشه یکی لطفا بگه کجا اشتباهه...

کد 1
کد 2
کد 3

دقت دقت دقت! صورت سوال رو همیشه دقیق بخونید.

ساختار خروجی:

در خط اول درجه‌ی چند جمله‌ای حاصل را بنویسید. در خط بعدی ضرایب چندجمله‌ای حاصل را به ترتیب با شروع از ضریب جمله‌ای که بیشترین توان x را دارد، بنوسید.

ممنون

 

[Olympiad]

سلام !!!!

سوال 1
سوال 2
سوال 3

 

[Olympiad]

خوب من نظرم اينه كه بريم سراغ سوالات قسمت پيشرفته ....... من كد هيچ كدوم رو ننوشتم !!!!!

اول به نظر من براي اين سوالها الگوريتمتون رو بنويسيد ...

 

[navidjalalmanesh]

سوالات قسمت پیشرفته :

لپ تاپ فروشی : [STRIKE]بدیهی یه که باید n جا لپ تاپ برداریم و n جای دیگه بفروشیم . برای انتخاب آن n شهری که از آن ها لپ تاپ بر می‏داریم اینگونه عمل می کنیم . این 2n عدد رو sort می کنیم و از کم به زیاد پیش می ریم . در هر مرحله , اگه می تونستیم یه شهر رو حذف کنیم (بررسی کنید خودتون ببینید شرط لازم و کافی که بتونیم یه شهر رو حذف کنیم چیه؟) , این کار رو می کنیم تا جایی که n تا شهر حذف شوند[/STRIKE]

برنامه ریزی داینامیک

(

می شه کدمون)

سوال سرمایه زیادی هم با استفاده از یه Segment Tree حل می شه. ایده خاصی نداره , فقط همون پیاده سازی Segment Tree یه کل سوال. زمان اجراش هم با پیاده سازی Segment Tree می شه

.

ویرایش : اصلاح الگوریتم سوال لپ تاپ فروشی.

 

[Olympiad]

سوالات قسمت پیشرفته :

لپ تاپ فروشی : بدیهی یه که باید n جا لپ تاپ برداریم و n جای دیگه بفروشیم . برای انتخاب آن n شهری که از آن ها لپ تاپ بر می‏داریم اینگونه عمل می کنیم . این 2n عدد رو sort می کنیم و از کم به زیاد پیش می ریم . در هر مرحله , اگه می تونستیم یه شهر رو حذف کنیم (بررسی کنید خودتون ببینید شرط لازم و کافی که بتونیم یه شهر رو حذف کنیم چیه؟) , این کار رو می کنیم تا جایی که n تا شهر حذف شوند (

می شه کدمون)

ميشه شرط لازم رو بگيد ؟!؟!؟! اين الگوريتمي كه گفتيد يه جوريه !!!!!!!!!!!!!!!

 

[navidjalalmanesh]

ميشه شرط لازم رو بگيد ؟!؟!؟! اين الگوريتمي كه گفتيد يه جوريه !!!!!!!!!!!!!!!

را برابر ماکسیمم سودی که می توانید تا شهر m ام بدست آوریم به طوری که n لپ تاپ برایمان باقی مانده باشد.

حال داریم

. با پر کردن این جدول , جواب مسئله که

است بدست می آید.

ویرایش : اصلاح الگوریتم سوال لپ تاپ فروشی

 

[zahraS]

ببخشید سوالش چیه که این الگوریتمو دادین؟کجاس؟

 

[navidjalalmanesh]

ببخشید سوالش چیه که این الگوریتمو دادین؟کجاس؟

سوال لپ ‏تاپ فروشی از مسابقه برنامه نویسی دانش آموزی ایران

 

[zahraS]

اینم جواب سوال:

 

[zahraS]

البته من این طور فهمیدم مسیله رو ها نمی دونم درسته یا نه.

به نظرم اگه یکم مسله رو با حال تر می کرد بهتر بود مثلا میگفت این شهرا رو که طرف می گردو بکشین یعنی به تر تیب اقاهه حرکت کنه به شهرا مام ببنیمم تو صفحه بعدم قیمت و مشخصات هر جا که می ره رو بغلش بنازه و کاری که می کنه رو نشون بهت که فروخته یا از انبار برداشته.

یعنی یه برنامه ی حرکتی.

البته این برنامه ی من یکم مشکل داره هر کی گفت مشکلش چیه ؟
ی 2 سه خط ....جا اندختم هر کیتونست بگه؟

 

[navidjalalmanesh]

البته من این طور فهمیدم مسیله رو ها نمی دونم درسته یا نه.

به نظرم اگه یکم مسله رو با حال تر می کرد بهتر بود مثلا میگفت این شهرا رو که طرف می گردو بکشین یعنی به تر تیب اقاهه حرکت کنه به شهرا مام ببنیمم تو صفحه بعدم قیمت و مشخصات هر جا که می ره رو بغلش بنازه و کاری که می کنه رو نشون بهت که فروخته یا از انبار برداشته.

یعنی یه برنامه ی حرکتی.

البته این برنامه ی من یکم مشکل داره هر کی گفت مشکلش چیه ؟
ی 2 سه خط ....جا اندختم هر کیتونست بگه؟

الگوریتمتون رو می تونید یه مختصر به فارسی توضیح بدید؟ کلا چی کار می کنه؟

 

[zahraS]

الگوریتم خواسی نداره

یه جاش مشکل داره حال ندارین بخونینش.؟
خیلی ساده و گوگولی نوشتم که راحت باشین. یه مشکل داره اونم چندتا شرطه که باید تو یه قسمش بیاد.

 

[navidjalalmanesh]

حوصله دانلود نداشتم

. الان دانلود کردم...

کدتون غلطه. شما می یاید از بزرگ به کوچک n تا عدد اول رو انتخاب می کنید و به عنوان جواب چاپ می کنید , در حالی که این کار غلطه . الگوریتمش رو یک بار توضیح دادم , باید این کار رو بکنید :

برنامه ریزی داینامیک :

را برابر ماکسیمم سودی که می توانید تا شهر m ام بدست آوریم به طوری که n لپ تاپ برایمان باقی مانده باشد.

حال داریم

. با پر کردن این جدول , جواب مسئله که

است بدست می آید.

ویرایش : اصلاح الگوریتم