آرشیو سوالات از گذشته تا کنون

[Dark Eagle]

پاسخ : آرشیو سوالات از گذشته تا کنون

ورودی رو به صورت یه آرایه ی <pair <int, int بگیر sort اِش کن یکمم فک کن حل میشه

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

 

[daneshvar.amrollahi]

پاسخ : آرشیو سوالات از گذشته تا کنون

سلام. من یه مقدماتی ام. تو بخش ۱.۱ سوال دومش رو نمیفهمم چی میخواد. ورودیش به چه ترتیبیه؟
http://cerberus.delos.com:790/usacoprob2?a=anup2nqYo43&S=gift1
سوال Greedy Gift
یه نفر سوالش رو فارسی هم توضیح بده راضیم چون فکر می کنم این سوال رو بتونم خودم حل کنم (اونقد دیگه خنگ نیستم!)

 

[Dark Eagle]

پاسخ : آرشیو سوالات از گذشته تا کنون

وقتی میری تو یوساکو اون بالا سمت راست نوشته change language برو توش بزن Persian ...
ولی فقط تا chapter 2 ترجمه کردن ... تا یه مدت خوبی کارتو راه میندازه بعد از اونم خودت دیگه می تونی ترجمه کنی

فقط یکم ترجمش بده یه جاهاشم غلطه ... خودت با اصلی مطابقت بدی میفهمی سوالو ...

 

[daneshvar.amrollahi]

پاسخ : آرشیو سوالات از گذشته تا کنون

وقتی میری تو یوساکو اون بالا سمت راست نوشته change language برو توش بزن Persian ...
ولی فقط تا chapter 2 ترجمه کردن ... تا یه مدت خوبی کارتو راه میندازه بعد از اونم خودت دیگه می تونی ترجمه کنی

فقط یکم ترجمش بده یه جاهاشم غلطه ... خودت با اصلی مطابقت بدی میفهمی سوالو ...

کلا ۶-۷ تا زبون داره که جالبه یکیش فارسیه! نمیدونستم این قابلیت رو. ممنون

 

[senator77]

پاسخ : آرشیو سوالات از گذشته تا کنون

سلام
یک سوال تخصصی
توی سوال 135http://acm.sgu.ru/problem.php?contest=0&problem=135

اولا میشه ثابت کرد که اگه ما n-1 خط داشته باشیم و x ناحیه تشکیل بشه وقتی که ما خط n ام رو اضافه میکنیم تعداد ناحیه های ما میشه x+n
با استقرا راحت میشه ثابت کرد

بعد دیگه سوالش آب خوردن میشه 5 خط کد

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

یکی هم غیر بازگشتی که کد من اینه

cout << (x*(x+1)/2)+1 << endl;

ولی میگه توی 21 امین جوابت غلطه میشه بگید چرا غلطه؟

 

[The Smith]

پاسخ : آرشیو سوالات از گذشته تا کنون

کف و سقف رو درست میگیری ؟

 

[senator77]

پاسخ : آرشیو سوالات از گذشته تا کنون

کف و سقف رو درست میگیری ؟

آها فهمیدم چرا غلطه مر30
چون اول n رو ضربب در n+1 میکنه و سقفش ی جوریه که از int میزنه بیرون دیگه بقیه عملیات رو درست انجام نمیده
long int باید میزاشتم
بازم مرسی

 

[mhnp]

پاسخ : آرشیو سوالات از گذشته تا کنون

از if و > < ==نمیتونین استفاده کنین

 

[The Smith]

پاسخ : آرشیو سوالات از گذشته تا کنون

#include <iostream>

using namespace std;

int main () {
	int a, b;
	cin >> a >> b;
	int ans = a - ((a - b) & ((a - b) >> (sizeof (int) * 8 - 1)));
	cout << ans << endl;
	return 0;
}

یکی دو جا هم که سرچ کردم
دیدم همین راهشون بود
تو سایت stackoverflow یه سری راه دیگه هم بود که سر در نیاوردم چیزی ازشون من.

 

[sara.speed]

پاسخ : آرشیو سوالات از گذشته تا کنون

سلام

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

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

قوانین

1.نمره و وقت هر سوال زیر سوال نوشته شده

2.بعضی از سوال ها چند قسمت دارن که هر قسمت رو اگه حل کنید نمره اون قسمت رو فقط میگیرید

3.اسپم ممنوع

4.جواب رو طوری بنویسید که حداقل من قانع شم فکر کنید من یکی از داور های مرحله دو هستم و میخوایید واسه اونا بنویسید

5.فعلا همین

رتبه بندی و امتیازات

رتبه نام کاربری امتیاز بر اساس نمره سوالات

1 s20 ๖ۣۜStefan

 

[The Smith]

پاسخ : آرشیو سوالات از گذشته تا کنون

من موافقم ولی صرفا برای حل سوال

 

[senator77]

پاسخ : آرشیو سوالات از گذشته تا کنون

منم هستم

 

[m.m.r]

پاسخ : آرشیو سوالات از گذشته تا کنون

سلام
منم اگه خدا عمر بده هستم

 

[Anita H]

پاسخ : آرشیو سوالات از گذشته تا کنون

منم
:-منتظر سوال اول

 

[sara.speed]

پاسخ : آرشیو سوالات از گذشته تا کنون

خب با اینکه کم هستیم ولی شروع میکنیم تا شاید بیشتر شدیم

سوال اول:

در کشور عجایب تعدادی شهر ک یکی از آنها پایتخت است و تعدادی جاده هم بین آنها وجود دارد,وجود دارد-میدانیم از هر شهر مسیری به پایتخت

وجود دارد-به زیر مجموعه ای از جاده ها نقشه میگوییم اگر و فقط اگر دو شرط زیر را داشته باشد

الف)با این جاده ها از هر شهر مسیری به سوی پایتخت وجود داشته باشد

ب)با حذف هر یک از جاده ها شرط الف دیگر برقرار نباشد

در یک نقشه یک شهر غیر پایتخت را تنها میگوییم اگر در نقشه فقط و فقط با یک شهر در تماس باشد و مسیری مستقیم به سوی فقط یک

شهر داشته باشد- در یک نقشه فاصله ی هر شهر تا پایتخت برابر است با تعداد جاده هایی که باید طی کرد تا به پایتخت رسید

هزینه ی یک نقشه برابر است با مجموع فواصل شهر های تنها تا پایتخت

یک نقشه قابل ساخت است اگر و فقط اگر در بین همه ی نقشه ها کمترین هزینه را داشته باشد(ممکن است بیش از یک نقشه قابل ساخت باشد)

ثابت کنید نقشه ی قابل ساختی وجود دارد که بین هیچ کدام از بین شهر های تنهای آن جاده ای(از بین جاده های نقشه یا سایر جاده ها) وجود ندارد

"نمره این سوال:20 نمره"
"وقت این سوال:3 روز"

 

[Dark Eagle]

پاسخ : آرشیو سوالات از گذشته تا کنون

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

میدانیم از هر شهر مسیری به پایتخت وجود دارد --> گراف همبند است.
از دو شرط الف و ب نتیجه می شود که هر نقشه یک درخت بوده و شهر های تنها برگ های آن درخت هستند ...

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

لم 1 : در هر درخت بین 2 راس یک و تنها یک مسیر وجود دارد ...
اثبات : در غیر این صورت دور ایجاد می شود و درخت دارای دور نیست ...


الگوریتم : 2 تا از برگ هایی را که به هم متصل هستند را در نظر گرفته آن ها را A و B می نامیم ... (ارتفاع A => ارتفاع B)

اولین پدر مشترک دو راس A و B را C نام می نهیم ...

یال بین A و B را اضافه می کنیم ...
طبق لم 1: مسیر بین B و C را در نظر میگیریم ...
یالی که این مسیر را به راس C متصل می کند را پاک می کنیم و ادامه می رهیم ...

حال باید 2 چیز را ثابت کنیم ....

1- با انجام الگوریتم فوق هزینه ثابت می ماند ...

هزینه ی قبل از انجام الگوریتم = ارتفاع A + ارتفاع B
هزینه ی بعد از انجام الگوریتم = ارتفاع A + اندازه ی مسیر B تا C

کاملا آشکار است که اندازه ی مسیر B تا C بیشتر از ارتفاع آن نیست ...
در ضمن ... اگر راس C راسی به جز پایتخت باشد هزینه ی ساخت کم تر می شود و این خلاف فرض است ...

2- باید ثابت کنیم الگوریتم فوق پایان پذیر است ...

به هر راس به روش زیر یک عدد نسبت می دهیم ... عدد یک راس با ارتفاع i برابر 2 به توان i می باشد ...
عدد افسردگی یک راس برابر مجموع اعداد نسبت داده شده بر روی راس های تنهای آن است ...

چون 3 به توان i از مجموع توان های کوچکتر 3 بزرگتر است در نتیجه با انجام الگوریتم فوق عدد افسردگی نقشه ی مذکور افزایش می یابد ...
این عدد حداکثر می تواند 3 به توان تعداد راس ها باشد ...

در نتیجه الگوریتم فوق پایان پذیر است ...

د.پ : ببخشید اگه زود جواب رو گفتم ... دلایل شخصی دارم واسش

 

[sara.speed]

پاسخ : آرشیو سوالات از گذشته تا کنون

با تبریک ب اونایی که قبول شدن-ایشالا منم سال بعد سوال بعدی رو میگم

سوال دوم:

بازی باستانی چهارچنگولی این طور انجام میشود:دو بازیکن در بازی شرکت دارند در یک لحطه هریک از آنها یک دو یا سه انگشت خود را بلند میکند
و هر دو همزمان میگویند که رقیب چه عددی را نشان داده است اگر هر دو نفر درست یا هر دو نفر نادرست گفته باشند بازی مساوی میشود اگر
یک نفر درست ویک نفر نادرست گفته باشد کسی که نادرست گفته است باید به اندازه ی تعداد کل انگشتان نشان داده شده دلار بپردازد اگر در این بازی شرکت کنید بهترین راه کارتون چه خواهد بود؟

اگه درست بگید نمره سوال: 15+
اگه غلط بگید:5-
زمان سوال:سه روز

 

[sara.speed]

پاسخ : آرشیو سوالات از گذشته تا کنون

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

 

[sara.speed]

پاسخ : آرشیو سوالات از گذشته تا کنون

مث این که این تایپیک هم خوابید

#یکی بیاد اینجارو قفل کنه

 

[Anita H]

پاسخ : آرشیو سوالات از گذشته تا کنون

Max(a, b)=(abs(a-b)+a+b)/2

اگر a>b باشد، مقدار قدر مطلق برابر a-b خواهد بود که -b با +b ساده میشه و...
اگر a<b باشد، مقدار قدر مطلق برابر b-a خواهد که +a با -a ساده میشه و...
اگر a=b باشد، تابع قدر مطلق، 0 برمیگرداند و a+b=2a که 2 ها با هم ساده میشن و...