Състезание по програмиране 2011

За да участвате, трябва да сте студент, който към момента не работи като програмист.

Условие на задачата от I кръг      Класиране      Награди      ?!

Условие на задачата

Дадени са N + 1 цели числа X1, X2, ..., XN и Y в интервала от 1 до 1000 включително. N е между 1 и 100 включително. Разполагаме с аритметичните операции събиране, изваждане, умножение и деление на реални числа. Те се записват с +, -, * и / съответно и имат стандартния приоритет и асоциативност.

Постройте възможно най-кратък аритметичен израз, който има стойност Y. Използвайте числата Xi, аритметичните операции и кръгли скоби за промяна на реда на операциите. Числата, операциите и скобите може да се използват произволен брой пъти, както и да не се използват. Дължината на израза се измерва в брой символи, така че не добавяйте интервали за четимост. Очаква се изразът да съдържа само цифри и символите +, -, *, /, ( и ).

Пример:

X1 = 3, X2 = 5, X3 = 7, X4 = 9, Y = 11
Едно решение е например "(3+3)*3-7", което е с дължина 9. Решения с минималната дължина 5 са например "3+3+5" или "9+7-5".

Вход и изход

Входът се подава като два командни параметъра: първият съдържа числата Xi, разделени със запетаи; вторият съдържа числото Y. Резултатът се отпечатва на стандартния изход. В момента, в който намерите по-добро решение от предишното, отпечатвайте новия, по-кратък израз на нов ред, защото програмата Ви може да бъде прекъсната преди да завърши.

Пример:

D:\Contest\bin>FindExpression.exe 3,5,7,9 11
(3+3)*3-7
9+7-5

Оценка

Решенията се сравняват едно с друго по няколко критерия в следния ред:
- Коректност: взимат се под внимание само изрази със стойност Y.
- Дължина на последния отпечатан израз: по-кратък израз печели пред по-дълъг.
- Време: при равни дължини печели решението, което намира израза по-бързо. Ще измерваме времето от стартиране на програмата до отпечатване на израза, а не до приключване/прекъсване на процеса.

Технологии

Изисквания към средствата за разработка

- Конзолно приложение за Windows.
- Програмен език: C#, VB.net, C++, Java или Pascal.
- Библиотеки: само вградените по подразбиране в средата за разработка.

Среда, в която ще се тества решението

Двуядрен процесор, 2 GB RAM, Windows 7 x64 с инсталиран .net framework 4.0 и Java 7.

IDE, с което ще се опитаме да компилираме сорс кода при нужда

- Visual Studio 2010 за решения на C#, VB.net и C++.
- Eclipse 3.7 за решения на Java.
- Delphi 2010 за решения на Pascal.

Срокът за предаване на решенията изтече.

Вижте класирането