حل، درخواست و تمرین سوالهای مسابقات جهانی برنامه نویسی (ACM)

[shahmohammadi]

خب! اولین مسئله رو که خیلی خیلی هم ساده هست خودم میذارم.
http://acm.timus.ru/problem.aspx?space=1&num=1000
این مسئله جمع دو عدد بدون استفاده از عملگر جمع (+) هست.
روش های زیادی داره. من یه روشش رو که توی سایت هم سابمیت کردم و قبول کرد رو میذارم.

public class sum

{

    public static void main()

    {

        string[] tokens = Console.ReadLine().Split(' ');

        int temp = 0;

        int a = int.Parse(tokens[0]);

        int b = int.Parse(tokens[1]);

        if (a < b)

        {

            temp = a;

            a = b;

            b = temp;

        }

        temp = a - b;

        Console.WriteLine((a * 2) - temp);

        string s= Console.ReadLine();

    }

    

}

دوستان لطفا کسی راه حل دیگه ای برای حل این مسئله رو میتونه بذاره؟

جالب بود يعني به جاي a+b ازعبارت زير استفاده كنيم:
2a-(a-b)=
2a+(b-a)=a+a+b-a=a+b
ممنون

[mehran_darag]

سلام به همگی کسی میتونه این رو حل کنه؟؟؟؟؟؟؟ یه توضیح کوچولو هم اگه بدین خوب میشه.

Local Roots

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:

• 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نمادها است.

خروجی

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

[shahmohammadi]

سلام.
در مساله رشته یا کلمه 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:
عبارات تولید شده برای سطر اول:

1. 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 هست.

امیدوارم توضیحاتم کامل و واضح بوده باشه.

[akbar_online]

با سلام
کسی میتونه در مورد این مسئله کمک کنه توضیح بدین چی می خواد
http://acm.hnu.cn/online/?action=pro...=show&id=12041

[مسعود اقدسی فام]

با سلام
کسی میتونه در مورد این مسئله کمک کنه توضیح بدین چی می خواد
http://acm.hnu.cn/online/?action=pro...=show&id=12041

یه بازی که مجموعه‌ای از میله‌ها وجود دارن که داخلشون یه تعداد سنگ هست. می‌تونی مثل برج هانوی تصور کنی. البته شرایط برج هانوی رو نداره و لزوما سه تا هم نیست. این بازی دو تا مرحله داره. مرحله‌ی اول بازیکن اول می‌تونه صفر یا هر چند تا میله رو که دلش می‌خواد از بازی کنار بذاره. همینطور بازیکن دوم. فقط اینکه نمی‌تونن همه‌ی میله‌ها رو حذف کنن.
مرحله‌ی دوم با بازی نفر اول شروع می‌شه. اون باید یه میله از میله‌های باقیمونده رو انتخاب کنه و یک یا هر چند تا سنگ که دوس داره ازش برداره. بعد نفر دوم، دوباره نفر اول و ...
برنده کسی می‌شه که آخرین سنگ رو برداره و کل میله‌ها خالی بشن.
خروجی اینه که نفر اول در مرحله‌ی اول حداقل چند تا سنگ رو باید برداره تا مطمئن باشه حتما برنده می‌شه. البته این مساله که مرحله‌ی اول میله حذف می‌شه، و نه یه تعداد سنگ، خودش جای توجه داره.

[akbar_online]

یه بازی که مجموعه‌ای از میله‌ها وجود دارن که داخلشون یه تعداد سنگ هست. می‌تونی مثل برج هانوی تصور کنی. البته شرایط برج هانوی رو نداره و لزوما سه تا هم نیست. این بازی دو تا مرحله داره. مرحله‌ی اول بازیکن اول می‌تونه صفر یا هر چند تا میله رو که دلش می‌خواد از بازی کنار بذاره. همینطور بازیکن دوم. فقط اینکه نمی‌تونن همه‌ی میله‌ها رو حذف کنن.
مرحله‌ی دوم با بازی نفر اول شروع می‌شه. اون باید یه میله از میله‌های باقیمونده رو انتخاب کنه و یک یا هر چند تا سنگ که دوس داره ازش برداره. بعد نفر دوم، دوباره نفر اول و ...
برنده کسی می‌شه که آخرین سنگ رو برداره و کل میله‌ها خالی بشن.
خروجی اینه که نفر اول در مرحله‌ی اول حداقل چند تا سنگ رو باید برداره تا مطمئن باشه حتما برنده می‌شه. البته این مساله که مرحله‌ی اول میله حذف می‌شه، و نه یه تعداد سنگ، خودش جای توجه داره.

کسی دیگه نظری نداره

[akbar_online]

یه بازی که مجموعه‌ای از میله‌ها وجود دارن که داخلشون یه تعداد سنگ هست. می‌تونی مثل برج هانوی تصور کنی. البته شرایط برج هانوی رو نداره و لزوما سه تا هم نیست. این بازی دو تا مرحله داره. مرحله‌ی اول بازیکن اول می‌تونه صفر یا هر چند تا میله رو که دلش می‌خواد از بازی کنار بذاره. همینطور بازیکن دوم. فقط اینکه نمی‌تونن همه‌ی میله‌ها رو حذف کنن.
مرحله‌ی دوم با بازی نفر اول شروع می‌شه. اون باید یه میله از میله‌های باقیمونده رو انتخاب کنه و یک یا هر چند تا سنگ که دوس داره ازش برداره. بعد نفر دوم، دوباره نفر اول و ...
برنده کسی می‌شه که آخرین سنگ رو برداره و کل میله‌ها خالی بشن.
خروجی اینه که نفر اول در مرحله‌ی اول حداقل چند تا سنگ رو باید برداره تا مطمئن باشه حتما برنده می‌شه. البته این مساله که مرحله‌ی اول میله حذف می‌شه، و نه یه تعداد سنگ، خودش جای توجه داره.

الگوریتم این چجوری باید باشه

[akbar_online]

کسی میتونه این رو حل کنه یه توضیح بدین
بعضی از اعداد را می توان به صورت مجموع یک یا تعدادی اعداد اول متوالی و متمایز نوشت. برای مثال عدد 15 را می توان بصورت 15=7+5+3 بیان کرد. در ورودی عدد صحیح و مثبت n که در آن 100000=>n داده می شود در خروجی باید تعداد روشهایی که می توان n را به صورت مجموع یک یا تعدادی عدد اول متوالی و متمایز نوشت را چاپ کنید
ورودی
ورودی شامل چند آزمون است.در سطر اول ورودی تعداد آزمون ها می آید.به ازای هر تست یک عدد صحیح و مثبت n که از 10 به توان 5 بیشتر نیست می آید
خروجی
به ازای هر تست باید جواب مسئله را در یک سطر جدا چاپ کنید
مثال:
ورودی نمونه
2تست
3
17
خروجی نمونه
1
2

[shahmohammadi]

خب! اولین مسئله رو که خیلی خیلی هم ساده هست خودم میذارم.
http://acm.timus.ru/problem.aspx?space=1&num=1000
این مسئله جمع دو عدد بدون استفاده از عملگر جمع (+) هست.
روش های زیادی داره. من یه روشش رو که توی سایت هم سابمیت کردم و قبول کرد رو میذارم.

public class sum

{

    public static void main()

    {

        string[] tokens = Console.ReadLine().Split(' ');

        int temp = 0;

        int a = int.Parse(tokens[0]);

        int b = int.Parse(tokens[1]);

        if (a < b)

        {

            temp = a;

            a = b;

            b = temp;

        }

        temp = a - b;

        Console.WriteLine((a * 2) - temp);

        string s= Console.ReadLine();

    }

    

}

دوستان لطفا کسی راه حل دیگه ای برای حل این مسئله رو میتونه بذاره؟

حالا كه مي شه از منها استفاده كرد، خوب از كد زير هم مي شه استفاده كرد:

int a,b;

cin>>a>>b;

cout<<a-(-b);

اين پست رو خيلي وقت پيش ديده بودم ولي الان يادم افتاد كه اينم ميشه.

[مسعود اقدسی فام]

حالا كه مي شه از منها استفاده كرد، خوب از كد زير هم مي شه استفاده كرد:

int a,b;

cin>>a>>b;

cout<<a-(-b);

اين پست رو خيلي وقت پيش ديده بودم ولي الان يادم افتاد كه اينم ميشه.

اون سوال نوشته "Use + operator". یعنی از + استفاده کنید! این یه سوال ساده هستش که صرفا روش کار مسابقات رو با شرکت کنندگان یاد می‌ده و به عنوان یه سوال تست اول هر مسابقه‌ی رسمی باید حل بشه. حتی خود ACM یا مسابقات بیان و اینا.

اینکه از کجا در آوردید بدون عملگر + باید باشه و اینکه اصلا اون سیستم داور چطور می‌خواد تشخیص بده ما از جمع استفاده کردیم یا نه برام جالبه.

همونطور که می‌دونید برای تست برنامه یه سری داده ورودی به برنامه داده می‌شه و خروجی با خروجی‌های مورد انتظار مقایسه می‌شه. اگه همگی درست باشن یعنی کد درست کار می‌کنه. خب حالا از حاصل جمع اعداد که خروجی این برنامه هستش چطور می‌خواد بفهمه که از + استفاده شده یا نه؟

یعنی یه سیستم هوشمند هم واسه کد کار می‌ذارن که علامت‌های + رو یکی یکی بررسی کنه که آیا برای جمع دو عدد برای تولید خروجی استفاده شده یا صرفا یه علامت رو مشخص می‌کنه یا دو تا رشته رو جمع زده و به خروجی ربطی نداره و یا قسمتی از ++ هستش و یا ... ؟؟؟

لطفا هم به روی سوال دقیق توجه کنید و هم اینکه فکر کنید چطور می‌شه اون نیت رو داشته باشه.

این کد جواب اونجاست:

#include<iostream>



int main()

{

 int a,b;

 std::cin>>a>>b;

 std::cout<<a+b;

 return 0;

}

به همین سادگی.

[shahmohammadi]

من هم توي اون سايت با همين روشي كه الان شما نوشتيد مساله رو حل كرده بودم.
همون دفعه ي اولي كه خوندم (1 سال پيش) فهميدم كه روشو درست ترجمه نكردن، الان فقط خواستم به سوالي كه اون دوستمون (از خودش) مطرح كرده بود (بدون عمل جمع) جواب بدم. نه به سوال اي سي ام.

[مسعود اقدسی فام]

من هم توي اون سايت با همين روشي كه الان شما نوشتيد مساله رو حل كرده بودم.
همون دفعه ي اولي كه خوندم (1 سال پيش) فهميدم كه روشو درست ترجمه نكردن، الان فقط خواستم به سوالي كه اون دوستمون (از خودش) مطرح كرده بود (بدون عمل جمع) جواب بدم. نه به سوال اي سي ام.

نه من روی صحبتم شما نبودید. حواسم نبود چی رو نقل قول کرده. دوستی که اشتباه ترجمه کرده مد نظرم بود. شما صرفا به قول خودتون برای ترجمه‌ی اشتباه ایشون یه راه خیلی ساده‌تر نوشته بودید. :)