ماراتن SGU , USACO

[rezashiri]

سلام.

از امروز این ماراتن شروع به کار می کنه و در اون سوالات این دو سایت حل می شن :

[center:c66149136d]http://acm.sgu.ru

http://ace.delos.com[/center:c66149136d][center:c66149136d]

سوالات حتما باید ترجمه بشن و اینجا قرار داده بشه.

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

تا سوالی حل نشده سوالی قرار داده نشه.

شماره سوال حتما زده بشه.

ترتیب مهم نیست فقط سعی بشه اول از سوالات راحت تر شروع بشه.

برای قرار دادن کد می توانید از این سایت یا کد خود سایت استفاده کنید.

دوستان لطفا همکاری لازم رو انجام بدید (خصوصا : SABB , Olympiad , navidjalalmanesh , Goharshady ) هر چند آقای گوهرشادی قول همکاری دادن.



===================================================

[/center:c66149136d]

دنباله فیبوناتچی به صورت زیر است :

[center:c66149136d]

برنامه ای بنویسید که با دریافت k ، مجموع k جمله اول دنباله فیبوناتچی را در خروجی چاپ کند.

محدودیت :

k<41​

[/center:c66149136d]
ورودی نمونه :

5

خروجی نمونه :

12

​

[center:c66149136d]آدرس سوال[/center:c66149136d]

 

[rezashiri]

چرا کسی نظری نمی ده؟

بابا این که دیگه خیلی آسون بود ....(احتمالا به دلیل راحتی زیاده)

اگه نمی خواین همکاری کنید جم کنیم بریم.

شما کد اینو بذارید از این به بعد سخت ترش می کنیم.

 

[erfankh]

[LEFT]#include<iostream> 
using namespace std; 
int main(){ 
    int n,f[100]; 
    f[0]=f[1]=1; 
    cin>>n; 
    for(int i=2;i<n;i++)f[I]=f[i-1]+f[i-2]; 
    cout<<f[n-1]<<endl; 
    return 0; 
    }

[/I][/LEFT]

 

[rezashiri]

[LEFT]#include<iostream> 
using namespace std; 
int main(){ 
    int n,f[100]; 
    f[0]=f[1]=1; 
    cin>>n; 
    for(int i=2;i<n;i++)f[I]=f[i-1]+f[i-2]; 
    cout<<f[n-1]<<endl; 
    return 0; 
    }

[/I][/LEFT]

خوب سوال بعدی رو بذارید دیگه ...

اگه نمی ذارین آقای گوهرشادی زحمتشو بکشن...

 

[Olympiad]

[LEFT]#include<iostream> 
using namespace std; 
int main(){ 
    int n,f[100]; 
    f[0]=f[1]=1; 
    cin>>n; 
    for(int i=2;i<n;i++)f[I]=f[i-1]+f[i-2]; 
    cout<<f[n-1]<<endl; 
    return 0; 
    }

[/I][/LEFT]

شما احیانا جمله ی k ام رو حساب نکردید !؟؟! !!!!

سوال مجموع k جمله ی اول رو خواسته :


اصلاحیه ی کد :

#include<iostream>
#include <conio.h>
using namespace std;

   int main()
	{
	   int n,f[100];
	   long long s=2;
	   f[0]=f[1]=1;
	   cin>>n;
	   for(int i=2;i<n;i++)
		{
		  f[i]=f[i-1]+f[i-2];
		  s+=f[i];
		}
    cout<<s<<endl;
    getch();
    return 0;
    }

 

[rezashiri]

[LEFT]#include<iostream> 
using namespace std; 
int main(){ 
    int n,f[100]; 
    f[0]=f[1]=1; 
    cin>>n; 
    for(int i=2;i<n;i++)f[I]=f[i-1]+f[i-2]; 
    cout<<f[n-1]<<endl; 
    return 0; 
    }

[/I][/LEFT]

شما احیانا جمله ی k ام رو حساب نکردید !؟؟! !!!!

سوال مجموع k جمله ی اول رو خواسته :


اصلاحیه ی کد :

#include<iostream>
#include <conio.h>
using namespace std;

   int main()
	{
	   int n,f[100];
	   long long s=2;
	   f[0]=f[1]=1;
	   cin>>n;
	   for(int i=2;i<n;i++)
		{
		  f[I]=f[i-1]+f[i-2];
		  s+=f[I];
		}
    cout<<s<<endl;
    getch();
    return 0;
    }

کد شمام مشکل داره...[/I][/I]

بهش بدید 1.

اینم کد نهایی که درسته :

#include <iostream>
//#include <conio.h>

using namespace std;

int main()
{
    int f[50],k,sum=0;
    
    cin>>k;
    for(int i=0;i<k;i++)
    {
		  f[i]=1;
		  f[i]=1;
		  if(i>=2)
		  f[i]=f[i-1]+f[i-2];
		  sum+=f[i];
    }
    
    cout<<sum;
    
    //getch();
    return 0;
}

یه نفر یه سوال ترجمه کنه بذاره...

اگه از USACO باشه بهتره...

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

خوب مثل اینکه کلا بخش کامپیوتر خوابیده !!!!!!!! برای اینکه راه بیفته ، سوال بعدی رو ترجمه میکنم ولی از این به بعد حتما الگوریتمتون رو کاملا توضیح بدید !!!!!

خوب میریم سراغ سوال !!!!!! فقط صورت سوال رو خلاصه مینویسم :4::4:


143

یه درخت یا n راس داریم ، به هر کدوم از راس ها یه عدد صحیح نسبت داده شده است . میخواهیم زیرگرافی ناتهی و همبند از این درخت پیدا کنیم که مجموع اعداد رئوسش بیشینه باشند . شما باید این مقدار بیشینه رو در خروجی چاپ کنید .
ورودی هم به این شکله که اول n رو میگیره بعد تو n-1 سطر بعدی ، تو هر سطر 2 تا عدد میگیره که نشون دهنده ی یال ها هستند ... خوب دیگه حلشون کنید .. :15:


توجه : باید حتما یه شهرها انتخاب کنه !! یعنی اگه همه ی شهرها منفی بودن ، کوچکترینش رو بده

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

خوب مثل اینکه کلا بخش کامپیوتر خوابیده !!!!!!!! برای اینکه راه بیفته ، سوال بعدی رو ترجمه میکنم ولی از این به بعد حتما الگوریتمتون رو کاملا توضیح بدید !!!!!

خوب میریم سراغ سوال !!!!!! فقط صورت سوال رو خلاصه مینویسم :4::4:


143

یه درخت یا n راس داریم ، به هر کدوم از راس ها یه عدد صحیح نسبت داده شده است . میخواهیم زیرگرافی ناتهی و همبند از این درخت پیدا کنیم که مجموع اعداد رئوسش بیشینه باشند . شما باید این مقدار بیشینه رو در خروجی چاپ کنید .
ورودی هم به این شکله که اول n رو میگیره بعد تو n-1 سطر بعدی ، تو هر سطر 2 تا عدد میگیره که نشون دهنده ی یال ها هستند ... خوب دیگه حلشون کنید .. :15:

کسی نیست ؟!!؟ نظری نبود ؟؟!!! :26: :26: حداقل یه نظر بدید !!!!!! :169:

 

[SABB]

پاسخ : ماراتن sgu , usaco

سلام.

برنامه م رو تست 2 WA میشه D:

#include <iostream>
using namespace std;


int n, u, v, best, V[16000];
pair<int, int> E[16000];
bool mark[16000];


int containing(int x, bool first, int s)
{
    mark[x] = true;
    s = 0;
    for(int i = 0; i < n - 1; i++)
            if(((E[i].first == x) && (!mark[E[i].second])) || ((E[i].second == x) && (!mark[E[i].first])))
            {
                   int newvertice = E[i].first;
                   if(E[i].first == x)
                                 newvertice = E[i].second;
                   int max = containing(newvertice, false, 0);
                   if(max)
                          s += max;
            }
    mark[x] = false;
    if(!first) return max(s + V[x], 0);
    if(first)  return s + V[x];
}


int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> V[i];
	for(int i = 0; i < n - 1; i++)
	{
		cin >> u >> v;
		E[i] = make_pair(u - 1, v - 1);
	}
	for(int i = 0; i < n; i++)
	{
            int max = containing(i, true, 0);
            if(max > best)
                   best = max;
    }
    cout << best << endl;
    //cin.get(); cin.get();
	return 0;
}

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

سلام.

برنامه م رو تست 2 wa میشه d:

#include <iostream>
using namespace std;


int n, u, v, best, v[16000];
pair<int, int> e[16000];
bool mark[16000];


int containing(int x, bool first, int s)
{
    mark[x] = true;
    s = 0;
    for(int i = 0; i < n - 1; i++)
            if(((e[i].first == x) && (!mark[e[i].second])) || ((e[i].second == x) && (!mark[e[i].first])))
            {
                   int newvertice = e[i].first;
                   if(e[i].first == x)
                                 newvertice = e[i].second;
                   int max = containing(newvertice, false, 0);
                   if(max)
                          s += max;
            }
    mark[x] = false;
    if(!first) return max(s + v[x], 0);
    if(first)  return s + v[x];
}


int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> v[i];
    for(int i = 0; i < n - 1; i++)
    {
        cin >> u >> v;
        e[i] = make_pair(u - 1, v - 1);
    }
    for(int i = 0; i < n; i++)
    {
            int max = containing(i, true, 0);
            if(max > best)
                   best = max;
    }
    cout << best << endl;
    //cin.get(); cin.get();
    return 0;
}

میشه اول الگوریتمت رو بگی ؟!؟!؟! :5::26:

پ.ن : ورود دوباره مون به سایت رو تبریک میگم :d:d

 

[SABB]

پاسخ : ماراتن sgu , usaco

برای هر راس ماکسیمم زیرگراف شامل اون راس رو در نظر گرفتم. بعد از اون ها ماکسیمم گرفتم.

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

برای هر راس ماکسیمم زیرگراف شامل اون راس رو در نظر گرفتم. بعد از اون ها ماکسیمم گرفتم.

دقیقا نفهمیدم تو کدت چیکار کردی !!!!!! اما بهتر بود به جای یه آرایه از pair ها یه وکتور از pair ها میگرفتی یا همون لیست مجاورت خودمون !!!!!!!! الان dfs زدی !؟!!!!؟! میشه بگی تو تابعت دقیقا چیکار کردی !!!!!!!!!!؟ :35:

 

[SABB]

پاسخ : ماراتن sgu , usaco

آره تو تابعه dfs‌ زدم. اومدم همه ی اونهایی که به این راسه x‌ وصلن رو حساب کردم اونهایی که مثبت بودنو با خود x جمع کردم که بشه ماکسیمم درختی که x توش هست.

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

آره تو تابعه dfs‌ زدم. اومدم همه ی اونهایی که به این راسه x‌ وصلن رو حساب کردم اونهایی که مثبت بودنو با خود x جمع کردم که بشه ماکسیمم درختی که x توش هست.

یه چیزی یادم رفت به سوال اضافه کنیم !!!!!! باید حتما یه شهرها انتخاب کنه !! یعنی اگه همه ی شهره منفی بودن ، کوچکترینش رو بده ..... من نمیدونم برنامه تو چجوری کامپایل کردی !!!!! یه دونه v و یه v[16000] داری !!!!!

 

[SABB]

پاسخ : ماراتن sgu , usaco

آره الان اون مشکلو حل کردم. ولی Time Limit‌میشه رو 7.

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

آره الان اون مشکلو حل کردم. ولی Time Limit‌میشه رو 7.

فکر کنم مشکل time limit شدنت اینه که روی هر راس داری dfs میزنی در حالی که میتونی 1 بار اینکار رو انجام بدی !!!! البته من bfs زدم اما فکر کنم میشه dfs هم زد !!!!!!!!!!

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

راه حل من با BFS :

از راس اول BFS میزنیم بعدش در حین BFS زدن صفشون هم تشکیل میدیم (یعنی ترتیب دیدن راس ها!!!!!) .... بعدش یه آرایه میگیریم که خونه ی a نشان دهنده ی بیشترین مجموع راس ها شامل راس i ام و زیردرخت آن می باشد ...... و داینامیک میزنیم !!!!!!!!!یعنی از آخر صف شروع میکنیم اگه عدد اون راس بزرگتر از صفر بود عدد اون راس رو به پدرش اضافه میکنیم (تو اون آرایهه !!!!!!!!!!) حالا کدشو بزنین دیگه !

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

نمیدونم چرا هیچ کسی همکاری نمیکنه !!!!! این بخش کامپیوتر رو قفل کنن ، هیچ کس نتونه پست بذاره ، بهتره !!!!!!!!!!!!!!!!!!!!!!!!!! اما ....

خوب هیچ کس که جواب سوال قبل رو نداد اما من کدم میزارم و سوال بعد رو تو پست بعدی ترجمه میکنم ......


این کد من واسه سوال 143 sgu هست :

143

See Code
​

 

[Olympiad]

پاسخ : ماراتن sgu , usaco

خوب یه نظر سنجی !!!!!!!! اینکه قانون ماراتن تغییر کنه و بشه همزمان بیش از 1 سوال حل نشده هم داشته باشیم !!!

نظرسنجی از الان شروع میشه و معلوم نیست کی تموم شه !!!!!!! اگه کمتر از 4 تا رای داشتیم این ماراتن جمع میشه !!! (تهدید) (تحدید) !!!!!!!!!!!!! :d


خوب من موافقم !!!!!!!!!!! :206:

 

[rezashiri]

پاسخ : ماراتن sgu , usaco

موافق ولی فکر نکنم به 4 تا برسه پس جمع کنیم بریم ...
راستی مرورگرم مشکل داره اصلا نمی تونم پست درست حسابی بذارم ...