| Вопрос: Олимпиада (C++, Delphi) | Добавлено: 04.10.05 14:37 |
Автор вопроса:  HACKER
|
|
Вот, опять, влез... Посколько что C++, что Delphi только поверхностно, прошу помощи. Впринципе техническую сторону связанную непосредственно с самим языком думаю я зделаю как нибуть, но отберут лучшие варианты, а не как нибуть, поэтому хотелось бы узнать как лучше...
Большенство заданий я даже понять немогу :) Растолкуйте чё хотят от меня, я начну программить и буду сюда вопросы по ходу скидывать. Задания: Пересечение отрезков На плоскости задано два отрезка. Необходимо найти точку их пересечения. Входные данные В первой строке содержится целое число T < 100 — количество тестов. Каждый тест состоит из описания двух отрезков. Каждый отрезок описывается в одной строке и состоит из координат начала и конца отрезка (X1 Y1 X2 Y2 по модулю не превышают 1000). Выходные данные Для каждого теста в отдельной строке через пробел выведите координаты точки пересечения с точностью три цифры после десятичной точки. Если отрезки не пересекаются или пересекаются в более чем одной точке выведите знак '-'. Приклад Вхiд Вихiд 2 5.000 5.000 0.000 0.000 10.000 10.000 - 0.000 10.000 10.000 0.000 0.000 0.000 10.000 10.000 0.000 10.000 3.000 7.000 Скобки Имеется шаблон, состоящий из круглых скобок и звездочек. Вам нужно определить, сколькими способами можно заменить звездочки круглыми скобками так, чтобы получилось правильное скобочное выражение. Входные данные Первая строка входных данных содержит единственное целое T (0<=T<=100) — количество тестов. В каждой из последующих T строк находится один шаблон. Длина шаблона не превышает 100 символов. Выходные данные Для каждого теста в отдельной строке выведите целое число N — количество правильных скобочных последовательностей, удовлетворяющих шаблону в тесте (0<=N<=2*109). Приклад Вхiд Вихiд 2 2 *)**** 0 *( Суперчисло Необходимо посчитать количество последовательностей длины N, которые состоят из 0 и 1, но в которых не может идти две единицы подряд. Назовем это количество суперчислом. Входные данные В первой строке находится целое число T < 10 — количество тестов. Каждый тест — отдельная строка, в которой записано целое число N (1<=N<=100). Выходные данные Для каждого теста выведите в отдельной строке его суперчисло. Приклад Вхiд Вихiд 2 5 3 8 4 Шиворот-навыворот Петин принтер был заражен вирусом. После отпечатки нескольких страниц он заметил, что каждая строка печатается «шиворот-навыворот». Другими словами, левая половина каждой строки печатается от середины страницы до левой границы, а правая — от правой границы до середины страницы. К примеру, строка “THIS LINE IS GIBBERISH” будет напечатана как “I ENIL SIHTHSIREBBIG S”. Вашей задачей будет помочь Пете перевести отпечатанные строки в их начальный порядок. Каждая строка состоит из четного числа символов. Длина строки не превышает 50 символов. Входные данные В первой строке находится число строк (T < 100) которые необходимо обработать. Далее идут T строк, отпечатанных зараженным принтером. Выходные данные Ваша программа должна вывести T строк с начальным порядком. Приклад Вхiд
1)5 2)I ENIL SIHTHSIREBBIG S 3)LEVELKAYAK 4)H YPPAHSYADILO 5)ABCDEFGHIJKLMNOPQRSTUVWXYZ 6)RUT OWT SNEH HCNERF EERHTEGDIRTRAP A DNA SEVODELT Вихiд 1)THIS LINE IS GIBBERISH 2)LEVELKAYAK 3)HAPPY HOLIDAYS 4)MLKJIHGFEDCBAZYXWVUTSRQPON 5)THREE FRENCH HENS TWO TURTLEDOVES AND A PARTRIDGE ... Это ПИПЕЦ!!! Энергетическая сеть Энергетическая сеть состоит из узлов (генераторов, потребителей и диспетчеров) соединенных энергетическими транспортными линиями. Узел u может принимать количество s(u)>=0 энергии, может генерировать количество 0<=p(u)<=pmax(u) энергии, может потреблять количество 0<=c(u)<=min(s(u),cmax(u)) энергии, а также передавать количество d(u)=s(u)+p(u)-c(u) энергии. При этом накладываются следующие ограничения: c(u)=0 для всех генераторов, p(u)=0 для всех потребителей, p(u)=c(u)=0 для всех диспетчеров. Существует максимум одна транспортная линия (u,v) из узла u в узел v; она передаёт количество 0<=l(u,v)<=lmax(u,v) энергии из u в v. Пускай Con = SUMu c(u) будет потребляемой энергией в сети. Вашей задачей будет посчитать максимальное значение для Con. Рассмотрим пример. Метка x/y генератора u показывает, что p(u)=x и pmax(u)=y. Метка x/y потребителя u показывает что c(u)=x и cmax(u)=y. Метка x/y энергетической транспортной линии (u,v) показывает, что l(u,v)=x и lmax(u,v)=y. Потребляемая энергия Con=6. Обратите внимание, что имеются и другие возможные состояния энергетической сети, но значение Con не может превысить 6. Входные данные В первой строке входных данных находится целое (T < 30) — количество тестовых наборов. Каждый тестовый набор описывает энергетическую сеть. Он начинается с четырех целых чисел: 0<=n<=100 (узлы), 0<=np<=n (генераторы), 0<=nc<=n (потребители) и 0<=m<=n2 (энергетические транспортные линии). Далее следует m триплетов (u,v)z, где: u и v — идентификаторы узлов (начиная с 0), и 0<=z<=1000 — значение lmax(u,v). Далее следует np дуплетов u(z), где: u — идентификатор генератора, и 0<=z<=10000 — значение pmax(u). Тестовый набор заканчивается nс дуплетами u(z), где: u — идентификатор потребителя, и 0<=z<=10000 — значение сmax(u). Все числа являются целыми. За исключением (u,v)z триплетов и u(z) дуплетов, в которых нет пробелов, всевозможные пробелы и переносы строк могут свободно присутствовать во входных данных. Выходные данные Для каждого тестового набора Ваша программа должна вывести максимальное значение потребляемой энергии в заданной сети. Каждый результат имеет целое значение и печатается с начала отдельной строки. Разбор примеров В первом тестовом наборе описывается сеть с 2 узлами, генератор 0 с pmax(0)=15 и потребитель 1 с cmax(1)=20, и 2 энергетические транспортные линии с lmax(0,1)=20 и lmax(1,0)=15. Максимальное значение Con = 15. Второй тестовый набор описывает энергетическую сеть, которая отображена на рисунке (см. выше). (рисунок на сайте позже выложу) Примеры Вход 1)2 2)2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20 3)7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)4)8 (2,3)1 (2,4)7 5) (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5) (6,0)5 6) (0)5 (1)2 (3)2 (4)1 (5)4 Выход 1) 15 2) 6 Мои сображения 1) Пересечение отрезков Задаем сколько линий, потом запрашуем координаты каждой линии и находим все пересечения. Вроде просто, наверно сделаю сам. 2) Скобки, мало чё понял, прошу объяснить 3) Суперчисло - аналогично 2 4) Шиворот-навыворот, детский сад, зделаю сам. 5) Энергетическая сеть - я в шоке, вы б видели картинку, чёрт ногу сломит. |
| Ответы | Всего ответов: 41 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 04.10.05 16:56 |
| А откуда задачи? Вечером приду, подумаю. | ||
|
Номер ответа: 2 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #2 | Добавлено: 04.10.05 21:27 |
|
1) наверно, через уравнения прямых с рассмотрением экстремального случая (вертикальная прямая) и отсечением по координате X (Y)
2) Правильное скобочное выражение, это в котором число ( = числу ) и ни в какой подстроке слева число ) не больше (, т.е. ()(()) - правильно, а (((()) или )( - неправильные. Не знаю (лень думать), почему число вариантов ограничено 2*N, но если это так, то простая рекурсия, перебирать все * слева направо, смотреть, можно ли заменить и на что (чтобы не было больше ), чем ( и чтобы в конце не получилось неравное число скобок) и передать этой же функции полученную после замены строку. 3) Тут надо чуток подумать, рассмотрим все случаи для N=3: 000 100 010 001 101 3 кончаются на 0, 2 на 1, следовательно, при N++ 3 могут получить в конец 1 или 0 (станет 3, кончающихся на 0 и 3 на 1), а 2 только 0, отсюда при N=4 3 кончается на 1, 5 на 0, продолжив еще на один раз, видим, что получается последовательность Фиббоначчи, вычисление ее N-го члена тривиальная задача. 4) Ну это просто, можно решать через 2 цикла, перебирая символы от среднего до первого, а потом от последнего до послесреднего. 5) Без картинки мало что понятно, но судя по всему это геморрная, но не особо сложная задача на графы-деревья (именно деревья, т.к. сказано, что путь максимум один). |
||
|
Номер ответа: 3 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #3 | Добавлено: 04.10.05 22:38 |
|
Это автоматизированная олимпиада, задание раздаёт компьютер, принимает тоже компьютер (сервер универа), потом его компилирует, тестирует чтобы совпадали по условию входные и выходные данные, если это так, то задача считается сданной. Выграет тот у кого наименшое кол-во действий (простота программы) и тот у кого наибольшая скорость, т.е. у кого самая быстрая программа, и тот у кого программа будет хавать минимальное кол-во памяти отводимое под приложение. Всё это как-то компбинируется сумируется таким макаром автоматически будет определён победитель. Так что задание знают все, закрытие этой олимпиады 10-ого числа, т.е. время ещё есть...
По поводу заданий, в принципе всё понятно, ну есть кое-что но думаю походу прояснится, абсолютно тёмными для меня остаются задания № 1 и 5 (Про линии, и про ту сеть). Если кто может, про линии растолкуйте подробнее! Что за формулы, как что считать итп... Про энергитическую сеть - картинку принесу завтра... |
||
|
Номер ответа: 4 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #4 | Добавлено: 04.10.05 22:40 |
| Кстати, Sharp, за терпение - спасибо! Не каждый согласен за спасибо так мозгами шивелить! | ||
|
Номер ответа: 5 Автор ответа: el-paso Вопросов: 3 Ответов: 164 |
Профиль | | #5 | Добавлено: 05.10.05 03:01 |
|
По поводу задачи о пересечении отрезков...
Давным-давно листал сайтик один с алгоритмами и вот сейчас припомнил, что видел описание нужного алгоритма, основанного на численных методах. Покопался и отыскал: http://algolist.manual.ru/maths/geom/intersect/lineline2d.php Помимо доходчивого объяснения имеется реализация на языке С. |
||
|
Номер ответа: 6 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #6 | Добавлено: 05.10.05 13:19 |
| супер! большое спасибо! | ||
|
Номер ответа: 7 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #7 | Добавлено: 05.10.05 14:32 |
| кстати, а можно как то в си, зная указатель одного из элементов массива возвратить все элементы этого массива? | ||
|
Номер ответа: 8 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #8 | Добавлено: 05.10.05 18:57 |
| Надо знать еще число элементов и номер этого одного из элементов. Где картинка к задаче 5? | ||
|
Номер ответа: 9 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #9 | Добавлено: 05.10.05 18:57 |
| Надо знать еще число элементов и номер этого одного из элементов. Где картинка к задаче 5? | ||
|
Номер ответа: 10 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #10 | Добавлено: 05.10.05 20:51 |
| а нема, сёдня в вычислительном центре дежруной небыло, а так за комп непустили, а другого доступа к сетке универа я неимею... ждёмс...наверно завтра принесу. | ||
|
Номер ответа: 11 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #11 | Добавлено: 05.10.05 20:56 |
|
про массивы
ну мас денамический, так что размер - sizeof а если я б знал номер я б и сам зделал  не номер то я могу найти, но циклом долго когда массив бАльшой, думал мож как-то по другому мона..
|
||
|
Номер ответа: 12 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #12 | Добавлено: 06.10.05 18:07 |
|
ну мас денамический, так что размер - sizeof Как ты себе это представляешь?
|
||
|
Номер ответа: 13 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #13 | Добавлено: 06.10.05 20:31 |
|
ненаю ладно пофиг, я по другому сделаю...
Насчёт второго задания, с этими скобками это ж... короче рекурсия непойдёт, потому что 2^100=1,26765060022823E+30 это столько комбинаций возможно в строке из 100 символов, пока всё рекурсивно перебрать - я постарею и умру, так что такой способ некатит. Честно говоря я общался с теми кто на подобных олимпиадах не первый раз, говорит когда я посмотрю авторсике решения, я охирею, там всё в десяток строк, элементрано, быстро и просто... так что надо думать, думать и ещё раз думать... |
||
|
Номер ответа: 14 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #14 | Добавлено: 06.10.05 22:16 |
| Автор говорит, что число вариантов меньше-равно 2*N, значит число вариантов меньше 2*N, следовательно, рекурсия будет нормально работать. | ||
|
Номер ответа: 15 Автор ответа: vitoРазработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #15 | Добавлено: 07.10.05 12:26 |
|
Задача 3.
Ну если разрешен С, тогда разрешен и ассемблер. Я быстренько программку набросал, вроде работает и быстро
В ней конечно полно багов(а может и нет, я больше всего удивлюсь ), нужно будет поправить и скорость можно увеличить(доделаешь, либо по другому реализуешь).
Суть такова – работаем с битами. int supernum (int r)// получаем длину числа
{ int count =pow(r,2) ; int num=0; int sum=0; __asm { xor eax,eax mov ecx,r//помещаем в регистр длину числа dec ecx mov eax,1b// устанавливаем старший бит rcl eax,cl // сдвигаем на длину числа xor ebx,ebx mov ebx,r mov ecx,count //устанавливаем счетчик цкла R1://пошли по циклу btc eax,ebx // перебираем возможные комбинации jc R2 // переход если флаг переноса установлен inc sum R2: dec ebx cmp ebx,0 // переключаем jz R4 inc ebx R4: Loop R1 } return sum;// а вот и оно, волшебное число точнее его количество } Что касается скорости и комкатности, то что надо. Если будут вопросы по доработке - буду рад помочь. |
||