ماراتن CPP
[center:6776b22fc8]
J
J
Code in snipt
[/center:6776b22fc8]
کد
#include <iostream>
using namespace std;
int main()
{
unsigned long long a[300][300];
a[0][0]=1;
for(unsigned long long i=1;i<100;i++)
{
a[i][i]=1;
a[i][0]=1;
}
for(unsigned long long i=1;i<100;i++)
for(unsigned long long j=1;j<i&&i!=j;j++)
a[i][j]=a[i-1][j]+a[i-1][j-1];
unsigned long long n;
cin>>n;
cout<<a[(2*n)][n]/(n+1)<<" "<<n+1;
return 0;
}
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:b3d9e6a878]K[/center:b3d9e6a878]
http://www.codechef.com/problems/MARBLES
ترجمه:
یه یارویی خواب می بینه رفته فروشگاه که قاقالیلی بخره. بعد k جور قاقالیلی مختلف وجود داره و از هرکدوم بی نهایت تا در دسترسه. اون می خواد n تا قاقالیلی بخره! به چند طریق می تونه این کارو بکنه به شرطی که از هر نوع حداقل یکی بخره؟
ورودی:
اول ورودی تعداد تست ها نوشته می شه. بعد در هر خط یک تست می آید که به ترتیب n و k رو نوشته
خروجی:
برای هر خط ورودی تعداد راهها را بنویسید
مثال:
ورودی:
2
10 10
7 30
خروجی:
1
475020
محدودیتها:
تعداد تستها حداکثر ۱۰۰ تاست و n و k بین ۱ تا ۱۰ به توان ۶ هستن
زمان : ۱ ثانیه
حداکثر سایز کد: ۱۰ کیلوبایت
تضمین شده که جواب نهایی در int64 یا همون long long خودمون جا می شه
http://www.codechef.com/problems/MARBLES
ترجمه:
یه یارویی خواب می بینه رفته فروشگاه که قاقالیلی بخره. بعد k جور قاقالیلی مختلف وجود داره و از هرکدوم بی نهایت تا در دسترسه. اون می خواد n تا قاقالیلی بخره! به چند طریق می تونه این کارو بکنه به شرطی که از هر نوع حداقل یکی بخره؟
ورودی:
اول ورودی تعداد تست ها نوشته می شه. بعد در هر خط یک تست می آید که به ترتیب n و k رو نوشته
خروجی:
برای هر خط ورودی تعداد راهها را بنویسید
مثال:
ورودی:
2
10 10
7 30
خروجی:
1
475020
محدودیتها:
تعداد تستها حداکثر ۱۰۰ تاست و n و k بین ۱ تا ۱۰ به توان ۶ هستن
زمان : ۱ ثانیه
حداکثر سایز کد: ۱۰ کیلوبایت
تضمین شده که جواب نهایی در int64 یا همون long long خودمون جا می شه
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
rezashiri گفت
[center:81479a5044]
K
[/center:81479a5044]تعداد حالت ها
می شه؟!؟
راستی خطای Runtime چی بود؟!؟
K
راستی خطای Runtime چی بود؟!؟
SIGSEGV:http://en.wikipedia.org/wiki/SIGSEGV
NZEC(وقتی برنامه صفر بر نمی گرداند)
SIGABRT:http://en.wikipedia.org/wiki/SIGABRT
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:92a54396a9]K[/center:92a54396a9]
این کد منه که با یه ایده ی جالب تونستم acc کنم:
http://social.msdn.microsoft.com/Fo...x/thread/75caf31d-7f39-41ea-9a9a-224096fdc3f8
این کد منه که با یه ایده ی جالب تونستم acc کنم:
http://social.msdn.microsoft.com/Fo...x/thread/75caf31d-7f39-41ea-9a9a-224096fdc3f8
راستی اون جوابی که توی قسمت نظرات http://www.codechef.com/problems/MARBLES گذاشتید public نیست...!؟
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
تو این سوال مشکل اساسی ما overflow شدن int64 هاست که برای محاسبه ی !n اتفاق می افته. کاری که همه ــ همه غیر از من ــ کردند استفاده از bignum و نوشتن تقسیم bignum بود که خودش کار خیلی سختیه. به همین دلیل time برنامه واقعا زیاده. پس ما وقت زیاد داریم و اصلا مهم نیست اگر راه حلمون O(n[SUP]2[/SUP]) باشه. خیلی راحت ۲ تا vector می گیریم. برای محاسبه ی nCk همه ی اعداد بین k و n رو تو vector اولی می ریزیم. ــ یعنی !k پایین رو ساده می کنیم ــ بعد همه ی اعداد بین ۱ تا n-k رو هم توی vector دومی می ریزیم. حالا جواب ما برابر است با حاصلضرب همه ی اعضای vector اول تقسیم بر حاصل ضرب همه ی اعضای vector دوم. برای تقسیم یه ایده می زنیم. در هر مرحله یکی از اعضای vector دوم را انتخاب می کنیم و تا وقتی که از ۱ بزرگتر است آن را به ترتیب با اعضای vector اول gcd می گیریم و هر دو ــ عضو vector اول و دوم ــ رو بر این gcd تقسیم می کنیم تا زمانی که عضو vector دوم برابر با ۱ بشه و همین کار رو برای همه ی اعضای vector دوم تکرار می کنیم. حالا جواب ما حاصلضرب اعداد vector اول است که تضمین شده در int64 جا می شه. ضرب می کنیم و خروجی می دیم.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:306e9310ee]~~ L ~~[/center:306e9310ee]
به عنوان سوال بعد سوال ۳۹۸ sgu رو حل کنیم:
http://acm.sgu.ru/problem.php?contest=0&problem=398
صورت سوال:
یه عده رفتن مهمونی. تو مهمونی هر کسی یه تعداد دوست داره . دوستی دوطرفه است.
یه نفر خاص رو در نظر می گیریم. می خواهیم دوستهای دوستهای این یارو رو پیدا کنیم. توجه کنید که خودش و دوستاش رو نباید به حساب بیارین.
ورودی«
در خط اول تعداد افراد و شماره ی اون یارو
در خط i+1 ام ابتدا تعداد افرادی که با i دوست هستند می آید و بعد لیست دوستهای i.
خروجی«
تو خط اول خروجی بنویسید مجموعه دوستهای دوستهای این بنده خدا چند تا عضو داره
در هر خط بعد یکی از اعضای این مجموعه رو بنویسید. ــ باید مرتب شده باشند ــ
به عنوان سوال بعد سوال ۳۹۸ sgu رو حل کنیم:
http://acm.sgu.ru/problem.php?contest=0&problem=398
صورت سوال:
یه عده رفتن مهمونی. تو مهمونی هر کسی یه تعداد دوست داره . دوستی دوطرفه است.
یه نفر خاص رو در نظر می گیریم. می خواهیم دوستهای دوستهای این یارو رو پیدا کنیم. توجه کنید که خودش و دوستاش رو نباید به حساب بیارین.
ورودی«
در خط اول تعداد افراد و شماره ی اون یارو
در خط i+1 ام ابتدا تعداد افرادی که با i دوست هستند می آید و بعد لیست دوستهای i.
خروجی«
تو خط اول خروجی بنویسید مجموعه دوستهای دوستهای این بنده خدا چند تا عضو داره
در هر خط بعد یکی از اعضای این مجموعه رو بنویسید. ــ باید مرتب شده باشند ــ
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
این کد من برای این سواله:
http://gist.github.com/571867
برای تایم نشدن باید از همه ی امکانات ++C استفاده کنیم
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:2d8ab98489]=>M<=[/center:2d8ab98489]
این سوال:
http://www.codeforces.com/contest/9/problem/C
ترجمه:
یک n به شما داده می شود. شما باید تعداد اعداد بین ۱ تا n که ارقام آنها فقط ۰ و ۱ است را به دست بیاورید
زمان: ۱ ثانیه
مموری: ۶۴ مگابایت
ورودی و خروجی استاندارد
n بین ۱ تا ۱۰ به توان ۹ است
مثال:
ورودی :
۱۰
خروجی:
۲
توضیح : پاسخها ۱ و ۱۰ هستند.
پی نوشت: آقای بیباک شما کجا هستید؟ اون سوال B رو چیکار کنیم؟ بر اساس ترجمه ی شما حل کنیم؟
این سوال:
http://www.codeforces.com/contest/9/problem/C
ترجمه:
یک n به شما داده می شود. شما باید تعداد اعداد بین ۱ تا n که ارقام آنها فقط ۰ و ۱ است را به دست بیاورید
زمان: ۱ ثانیه
مموری: ۶۴ مگابایت
ورودی و خروجی استاندارد
n بین ۱ تا ۱۰ به توان ۹ است
مثال:
ورودی :
۱۰
خروجی:
۲
توضیح : پاسخها ۱ و ۱۰ هستند.
پی نوشت: آقای بیباک شما کجا هستید؟ اون سوال B رو چیکار کنیم؟ بر اساس ترجمه ی شما حل کنیم؟
Goharshady گفت
[center:72c53067a5]=>M<=[/center:72c53067a5]
این سوال:
http://www.codeforces.com/contest/9/problem/C
ترجمه:
یک n به شما داده می شود. شما باید تعداد اعداد بین ۱ تا n که ارقام آنها فقط ۰ و ۱ است را به دست بیاورید
زمان: ۱ ثانیه
مموری: ۶۴ مگابایت
ورودی و خروجی استاندارد
n بین ۱ تا ۱۰ به توان ۹ است
مثال:
ورودی :
۱۰
خروجی:
۲
توضیح : پاسخها ۱ و ۱۰ هستند.
پی نوشت: آقای بیباک شما کجا هستید؟ اون سوال B رو چیکار کنیم؟ بر اساس ترجمه ی شما حل کنیم؟
این سوال:
http://www.codeforces.com/contest/9/problem/C
ترجمه:
یک n به شما داده می شود. شما باید تعداد اعداد بین ۱ تا n که ارقام آنها فقط ۰ و ۱ است را به دست بیاورید
زمان: ۱ ثانیه
مموری: ۶۴ مگابایت
ورودی و خروجی استاندارد
n بین ۱ تا ۱۰ به توان ۹ است
مثال:
ورودی :
۱۰
خروجی:
۲
توضیح : پاسخها ۱ و ۱۰ هستند.
پی نوشت: آقای بیباک شما کجا هستید؟ اون سوال B رو چیکار کنیم؟ بر اساس ترجمه ی شما حل کنیم؟
http://snipt.net/rezashiri/contest-9-c
[center:0bb3a086b4]
[/center:0bb3a086b4]
می شه اینو ترجمه کنید: http://www.codeforces.com/contest/9/problem/B
[/center:0bb3a086b4]
می شه اینو ترجمه کنید: http://www.codeforces.com/contest/9/problem/B