КИТА unofficial
Март 29, 2024, 05:44:09 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости:
 
   Начало   ПРАВИЛА Помощь WIKI PDA Войти Регистрация  


Страниц: [1]   Вниз
  Печать  
Автор Тема: Transform Array  (Прочитано 7671 раз)
Описание темы: уровень 1
0 Пользователей и 1 Гость смотрят эту тему.
vimmax
Модератор
Декан
*****

Карма: +42/-3
Offline Offline

Пол: Мужской
Награды:
лучшая гитара мира
Сообщений: 1713


♪♪ ♫ ♪♪ ♫ ♪♪ ♫ ♪♪


« : Ноябрь 20, 2007, 12:33:53 »

TransformArray
Преобразование массивов (уровень 1).

оригинал тут

Очки за задачу: 250
Кол-во присланных решений / кол-во участников   61 / 73 (83.56%)
Количество решений прошедших все тесты / общее количество решений   47 / 61 (77.05%)

Постановка задачи:
У нас есть массив положительных чисел. Мы должны преобразовать этот массив повторяя одну и ту же оперцию, покане останется менее двух элементов в массиве:

1) выбрать два элемента, которые имеют минимальную абсолютную разницу. Если таких пар несколько, то выбрать пару, чья сумма элементов минимальна. Если все равно осталось несколько пар, то выбрать любую.
2) уменьшить значение элементов выбранной пары на 1.
3) удалить нулевые элементы массива.

Легко заметить, что процесс конечен за фиксированное кол-во шагов.
Например, имеем массив из 4 элементов {3, 2, 3, 2}. Процесс преобразования будет происходить следующим образом:
Step 1: (3, 2, 3, 2) --> (3, 1, 3, 1) (уменьшаем элементы 2 и 2)

Step 2: (3, 1, 3, 1) --> (3, 3) (очередное уменьшение значений элементов делает их равными 0 и 0, удаляем их)

Step 3: (3, 3) --> (2, 2)

Step 4: (2, 2) --> (1, 1)

Step 5: (1, 1) --> ()

Получили пустой массив.

В программе мы получаем int[] которые представляют трансфоруемый массив. Необходимо вернуть количество шагов преобразования. Реализацию алгоритма произвести в методе класса:
   
class TransformArray {
public:
  int doTransform(vector <int>);
};

 
Ограничения:
- размер массива от 1 до 50.
- каждый элемент может принимать значения от 1 до 1000.

Примеры:

- {3,2,3,2}
ответ: 5

- {3}
ответ: 0
Мы уже имеем 1 элемент в массиве, поэтому трансформация не требуется.

- {1,2,3,4}
ответ: 4
Трансформация должна пройти следующим образом:
{1, 2, 3, 4} --> {1, 3, 4} --> {1, 2, 3} --> {1, 3} --> {2}

- {10,6,3,7,7,9,5,1,8,4}
ответ: 27


Решение:

Т.к. ограничений в задаче мало, то она может быть решена простым перебором. Достаточно лишь делать то, что требуется. Наибольшую сложность в этой задаче представляет то, что требуется на каждом шаге выбирать пару с минимальной разницей элементов и минимальной суммой элементов.
Лучшим решением признано решение кодера RuslanSM.

Код: (cpp)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class TransformArray {
public:
  int doTransform(vector <int>);
};

int TransformArray::doTransform(vector <int> elements) {
  int ans=0;
  while (true)
  {
    int minn=100000;
    int minx=100000;
    int mini,minj;
    for(int i=0;i<elements.size();i++)
    {
      for(int j=i+1;j<elements.size();j++)
      {
        if (i!=j &&
           elements[i]!=0 &&
           elements[j]!=0 &&
           ((abs(elements[i]-elements[j])<minn) || (abs(elements[i]-elements[j])==minn && elements[i]+elements[j]<minx)) )
        {
          minn=abs(elements[i]-elements[j]);
          minx=elements[i]+elements[j];
          mini=i;
          minj=j;
        }
      }
    }
    if (minn!=100000)
    {
      elements[mini]--;
      elements[minj]--;
    } else break;
    ans++;
  }
  return ans;
}
Записан

♪♪ ♫  LET FOREVER BE  ♫ ♪♪ ♫ ♪♪ ♪♪ ♫
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Penguins Counter Powered by MySQL Powered by PHP Powered by SMF 1.1.8 | SMF © 2006-2008, Simple Machines LLC Valid XHTML 1.0! Valid CSS! Internetmap
Страница сгенерирована за 0.036 секунд. Запросов: 30.