Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Delphi] Задача ЕГЭ С4 
:(
    Опции темы
Lacoste1024
Дата 6.6.2012, 21:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
Доброе время суток. Возник вопрос при решении задачи. Суть в том, чтобы из набора чисел отобрать минимальную пару чётных чисел, а если такой нет, то просто минимальную пару. У меня за эту задачу 1 из 4х баллов. Своё решение выкладывать пока не буду т.к. хочу узнать ваши методы решения этой задчи.
Формат входных данных: в первой строке - N - количество чисел, далее в каждой строке идёт N числел от 0 до 30000.
Выходные данные: минимальная сумма указанная в условии

P.S. Задачу решить нужно наиболее оптимальным способом как по памяти, так и по времени

Это сообщение отредактировал(а) Lacoste1024 - 6.6.2012, 21:52
PM MAIL   Вверх
iff
Дата 6.6.2012, 21:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Администратор
**


Профиль
Группа: Участник
Сообщений: 949
Регистрация: 23.3.2007

Репутация: 3
Всего: 16
Цитата(Lacoste1024 @  6.6.2012,  21:32 Найти цитируемый пост)
минимальную пару 

Или минимальное произведение?

Это сообщение отредактировал(а) iff - 6.6.2012, 21:37


--------------------
DOS... Синей пеленой экран заполнил чистый DOS 
Мышь... Стала вдруг квадратной, потеряла форму мышь... 
Я разбил окно, девяностопятое мастдайное окно, 
И поставил DOS, и тогда увидел: Это счастье, — вот оно.  
PM MAIL WWW   Вверх
Lacoste1024
Дата 6.6.2012, 21:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
iff, Минимальную пару, т.е. сумму
P.S. Задачу решить нужно наиболее оптимальным способом как по памяти, так и по времени

Это сообщение отредактировал(а) Lacoste1024 - 6.6.2012, 21:52
PM MAIL   Вверх
Qu1nt
Дата 6.6.2012, 23:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: нет
Всего: 50
Особо не тестировал, но суть такая:
Код

program ProblemC4;

{$APPTYPE CONSOLE}

procedure Solve;

  procedure CompareAndUpdate(Value: SmallInt; var MinFirst, MinSecond: SmallInt);
  begin
    if Value < MinFirst then
    begin
       MinSecond := MinFirst;
       MinFirst := Value;
    end
    else if Value < MinSecond then
      MinSecond := Value;
  end;

const
  MaxValue = High(SmallInt);
var
  Count, I: Integer;
  Current, MinFirst, MinSecond, MinOddFirst, MinOddSecond: SmallInt;
  FindOddPair: Boolean;
begin
  MinFirst := MaxValue;
  MinSecond := MaxValue;
  MinOddFirst := MaxValue;
  MinOddSecond := MaxValue;
  FindOddPair := False;

  ReadLn(Count);
  for I := 0 to Count - 1 do
  begin
    ReadLn(Current);
    if Odd(Current) then
    begin
      CompareAndUpdate(Current, MinOddFirst, MinOddSecond);
      if not FindOddPair then
        FindOddPair := (MinOddFirst <> MaxValue) and (MinOddSecond <> MaxValue);
    end;

    if not FindOddPair then
      CompareAndUpdate(Current, MinFirst, MinSecond);
  end;

  if FindOddPair then
    Count := MinOddFirst + MinOddSecond
  else
    Count := MinFirst + MinSecond;

  WriteLn(Count);
end;

begin
  Solve;
end.


Это сообщение отредактировал(а) Qu1nt - 7.6.2012, 00:14
PM MAIL   Вверх
northener
Дата 7.6.2012, 01:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1361
Регистрация: 2.9.2010

Репутация: нет
Всего: 20
А ЕГЭ по информатике разве уже был?
Сегодня только ночь 7-го июня.


--------------------
Но только лошади летают вдохновенно.
Иначе лошади разбились бы мгновенно!
PM MAIL   Вверх
Lacoste1024
Дата 7.6.2012, 05:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
28 мая был. Я решил задачу таким же алгоритмом как Qu1nt. Какие будут ещё версии решения?
PM MAIL   Вверх
MetalFan
Дата 7.6.2012, 07:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Аццкий Сотона
****


Профиль
Группа: Комодератор
Сообщений: 3815
Регистрация: 2.10.2006
Где: Moscow

Репутация: нет
Всего: 128
Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена! 


--------------------
There are always someone smarter than you...
PM MAIL   Вверх
Qu1nt
Дата 7.6.2012, 09:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: нет
Всего: 50
Lacoste1024, когда в таких задачах просят использовать наименьшее количество памяти — по сути это отказ от массива. У меня его нет. Единственное, что можно сделать — избавиться от переменной I. А это уже смешно.
Когда подобные задачи просят решить за минимальное время, это значит, что сложность алгоритма должна быть O(n). У меня так. Уменьшить количество сравнений? Какая-то экономия на спичках.
Когда за решение задачи ставят 1/4 — это значит, что задача решена не полностью, ну или человек, который её оценивал не до конца с ним разобрался smile Соответственно, о каких-то баллах за оптимальность речь не идет.
PM MAIL   Вверх
Lacoste1024
Дата 7.6.2012, 13:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
Qu1nt, спасибо большое!

Это сообщение отредактировал(а) Lacoste1024 - 7.6.2012, 19:44
PM MAIL   Вверх
Lacoste1024
Дата 7.6.2012, 19:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
Qu1nt, я задачу решил таким же алгоритмом. Сначала отбор 4х чисел, а затем выбор. 

Получается, у меня правильное решение, однако стоит 1 балл из 4х. Может ли кто-нибудь предложить ещё свои варианты?
PM MAIL   Вверх
Amphiluke
Дата 7.6.2012, 23:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


   ☽
***


Профиль
Группа: Завсегдатай
Сообщений: 1253
Регистрация: 26.8.2009

Репутация: нет
Всего: 112
Еще возможный вариант. Использует немного меньше переменных (в том числе за счет избавления от цикла со счетчиком, о чем говорил Qu1nt). По производительности вряд ли быстрее, но логика, пожалуй, чуть запутаннее   smile   (сопроводил код комментами на всякий).

Код

program FindMinOddPair;

{$APPTYPE CONSOLE}

  procedure Solve;
  var
    N: Integer;
    Min, NextMin, FirstEven, Curr: Word;
  begin
    Min := High(Word);
    if Min mod 2 = 0 then Dec(Min); // put an odd number initially
    NextMin := Min;
    FirstEven := 1; // put an odd number initially
    Readln(N);
    while N > 0 do
    begin
      Readln(Curr);
      if (Min mod 2 = NextMin mod 2) and (Min mod 2 = Curr mod 2) then
      begin // Min, NextMin and Curr are all either odd or even
        if Curr < Min then // Let Min always be less than or equal to NextMin
          Min := Curr
        else if Curr < NextMin then
          NextMin := Curr;
      end
      else
        if Curr mod 2 = 0 then // Both Min and NextMin are odd, and Curr is even
          if FirstEven = 1 then
            FirstEven := Curr // Store the first even number detected
          else
            if FirstEven < Curr then // Let Min always be less than or equal to NextMin
            begin
              Min := FirstEven;
              NextMin := Curr;
            end
            else
            begin
              Min := Curr;
              NextMin := FirstEven;
            end;
      Dec(N);
    end;
    Writeln(Min, ' + ', NextMin, ' = ', Min + NextMin);
  end;

begin

  Solve();
  Readln;

end.
PM   Вверх
Qu1nt
Дата 8.6.2012, 12:02 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: нет
Всего: 50
Amphiluke, проверять чётность числа через деление — моветон. Только Odd, только хардкор!
PM MAIL   Вверх
Amphiluke
Дата 8.6.2012, 12:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


   ☽
***


Профиль
Группа: Завсегдатай
Сообщений: 1253
Регистрация: 26.8.2009

Репутация: нет
Всего: 112
Qu1nt, экономия на переходах.  smile 
недооценил компилятор.

Это сообщение отредактировал(а) Amphiluke - 8.6.2012, 12:32
PM   Вверх
Amphiluke
Дата 8.6.2012, 12:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


   ☽
***


Профиль
Группа: Завсегдатай
Сообщений: 1253
Регистрация: 26.8.2009

Репутация: нет
Всего: 112
Qu1nt, кстати, что в вашем примере, что в моем есть несоответствие условию задачи (если я правильно понял)


Цитата(Lacoste1024 @  7.6.2012,  01:32 Найти цитируемый пост)
из набора чисел отобрать минимальную пару чётных чисел, а если такой нет, то просто минимальную пару


К примеру, на таком наборе введенных данных
Код

0
1
3
5
7

наши примеры выдадут ответ 1 + 3 = 4
А должно быть 0 + 1 = 1.  smile 
Следовательно, надо перед выдачей ответа ставить дополнительную проверку на случай, когда есть только одно четное число в наборе, и оно меньше одного из найденных (или обоих) наименьших нечетных.


Приложу свой исправленный вариант:
Код

program FindMinOddPair;

{$APPTYPE CONSOLE}

  procedure Solve;
  var
    N: Integer;
    Min, NextMin, FirstEven, Curr: Word;
  begin
    Min := High(Word);
    if not Odd(Min) then Dec(Min); // put an odd number initially
    NextMin := Min;
    FirstEven := 1; // put an odd number initially
    Readln(N);
    while N > 0 do
    begin
      Readln(Curr);
      if (Odd(Min) = Odd(NextMin)) and (Odd(Min) = Odd(Curr)) then
      begin // Min, NextMin and Curr are all either odd or even
        if Curr < Min then // Let Min always be less than or equal to NextMin
          Min := Curr
        else if Curr < NextMin then
          NextMin := Curr;
      end
      else
        if not Odd(Curr) then // Both Min and NextMin are odd, and Curr is even
          if FirstEven = 1 then
            FirstEven := Curr // Store the first even number detected
          else
            if FirstEven < Curr then // Let Min always be less than or equal to NextMin
            begin
              Min := FirstEven;
              NextMin := Curr;
            end
            else
            begin
              Min := Curr;
              NextMin := FirstEven;
            end;
      Dec(N);
    end;

    if Odd(Min) then // Here, both Min and NextMin are of the same parity
      if FirstEven <> 1 then // The only even number in an input set
        if FirstEven < Min then
        begin
          NextMin := Min;
          Min := FirstEven;
        end
        else if FirstEven < NextMin then
          NextMin := FirstEven;

    Writeln(Min, ' + ', NextMin, ' = ', Min + NextMin);
  end;

begin

  Solve();
  Readln;

end.


Это сообщение отредактировал(а) Amphiluke - 8.6.2012, 13:06
PM   Вверх
Qu1nt
Дата 8.6.2012, 15:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: нет
Всего: 50
А я искал пару нечетных smile
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1262 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.