سلام به همگی کسی میتونه این رو حل کنه؟؟؟؟؟؟؟ یه توضیح کوچولو هم اگه بدین خوب میشه.
Consider a word w consisting of n symbols. We can decompose it at point i (1 ≤ i ≤ n − 1) into a prefix p of length i and a suffix s of length n − i. Local root of a word w at point i is a non-empty word r such that:Local Roots
- p is a suffix of r, or r is a suffix of p, or r is equal to p;
- s is a prefix of r, or r is a prefix of s, or r is equal to s;
- r has minimal possible length.
Your goal is to find such a point that the length of local root at this point is maximal possible.
Input
The only line contains a word w consisting of lowercase English letters. Its length is at least two and at most 300 000 symbols.
Output
Output the required point of decomposition and the length of local root at this point. If there are several possible answers, output any of them.
ریشه های محلی:W کلمه متشکل از نمادهای N را در نظر بگیرید.ما می توانیم آن را در نقطه تجزیه (1 ≤i ≤ N - 1) به پیشوند P از طول i و یک پسوندs ازطولN -i ریشه محلی W کلمه در نقطه i یک کلمه غیر تهی R هستبه طوری که:P پسوندR است، و یا R پسوندP است ، یا R بهP برابر است؛s یک پیشوندR، R یک پیشوند از S یاR تا S برابر است؛R دارای طول حداکثر ممکن است.هدف شما پیدا کردن یک نقطه که طول ریشه های محلی در این مرحله حداکثر ممکن است.ورودیخط تنها حاوی W کلمه متشکل از حروف کوچک انگلیسی. طول آن حداقل 2 و حداکثر 300000نمادها است.خروجیخروجی نقطه مورد نیاز از تجزیه و طول ریشه های محلی در این نقطه. اگر چندین جواب ممکن است ، خروجی هر کدام از آنها وجود دارد.
آخرین ویرایش به وسیله mehran_darag : جمعه 11 آذر 1390 در 16:26 عصر
سلام.
در مساله رشته یا کلمه w شامل n حرف داده شده.
- p is a suffix of r, or r is a suffix of p, or r is equal to p;
- s is a prefix of r, or r is a prefix of s, or r is equal to s;
- r has minimal possible lengt
برای حلش از هر دو سطر اول و دوم یکی از شرایط باید رعایت شه. و تعداد بینهایت رشته برای هر کدوم تولید میشه. که اشتراک عبارات تولید شده برای اولی و دومی تعداد کمی کلمه می شه. حالا بنا به سطر آخر کوچکترین کلمه می شه ریشه محلی در نقطه i.
اگه i حرف اول رو تو p بذاریم و بقیه رو تو s:
عبارات تولید شده برای سطر اول:
- p پسوند r هست: در این صورت r شامل تمام رشته های زیر هست: (به جای ... هر چیزی می تونید بذازید)
...p
2. r پسوند p هست:
p=...r
3. r=p
برای سطر دوم:
1. s پیشوند r هست:
r=s...
2. r پیشوند s باشه:
s=r...
3. r=s
حالا اشتراک سطر اول و دوم می شه تعدادی کلمه که کوچکترین اونها می شه r تو نقطه i. مساله می خاد ما r رو برای تمام i ها بدست بیاریم و بزرگترینشو انتخاب کنیم.
برای اینکه واضح تر بشه یه مثال می زنم:
w=aababaaa
i=5
p=aabab , s=aaa
r=...aabab (1) or aabab=...r (2) or r=aabab (3)
and
r=aaa... (10) or aaa=r... (20) or r=aaa (30)
عباراتی که از 2 برای r نتیجه میشه: r=b,r=ab,r=bab,r=abab
عباراتی که از 20 نتیجه میشه: r=a,r=aa
کوتاه ترین عبارتی که تو 1 و 10 صدق کنه r=aaabab هست.
با توجه به "یا"ها و "و"ها کوتاهترین عبارتیکه میشه تولید کرد r=aaabab هست.
امیدوارم توضیحاتم کامل و واضح بوده باشه.
آخرین ویرایش به وسیله shahmohammadi : شنبه 19 آذر 1390 در 01:59 صبح
با سلام
کسی میتونه در مورد این مسئله کمک کنه توضیح بدین چی می خواد
http://acm.hnu.cn/online/?action=pro...=show&id=12041
یه بازی که مجموعهای از میلهها وجود دارن که داخلشون یه تعداد سنگ هست. میتونی مثل برج هانوی تصور کنی. البته شرایط برج هانوی رو نداره و لزوما سه تا هم نیست. این بازی دو تا مرحله داره. مرحلهی اول بازیکن اول میتونه صفر یا هر چند تا میله رو که دلش میخواد از بازی کنار بذاره. همینطور بازیکن دوم. فقط اینکه نمیتونن همهی میلهها رو حذف کنن.
مرحلهی دوم با بازی نفر اول شروع میشه. اون باید یه میله از میلههای باقیمونده رو انتخاب کنه و یک یا هر چند تا سنگ که دوس داره ازش برداره. بعد نفر دوم، دوباره نفر اول و ...
برنده کسی میشه که آخرین سنگ رو برداره و کل میلهها خالی بشن.
خروجی اینه که نفر اول در مرحلهی اول حداقل چند تا سنگ رو باید برداره تا مطمئن باشه حتما برنده میشه. البته این مساله که مرحلهی اول میله حذف میشه، و نه یه تعداد سنگ، خودش جای توجه داره.
کسی میتونه این رو حل کنه یه توضیح بدین
بعضی از اعداد را می توان به صورت مجموع یک یا تعدادی اعداد اول متوالی و متمایز نوشت. برای مثال عدد 15 را می توان بصورت 15=7+5+3 بیان کرد. در ورودی عدد صحیح و مثبت n که در آن 100000=>n داده می شود در خروجی باید تعداد روشهایی که می توان n را به صورت مجموع یک یا تعدادی عدد اول متوالی و متمایز نوشت را چاپ کنید
ورودی
ورودی شامل چند آزمون است.در سطر اول ورودی تعداد آزمون ها می آید.به ازای هر تست یک عدد صحیح و مثبت n که از 10 به توان 5 بیشتر نیست می آید
خروجی
به ازای هر تست باید جواب مسئله را در یک سطر جدا چاپ کنید
مثال:
ورودی نمونه
2تست
3
17
خروجی نمونه
1
2
اون سوال نوشته "Use + operator". یعنی از + استفاده کنید! این یه سوال ساده هستش که صرفا روش کار مسابقات رو با شرکت کنندگان یاد میده و به عنوان یه سوال تست اول هر مسابقهی رسمی باید حل بشه. حتی خود ACM یا مسابقات بیان و اینا.
اینکه از کجا در آوردید بدون عملگر + باید باشه و اینکه اصلا اون سیستم داور چطور میخواد تشخیص بده ما از جمع استفاده کردیم یا نه برام جالبه.
همونطور که میدونید برای تست برنامه یه سری داده ورودی به برنامه داده میشه و خروجی با خروجیهای مورد انتظار مقایسه میشه. اگه همگی درست باشن یعنی کد درست کار میکنه. خب حالا از حاصل جمع اعداد که خروجی این برنامه هستش چطور میخواد بفهمه که از + استفاده شده یا نه؟
یعنی یه سیستم هوشمند هم واسه کد کار میذارن که علامتهای + رو یکی یکی بررسی کنه که آیا برای جمع دو عدد برای تولید خروجی استفاده شده یا صرفا یه علامت رو مشخص میکنه یا دو تا رشته رو جمع زده و به خروجی ربطی نداره و یا قسمتی از ++ هستش و یا ... ؟؟؟
لطفا هم به روی سوال دقیق توجه کنید و هم اینکه فکر کنید چطور میشه اون نیت رو داشته باشه.
این کد جواب اونجاست:
#include<iostream>
int main()
{
int a,b;
std::cin>>a>>b;
std::cout<<a+b;
return 0;
}
به همین سادگی.
آخرین ویرایش به وسیله مسعود اقدسی فام : جمعه 26 آبان 1391 در 11:53 صبح
من هم توي اون سايت با همين روشي كه الان شما نوشتيد مساله رو حل كرده بودم.
همون دفعه ي اولي كه خوندم (1 سال پيش) فهميدم كه روشو درست ترجمه نكردن، الان فقط خواستم به سوالي كه اون دوستمون (از خودش) مطرح كرده بود (بدون عمل جمع) جواب بدم. نه به سوال اي سي ام.
کاربر دائمی