سوال ACM غزب آسیا دانشگاه شریف

[Golden Galaxy]

سلام دوستان

یک برنامه نوشتم که دیدم جالبه در موردش بحث کنیم . این سوال مسابقات ACM غرب آسیاست .

کاربر به شما دو عدد تک رقمی می دهد که اولی رقم یکان یک عدد نا معلو م و دومی یک عدد تک رقمی است .
حالا برنامه شما باید یک عدد int پیدا کند که رقم یکانش آن عدد اول باشد و هنگامی که در عدد تک رقمی دوم ضرب می شود رقم یکان به آخر عدد منتقل شود و اگر پیدا نکرد صفر برگرداند .

مثال : عدد اول به عنوان رقم یکان : 5 / ********* / عدد دوم به عنوان ضریب : 4

عددی که برنامه بر می گرداند : 128205 / ******** / زیرا : 512820 = 4 * 128205

* در موردش فکر کنید ولی فکر نکنید باید همه اعداد رو چک کرد *

[mohandese_hiclass]

سوال d acm بود که رنگه باد کنکشم زرد بود درسته ما تو مسابقات این سوالو حل کردیم سوال ساده ای ولی خوبه روش بحث بشه نمی گم تا بحث بشه

[someCoder]

خاک تو سر ما که وقتی 10 دقیقه به آخر وقت رسیده بود تازه فهمیدیم قضیه چی بوده و هرگز جواب درست رو submit نکردیم! :(((((((((((((
اما خداییش سوالات امسال اصلا باحال نبود! (در مقایسه با مناطق دیگه)

[mohandese_hiclass]

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

[Mahdi_Delphi]

ببخشید که میپرم وسط ولی این امتحانات بصورت آنلاین هست؟
کی و چه جوری میشه ثبت نام کرد ؟

[mohandese_hiclass]

ببخشید که میپرم وسط ولی این امتحانات بصورت آنلاین هست؟
کی و چه جوری میشه ثبت نام کرد ؟

یکسری مسابقات هم تو دانشگاه شریف و بین دانشگاها برگزار میشه البته تیمهایی هم از کشورهای غرب آسیا می یان که دو تیم برتر میره مسابقات جهانی

[ms1024]

سلام دوستان

یک برنامه نوشتم که دیدم جالبه در موردش بحث کنیم . این سوال مسابقات ACM غرب آسیاست .

کاربر به شما دو عدد تک رقمی می دهد که اولی رقم یکان یک عدد نا معلو م و دومی یک عدد تک رقمی است .
حالا برنامه شما باید یک عدد int پیدا کند که رقم یکانش آن عدد اول باشد و هنگامی که در عدد تک رقمی دوم ضرب می شود رقم یکان به آخر عدد منتقل شود و اگر پیدا نکرد صفر برگرداند .

مثال : عدد اول به عنوان رقم یکان : 5 / ********* / عدد دوم به عنوان ضریب : 4

عددی که برنامه بر می گرداند : 128205 / ******** / زیرا : 512820 = 4 * 128205

* در موردش فکر کنید ولی فکر نکنید باید همه اعداد رو چک کرد *
جواب من:
Z=ضریب
Y=رقم یکان عدد مورد نظر
باید اول Z رو در Y ضرب کنیم
بعد Z رو در رقم یکان عدد به دست آمده ضرب کنیم و با رقم دهگان جمع کنیم و همین طور ادامه بدیم تا به Y برسیم
اجازه بدید رو همین مثال پیاده سازی کنیم:


4*5=20
(4*0)+2=2
(4*2)+0=8
(4*8)+0=32
(4*2)+3=11
(4*1)+1=5

حالا که به 5 رسیدیم رقم یکان های حواصل (حاصل ها!) رو به ترتیب از پایین به بالا مینویسیم:
512820
و با تقسیم این عدد بر Z (که همون 4 هست) خواهیم داشت :


512820 / 4 = 128205

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

[ms1024]

مساله B (همونی که به قو ل دوستمون شوته :چشمک: ) :
بهترین SMS برای تایپ
همون طور که میدونید امروزه استفاده از SMS خیلی زیاد شده و متناسب با این رشد، نیاز به تایپ سریع SMS احساس میشه...
معمولا حروف انگلیسی به این صورت به کلیدها اختصاص داده میشن:
http://i4.tinypic.com/23kompx.png
برای تایپ یک حرف باید کلید مربوطه رو یک، دو، سه یا چهار مرتبه فشار داد.
نکته : اگر نیاز به تایپ دو حرف باشه که هر دو در یک کلید قرار داشته باشن باید بعد از تایپ اولی کمی صبر کرد تا fix بشه بعد حرف بعدی رو تایپ کرد (مثلا کلمه AB) در غیر این صورت شما میتونید بلافاصله بعد از تایپ یک حرف ، حرف بعدی رو تایپ کنید.
و اما مساله :
به شما زمان فشار دادن یک کلید و زمان fix شدن یک حرف داده میشه، شما باید برنامه ای بنویسید که کمترین زمان رو برای تایپ یک رشته غیر تهی (که اونم به شما داده میشه) محاسبه کنه
نکته : دکمه شماره 1 برای کاراکتر space استفاده میشه و زمان fix شدن اون صفر هستش
مثالی از ورودی برنامه :


2 10
ABBAS SALAM

[ms1024]

اگر عمری باقی بود (و البته اگر تونستم) سعی میکنم سوالات مشکلتر رو هم ترجمه کنم (نیاز به همکاری دوستان)
البته من نمیدونم ترجمه این سوالات جایی هست یا نه، ولی من که هرچی گشتم پیدا نکردم
راستی این سوالات (سوالات امسال انتخابی آسیا) رو هر کس نداره میتونه از اینجا بگیره
http://sharif.ac.ir/~acmicpc/acmicpc05/problems/problems.pdf
size=190kb

[ms1024]

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



0<m<500
تعداد مردها
0<f<500
تعداد زنها
0<r<500
تعداد اتاقها
c>0
تعداد روابط زناشویی بین افراد
نکته : چند همسری نداریم

همچنین به ازای هر اتاق(r) یک ظرفیت و یک قیمت وجود داره که در ادامه ورودی خواهد آمد:



0<bi<5
ظرفیت اتاق
0<pi<1000
قیمت اتاق

خروجی برنامه :
پیدا کردن کمترین هزینه ممکن. (اتاق ها رو طوری به مشتریان اختصاص بدیم که هزینه کل کمترین باشه)
و در صورتی که اختصاص اتاقها غیر ممکن باشه برنامه باید "Impossile" برگردونه. (به مثال توجه کنید)
---------------------------
مثال :
ورودی برنامه:


2 1 3 1
3 5
2 10
2 4

تعداد مردها : 2
تعداد زنها : 1
تعداد اتاق ها : 3
تعداد روابط زناشویی : 1
خروجی برنامه 9 است
چون اتاق آخر به زن و شوهر اختصاص داده میشه : 4
و اتاق اول هم به یک نفر مرد باقی مانده : 5

مثال 2 :
ورودی :


1 1 1 0
1 4

خروجی :
Impossible

[BitMap]

می دونم این تاپیک قدیمی هست ولی راه حل من برای مسئله ی اول رو ببینید:

رقم یکان = m
ضریب = n

1-
اولین عدد بخشپذیر بر n با دهگان m را پیدا می کنیم p=
(حداکثر به 10 مقایسه نیاز داریم.)

2-
q = n * m

3-
y هم تعداد ارقام q است


4-

z =[ ( p * 10^y ) + q ]/n


z همان عدد است.
مثلا:

ورودی :
5
4

P=52
Q=20
Z = [ 52*100 + 20 ] / 4 = 1305

به نظر شما این روش درست هست؟ به نظر خودم خیلی ساده حل شد !
جالب این است که در این روش می توان عدد حاصل با هر تعداد رقم تولید کرد.

[BraveMind]

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