ماراتون uva

[hoco.hc]

سلام.

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

اوّل برید تو سایت و ثبت نام کنید. بعدش برید اینجا . تا با لیست طبقه بندی شده سوالات روبرو بشید ( دی ) .
[HR][/HR]پ.ن. : قوانین:
1- در هر زمان فقط یه سوال می تونه جاری باشه.

2- اگه می خواید بحثی در مورد یه سوال بکنید یا جوابشو بزارید یا کلا هر کاری راجع به یه سوال انجام بدید شمارشو باید بالای پستتون وارد کنید.
3- سعی کنید یه توضیح خیلی مختصر در رابطه با کدتون بدید ( کلیت این که چی کار کردی​

 

[hoco.hc]

پاسخ : ماراتون uva

اوّلین سوال رو خودم میزارم.
سوال خیلی راحته و بیشتر جنبه آشنایی داره . ( دی )
سوال shapaholic
ترجمه:
یه خانمی می خواد یه سری کالا بخره. و فروشگاهی که ازش می خواد خرید کنه این مزیت رو داره که به ازای دو کالایی که خرید یه کالا رو مجانی حساب می کنه. ولی یه چیز جالب اینه که فروشگاه همیشه ارزون ترین کالا رو مجانی می ده. خانمه هم می تونه، به جای این که همه رو با هم حساب کنه، در چند دفعه مختلف بره و خریداش رو حساب کنه. ( ممکنه تخفیف بیشتری بگیره ) ( و در هر دفعه هم همونطور که گفته شد، از بین سه کالا ارزون ترینش مجانی هست )
مثلا اگه اون خانم بره و جنس های 400 و 350 و 300 و 250 و 200 و 150 و 100 دلاری بخره و همه رو با هم حساب کنه، 250 دلار تخفیف می گیره.
اما اگه اول بره و 400 و 300 و 250 رو حساب کنه ( اول 250 دلار تخفیف می گیره ) ، بعدش جنس 350 دلاری ، و بعدش 200 و 150 و 100 دلاری رو حساب کنه ( دفعه دوم هم 100 دلار تخفیف می گیره ) روی هم 250 + 100 = 350 دلار تخفیف می گیره.
حالا شما باید بیشترین تخفیفی که این خانم می تونه بگیره رو حساب کنید.

ورودی: اول مقدار t رو به عنوان ورودی می ده ( t تعداد تست هایی است که روی برنامه تون اجرا می شه ) (

) . بعدش توی هر تست، اوّل n رو می ده که تعداد کالاهایی هست که می خواد بخره و در سطر بعدی، n ورودی می ده که قیمت کالاهایی است که می خره.

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

[HR][/HR]پ.ن. :لطفا سریع تر کدتون رو بزارید تا سریع تر بریم رو سوال های سخت تر

 

[rezashiri]

پاسخ : ماراتون uva

اوّلین سوال رو خودم میزارم.
سوال خیلی راحته و بیشتر جنبه آشنایی داره . ( دی )
سوال shapaholic
ترجمه:
یه خانمی می خواد یه سری کالا بخره. و فروشگاهی که ازش می خواد خرید کنه این مزیت رو داره که به ازای هر دو کالایی که خرید یه کالا رو مجانی حساب می کنه. ولی یه چیز جالب اینه که فروشگاه همیشه ارزون ترین کالا رو مجانی می ده. خانمه هم می تونه، به جای این که همه رو با هم حساب کنه، در چند دفعه مختلف بره و خریداش رو حساب کنه. ( ممکنه تخفیف بیشتری بگیره ) ( و در هر دفعه هم همونطور که گفته شد، از بین سه کالا ارزون ترینش مجانی هست )
مثلا اگه اون خانم بره و جنس های 400 و 350 و 300 و 250 و 200 و 150 و 100 دلاری بخره و همه رو با هم حساب کنه، 250 دلار تخفیف می گیره.
اما اگه اول بره و 400 و 300 و 250 رو حساب کنه ( اول 250 دلار تخفیف می گیره ) ، بعدش جنس 350 دلاری ، و بعدش 200 و 150 و 100 دلاری رو حساب کنه ( دفعه دوم هم 100 دلار تخفیف می گیره ) روی هم 250 + 100 = 350 دلار تخفیف می گیره.
حالا شما باید بیشترین تخفیفی که این خانم می تونه بگیره رو حساب کنید.

ورودی: اول مقدار t رو به عنوان ورودی می ده ( t تعداد تست هایی است که روی برنامه تون اجرا می شه ) (

) . بعدش توی هر تست، اوّل n رو می ده که تعداد کالاهایی هست که می خواد بخره و در سطر بعدی، n ورودی می ده که قیمت کالاهایی است که می خره.

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

[HR][/HR]پ.ن. :لطفا سریع تر کدتون رو بزارید تا سریع تر بریم رو سوال های سخت تر

لطفا صورت سوال رو درست کن!

اینم کد من

 

[hoco.hc]

پاسخ : ماراتون uva

درسته.
اینم کد خودم.
سوال بعدی:
wine trading in gergovia
اگه خودتون می تونید ترجمه اش کنید. اگه نه ، ایشالله یه ساعت دیگه ترجمه اش می کنم. ( الان کدفورس کانتست هست )
[HR][/HR]ویرایش1:
ترجمه سوال:
جرگوویا یه شهری هست که مردمش فقط نوشیدنی می فروشند و می خرند. خونه های جرگوویا روی یه خط راست قرار داره. اگه کسی بخواد نوشیدنی رو به یکی دیگه بفروشه، به ازای هر لیتر نوشیدنی به اندازه ی فاصله ی بین خونه ی خودش و خونه ی خریدار هزینه انتقال هست. حالا شما باید کمترین مقدار مجموع کل هزینه انتقال رو حساب کنید.

ورودی: ورودی شامل چندین تست هست. در هر تست ابتدا تعداد خانه ها ( n ) و سپس در خط بعدی n عدد می دهد. که عدد i ام نشان گر میزان خرید یا فروش نوشیدنی خانه i ام ( به لیتر ) است. + به معنای خرید و - به معنای فروش.
تست ها پس از این که به جای n عدد 0 را وارد کردیم تمام می شود.
به ورودی نمونه و خروجی نمونه در خود سایت توجه کنید.

 

[rezashiri]

پاسخ : ماراتون uva

درسته.
اینم کد خودم.
سوال بعدی:
wine trading in gergovia
اگه خودتون می تونید ترجمه اش کنید. اگه نه ، ایشالله یه ساعت دیگه ترجمه اش می کنم. ( الان کدفورس کانتست هست )
[hr][/hr]ویرایش1:
ترجمه سوال:
جرگوویا یه شهری هست که مردمش فقط نوشیدنی می فروشند و می خرند. خونه های جرگوویا روی یه خط راست قرار داره. اگه کسی بخواد نوشیدنی رو به یکی دیگه بفروشه، به ازای هر لیتر نوشیدنی به اندازه ی فاصله ی بین خونه ی خودش و خونه ی خریدار هزینه انتقال هست. حالا شما باید کمترین مقدار مجموع کل هزینه انتقال رو حساب کنید.

ورودی: ورودی شامل چندین تست هست. در هر تست ابتدا تعداد خانه ها ( n ) و سپس در خط بعدی n عدد می دهد. که عدد i ام نشان گر میزان خرید یا فروش نوشیدنی خانه i ام ( به لیتر ) است. + به معنای خرید و - به معنای فروش.
تست ها پس از این که به جای n عدد 0 را وارد کردیم تمام می شود.
به ورودی نمونه و خروجی نمونه در خود سایت توجه کنید.

بازم صورت سوال رو کامل ننوشتی!:d

توی سوال گفته که می دونیم مجموع این اعداد صفر هستش(اگه این شرط نباشه فکر نکنم گریدی جواب بده!!؟)

من اگوریتمش رو می گم چون اصلا حس کد زدن نیست!!(هر چند از این که می دونیم گریدیه دیگه الگوریتمش واضحه!!)

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

پ.ن : راستی چطوری ثابت می شه مثلا این الگوریتم بهینه است؟

 

[hoco.hc]

پاسخ : ماراتون uva

درسته، ولی من یه کار دیگه کردم. از اوّل آرایه شروع کردم و خانه شماره i را تا وقتی صفر نشده، کمش کردم.
اینم کدم. نمی دونم چرا جواب نمی ده. اصلا انگار تابعش عمل نمی کنه.
کسی می تونه جوب گیری کنه؟
( توجه : fabs(i) یعنی قدر مطلق i )
[HR][/HR]پ.ن. : تقریبا بدیهی هست که الگوریتمی که گفتم بهینه هست.
+ تو الگوریتم شما، اگه در یه مرحله هم از سمت راست به منفی رسید هم از سمت چپ، چی کار می کنه؟
+ اگه کدم توضیحی می خواست بگید تا بگم

 

[rezashiri]

پاسخ : ماراتون uva

باگت دراومد (نیم ساعت وقتمو گرفت!!) مجبور شدم خودم کدشو بزنم :

اینم کدم

فکر کنم کدمو ببینی باگت رو می فهمی اگه نفهمیدی بگو تا بگم (سوتی جالبی دادی!!)

 

[hoco.hc]

پاسخ : ماراتون uva

آقا بگو باگمو.
عذابی کشیدم سرش.
کدت که مثل کد منه. کجای کدم باگ داره؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

 

[rezashiri]

پاسخ : ماراتون uva

آقا بگو باگمو.
عذابی کشیدم سرش.
کدت که مثل کد منه. کجای کدم باگ داره؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

به جای این که بنویسی :

a[i]+=a[j];
                a[j]=0;
                s+=(j-i)*fabs(a[j]);

باید بنویسی :

a[i]+=a[j];
                s+=(j-i)*fabs(a[j]);
                a[j]=0;

چون درواقع اول a[j] رو صفر کرده بودی بعد جوابتو با صفر جمع کردی؟!؟

 

[hoco.hc]

پاسخ : ماراتون uva

ممنون. فقط یه چیزی، وقتی می خوام acc کنمش، تایم می خوره. ولی حتی اگه n=100000 هم باشه، و هر مرحله هم 100000 کار انجام بده، باز هم نباید تایم بخوره که( تایم لیمیت 3 ثانیه هست )

 

[Olympiad]

پاسخ : ماراتون uva

ممنون. فقط یه چیزی، وقتی می خوام acc کنمش، تایم می خوره. ولی حتی اگه n=100000 هم باشه، و هر مرحله هم 100000 کار انجام بده، باز هم نباید تایم بخوره که( تایم لیمیت 3 ثانیه هست )

خوب 10^10 تا کار رو کامپیوتر چجوری تو 3 ثانیه انجام میده ؟!؟!!؟!؟؟؟ کامپیوتر تو هر ثانیه 7^10 تا کار انجام میده حالا مثلا فرض کنیم uva خفن هم باشه و 9^10 کار در ثانیه انجام بده (سرعت توهمی !!!! ) بازم نمیشه !!!!!!!!!! خیلی زیاده 10^10 !!!!!!!!!!

 

[rezashiri]

پاسخ : ماراتون uva

شما اشتباه کردید ، چون برای هر testcase باشد خروجی بدید ، نه اینکه همرو یه جا توی آخر بدید !!

چون کد من تایم نخورده !!! (2.86)

 

[hoco.hc]

پاسخ : ماراتون uva

شما اشتباه کردید ، چون برای هر testcase باشد خروجی بدید ، نه اینکه همرو یه جا توی آخر بدید !!

چون کد من تایم نخورده !!! (2.86)

هر کاری کردم باز هم تایم می خوره. حدود 6 بار با تغییرات کوچیک اکثپت کردمش، ولی اکسپت نشد . ( دی :202: )
حتی کد شما ( تو صفحه قبل رو هم زدم ) ، باز هم تایم می خورد !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

[rezashiri]

پاسخ : ماراتون uva

هر کاری کردم باز هم تایم می خوره. حدود 6 بار با تغییرات کوچیک اکثپت کردمش، ولی اکسپت نشد . ( دی :202: )
حتی کد شما ( تو صفحه قبل رو هم زدم ) ، باز هم تایم می خورد !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

الآن من که Acc شدم که!!!؟!!

اینو ببینید: http://eup.hostzi.com/photos/98475c83b470.gif

 

[hoco.hc]

پاسخ : ماراتون uva

الآن من که Acc شدم که!!!؟!!

اینو ببینید: http://eup.hostzi.com/photos/98475c83b470.gif

خیلی جالبه، برا من اکسپت نمی شه. مطمئنی همون کدی رو اکسپت کردی که گذاشته بودی؟

 

[hoco.hc]

پاسخ : ماراتون uva

خب، تا اون جایی که فهمیدین ، این سوال آخریه خیلی سخت اکسپت شد. ( احتمالا کلا الگوریتمش اشتباه هست وگرنه نباید تایم بخوره. ) ولی می ریم سوال بعدی. ایشالله بعد از این می ریم گراف یا dp.( شایدم complete search ، شما نظر بدید) دی

سوال dragon of loowater
خب می گه یه اژدها می خواد امپراطوری رو از بین ببره. اژدها n تا سر داره. و امپراطوری m تا شوالیه. هر شوالیه می تونه فقط یه سر رو قطع کنه. در صورتی یه شوالیه می تونه یه سر رو قطع کنه که قدش از قطر سر بیشتر باشه. اگه همه سرها بریده بشند اژدها از بین میره. و اگه یه شوالیه سر رو ببره، امپراطوری به اندازه قد شوالیه بهش سکه میده.
حد اقل تعداد سکه مورد نیاز رو بگید.
ورودی: شامل چندین تست کیس: در هر تست ، ابتدا n و m رو می ده. بعد تو n خط بعدی قطر سر های اژدها رو می ده و تو m خط بعدش اندازه قد شوالیه ها رو.
خروجی: حداقل تعداد سکه ، یا اگه نمی شه اژدها رو کشت چاپ کنه: Loowater is doomed!

 

[Olympiad]

پاسخ : ماراتون uva

خب، تا اون جایی که فهمیدین ، این سوال آخریه خیلی سخت اکسپت شد. ( احتمالا کلا الگوریتمش اشتباه هست وگرنه نباید تایم بخوره. ) ولی می ریم سوال بعدی. ایشالله بعد از این می ریم گراف یا dp.( شایدم complete search ، شما نظر بدید) دی

سوال dragon of loowater
خب می گه یه اژدها می خواد امپراطوری رو از بین ببره. اژدها n تا سر داره. و امپراطوری m تا شوالیه. هر شوالیه می تونه فقط یه سر رو قطع کنه. در صورتی یه شوالیه می تونه یه سر رو قطع کنه که قدش از قطر سر بیشتر باشه. اگه همه سرها بریده بشند اژدها از بین میره. و اگه یه شوالیه سر رو ببره، امپراطوری به اندازه قد شوالیه بهش سکه میده.
حد اقل تعداد سکه مورد نیاز رو بگید.
ورودی: شامل چندین تست کیس: در هر تست ، ابتدا n و m رو می ده. بعد تو n خط بعدی قطر سر های اژدها رو می ده و تو m خط بعدش اندازه قد شوالیه ها رو.
خروجی: حداقل تعداد سکه ، یا اگه نمی شه اژدها رو کشت چاپ کنه: Loowater is doomed!

از این گریدی تر نمیشه :3:

این کدم

من نظرم اینه که کدهایی که توی این ماراتن(یا ماراتن های برنامه نویسی دیگه !) زده میشه رو یه جا جمع آوری کنیم مثلا یه جا مثل snipt.net یا ..... من با گراف موافقم فقط منظورتون از dp چیه ؟!!؟ من با complete search زیاد موافق نیستم

 

[hoco.hc]

پاسخ : ماراتون uva

منظورم از dp داینامیکه ( dynamic programming )
اینم کد من
در مورد جمع آوری کد ها هم خیلی خوبه. می تونیم یه اکانت توی snipt یا حتی pastebin بسازیم ( یا حتی یه وبلاگ که اونا رو سازمان دهی کنه ). چیز خوبی می شه.

 

[hoco.hc]

پاسخ : ماراتون uva

یه چیزی، اگه دقت کرده باشید اکثر این سوالایی که حل کردیم راحت بودند. ولی از یه طرفی هم دیگه حال ندارم گریدی بزنم. امروز اینقدر دوست داشتم گراف بزنم ( یا حتی داینامیک ) :2:
حالا شما چی می گید. بشینیم چند تا گریدی سخت تر حل کنیم یا بریم سراغ گراف یا داینامیک ( یا یه مبحث دیگه ( خودتون پیشنهاد بدید ))

 

[Olympiad]

پاسخ : ماراتون uva

یه چیزی، اگه دقت کرده باشید اکثر این سوالایی که حل کردیم راحت بودند. ولی از یه طرفی هم دیگه حال ندارم گریدی بزنم. امروز اینقدر دوست داشتم گراف بزنم ( یا حتی داینامیک ) :2:
حالا شما چی می گید. بشینیم چند تا گریدی سخت تر حل کنیم یا بریم سراغ گراف یا داینامیک ( یا یه مبحث دیگه ( خودتون پیشنهاد بدید ))

منم با شما موافقم !!!! گریدی هم خوبه اما داینامیک و گراف بیشتر حال میدن از بین داینامیک و گراف برای من زیاد فرقی نداره .... (حالا وبلاگ بسازیم یا توی snipt ؟؟ فک کنم snipt بهتر باشه ، نه ؟!؟!)