ماراتن ++C

[rezashiri]

سلام!
ببخشید سوال دقیقا چیه؟
من تا جایی که متوجه شدم اینه که یه پرانتزگذاری صحیحه؟!
میشه بگید کدم درسته یا نه؟؟
http://snipt.net/SABB/inoi-practice-2

سوالات تو وبلاگ آقای گوهرشادی هست.

اینم لینک دریافت سوالات : http://turboupload.com/c9c1dfie63da

 

[rezashiri]

سلام!
ببخشید سوال دقیقا چیه؟
من تا جایی که متوجه شدم اینه که یه پرانتزگذاری صحیحه؟!
میشه بگید کدم درسته یا نه؟؟
http://snipt.net/SABB/inoi-practice-2

با این توضیحاتی که آقای گوهرشادی دادن باید درست باشه.

 

[Goharshady]

متاسفانه الآن learn.inoi.ir کار نمی کنه. الآن هم که codechef august cook off داره شروع می شه نمی تونم خودم تستر بنویسم. بعدا برای سوالات تستر می نویسم.

 

[rezashiri]

مرتب سازی ادغامی چیه؟!

 

[SABB]

یک ماتریس n×n از اعداد صحیح داریم. از خانه ی (1,1) شروع می کنیم و در هر مرحله یک خانه به سمت راست یا پایین (در صورت وجود) می رویم تا به خانه ی (n,n) برسیم. ولی می خواهیم مجموع درایه هایی که از روی آن ها عبور می کنیم مینیمم شود. برنامه ای بنویسید که این مقدار مینیمم را حساب کرده و سپس مسیری که شرط مساله را برقرار می کند در خروجی چاپ کند.
مثلا:

:SAMPLE INPUT
5
02 10 31 71 02
05 23 17 49 52
12 91 01 11 04
03 02 08 49 31
31 11 60 71 62

:SAMPLE OUTPUT
156
1 1
2 1
2 2
2 3
3 3
3 4
3 5
4 5
5 5



​

​

 

[rezashiri]

یک ماتریس n×n از اعداد صحیح داریم. از خانه ی (1,1) شروع می کنیم و در هر مرحله یک خانه به سمت راست یا پایین (در صورت وجود) می رویم تا به خانه ی (n,n) برسیم. ولی می خواهیم مجموع درایه هایی که از روی آن ها عبور می کنیم مینیمم شود. برنامه ای بنویسید که این مقدار مینیمم را حساب کرده و سپس مسیری که شرط مساله را برقرار می کند در خروجی چاپ کند.
مثلا:

:SAMPLE INPUT
5
02 10 31 71 02
05 23 17 49 52
12 91 01 11 04
03 02 08 49 31
31 11 60 71 62

:SAMPLE OUTPUT
156
1 1
2 1
2 2
2 3
3 3
3 4
3 5
4 5
5 5



​

​

مسئله های الگوریتمی - سوال 9

 

[SABB]

مرتب سازی ادغامی چیه؟!

http://en.wikipedia.org/wiki/Merge_sort

 

[SABB]

یک ماتریس n×n از اعداد صحیح داریم. از خانه ی (1,1) شروع می کنیم و در هر مرحله یک خانه به سمت راست یا پایین (در صورت وجود) می رویم تا به خانه ی (n,n) برسیم. ولی می خواهیم مجموع درایه هایی که از روی آن ها عبور می کنیم مینیمم شود. برنامه ای بنویسید که این مقدار مینیمم را حساب کرده و سپس مسیری که شرط مساله را برقرار می کند در خروجی چاپ کند.
مثلا:

:SAMPLE INPUT
5
02 10 31 71 02
05 23 17 49 52
12 91 01 11 04
03 02 08 49 31
31 11 60 71 62

:SAMPLE OUTPUT
156
1 1
2 1
2 2
2 3
3 3
3 4
3 5
4 5
5 5



​

​

مسئله های الگوریتمی - سوال 9

قسمت الف

 

[rezashiri]

یک ماتریس n×n از اعداد صحیح داریم. از خانه ی (1,1) شروع می کنیم و در هر مرحله یک خانه به سمت راست یا پایین (در صورت وجود) می رویم تا به خانه ی (n,n) برسیم. ولی می خواهیم مجموع درایه هایی که از روی آن ها عبور می کنیم مینیمم شود. برنامه ای بنویسید که این مقدار مینیمم را حساب کرده و سپس مسیری که شرط مساله را برقرار می کند در خروجی چاپ کند.
مثلا:

:SAMPLE INPUT
5
02 10 31 71 02
05 23 17 49 52
12 91 01 11 04
03 02 08 49 31
31 11 60 71 62

:SAMPLE OUTPUT
156
1 1
2 1
2 2
2 3
3 3
3 4
3 5
4 5
5 5



​

​

مسئله های الگوریتمی - سوال 9

قسمت الف

امشب که حسش نیست(باید 30 تا تست هندسه حل کنم

)

فردا حتما روش فکر می کنم.

 

[rezashiri]

سلام.

تو کدتو با اون رابطه بازگشتی توی کتاب زدی؟!؟

من از اون رابطه سردر نیاوردم؟!؟

 

[SABB]

سلام.

تو کدتو با اون رابطه بازگشتی توی کتاب زدی؟!؟

من از اون رابطه سردر نیاوردم؟!؟

کد همین ماتریسه رو می گی؟؟
پ.ن. الآن که کتابو خوندم تقریبا یه چیزایی استفاده شده بود که منم استفاده کردم. ولی من بازگشتی نرفتم.

 

[rezashiri]

حل نشد.

میشه الگوریتمت رو بگی!

 

[SABB]

یه آرایه کمکی درست کردم. بعد از اندیس n,n شروع کردم و مقدار خونه i,j اون آرایه کمکیه رو برابر با کوتاهترین مسیر مطلوب از i,j به n,n قرار دادم. که مقدار خونه ی i,j بستگی به مقدار خونه های i+1,j و i,j+1 (در صورت وجود) داره که اگه هر کدوم کوچکتر بود باید به مقدار خونه ی i,j اضافه بشه.
آخر سر هم مقدار خونه 0,0 همون مقدار مطلوبمون می شه.
http://snipt.net/SABB/minimum-way-in-matrix/

 

[Goharshady]

مرتب سازی ادغامی چیه؟!

مرتب سازی ادغامی یا merge sort یک مرتب سازی از مرتبه ی nlgn است که از نظر مجانبی بهینه هم هست.
الگوریتمش اینطوریه که برای sort کردن یک آرایه اول آرایه را به دو قسمت تقسیم می کنه بعد این دو قسمت رو به صورت بازگشتی مرتب می کنه و با هم merge می کنه یعنی طوری اعداد این دو قسمت رو قرار می ده که مرتب بشن. مثلا فرض کنید می خواهید آرایه ی زیر را مرتب سازی ادغامی کنید:
۱ ۲ ۳ ۴
اول ۳و۴ را جداگانه و ۲ و ۱ را جداگانه مرتب می کنیم
۲ ۱ ۴ ۳
بعد دو قسمت مرتب شده را داخل هم قرار می دهیم.
۲ ۴ ۱ ۳
۴ ۲ ۱ ۳
۴ ۲ ۳ ۱
۴ ۳ ۲ ۱
همونطور که دیدید این مرتب سازی در زمان nlgn کار می کند مثلا برای n=4 دارای ۶ مرحله است.

 

[Goharshady]

سلام.

تو کدتو با اون رابطه بازگشتی توی کتاب زدی؟!؟

من از اون رابطه سردر نیاوردم؟!؟

کد همین ماتریسه رو می گی؟؟
پ.ن. الآن که کتابو خوندم تقریبا یه چیزایی استفاده شده بود که منم استفاده کردم. ولی من بازگشتی نرفتم.

الگوریتم شما کاملا DYNAMIC است

 

[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

​

 

[SABB]

یه سوال داشتم؛
نمی شه یه vector دوبعدی تعریف کرد و با یه سطرش مثل یدونه vector رفتار کرد؟
آخه من یه vector دوبعدی ساختم و برنامه سر سطری که نوشتم (game[j].push_back(i از برنامه بیرون میپره

 

[Goharshady]

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

 

[SABB]

این کدی بود که نوشتم؛ ولی نتوستم مشکل دیگه ای پیدا کنم!
http://snipt.net/SABB/inoi-1-2nd-round

 

[Olympiad]

ميشه يكم راجع به اشاره گر ها توضيح بدي ؟؟؟؟؟