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

[dousti_design]

با سلام.
مسابقات جهانی برنامه نویسی acm هر ساله در سطح جهان توسط شرکت ibm برگذار میشه.
هدف از برگذاری این مسابقات ایجاد رقابت بین دانشجویان سراسر جهان است. خوشبختانه این مسابقات در کشور ما هم به صورت جدی برگذار میشه و همه دانشجویان میتونن شرکت کنند.
من این تاپیک رو بنا به علاقه خودم و درخواست چند نفر از بچه ها زدم تا بتونیم اینجا مسئله های مسابقات رو بگذاریم، به روش های مختلف حل کنیم و برای مسابقات آماده بشیم.
توی این تاپیک سوالاتی رو قرار میدیم. روش های مختلف برای حلش رو بررسی و تحلیل میکنیم و اگر کسی مشکل یا سوالی داشت پاسخ میدیم(البته مورد آخر رو دوستان دیگه. چون من مبتدی هستم:لبخندساده: )
با همکاری و کمک همدیگه و با تلاش خودمون موفق میشیم:چشمک:

[dousti_design]

خب! اولین مسئله رو که خیلی خیلی هم ساده هست خودم میذارم.
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();
}

}

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

[accepted]

دوستان شدیدا توصیه میکنم که از زبان ++C استفاده کنید.
به جز روسیه، تقریبا همه تیمها از ++C استفاده میکنند. روسیه هم نمیدونم چرا چسبیدن به پاسکال، گویا بهش عادت دارن، وگرنه STL توی ++C تو پاسکال معادلی نداره و این کارشونو واقعا سخت میکنه. انتخاب ++C دلایل زیادی داره :
اول اینکه جاوا پوینتر نداره و این تو بعضی سوالا به شدت مشکل سازه. مثلا سوال E سال 2008 شریف رو تقریبا بدون پوینتر کاری کدش افتضاح میشه.
دوم اینکه جاوا خیلی به نسبت ++C کنده و تقریبا 1.5 برارش زمان میگیره. همون طور که میدونید time limit تو بعضی سوالا خیلی حساسه و 1.5 برابر، زمان خیلی زیادیه. البته تو بعضی سایتای online judge مقدار time limit رو برای کدهای java بیشتر در نظر میگیرند که این مشکل رو برطرف کنه ولی تو مسابقات از این خبرا نیست و محدودیت زمانی یکسانه.
جاوا فقط به درد بعضی سوالای خاص میخوره که از library ها و کدهایی که توش داره استفاده کنید تا کدتون راحت تر زده بشه که اینم فقط به درد سوالای BigInt میخوره که با جاوا راحت کد میشن ولی با ++C خودتون باید کلاسش رو بنویسید.
بازم دلیل هست ولی مهماش اینا بود. ضمنا کامپایلرتون هم آخرین ورژن mingw باشه ترجیحا. چون تو مسابقات کامپایلرشون اینه و این کامپایلر یه امکانات جالبی در اختیار برنامه نویس قرار میده که توی ++C استاندارد نیست. به عنوان مثال شما میتونید آرایه با سایز متغیر (!!!) بگیرید که در واقع این آرایه ها رو از حافظه دینامیک میگیره. (به جای استاتیک) که البته اگه لازمتون نباشه نباید این کار رو کرد ولی خوب مثلا برای پیاده سازی لیست مجاورت گراف، خیلی کاربرد داره.

[dousti_design]

ممنون از راهنماییتون. مرسی
دوستان میشه اینجا رو یه نگاهی بندازید؟
http://acm.timus.ru/problem.aspx?space=1&num=1484
من برنامشو نوشتم ولی برنامه من برای همون مثالی که آورده جوابش 90 هست. نمیدونم چرا!
کسی هست راهنماییم کنه؟ لطفا؟

[accepted]

ممنون از راهنماییتون. مرسی
دوستان میشه اینجا رو یه نگاهی بندازید؟
http://acm.timus.ru/problem.aspx?space=1&num=1484
من برنامشو نوشتم ولی برنامه من برای همون مثالی که آورده جوابش 90 هست. نمیدونم چرا!
کسی هست راهنماییم کنه؟ لطفا؟

the amount of (114 + p)/(12+p) should not be <=2, it should be <2.05

یه نیگاهی به Discuss (http://acm.timus.ru/forum/?space=1&num=1484) بنداز

[qwerty11]

سلام accepted جان. این سوالیه که چند وقتیه بدجور رفته رو مخم :

http://www.spoj.pl/problems/RENT/

راه حلی که پیچیدگی n^2 داره که کاری نداره اما برای accept گرفتن باید برنامت پیچیدگی n.log n باشه. تقریباً میدونم باید از یه چیزی مثل bbst استفاده کنما! اما نمیدونم چجوری! به هر کی هم میل زدیم جواب ما رو نداده :-/

ممنون از توجهت :)

[accepted]

تقریباً میدونم باید از یه چیزی مثل bbst استفاده کنما! اما نمیدونم چجوری!

منظورت از bbst چیه؟

[qwerty11]

binary balanced search tree دیگه

هیچ راهی به ذهن مبارکت خطور نمیکنه ؟ به نظر سوال راحتی میادا! اما نمیدونم چرا چیزی به ذهنم نمیرسه...

[accepted]

سلام accepted جان. این سوالیه که چند وقتیه بدجور رفته رو مخم :

http://www.spoj.pl/problems/RENT/

راه حلی که پیچیدگی n^2 داره که کاری نداره اما برای accept گرفتن باید برنامت پیچیدگی n.log n باشه. تقریباً میدونم باید از یه چیزی مثل bbst استفاده کنما! اما نمیدونم چجوری! به هر کی هم میل زدیم جواب ما رو نداده :-/

ممنون از توجهت :)

من یه راه با ( O( d+n پیدا کردم که داینامیکه

[qwerty11]

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

[dousti_design]

ببخشید من یه سوال راجع به مسئله خودم دارم:افسرده:
توی متن مسئله نوشته که باید یه کاری کنیم که x از y بزرگتر نشه. اینجا y مقدارش 2.0 هست(توی مثال).
حالا ما اگه بیاییم 86تا رای 1 درج کنیم x که 9.5 بود میشه 2.04 درسته؟
خب آخه گفته بزرگتر از 2 نشه:اشتباه:

[accepted]

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

نه منظورم بعد از سورتش بود. یعنی اردر داینامیکش d+n میشه. اردر کل سوال d+N*lg N میشه
اول order ها رو بر اساس زمان پایان مرتبشون میکنیم و میریزیم تو یه آرایه ای به نام order از خونه صفر تا n-1 . بعد یه آرایه d تایی به نام best دارم که [ best [ i میگه که اگه کلا از زمان صفر تا i مهلت داشته باشیم که اجاره بدیم (یعنی بعد از زمان i دیگه نتونیم اجاره بدیم) بیشترین سودی که میشه کرد چقدره؟
حتما قبول داری که 0 = [ best [ 0. حالا یه شمارنده به نام conter در نظر بگیر که شماره آخرین سفارش رو توش داره. پس اول کار برابر با صفره.
بقیه ش رو هم تو فایل ضمیمه ببین

[accepted]

ببخشید من یه سوال راجع به مسئله خودم دارم:افسرده:
توی متن مسئله نوشته که باید یه کاری کنیم که x از y بزرگتر نشه. اینجا y مقدارش 2.0 هست(توی مثال).
حالا ما اگه بیاییم 86تا رای 1 درج کنیم x که 9.5 بود میشه 2.04 درسته؟
خب آخه گفته بزرگتر از 2 نشه:اشتباه:
به صورت سوال دقت کن. گفته عددا رو گرد میکنه. یعنی 2.04 ~ 2.0
به توضیحی که راجع به نحوه گرد کردن داده دقت کن که رقمهای صدم و کوچکتر رو اگه به 5 صدم رسید، به عدد بزرگتر تقریب میزنه و اگر نرسید به عدد کوچکتر. مثلا:

2.0 ~ 2.04
2.1 ~ 2.05
2.1 ~ 2.066
2.0 ~ 2.049999999999

[Altech]

آقا این سایت برا من باز نمیشه . میشه روی سوال رو تو سایت بذارین ؟

[dousti_design]

آقا این سایت برا من باز نمیشه . میشه روی سوال رو تو سایت بذارین ؟
منظورتون کدوم سواله؟

[Altech]

خب! اولین مسئله رو که خیلی خیلی هم ساده هست خودم میذارم.
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();
}

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

حالا چرا بدون استفاده از عملگر جمع ؟
اون judger که نمی دونه شما از چه راهی حل کردی . اون فقط این انتظارو داره که به ازای فایل ورودی خودش دقیقا خروجی ایده آل حاصل بشه . دیگه اینکه با چه روشی حل کردین رو نمی دونه که . مگر اینکه Time اش مشکل داشته باشه .
این سوال فقط برا اینه که شما با نحوه submit کردن و اینا تو سایت آشنا بشین .
این کد هم accept شده :


#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << a + b << endl;
return 0;
}

منظورتون کدوم سواله؟

نه حل شد مرسی

[Altech]

من اصلا روی این سوال 1484 رو نفهمیدم . یعنی چی چندبار این کارو تکرار کنه که ریتینگ بیشتر از y نشه ؟

[farid_mov2006]

خب! اولین مسئله رو که خیلی خیلی هم ساده هست خودم میذارم.
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();
}

}

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

[Altech]

سلام
ببخشید کجاش گفته بدون استفاده از عملگر جمع؟:خجالت::گیج:

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

[dousti_design]

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

من اصلا روی این سوال 1484 رو نفهمیدم . یعنی چی چندبار این کارو تکرار کنه که ریتینگ بیشتر از y نشه ؟
والا اونطور که من فهمیدم یه نفر میخواد میانگین رای هارو توی سایت بیاره پایین تا برسه به y.
واسه این که این کار رو بکنه مجبوره چندین بار رای 1(min) رو درج کنه. حالا ما باید با دریافت ورودی تعیین کنیم که چند بار رای بده x(میانگین قبلی) میرسه به y(میانگینی که ما میخواهیم).
توی صورت مسئله گفته که اگر غیر ممکن بود چاپ کنه Impossible
ولی من نمیدونم کی غیر ممکن میشه؟:متفکر:

[dousti_design]

یک سوال:
دانشجویان دوره کارشناسی ارشد و بالاتر هم در مسابقات acm شرکت میکنند؟؟؟

[accepted]

یک سوال:
دانشجویان دوره کارشناسی ارشد و بالاتر هم در مسابقات acm شرکت میکنند؟؟؟

فایل ضمیمه رو ببین

[newamir]

نه منظورم بعد از سورتش بود. یعنی اردر داینامیکش d+n میشه. اردر کل سوال d+N*lg N میشه
اول order ها رو بر اساس زمان پایان مرتبشون میکنیم و میریزیم تو یه آرایه ای به نام order از خونه صفر تا n-1 . بعد یه آرایه d تایی به نام best دارم که [ best [ i میگه که اگه کلا از زمان صفر تا i مهلت داشته باشیم که اجاره بدیم (یعنی بعد از زمان i دیگه نتونیم اجاره بدیم) بیشترین سودی که میشه کرد چقدره؟
حتما قبول داری که 0 = [ best [ 0. حالا یه شمارنده به نام conter در نظر بگیر که شماره آخرین سفارش رو توش داره. پس اول کار برابر با صفره.
بقیه ش رو هم تو فایل ضمیمه ببین

این مسأله رو توی زمان اجرای (n*lg(n هم میشه حل کرد. به جای اینکه جدول داینامیک رو روی زمان بگیریم روی تعداد بازه ها میگیریم و هربار حساب میکنیم که اگر یک بازه باشد زمان اجرا بهتر میشود یا اگر نباشد. یک هزینه (lg(n برای پر کردن هرکدام از خانه های جدول صرف میشود. البته پیاده سازی اون از راه قبلی یه خورده سخت تره، و اگه قبلی accept شده خوب همون بهتره.

[a.gh.n]

توی صورت مسئله گفته که اگر غیر ممکن بود چاپ کنه Impossible
ولی من نمیدونم کی غیر ممکن میشه؟:متفکر:
احتمالا منظور اینه که خروجی به اضافه ی N باید در بازه ی N تعریف بشه.

[qwerty11]

این مسأله رو توی زمان اجرای (n*lg(n هم میشه حل کرد. به جای اینکه جدول داینامیک رو روی زمان بگیریم روی تعداد بازه ها میگیریم و هربار حساب میکنیم که اگر یک بازه باشد زمان اجرا بهتر میشود یا اگر نباشد. یک هزینه (lg(n برای پر کردن هرکدام از خانه های جدول صرف میشود. البته پیاده سازی اون از راه قبلی یه خورده سخت تره، و اگه قبلی accept شده خوب همون بهتره.
چه جالب :لبخند: آخه من راه حل قبلی رو که پیاده سازی کردم time limit گرفتم :ناراحت::ناراحت:
ممنون میشم اگه یکم بیشتر درباره ی نحوه ی پیاده سازیش توضیح بدین :لبخندساده::لبخندساده:

[accepted]

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

اگه time limit گرفتی، به خاطر اشتباه در پیاده سازیت بوده. این راه حل در زمان چند میلی ثانیه باید جواب بده. در حالی که time limit سوالهای ای.سی.ام در حدود ثانیه ست. (0.5 ، 1 ، 2 ثانیه)
احتمالا یه جا تو لوپ میفته

[saymon]

میشه لطفا به این سوال جوا ب بدین :
یافتن حداقل فاصله ی دونقطه یا مختصات دونقطه با کمترین فاصله به روش تقسیم وغلبه .این سوال clrs بوده یه چیزایی در موردش خوندم امابرای پیاده سازیه دقیقش مشکل دارم میشه منو راهنمایی کنید

[jlover]

سلام
من اتفاقی وارد این تالار شدم و به این تاپیک علاقه مند شدم و ...
Cipher Message 2
http://acm.timus.ru/forum/thread.aspx?space=1&num=1706&id=23887&upd=634057230736032500
همه ی کارایی که کردم تو این بحث آورده شده...
خوشحال میشم اگه کسی علاقه مند بود نظر بده ، دیگه واقعن بریدم :عصبانی++:

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

با تشکر

[aasmass]

ميشه تمنا کنم چندتا نمونه سوالacm رو با حل الگوريتم بذاريد؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟ ؟؟؟؟؟خواهش ميکنم

[qwerty11]

اینم به خاطر شما :

سوال : https://www.spoj.pl/problems/CLEANRBT/

جواب :


import java.io.*;
import java.util.*;
public class Main {
static int w[][],num;
static int dp[][];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int m,n;
while(true){
StringTokenizer st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
if(m==0 && n==0) break;
ArrayList<Integer> dirt=new ArrayList<Integer>();
int first=0;
char map[][]=new char[m][n];
for (int i = 0; i < m; i++) {
String s=br.readLine();
for (int j = 0; j < n; j++) {
if((map[i][j]=s.charAt(j))=='o'){
first=n*i+j;
dirt.add(0,first);
}
if(map[i][j]=='*') dirt.add(n*i+j);
}
}
w=new int[10][10];
int move[][]={{1,0},{-1,0},{0,1},{0,-1}};
num=dirt.size();
for (int i = 0; i < num; i++) {
boolean check[][]=new boolean[m][n];
LinkedList<Integer> q=new LinkedList<Integer>();
int pop=dirt.get(i),x=pop/n,y=pop%n,L=0;
q.add(pop);
check[x][y]=true;
while(!q.isEmpty()){
int l=q.size();
for (int k = 0; k < l; k++) {
pop=q.removeFirst();
x=pop/n; y=pop%n;
if(map[x][y]=='*' || map[x][y]=='o')
w[i][dirt.indexOf(n*x+y)]=L;
for (int j = 0; j < 4; j++) {
int X=x+move[j][0],Y=y+move[j][1];
if(X==-1 || X==m || Y==-1 || Y==n || check[X][Y] || map[x][y]=='x') continue;
q.add(n*X+Y);
check[X][Y]=true;
}
}
L++;
}
}
boolean bad=false;
for (int i = 0; i < num; i++) {
for (int j = i+1; j < num; j++) {
if(w[i][j]==0) bad=true;
}
}
if(bad){
System.out.println(-1);
continue;
}
dp=new int[num][1<<num];
for (int i = 0; i < num; i++) {
Arrays.fill(dp[i], -1);
}
System.out.println(f(0,(1<<num)-1));
}
}
static int f(int i,int j){
if(dp[i][j]!=-1) return dp[i][j];
if(j==1) return 0;
int min=100000;
for (int k = 1; k < num; k++) {
if((j&(1<<k))!=0)
min=Math.min(min, w[i][k]+f(k,j-(1<<k)));
}
return dp[i][j]=min;
}
}

[qwerty11]

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

سوال : https://www.spoj.pl/problems/BOTTOM/

جواب :


import java.io.*;
import java.util.*;
public class Main{
static Vector<Integer> g[]=new Vector[5000];
static Vector<Integer> gt[]=new Vector[5000];
static int time[]=new int [5000];
static boolean check[]=new boolean[5000];
static int find[]=new int [5000],index;
public static void main(String[] args) throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
PrintWriter out = new PrintWriter(System.out);
while(true){
in.nextToken();
int n=(int)in.nval;
if(n==0) break;
index=0;
in.nextToken();
int m=(int)in.nval;
for (int i = 0; i < n; i++) {
g[i]=new Vector<Integer>();
gt[i]=new Vector<Integer>();
}
for (int i = 0; i < m; i++) {
in.nextToken();
int a=(int)in.nval-1;
in.nextToken();
int b=(int)in.nval-1;
g[a].add(b);
gt[b].add(a);
}
for (int i = 0; i < n; i++) {
if(!check[i]) dfs1(i);
}
index=0;
for (int i = n-1; i>=0; i--) {
if(check[time[i]]) dfs2(time[i]);
index++;
}
boolean isSink[]=new boolean[n];
for (int i = 0; i < n; i++) {
if(isSink[find[i]]) continue;
for (int j = 0; j < g[i].size(); j++)
if(find[i]!=find[g[i].get(j)]){
isSink[find[i]]=true;
break;
}
}
for (int i = 0; i < n; i++) {
if(!isSink[find[i]])
out.print((i+1)+" ");;
}
out.println();
}
out.flush();
}
static void dfs1(int i){
check[i]=true;
int len=g[i].size(),x;
for (int j = 0; j < len; j++) {
x=g[i].get(j);
if(!check[x])
dfs1(x);
}
time[index++]=i;
}
static void dfs2(int i){
find[i]=index;
check[i]=false;
int len=gt[i].size(),x;
for (int j = 0; j < len; j++) {
x=gt[i].get(j);
if(check[x])
dfs2(x);
}
}
}

[hoseyn_hp]

با عرض سلام
بنده احتیاج به حل مسأله شماره 1253 یعنی markov trains دارم.
هر کسی که بتونه این مسأله رو حل کنه یا حلش رو پیدا کنه من تا آخر عمر مدیونش هستم.
این رو هم بگم که وقت زیادی ندارم.
التماس می کنم به کسانی که می تونند این مسأله رو حل کنند که کمکم کنند.
اینم لینکش:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1253
این برنامه حتما باید به زبان c یا c++ نوشته شود.
با تشکر

[مصطفی ساتکی]

هر کسی که بتونه این مسأله رو حل کنه یا حلش رو پیدا کنه من تا آخر عمر مدیونش هستم.
حداقل شما یه زحمتی می کشیدید سوال مورد نظرتون ترجمه می کردید و به صورت یه تاپیک عنوان می کردید تا افراد به شما جواب بدن .

[hoseyn_hp]

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

[DLL_DLL]

سوالاتشون به نظر من بیشتر ریاضی تا برنامه نویسی...
ممکنه یک برنامه نویس همه نوع syntax بلد باشه اما فرمول ندونه.
بنظره من بیشتر مسابقات ریاضی تا برنامه نویسی

[8611670474]

سلام.

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

لطفا اونایی که شرکت کردن جواب بدن.

مرسی

[qwerty11]

سلام،

به محیط ربطی نداره، به شما چند تا سوال میدن شما باید با استفاده از یکی از زبان های برنامه نویسی که میشه باهاش سوالات رو حل کرد اقدام به حل درست سوال بکنین. پس محیط اصلاً مهم نیست. اما همینو بگم که در مسابقات شریف اگر اشتباه نکنم توربو سی یابورلند سی ندارین و باید تو محیط هایی مثل visual c++ یا codeblocks یا dev c++ برنامتون رو بنویسین ...

تمام مباحث برنامه نویسی مهم هستن. و از همه جاش ممکنه سوال بیاد. مباحثی نظیر : گراف، برنامه نویسی پویا، الگوریتم های حریصانه، عقب گرد، هندسه و تمام مباحثی که مربوط به ریاضیات میشن.

جای هم فعلاً نباید ثبت نام کنید. مسابقه ی منطقه ای امسال آذر ماه برگزار میشه. هر دانشگاه چندتا سهمیه داره. فعلاً بهتره با کسانی از دانشگاهتون که رفتن شریف صحبت کنید. اما تمام نکات مربوط به ثبت نام رو هم میتونید تو سایت www.acmtehran.blogspot.com دنبال کنید...

[Salar Ashgi]

سوالاتشون به نظر من بیشتر ریاضی تا برنامه نویسی...
ممکنه یک برنامه نویس همه نوع syntax بلد باشه اما فرمول ندونه.
بنظره من بیشتر مسابقات ریاضی تا برنامه نویسی
به هیچ وجه اینطور نیست ، برنامه نویسی از ملزومات اصلی دانش هر برنامه نویس باید باشه ، اصلا
مگه بدون ریاضی برنامه نویسی ممکنه ؟!



تو چه محیطی کد مینویسن؟
محیط مهم نیست ، مهم زبان برنامه نویسی است ، که بیشتر ++C یا Java میباشد .
حالا وقتی شما ++C میدونید ، دیگه محیط یا کامپایلر براتون چه فرقی میکنه ، DEV باشه یا Borland یا
Turbo و ...



کدوم مباحث برنامه نویسی مهمتره؟
ببینید ، گروه ها معمولا 3 نفره اند که متشکل میشن از فردی که کد نویسیش خوبه ، فردی که ریاضیش
و قدرت تحلیل الگوریتمش خوبه و فردی که سوالارو ترجمه میکنه ! البته اینطور نیست که یه فردی فقط
مسئول ترجمه باشه ، بلکه ممکنه تو سایر قسمت ها هم مثل کدنویسی به سایر اعضا کمک خاصی
بکنه ولی این یه روال کلی کار بود .
مباحث هم بیشتر ، الگوریتم های ریاضیات گسسته هستن و به همین دلیل گروههایی موفق ترند که تو
گروهشون یه نفر باشه که از لحاظ طراحی الگوریتم در سطح Ultra و یه نفر هم از لحاظ کدنویسی و سرعت
عمل Ultra ! چون عموما تو چنین مسابقاتی سرعت عمل ، حرف اول رو میزنه !

[topline]

دوست عزیز بغیر از این دو این چند زبانی که اشاره کردی از زبان های دیگه ای هم میشه استفاده کرد مثلا C#

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

دوست عزیز بغیر از این دو این چند زبانی که اشاره کردی از زبان های دیگه ای هم میشه استفاده کرد مثلا C#

کدوم مسابقات منظورتونه که می‌شه از سی شارپ استفاده کرد؟ تا جایی که می‌دونم و دیدم، مسابقات منطقه‌ای سایت تهران این زبان را ساپرت نمی‌کنه. مسابقات جهانی هم همینطور.

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


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=problem&type=show&id=12041

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

با سلام
کسی میتونه در مورد این مسئله کمک کنه توضیح بدین چی می خواد
http://acm.hnu.cn/online/?action=problem&type=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 سال پيش) فهميدم كه روشو درست ترجمه نكردن، الان فقط خواستم به سوالي كه اون دوستمون (از خودش) مطرح كرده بود (بدون عمل جمع) جواب بدم. نه به سوال اي سي ام.

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