Yousefi

Well-Known Member
ارسال ها
432
لایک ها
602
امتیاز
93
#21
پاسخ : ماراتن برنامه نویسی 92

کسی نبود، 6 رو حل کنه؟
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#22
پاسخ : ماراتن برنامه نویسی 92

محدودیت زمانی: 2 ثانیه، محدودیت حافظه: 256 مگابایت



سوال 6 - شهرهای بژستان


بژستان n شهر دارد، که با 1 تا n نام گذاری شده.بعضی از این شهر ها با یک جاده به هم متصل هستند به طوری که از هر شهر می توان سفر کرد و به شهر دیگر رسید. به جاده ای که با تخریب آن، دو شهر مثل A و B وجود داشته باشند که دیگر نتوان از شهر A به شهر B رفت، جاده ی مهم می گوییم، هدف شما این است که بگویید، شهر داده شده، چند جاده ی مهم دارد؟

نوع ورودی

ورودی در n خط است، در هر خط n عدد بولیین وجود دارد. به طوری که عدد i-اُم از خط j-اُم، نشان دهنده ی متصل بودنِ دو شهر i و jاست، اگر 1 بود یعنی آن دو شهر به هم متصل اند و در غیر این صورت، متصل نیستند. (n < 10[SUP]2[/SUP])


نوع خروجی

تنها یک عدد صحیح، که نشان دهنده ی تعداد جاده های مهم است.

مثال

کد
0 1 0
1 0 1
0 1 0
کد
2
[HR][/HR]
کد
[LEFT]
0 1 1
1 0 1
1 1 0[/LEFT]
کد
0
توضیحات

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

در مورد اولین تست : شهر 1 به 2 وصله و شهر 2 به 3، هر کدوم از این جاده ها رو حذف کنیم دیگه نمیشه از شهر 1 به شهر 3 رفت.
و دومین تست کیس هم : همه ی شهر ها به هم وصل ان و اگه هر کدوم رو حذف کنیم، هیچ اتفاقی نمی افته!
منظور سوال پیدا کردن یال برشی در گراف همبند هستش که چون تعداد راسها کمه راحت می شه از dfs استفاده کرد(البته این بهینه نیست) برای مطالعه بیشتر برید اینجا

---- دو نوشته به هم متصل شده است ----




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

الف ) تعداد n عدد داریم و می خوایم حداکثر تعداد جفت هایی از اونارو پیدا کنیم که حداکثر اختلافشون t باشه. (
)

کد
input :
10 3
1 6 2 2 7 11 32 12 18 20 

output:
4
=============

ب) برنامه ای بنویسید که مجموعه ای از زمان ها رو بگیره و مرتبشون کنه (زمان ها برحسب ساعت ، دقیقه و ثانیه هستن)

کد
input :
6
11 11 11
11 12 11
12 11 11
11 11 12
11 12 10
11 10 12

output:
11 10 12
11 11 11
11 11 12
11 12 10
11 12 11
12 11 11
 

Yousefi

Well-Known Member
ارسال ها
432
لایک ها
602
امتیاز
93
#23
پاسخ : ماراتن برنامه نویسی 92

منظور سوال پیدا کردن یال برشی در گراف همبند هستش که چون تعداد راسها کمه راحت می شه از dfs استفاده کرد(البته این بهینه نیست) برای مطالعه بیشتر برید اینجا

---- دو نوشته به هم متصل شده است ----




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

الف ) تعداد n عدد داریم و می خوایم حداکثر تعداد جفت هایی از اونارو پیدا کنیم که حداکثر اختلافشون t باشه. (
)

کد
input :
10 3
1 6 2 2 7 11 32 12 18 20 

output:
4
=============

ب) برنامه ای بنویسید که مجموعه ای از زمان ها رو بگیره و مرتبشون کنه (زمان ها برحسب ساعت ، دقیقه و ثانیه هستن)

کد
input :
6
11 11 11
11 12 11
12 11 11
11 11 12
11 12 10
11 10 12

output:
11 10 12
11 11 11
11 11 12
11 12 10
11 12 11
12 11 11

دومی : Ubuntu Pastebin
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#24
پاسخ : ماراتن برنامه نویسی 92

[TABLE="width: 100%"]
[TR]
[TD] 1. Accepted
2. Accepted
3. Accepted
4. Accepted
5. Accepted
6. Accepted
7. Accepted
8. Accepted
9. Accepted
10. Accepted
11. Accepted
12. Accepted
13. Accepted
14. Accepted
15. Accepted
16. Accepted
17. Accepted
18. Accepted
19. Accepted
20. Accepted
21. Accepted
22. Accepted
23. Accepted
24. Accepted
25. Accepted
26. Accepted
27. Accepted
28. Accepted
29. Accepted
30. Accepted
31. Accepted
32. Accepted
33. Accepted
34. Accepted
35. Accepted
36. Accepted
37. Accepted
38. Accepted
39. Accepted
40. Accepted
41. Accepted
42. Accepted
43. Accepted
44. Accepted
45. Accepted
46. Accepted
47. Accepted
48. Accepted
49. Accepted
50. Accepted
51. Accepted [/TD]
[/TR]
[/TABLE]


Accepted ! :D اینم کد من !
 

Yousefi

Well-Known Member
ارسال ها
432
لایک ها
602
امتیاز
93
#25
پاسخ : ماراتن برنامه نویسی 92

[table="width: 100%"]
[tr]
[td] 1. Accepted
2. Accepted
3. Accepted
4. Accepted
5. Accepted
6. Accepted
7. Accepted
8. Accepted
9. Accepted
10. Accepted
11. Accepted
12. Accepted
13. Accepted
14. Accepted
15. Accepted
16. Accepted
17. Accepted
18. Accepted
19. Accepted
20. Accepted
21. Accepted
22. Accepted
23. Accepted
24. Accepted
25. Accepted
26. Accepted
27. Accepted
28. Accepted
29. Accepted
30. Accepted
31. Accepted
32. Accepted
33. Accepted
34. Accepted
35. Accepted
36. Accepted
37. Accepted
38. Accepted
39. Accepted
40. Accepted
41. Accepted
42. Accepted
43. Accepted
44. Accepted
45. Accepted
46. Accepted
47. Accepted
48. Accepted
49. Accepted
50. Accepted
51. Accepted[/td]
[/tr]
[/table]


accepted ! :d اینم کد من !
51 یی تست کیس داشتییید؟ :دی

کدامون چقدر شبیهن!

Ps: جاج خاصی استفاده می کنید؟
 
آخرین ویرایش توسط مدیر

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#26
پاسخ : ماراتن برنامه نویسی 92

51 یی تست کیس داشتییید؟ :دی

کدامون چقدر شبیهن!
من نداشتم ... سایته داشت ! :p ...

بهله ! :d

ماله یه سایت بود ... جاجم میشه راحت نوشت ... حوصله ندارم! :D
 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#27
پاسخ : ماراتن برنامه نویسی 92

سلام
گفتم این تاپیکو دوباره راه بندازم تا با هم برنامه نویسی کنیم
یه مسئله هست که میگه:
از 1 تا 10000000 چند عدد بالای 100 مقسوم علیه دارن؟
من یه برنامه براش نوشتم ولی فک کنم 3 و4 ساعتی طول بکشه تموم بشه:
 

kagali

New Member
ارسال ها
88
لایک ها
11
امتیاز
0
#28
پاسخ : ماراتن برنامه نویسی 92

سلام
گفتم این تاپیکو دوباره راه بندازم تا با هم برنامه نویسی کنیم
یه مسئله هست که میگه:
از 1 تا 10000000 چند عدد بالای 100 مقسوم علیه دارن؟
من یه برنامه براش نوشتم ولی فک کنم 3 و4 ساعتی طول بکشه تموم بشه:
آره منم موافقم حداقل روزی دو یا سه تا سوال برنامه نویسی حل کنیم:153:
 

Yousefi

Well-Known Member
ارسال ها
432
لایک ها
602
امتیاز
93
#29
پاسخ : ماراتن برنامه نویسی 92

سلام
گفتم این تاپیکو دوباره راه بندازم تا با هم برنامه نویسی کنیم
یه مسئله هست که میگه:
از 1 تا 10000000 چند عدد بالای 100 مقسوم علیه دارن؟
من یه برنامه براش نوشتم ولی فک کنم 3 و4 ساعتی طول بکشه تموم بشه:
.
.
.
69782
Execution Time: 70.730
[CPP] Number of divisors - Posted by Yousefi - iPASTE.org - Code Paste Snippet and Code Store.
 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#30
پاسخ : ماراتن برنامه نویسی 92

صفحتون برای من بالا نمیاد
 

Yousefi

Well-Known Member
ارسال ها
432
لایک ها
602
امتیاز
93
#33
پاسخ : ماراتن برنامه نویسی 92

چند تا سوال داشتم:
1-چقدر طول میکشه برنامه اجرا بشه؟ تو کامپیوتر من، ۷۰ ثانیه.
2-این قسمت رو میشه توضیح بدین:

if (!(n % i)) answer += 1 + (i * i != n);
اگر x مقسوم‌علیه n باشه، n / x هم مقسوم‌علیه n هستش، پس کافیه تا رادیکال n بریم و اگه n بر i بخش‌پذیر بود، ۲ تا به تعداد مقسوم‌علیه‌ها اضافه کنیم، اما این یه مشکلی داره، مثلا در مورد مربع‌ها مثل ۳۶، وقتی می‌بینیم ۳۶ بر ۶ بخش‌پذیره نباید ۲ تا اضافه کنیم. (i * i != n) وقتی i دقیقا رادیکال n هستش مقدار صفر می‌گیره و در غیر این صورت یک.

3-clock نقشش چیه؟ برای این‌که ببینیم چه‌قدر طول کشیده تا برنامه جواب بده استفاده می‌شه، اول برنامه یه بار تایم رو توی یه متغیری ذخیره می کنیم در آخر هم تایم کنونی رو از تایم اول برنامه کم می‌کنیم و تقسیم بر CLOCKS_PER_SEC می‌کنیم، تا به ثانیه تبدیل شه.
^ جوابا قرمز بالا ^
 

joomine.com

New Member
ارسال ها
112
لایک ها
70
امتیاز
0
#34
پاسخ : ماراتن برنامه نویسی 92

دوستان کسی میتونه برای این سوال آخر یه الگوریتم بهتر ارایه بده؟؟
الان این خیلی افتضاحه از نظر زمان اجرا.
سوال اینه که اولین عددی که بیشتر از 500 مقسوم علیه دارد رو پیدا کنید.(یکی از سوالای پراجکت اویلر بوده)
چون با این ایده ی بالا نمیشه جواب گرفت..
یا کسی اگه ایده ی بهتر و متفاوت تری داره یه راهنمایی بکنه.
با تشکر از همه
 

peymans

New Member
ارسال ها
3
لایک ها
0
امتیاز
0
#35
پاسخ : ماراتن برنامه نویسی 92

با سلام خدمت دوست خوبم
مطالب بسیار خوب و مفیدی بود
سپاسگزارم
موفق،پیروز و سربلند باشید
www.gowebsite.ir
 
بالا