یافتن اشتباه کد

[sa1378]

سلام
من برای این سوال:
125006
کد زیر رو زدم:
/*
ID: sa.13781
PROG: namenum
LANG: C++
*/


#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
#define N 5000
vector <string> v;
char num[20],a[20];
string dict[N];

int tool(char x[]) //CORRECT
{
int p=0;
for(int i=0;x[i]!=0;i++)
p++;
return p;
}

void prp() //CORRECT
{
ifstream fin ("dict.txt");
for(int i=0;fin>>dict[i];i++);
}

char num_char(char x,int a) //CORRECT
{
if(x=='2')
{
if(a==0)
return 'A';
if(a==1)
return 'B';
if(a==2)
return 'C';
}
if(x=='3')
{
if(a==0)
return 'D';
if(a==1)
return 'E';
if(a==2)
return 'F';
}
if(x=='4')
{
if(a==0)
return 'G';
if(a==1)
return 'H';
if(a==2)
return 'I';
}
if(x=='5')
{
if(a==0)
return 'J';
if(a==1)
return 'K';
if(a==2)
return 'L';
}
if(x=='6')
{
if(a==0)
return 'M';
if(a==1)
return 'N';
if(a==2)
return 'O';
}
if(x=='7')
{
if(a==0)
return 'P';
if(a==1)
return 'R';
if(a==2)
return 'S';
}
if(x=='8')
{
if(a==0)
return 'T';
if(a==1)
return 'U';
if(a==2)
return 'V';
}
if(x=='9')
{
if(a==0)
return 'W';
if(a==1)
return 'X';
if(a==2)
return 'Y';
}
}

void calc(char x[],int n)
{
if(n==0)
{
v.push_back(x);
return;
}

for(int i=0;i<3;i++)
{
x[n-1]=num_char(num[n-1],i);
calc(x,n-1);
}
}

void search()
{
ofstream fout("namenum.out");
int p=0;
for(int i=0;dict[i]!="";i++)
{
if(dict[i].size()==tool(num))
{
for(int j=0;j<v.size();j++)
if(v[j]==dict[i])
{
fout<<dict[i]<<"\n";
p++;
}
}
}
if(p==0)
fout<<"NONE"<<endl;
}

void test_calc() //CORRECT
{
for(int j=0;j<v.size();j++)
cout<<v[j]<<" ";
}

int main() {
//cout<<tool("alireza");
//cout<<num_char('3',2);
ifstream fin("namenum.in");

fin>>num;

prp();
//cout<<dict[3];
calc(a,tool(num));
//cout<<v.size()<<endl;
//test_calc();
search();



return 0;
}
و کد به ازای تمام خروجی ها درست جواب میده
ولی سایت usaco که سوال مال اونه گفته توی یه تست جواب اشتباه داده و این ارور رو هم داده:
125007
به ازای عددی که توی ارور گفته من برنامه رو اجرا کردم و خروجی درست هم داده
مشکل از کجاست؟

[مسعود اقدسی فام]

std::bad_alloc خطای تخصیص حافظه هست. زمانی که به هر دلیلی امکان تخصیص حافظه به متغیر وجود نداشته باشه این خطا رخ می‌ده. مثلا شاید به خاطر تخصیص بیش از حد مجاز.


http://www.cplusplus.com/reference/new/bad_alloc/

[sa1378]

std::bad_alloc خطای تخصیص حافظه هست. زمانی که به هر دلیلی امکان تخصیص حافظه به متغیر وجود نداشته باشه این خطا رخ می‌ده. مثلا شاید به خاطر تخصیص بیش از حد مجاز.


http://www.cplusplus.com/reference/new/bad_alloc/


خب من کد رو به این صورت قرار دادم که دیگه نیاد همه حالات رو توی وکتور بریزه و همینجوری برای هر عدد حساب کنه:
/*
ID: sa.13781
PROG: namenum
LANG: C++‎‎‎‎‎‎
*/


#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
#define N 5000

char num[20],a[20];
string dict[N];
int p;

int tool(char x[]) //CORRECT
{
int p=0;
for(int i=0;x[i]!=0;i++)
p++;
return p;
}

void prp() //CORRECT
{
ifstream fin ("dict.txt");
for(int i=0;fin>>dict[i];i++);
}

char num_char(char x,int a) //CORRECT
{
if(x=='2')
{
if(a==0)
return 'A';
if(a==1)
return 'B';
if(a==2)
return 'C';
}
if(x=='3')
{
if(a==0)
return 'D';
if(a==1)
return 'E';
if(a==2)
return 'F';
}
if(x=='4')
{
if(a==0)
return 'G';
if(a==1)
return 'H';
if(a==2)
return 'I';
}
if(x=='5')
{
if(a==0)
return 'J';
if(a==1)
return 'K';
if(a==2)
return 'L';
}
if(x=='6')
{
if(a==0)
return 'M';
if(a==1)
return 'N';
if(a==2)
return 'O';
}
if(x=='7')
{
if(a==0)
return 'P';
if(a==1)
return 'R';
if(a==2)
return 'S';
}
if(x=='8')
{
if(a==0)
return 'T';
if(a==1)
return 'U';
if(a==2)
return 'V';
}
if(x=='9')
{
if(a==0)
return 'W';
if(a==1)
return 'X';
if(a==2)
return 'Y';
}
}

void search(char x[])
{
ofstream fout("namenum.out");

for(int i=0;dict[i]!="";i++)
{
if(dict[i]==x)
{
fout<<x<<endl;
p++;
}
}

}


void calc(char x[],int n)
{

if(n==0)
{
search(x);
return;
}

for(int i=0;i<3;i++)
{
x[n-1]=num_char(num[n-1],i);
calc(x,n-1);
}
}


int main() {
//cout<<tool("alireza");
//cout<<num_char('3',2);
ifstream fin("namenum.in");
ofstream fout("namenum.out");

fin>>num;

prp();
//cout<<dict[3];
calc(a,tool(num));
//cout<<v.size()<<endl;
if(p==0)
fout<<"NONE"<<endl;




return 0;
}
ولی زمان اجراش زیاد شد(به نظرم نباید تغییر میکرد اصلا)
روی تست سوم ارور زمان اجرا داد
چجوری مشکل رو برطرف کنم؟

[rahnema1]

در چند مساله اخیر که شما می خواستید جواب را پیدا کنید مسیر را درست می رفتید تا جواب را پیدا کنید ( که این کار از خیلی ها ساخته نیست) اما چند نکته لازمه در نظر بگیرید اگر می خواهید در این مسابقات امتیاز بالا بگیرید
ببینید در این جور مسابقات، سرعت حرف اول را می زنه در نتیجه باید از کارهای اضافی پرهیز کنید
در صورتی که میشه دو تا آرایه را مقایسه کرد چه ضرورتی داره یک آراه سوم ایجاد بشه و مرتبا مقادیر آرایه ها در اون کپی بشه؟
اگر انجام یک عمل بدون صدا زدن تابع امکان پذیر باشه حتی الامکان از تابع استفاده نکنید چون صدا زدن تابع هزینه داره هرچند هزینه اش کم باشه
توی چند مورد دیدم یک تابع می نویسید که داخلش مقایسه انجام می دهید واون تابع را به تعداد زیاد صدا می زنید خب شما می تونید از آرایه استفاده کنید مثلا به این شکل
char adad[] = "222333444555...
تا می تونید از امکانات کتابخانه STL از جمله vector و push_back و الگوریتم غیره استفاده نکنید . مگه وقت کم داشته باشید که نشه الگوریتم مورد نظر را پیاده سازی کرد. علیرغم اینکه استفاده از این کتابخونه آسونه ولی میتونه سرعت برنامه را پایین بیاره. علتش اینه که هنگام طراحی این کتابخانه هدف اصلی سرعت نبوده بلکه موارد دیگه هم مطرح بوده. همون آرایه ساده خیلی مناسبه و مهم تر اینه که می دونید دارید چیکار کنید
برای محاسبه طول رشته تابع strlen استفاده کنید چون اینها با استفاده از اسمبلی پیاده سازی شده که از کدی که شما نوشتید سریعتر میتونه باشه
به هدر string.h مراجعه و تابعهای موجود در اون را مرور کنید خیلی از اونها به کار شما می خوره
نهایتا اگه همون طور که گفتم این برنامه را بتونید با آرایه انجام بدید حداکثر در چند خط میشه برنامه را نوشت با سرعت بیشتر

[a.r.khoshghalb]

دوست خیلیییی عزیز!!!
اوردر این برنامه نماییه!! اوردرت اینه:

3^n * m
که n طول عدد ورودیه و m تعداد کلمات توی دیکشنری!!!
سوال گفته m که 5000 هست حداکثر! n رو توی عکسی که دادی نگفته چنده ولی n اگر حتی 10 هم باشه برنامت تو 3 ثانیه جواب میده! که به احتمال زیاد تایم لیمیت سوال 2 ثانیه باشه! اما باز هم راهت خیلی اوردرش زیاده!! n رو نگفته تو سوال تا چنده؟ اگر n تا 100 باشه برنامت بیشتر از چند سال طول میکشه که جواب بده :لبخند::لبخند::لبخند:
این دلیلیه که میگن یهو با کد زدن برنامه نویسی رو شروع نکنید!! کد زدن راحت ترین و آخرین مرحله است!
راهی که به ذهن من میرسه و اوردرش هم خوبه BFS درخت trie ساخته شده از روی فایل دکشنریه!
BFS که میدونی چیه اگر trie رو نمیدونی چیه برو حتما بخون از تو کتابی اگر داری، اگر نداری ویکیپدیا!

[sa1378]

دوست خیلیییی عزیز!!!
اوردر این برنامه نماییه!! اوردرت اینه:

3^n * m
که n طول عدد ورودیه و m تعداد کلمات توی دیکشنری!!!
سوال گفته m که 5000 هست حداکثر! n رو توی عکسی که دادی نگفته چنده ولی n اگر حتی 10 هم باشه برنامت تو 3 ثانیه جواب میده! که به احتمال زیاد تایم لیمیت سوال 2 ثانیه باشه! اما باز هم راهت خیلی اوردرش زیاده!! n رو نگفته تو سوال تا چنده؟ اگر n تا 100 باشه برنامت بیشتر از چند سال طول میکشه که جواب بده :لبخند::لبخند::لبخند:
این دلیلیه که میگن یهو با کد زدن برنامه نویسی رو شروع نکنید!! کد زدن راحت ترین و آخرین مرحله است!
راهی که به ذهن من میرسه و اوردرش هم خوبه BFS درخت trie ساخته شده از روی فایل دکشنریه!
BFS که میدونی چیه اگر trie رو نمیدونی چیه برو حتما بخون از تو کتابی اگر داری، اگر نداری ویکیپدیا!
من n رو به صورت آرایه ای از کاراکتر ها دریافت کردم و سوال گفته تا 12 رقم هست
فکر میکنم که اون 3n هم لازم باشه چونکه باید به ازای هر ورودی همه ی حالت هارو بررسی کرد

[sa1378]

در چند مساله اخیر که شما می خواستید جواب را پیدا کنید مسیر را درست می رفتید تا جواب را پیدا کنید ( که این کار از خیلی ها ساخته نیست) اما چند نکته لازمه در نظر بگیرید اگر می خواهید در این مسابقات امتیاز بالا بگیرید
ببینید در این جور مسابقات، سرعت حرف اول را می زنه در نتیجه باید از کارهای اضافی پرهیز کنید
در صورتی که میشه دو تا آرایه را مقایسه کرد چه ضرورتی داره یک آراه سوم ایجاد بشه و مرتبا مقادیر آرایه ها در اون کپی بشه؟
اگر انجام یک عمل بدون صدا زدن تابع امکان پذیر باشه حتی الامکان از تابع استفاده نکنید چون صدا زدن تابع هزینه داره هرچند هزینه اش کم باشه
توی چند مورد دیدم یک تابع می نویسید که داخلش مقایسه انجام می دهید واون تابع را به تعداد زیاد صدا می زنید خب شما می تونید از آرایه استفاده کنید مثلا به این شکل
char adad[] = "222333444555...
تا می تونید از امکانات کتابخانه STL از جمله vector و push_back و الگوریتم غیره استفاده نکنید . مگه وقت کم داشته باشید که نشه الگوریتم مورد نظر را پیاده سازی کرد. علیرغم اینکه استفاده از این کتابخونه آسونه ولی میتونه سرعت برنامه را پایین بیاره. علتش اینه که هنگام طراحی این کتابخانه هدف اصلی سرعت نبوده بلکه موارد دیگه هم مطرح بوده. همون آرایه ساده خیلی مناسبه و مهم تر اینه که می دونید دارید چیکار کنید
برای محاسبه طول رشته تابع strlen استفاده کنید چون اینها با استفاده از اسمبلی پیاده سازی شده که از کدی که شما نوشتید سریعتر میتونه باشه
به هدر string.h مراجعه و تابعهای موجود در اون را مرور کنید خیلی از اونها به کار شما می خوره
نهایتا اگه همون طور که گفتم این برنامه را بتونید با آرایه انجام بدید حداکثر در چند خط میشه برنامه را نوشت با سرعت بیشتر

حرفاتون رو قبول دارم
ولی یه چیزی که درباره من هست اینکه که کدهام فوق العاده باگ دارن
برای همین به صورت تابع های جدا مینویسم تا دیباگش راحت باشه

الان مشکل من اینه که کد اولم روی تست سوم اشکال زمان نمیداد
ولی کد دومم که تو اوردر با اون فرقی نداره ارور زمان میده
چرا؟

[a.r.khoshghalb]

من n رو به صورت آرایه ای از کاراکتر ها دریافت کردم و سوال گفته تا 12 رقم هست
فکر میکنم که اون 3n هم لازم باشه چونکه باید به ازای هر ورودی همه ی حالت هارو بررسی کرد

خوب اگر n=12 باشه برنامت توی 26 ثانیه جواب میده! و این خیلی زیاده!
اصلا لازم نیست n^3 باشه و هیچ نیازی نیست که همه حالت ها رو بسازیم!
میشه هم از راهی رفت که توش همه حالت ها رو بسازیم ولی اون وقت دیگه برای اینکه ببینی کدوم حالت ها توی دیکشنری اومدن نباید به ازای هر حالت ساخته شده همه کلمه های دیکشنری رو بخونی! باید با الگوریتم بهتری بگردی دنبال کلمه ات توی دیکشنری.
از هر کدوم از راه ها که بخوای بری (چه اینکه همه حالت ها رو بسازی بعد با اوردر خوب تو دیکشنری بگردی چه اینکه از همون اول به جای اینکه همه رو بسازی ببینی تو دیکشنری کدوما با این اعداد ساخته میشن) باید از درخت Trie استفاده کنی.
درخت Trie رو برو بخون چیه.

[rahnema1]

حرفاتون رو قبول دارم
ولی یه چیزی که درباره من هست اینکه که کدهام فوق العاده باگ دارن
برای همین به صورت تابع های جدا مینویسم تا دیباگش راحت باشه

الان مشکل من اینه که کد اولم روی تست سوم اشکال زمان نمیداد
ولی کد دومم که تو اوردر با اون فرقی نداره ارور زمان میده
چرا؟

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

لزومی نداره فایل را بخونید و لغات خونده شده را بصورت string در آرایه dic بریزید
تنها و تنها با یک بار پیمایش فایل مساله را میشه حل کرد ( بدون استفاده از هیچ ساختاری)
به دست آوردن رقم معادل با تابع num_char گرچه جواب درست میده ولی روش بهتر از اون هم با آرایه هست
endl سرعت را کم می کنه به جای اون "n\" استفاده کنید
string سرعت نداره یک آرایه char به اندازه 14 ایجاد کنید و همیشه از اون استفاده کنید

[sa1378]

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

لزومی نداره فایل را بخونید و لغات خونده شده را بصورت string در آرایه dic بریزید
تنها و تنها با یک بار پیمایش فایل مساله را میشه حل کرد ( بدون استفاده از هیچ ساختاری)
به دست آوردن رقم معادل با تابع num_char گرچه جواب درست میده ولی روش بهتر از اون هم با آرایه هست
endl سرعت را کم می کنه به جای اون "n\" استفاده کنید
string سرعت نداره یک آرایه char به اندازه 14 ایجاد کنید و همیشه از اون استفاده کنید
ممنون برنامه رو به همین صورت مینویسم که با یکبار پیمایش فایل انجام بشه
اون endl رو هم حواسم نبوده
استاد من میگه که از char استفاده نکن چون string همه ی قابلیت های اون رو داره و قابلیت های اضافه هم داره پس توی c++ لزومی نداره از char استفاده کرد...الان من چیکار کنم آخرش؟

[sa1378]

خوب اگر n=12 باشه برنامت توی 26 ثانیه جواب میده! و این خیلی زیاده!
اصلا لازم نیست n^3 باشه و هیچ نیازی نیست که همه حالت ها رو بسازیم!
میشه هم از راهی رفت که توش همه حالت ها رو بسازیم ولی اون وقت دیگه برای اینکه ببینی کدوم حالت ها توی دیکشنری اومدن نباید به ازای هر حالت ساخته شده همه کلمه های دیکشنری رو بخونی! باید با الگوریتم بهتری بگردی دنبال کلمه ات توی دیکشنری.
از هر کدوم از راه ها که بخوای بری (چه اینکه همه حالت ها رو بسازی بعد با اوردر خوب تو دیکشنری بگردی چه اینکه از همون اول به جای اینکه همه رو بسازی ببینی تو دیکشنری کدوما با این اعداد ساخته میشن) باید از درخت Trie استفاده کنی.
درخت Trie رو برو بخون چیه.
اون روشی که دوست عزیز rahnema گفتم اجراش ساده هست
ولی امروز میرم Trie رو هم میخونم بدرد میخوره حتما

[rahnema1]

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

اتفاقا نقطه ضعفش همینه که چندکاره هست و قابلیتهای اضافه داره. من فقط اگه بخوام از یک قابلیت این string استفاده کنم باید هزینه قابلیت های دیگه اون را هم تحمل کنم
مثلا همین عملگر [ ] چون overload شده پس مستلزم صدا زدن تابع هست
یا مثلا عملگر == که چند تا کار اضافه انجام میده
بذارید خیال شما را راحت کنم در این مسابقات از امکانات زبان ++c زمانی استفاده کنید که مطمئن باشید سرعت کار را بالا می بره ( یا مثلا کمبود وقت در پیاده سازی یک الگوریتم ). در غیر این صورت امکانات زبان c کافیه
حتی خودتون هم می تونید اینها را تست کنید یه سری برنامه با تعداد تکرار زیاد ایجاد کنید و زمان بگیرید ببینید کدام سرعتش بیشتر میشه

[a.r.khoshghalb]

اون روشی که دوست عزیز rahnema گفتم اجراش ساده هست
ولی امروز میرم Trie رو هم میخونم بدرد میخوره حتما

سلام
خیلی خوبه که میخونی Trie رو.
و تشکر بسیار از rahnema!! راهشون بسیار خوب بود برای حل این مساله!
بین راه ایشون و Trie شک نکن باید راه ایشون رو پیاده کنی. بسیار خوب و عالی! از نظر زمانی هم خیلی خوبه. من خیلی سخت فکر کردم.