Олимпиадные задачки по программированию

Просмотр 15 сообщений - с 1 по 15 (из 21 всего)
  • Автор
    Сообщения
  • #1923794
    Священник
    Участник

    Вот посмотрел я тему про точку нет, и пришла такая идея: а почему бы не создать темку по олимпиадным задачам по программированию? Думаю это будет всем интересно, в особенности новичкам в этом деле, понять и узнать что за мысли бывают в головах иных разработчиков.
    Теперь думаю введем некоторые условие выбора лучшей реализации:Алгоритм ее работы должен быть таков, чтобы за наименьшее возможное вол-во времени и памяти она выполнила задачу.Ну и решения не советую слизывать с нета, потому как какой в этом прикол, и тем более, что частенько бывает так, что решения выложенные в нете неверные просто.
    Так, а теперь предлагаю следующие задачки вам на обдумывание:1). дано уравнение:ax + by = ca, b, c, x, y – целые неотрицательные числа. a<=100000 b<=100000 и c<=100000при заданных их значениях найти пары x и y, удовлетворяющие данному уравнению. Программа должна отработать не более чем за секунду.2). Проверить корректность расстановки скобок в арифметическом выражении.3). Для входящих A и B вычислить последнюю цифру числа A^B. A<=999999999 и B<=999999999.
    Жду ваших решений 🙂 Честно, задачки достаточно простые и решаются в 10-20 минут от силы))).

    #1923800
    zerkms
    Участник

    если сабж интересен – смотриhttp://algolist.manual.ru/olimp/

    #1923836
    -sc-
    Участник

    во всех трех задачах недостаточно условий1) при a=b=c=0 x,y – любые числа2) что понимать под корректностью? парность скобок? т.е. (()) – правильно а ())( – нет? Если так, то юзаем стек3) здесь если ^ – степень то, для 0 и 1 вычислять ничего не надо)Даешь больше условий!

    #1923852
    Священник
    Участник

    Задачи таковы, каковы мне их давали в свое время. Перепечатал 1 в один. Раз уж нужны пояснения, то дело так:1). По сути, 0 по формулировке может быть, но действительно, при решении 0 не может включаться, потому как бесконечное кол-во решений не является решением для программиста и ты сам должен додумать, что 0 – не входит.2). Да, парность скобок. Просетйшая задача на конечный автомат. Вот только можно усложнить: добавить кроме ( и ) еще [ и ].3). А чего тебе 0 не нравится или 1? тоже варианты. Естественно, что А и В неотрицательны. А если у тебя например будет А=20, В=1345636, то что ты будешь делать? В принципе, усливий здесь достаточно.

    #1924003
    Дикий Билл
    Участник

    Неее… Скучно. На SQL веселей порешать 🙂

    #1924013
    Дикий Билл
    Участник

    Тут кстати можно будет под шумок предложить в виде интересной задачки, то что у самого не получается 🙂 Вот к примеру интересная задачка – найти “пропуски”, или как их назвать.(это не тот случай, про который я выше сказал 🙂 ) Дана таблица с чсилами 1,2,3,7,9,10 Ну или дюбые другие.В этом случае запрос должен выдать3,77,9Кстати, эта задача имеет и практический смысл. Правда те, для кого она имеет такой смысл наверняка ее решали 🙂 Но мож студентам будет интересно. Забыл уточнить – спомощью SQL естественно.

    #1924020
    zerkms
    Участник

    “Неее… Скучно. На SQL веселей порешать”
    2Дикий Билл:пожалуйстаsql-ex.ru
    [smile ;)]

    #1924025
    Дикий Билл
    Участник

    [quote name='zerkms'] sql-ex.ru [/quote]Мнене интересен просто набор упражнений 🙂 Мне интересно во первых общение с комсомольчанами, а во вторых чтоб задачка была интересной и желательно с практическим смыслом. Причем главное в этих пунктах именно общение 🙂

    #1924056
    zerkms
    Участник

    SELECT `id` FROM `t` `outer` WHERE NOT EXISTS ( SELECT * FROM `t` `inner` WHERE `inner`.`id` = `outer`.`id` + 1 )
    ps: не могу представить _реальную_ задачу для которой для _реляционной_ mysql (при условии нормальной проектировки БД). просветишь?pps: общение касаемо sql тебе интересно сугубо с комсомольчанами и в форуме или irc тоже как вариант принимается?

    #1924222
    Дикий Билл
    Участник

    Ответ неправильный 🙂 Ты хоть проверил бы сначала. А насчет смысла, да еще “при условии нормальной проектировки БД” [smile :))] Смысл есть. Сначала реши.
    Хотя ладно. Первое возможное применение – узнать “пропуски” в ид. Автоинкрементных. Мало ли зачем это.Второе применение. Это в данном случае это целое поле, но могло быть и датой, при этом запрос практически не изменится, а тут уже больше применений.

    #1924224
    Дикий Билл
    Участник

    [quote name='zerkms']pps: общение касаемо sql тебе интересно сугубо с комсомольчанами и в форуме или irc тоже как вариант принимается? [/quote]Ну irc у меня нет, так что только с комсомольчанами и в форуме 🙂

    #1924229
    zerkms
    Участник

    DROP TABLE IF EXISTS `t`;
    CREATE TABLE `t` ( `id` int(11) NOT NULL auto_increment, PRIMARY KEY (`id`), UNIQUE KEY `id` (`id`), KEY `indx` (`id`)) ENGINE=MyISAM DEFAULT CHARSET=latin1;
    ## Data for the `t` table (LIMIT 0,500)#
    INSERT INTO `t` (`id`) VALUES (1), (2), (3), (7), (8), (10), (12), (13), (15), (19);
    COMMIT;
    SELECT `outer`.`id`, MIN(`inner`.`id`) FROM `t` `outer` INNER JOIN `t` `inner` ON `outer`.`id` < `inner`.`id` WHERE NOT EXISTS ( SELECT * FROM `t` `inner` WHERE `inner`.`id` = `outer`.`id` + 1 ) GROUP BY `outer`.`id`
    +—-+——————-+| id | MIN(`inner`.`id`) |+—-+——————-+| 3 | 7 || 8 | 10 || 10 | 12 || 13 | 15 || 15 | 19 |+—-+——————-+5 rows in set (0.00 sec)
    ps: про пропуски в автоинкрементных полях с тобой категорически не согласен – не считаю что этот самый “пропуск” может играть какую либо роль для приложенияpps: с датами тоже увы ничего _практического_ придумать не могу ;( выручай [smile ;)]ppps: http://community.livejournal.com/ru_mysql/profile (не сочтите за рекламу)pppps: было бы очень интересно увидеть твоё решение либо решение тех, кто имелся ввиду “Правда те, для кого она имеет такой смысл наверняка ее решали”

    #1924243
    Дикий Билл
    Участник

    Вот сейчас правильно 🙂 Насчет практического смысла. У меня такой задачи не возникало, но она с завидной регулярностью появляется на sql.ru. Вот я и решил, что это интересная задача. В любом случае ты хорошо время провел, решая ее, разве нет? 🙂 Мне рассказывали случай в нашем городе. У них был оракл. Там у сиквенса задается ограничение к примеру 9999999999 И вот они стали пожходить к пределу. Пришлось искать эти самые интервалы и менять процедуры удаления и вставки. Ввести промежуточную таблицу для удаленных номеров, а при вставке сначала брать из нее. В общем тут ты прав, если б заранее продумали, то и не возникло бы.Но вот другой чел спрашивал то же самое. У них там прибор какой-то который чето там регистрирует, и результаты заносятся в базу. И утром они проверяют эти самые интервалы в показаниях. Да и еще много всяких преименений встречал. Мое решение 🙂 Я его накатал минут за 10 перед тем как запостить сюда, поэтому хуже твоего, признаю. Думаю еще через некоторое время пришел бы к такому же:)select * from(select a.i i1,(select min(i) from @t b where b.i>a.i) i2from @t awhere not exists(select 1 from @t c where c.i=a.i+1)) a where i2 is not nullМне еще буквально чуток не хватило терпения подумать 🙂 Решение тех, кто действительно ее решал смотри на sql.ru там поиск по “интервлы”. Море.

    #1924291
    Квант
    Участник

    Люди, у меня тоже есть интересная задача для програмирования правда для Бейсика. Надо решить систему линейных уравнений методом итерации. Не подскажите как! прошу Вас помочь. Заранее бл 😎 агодарен

    #1924324
    ArchiMage
    Участник

    Самое интересное, что в данном случае мы наткнулись на отсутствие в Оракле Cascade Update у ключа, что есть в MSSQL-е.В свое время мы горячо спорили с нашим админом Оракла о полезности/бесполезности таких вещей. Вот один из примеров крайней полезности, когда можно было бы просто создать новую последовательность и убить пропуски простым апдейтом.Кстати, такая проблема возникает в Oracle Forms, которые сразу кешируют определенное количество SEQ.NEXT_VAL, а запись порождается обычно одна за транзакцию.

Просмотр 15 сообщений - с 1 по 15 (из 21 всего)
  • Для ответа в этой теме необходимо авторизоваться.