المپیاد سوالات الگوریتم

[armita]

بهتر نیست هر سوالی رو کسی مشکل داشت بذاریم ؟
مثلا من بگم فلان سوال فلان چپتر رو نمی‌دونم بعد بقیه بیان اون رو توضیح بدن ! اولاش رو راحت می‌شد فهمید

این تاپیک هم راجع به یوساکوئه
http://www.sampadia.com/forum/index.php/topic,19198

#این تاپیک ادامه ی تاپیک"ماراتن یوساکو usaco (ترجمه سوالات یوساکو)" هس ما اینجا می خوایم اشکال هایی که توی یوساکو داریم رو با هم حل کنیم

 

[parsa_spy]

پاسخ : سوالات الگوریتم

اینجوری که کد آماده به همدیگه می دید اصلا خوب نیست! خودتون ضررش رو می بینید. اگه دیگه خیلی گیر کرده بودید الگوریتم رو بپرسید! ولی به هیچ وجه کد آماده بقیه رو نگیرید.

 

[7991]

پاسخ : سوالات الگوریتم

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

#include<fstream>
using namespace std;
      ifstream  fin ("friday.in.txt");
      ofstream fout ("friday.out.txt");
    
int main(){
int n,day=0,a[7];
  int days;
    for(int i=0;i<7;i++)
    a[i]=0;
    a[0]=1;
   fin>>n;
   for(int year=1990;year<(1990+n);year++){
           for(int month=0;month <12;month++){
                   
                   if (month==0 ||month==2 ||month==4 ||month==6 ||month==7 ||month==9 ||month==11)
           days= 31;
      else if (month==3 ||month==5 ||month==8 ||month==10)
           days= 30;
      else if(month==1){
          if((year%400) ==0 ||((year%100)!=0)&& (year%4)==0)
               days= 29;
          else
               days= 28;
               }
               
               
                   day=(day+days)%7;
                   a[day]++;
                   if(year==(1989+n ) && month==11)
                        a[day]--;                   
                   }
           }
   for(int i=0;i<=6;i++){
           if(i==6)
           fout<<a[i]<<endl;
           else
           fout<<a[i]<<" ";
           }
    return 0;
}

 

[8161]

پاسخ : سوالات الگوریتم

سلام!!! احتمالا خیلی دیر شده و تا حالا 100 بار اکسپتش کردی ولی به این مسیله فکر کردی که یوساکو سال شروعو1900 گرفته و تو 1990؟؟؟
فکر کنم اشتباهت همین بوده!

 

[Feri]

پاسخ : سوالات الگوریتم

این سوالو تو قسمت الگوریتم هم گذاشتم.
من برنامه milk2 رو نوشتم و تا تست 6 درست کار میکنه ولی تست 7 رو غلط میگیره هر کاری کردم نفهمیدم اشکالم چیه اگه میشه شما بگید:

#include<iostream>
#include<fstream>

using namespace std;

void shift(int* a,int time,int start,int n)
{
	for(int i=0;i<time;i++)
	{
		for(int j=n;j>=start;j--)
			a[j]=a[j-1];
		n++;
	}
}

int main()
{
	ifstream fin("milk2.in");
	ofstream fout("milk2.out");
	int n;
	int times[6000]={0};
	int s,e;
	int start[2],end[2];
	int noot=1;
	times[0]=-2;
	times[1]=99999999999;
	fin>>n;
	for(int q=0;q<n;q++)
	{
		fin>>s>>e;
		for(int i=0;i<=noot;i++)
		{
			if(s>=times[i])
			{
				start[0]=i;
				start[1]=i+1;
			}
			if(e>=times[i])
			{
				end[0]=i;
				end[1]=i+1;
			}
		}
		if(end[0]==start[0])
		{
			if(end[0]%2==0)
			{
				shift(times,2,end[0]+1,noot+1);
				times[end[0]+1]=s;
				times[end[0]+2]=e;
				noot+=2;
			}
		}
		else
		{
			if(start[1]==end[0])
			{
				if(start[1]%2==1)
					times[start[1]]=s;
				else
					times[start[1]]=e;
			}
			else
			{
				if(start[1]%2==1)
					times[start[1]]=s;
				if(end[0]%2==0)
					times[end[0]]=e;
			}
			for(int i=start[1]+1;i<end[1]-1;i++)
				times[i]=-1;
		}
		int help=noot;
			for(int i=1;i<noot;i++)
			{
				if(times[i]==-1)
				{
						for(int j=i;j<noot;j++)
							times[j]=times[j+1];
						i--;
						help--;
				}
			}
			noot=help;
	}
	
	for(int i=2;i<noot-1;i+=2)
		if(times[i]==times[i+1])
			times[i]=times[i+1]=-1;
			
	int help=noot;
	for(int i=1;i<noot;i++)
	{
		if(times[i]==-1)
		{
			for(int j=i;j<noot;j++)
				times[j]=times[j+1];
			i--;
			help--;
		}
	}
	noot=help;
	int max1=0,max2=0;
	for(int i=1;i<noot-1;i+=2)
	{
		if(times[i+1]-times[i]>max1)
			max1=times[i+1]-times[i];
	}
	for(int i=2;i<noot-1;i+=2)
	{
		if(times[i+1]-times[i]>max2)
			max2=times[i+1]-times[i];
	}
	fout<<max1<<" "<<max2<<endl;
	return 0;
}

 

[3pideh]

پاسخ : سوالات الگوریتم

سلام دوستان
یه مشکلی داشتم با سوال namenum 1.2 تو کامپوتر جواب درست میده ولی یوساکو این ارور رو میده :

Execution error: Your program had this runtime error: Bad
syscall #32000175 (RT_SIGPROCMASK) [email kolstad if you think
this is wrong]. The program ran for 0.227 CPU seconds before the
error. It used 16284 KB of memory.

------ Data for Run 10 ------
463373633623
----------------------------

Your program printed data to stderr. Here is the data:
-------------------
terminate_called_after_throwing_an_instance_of_'St9bad_alloc'
__what():__std::bad_alloc
-------------------

میشه راهنماییم کنید لطفا یه ماهه گیر این سوالم همش یجاش میلنگه...!!

 

[Xam]

پاسخ : سوالات الگوریتم

خوب مال اینه دارید 16مگ و خورده ای حافظه مصرف می کنید (شایدم بیشتر) !
یوساکو نهایتا 16 مگ اجازه می ده برنامتون حافظه بگیره ! اون یه خورده ای (شایدم بیشتر) مشکلو درست کرده !

 

[3pideh]

پاسخ : سوالات الگوریتم

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

#include<fstream>
#include<iostream>

using namespace std;

const int MaxN=5000;
const int MaxM=54*100*100 ;
string name[MaxN] , s[MaxM] ;
string a;
int b ,sep ,tav ;

      ifstream  fin ("namenum.in");
      ofstream fout ("namenum.out");


void compare(int i,int start,int end){

     for(int j=start ;j<end ;j++){

                    if(s[j] == name[i]){

                               fout << s[j] << endl;
                               sep ++ ;
                               }
                          }
     }


void harf1(int aa,int i){

    for(int j=0 ;j<b ;j++){

     if(a[i] == 50)
          s[aa+j] += "A";
     else if(a[i] == 51)
          s[aa+j] += "D";
     else if(a[i] == 52)
          s[aa+j] += "G";
     else if(a[i] == 53)
          s[aa+j] += "J";
     else if(a[i] == 54)
          s[aa+j] += "M";
     else if(a[i] == 55)
          s[aa+j] += "P";
     else if(a[i] == 56)
          s[aa+j] += "T";
     else if(a[i] == 57)
          s[aa+j] += "W";
}
}

void harf2(int aa,int i){

    for(int j=0 ;j<b ;j++){

     if(a[i] == 50)
          s[aa+j] += "B";
     else if(a[i] == 51)
          s[aa+j] += "E";
     else if(a[i] == 52)
          s[aa+j] += "H";
     else if(a[i] == 53)
          s[aa+j] += "K";
     else if(a[i] == 54)
          s[aa+j] += "N";
     else if(a[i] == 55)
          s[aa+j] += "R";
     else if(a[i] == 56)
          s[aa+j] += "U";
     else if(a[i] == 57)
         s[aa+j] += "X";
}
}

void harf3(int aa,int i){

     for(int j=0 ;j<b ;j++){

     if(a[i] == 50)
          s[aa+j] += "C";
     else if(a[i] == 51)
          s[aa+j] += "F";
     else if(a[i] == 52)
          s[aa+j] += "I";
     else if(a[i] == 53)
          s[aa+j] += "L";
     else if(a[i] == 54)
          s[aa+j] += "O";
     else if(a[i] == 55)
          s[aa+j] += "S";
     else if(a[i] == 56)
          s[aa+j] += "V";
     else if(a[i] == 57)
          s[aa+j] += "Y";
          }
}


int main() {

    ifstream userstream("dict.txt");
    int zz=0 ;

    while(!userstream.eof()){
                                  userstream >> name[zz];
                                     zz++;
                                  }


    fin >> a;


    int tav=1;
    for(int i=0 ;i<a.length() ;i++)
            tav *=3 ;

    int c=1;
    for(int i=0 ;i<a.length();i++){
                   c *=3 ;


    b = tav/c ;
    int aa=0;

    while( aa < tav ){

        if( (aa/b)%3 == 0 )
             harf1(aa,i);


        else if( (aa/b)%3 == 1 )
              harf2(aa,i);


        else if( (aa/b)%3 == 2 )
             harf3(aa,i);


        aa += b;
        }


           }

    for(int i=0 ;i<zz ;i++){
            if(name[i][0]==s[0][0] )
                     compare(i,0,tav/3);
            else if ( name[i][0]==s[tav/3][0])
                     compare(i,tav/3,2*tav/3);
            else if ( name[i][0]==s[2*tav/3][0])
                     compare(i,2*tav/3,tav);

                               }

    if(sep==0)
         fout << "NONE" << endl;


    return 0;
                           }

 

[Xam]

پاسخ : سوالات الگوریتم

ببین الان میای به ازای عدده هر کلمه ای که عددش اون می شه رو می سازی؟؟؟؟؟یعنی 3^12 تا رشته؟
پیشنهاد من اینه به جای این ، هر بار یه کلمه بیار عددشو به دست بیار ! اگه عددش با عدد اصلی یکی شد چاپش کن !

 

[3pideh]

پاسخ : سوالات الگوریتم

ببین الان میای به ازای عدده هر کلمه ای که عددش اون می شه رو می سازی؟؟؟؟؟یعنی 3^12 تا رشته؟
پیشنهاد من اینه به جای این ، هر بار یه کلمه بیار عددشو به دست بیار ! اگه عددش با عدد اصلی یکی شد چاپش کن !

اَاَاَاَاَ چقدر راحت حل شد
چرا به فکر خودم نرسید
حیف اون همه وقتی که گذاشتم سر این کد....
مرسی از راهنماییت :) طلا شی ایشااله