вестник Компютри

Уважаеми читатели, от тази седмица вестник “Компютри”, с генералното спонсорство на Американската фондация за България, както и с медийното партньорство на Дир.БГ, стартира своя пети конкурс по програмиране. Отправяме предизвикателство към всички талантливи български програмисти с една атрактивна и същевременно актуална задача, която намира своето достойно място в теорията на игрите. Kаним ви да вземете участие в надпреварата, която ще подложи на изпитание състезателния ви дух и същевременно може да ви донесе някоя от атрактивните предметни награди, осигурени от генералния спонсор на конкурса – Американската фондация за България. Те са на стойност съответно: за първо място – 1000 лв., второ място – 500 лв., и трето място – 300 лв. Ще бъдат раздадени и много поощрителни награди. “Ние вярваме, че в свободното и демократично гражданско общество всеки човек трябва да има възможност да постига целите си. Водени от това разбиране, подкрепяме младите хора в стремежа им да развиват своите таланти и умения в избраните от тях области и работим за по-доброто разбиране на България от страна на американците”, заявиха от Американската фондация за България по повод началото на конкурса. Представяне на играта “Изместване” Играта “Изместване” се играе от един играч на игрално табло с M колони и N реда. На таблото плътно са подредени квадратни плочки от C различни цвята. Плочките могат да се разместват с помощта на четири операции за изместване. Всеки ред може да бъде изместен с една позиция вляво или една позиция вдясно. Аналогично всяка колона може да бъде измествана с една позиция надолу или една позиция нагоре. Плочката, която изпада от ръба на игралното табло, постъпва на освободеното място в другия край. Всеки ход се обозначава с една латинска буква: L – вляво, R – вдясно, D – надолу, U – нагоре. След буквата следва цяло положително число от 1 до M или от 1 до N, според номера на стълба или реда, над който изместването е приложено. Задача Напишете програма SHIFTING.EXE, която преобразува с минимален брой ходове игралното табло от изходно състояние до целево състояние само чрез използване на вече описаните операции. Вашата програма получава данните си от входен файл SHIFTING.INP и записва резултата в изходен файл SHIFTING.OUT. Входният файл съдържа три цели положителни числа на първия ред – M, N и C (1<M<1000, 1<N<1000, 1<C<100), разделени с интервал. Следват N реда от M цели положителни числа, разделени с интервал и задаващи изходното състояние. След тях следват още N реда от М цели положителни числа, разделени с интервал и задаващи целевото състояние. Всяка плочка от игралното табло е представена от цяло положително число в интервала от 1 до C, съответстващо на цвета. Изходният файл се състои само от един ред, на който са записани операциите за изместване в реда, в който трябва да се изпълнят, за да се премине от изходното състояние в целевото състояние. Пример: SHIFTING.INP SHIFTING.OUT 4 3 4 U2 R3 D4 1 2 1 3 4 3 4 2 2 4 3 1 1 3 1 3 4 4 4 3 1 2 2 2 Тестовите примери ще бъдат така подбрани, че целевото състояние да бъде винаги достижимо от изходното. Решенията ще бъдат оценени по точкова система, като от значение са броят ходове и времето за изпълнение на програмата. Очакваме вашите решения до 30 юни 2006 г. на адрес: [email protected]. Всяко решение трябва да бъде оформено като ZIP архив, който да съдържа следните файлове: 1. author.html (трите имена, адрес (населено място, пощенски код, квартал, улица, блок, вход, апартамент, етаж), занимание (ученик/студент/работещ/безработен), IM номер (ICQ, MSN, Yahoo и др.), стационарен телефон, мобилен телефон, e-mail). 2. Един или повече файлове с програмния код, които без грешка се компилират до изпълним файл. 3. doc.html (добре оформена, точна и подробна документация на използвания алгоритъм). 4. Изпълним файл (Win32 конзолно приложение, .NET exe или Java jar файл). За допълнителни въпроси, коментари или често задавани въпроси може да посетите форума ни в клубовете на Дир.БГ. Пожелаваме ви късмет и успех! www.computers.bg