سوال ۴ روز اول: رنگ‌آمیزی بازه‌های روی محور اعداد حقیقی با هر رنگی که با یک عدد طبیعی شناخته می‌شود
سوال 1 روز دوم: مرتب کردن دنباله‌ي A در کم‌ترین تعداد مرحله
سوال 2 روز دوم: تقسیم شهرها به دو دسته به طوری که جاده‌های درون هر دسته آسفالت باشد
سوال 3 روز دوم: شکار خرگوش نامرئی بعد از حداکثر 10000 شلیک
یک مربع بزرگ را در نظر بگیرید. در داخل آن 1389 ...
2010 عدد طبیعی دلخواه نه لزوما متمایز کوچکتر از $2^1389$ را...
در یک شبکه 3x3 نقطه ای ، بین هر دو نقطه مجاور ...
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
فرض کنید $w_n$,⋯,$w_1$ رشته‌هایی متمایز با حروف انگلیسی کوچک باشند که مجموع طول آن‌ها از $Q$ تجاوز نمی‌کند. $W$ را نیز یک رشته انگلیسی دلخواه با طول $Q$ در نظر بگیرید.
عدد $a_i$ (که $i$=۱,⋯,$n$ است) را برابر تعداد ظاهرشدن رشته $w_i$ در $W$ تعریف میکنیم. به عنوان مثال، اگر $w_1=ab$، $w_2=aca$٬ $w_3=bb$ و $W=abcabbb$ باشند، آنگاه $a_1 = 2$، $a_2 = 0$ و $a_3 = 2$ خواهد بود.
ثابت کنید:
$$min(a_1,a_2,⋯,a_n)\le \frac{2 \times Q \times \sqrt {Q}}n$$
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:15:22 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:23:19 -0500 امیر شکریاگه مینیمم از اون عبارت بیشتر باشه در این صورت $\sum{a_{i}} > 2Q\sqrt{Q}$ .
حال سعی میکنیم ماکسیمم مقدار $\sum{a_{i}}$ را بدست آوریم.
رشته ها را دسته بندی میکنیم به طوری که رشته های به طول $i$ را در دسته ی $s_{i}$ قرار میدهیم.
اگر ماکسیمم تعداد دسته های را x بگیریم $x(x+1)/2 \le Q$ که از اینجا بدست میاید $x \le \sqrt{2Q}$ .
هر دسته $s_{i}$ حداکثر مجموع اعداد اعضایش $Q-i+1$ است و هرچه i کمتر باشد این تعداد بیشتر خواهد شد پس ماکسیمم مقدار $\sum{a_{i}}$ برابر است با:
${Q+1 \choose 2}-{Q-x \choose 2} \le \frac{2Qx+x}{2} \le 2Q \sqrt{Q}$
که اگر اشتباه محاسباتی نداشته باشم حکم مسئله را ثابت میکند.
یه نکته ی خیلی ضریف توی محساباتت اینه که یکی از اون نامساویا برای q > 1 درسته . بهتره مثلا q = 1 رو بنویسیم واضح است .
2022-05-03 09:21:27 -0500 محمدعرفان گونه