Как проблема FlowerGarden на TopCoder относится к DP?

Это не проблема динамического программирования. Это проблема жадного алгоритма.

Меня это тоже смутило, поскольку собственное руководство по динамическому программированию от topcoder ссылается на него как на практическую задачу в разделе "Элементарно".

Рассортируйте цветы по высоте, от самых низких к самым высоким. Начните с пустого списка строк. Для каждого цветка (от самого короткого до самого высокого) найдите самое переднее место, куда вы можете вставить этот цветок так, чтобы он не блокировал цветы позади себя.

В Питоне:

def getOrdering(height, bloom, wilt):
    flowers = zip(height, bloom, wilt)
    flowers.sort()

    def flowersOverlap(f1, f2):
        # Overlap if each blooms before the other wilts.
        return f2[1] <= f1[2] and f1[1] <= f2[2]

    rows = [ ]
    for flower in flowers:
        rowIndex = len(rows)
        # Start at the back and march forward as long as
        # `flower` wouldn't block any flowers behind it.
        while rowIndex > 0 and not flowersOverlap(flower, rows[rowIndex - 1]):
            rowIndex -= 1
        rows[rowIndex:rowIndex] = [flower]

    return [flower[0] for flower in rows]

public int[] getOrdering(int[] height, int[] bloom, int[] wilt) {
    int[] optimal = new int[height.length];
    int[] optimalBloom = new int[bloom.length];
    int[] optimalWilt = new int[wilt.length];

    // init state
    optimal[0] = height[0];
    optimalBloom[0] = bloom[0];
    optimalWilt[0] = wilt[0];

    // run dynamic programming
    for(int i = 1; i < height.length; i ++) {
        int currHeight = height[i];
        int currBloom = bloom[i];
        int currWilt = wilt[i];

        int offset = 0; // by default, type i is to be put to 1st row
        for(int j = 0; j < i; j ++) {
            if(currWilt >= optimalBloom[j] && currWilt <= optimalWilt[j] ||
                    currBloom >= optimalBloom[j] && currBloom <= optimalWilt[j] ||
                    currWilt >= optimalWilt[j] && currBloom <= optimalBloom[j]) {  // life period overlap
                if(currHeight < optimal[j]) {  // life overlap, and type i is shorter than type j
                    offset = j;
                    break;
                } else {
                    offset = j + 1; // type i overlap with type j, and i is taller than j. Put i after j
                }
            } else {  // not overlap with current
                if(currHeight < optimal[j]) {
                    offset = j + 1; // type i not overlap with j, i is shorter than j, put i after j
                }
                // else keep offset as is considering offset is smaller than j
            }
        }

        // shift the types after offset
        for(int k = i - 1; k >= offset; k -- ) {
            optimal[k+1] = optimal[k];
            optimalBloom[k+1] = optimalBloom[k];
            optimalWilt[k+1] = optimalWilt[k];
        }
        // update optimal
        optimal[offset] = currHeight;
        optimalBloom[offset] = currBloom;
        optimalWilt[offset] = currWilt;
    }
    return optimal;
}

Это мой проверенный рабочий код.

Я целый день боролся с этим точным вопросом, а также не смог найти для него решения DP.

Вот мой жадный подход в java, похожий на другие, уже опубликованные, ключевой момент - действовать в соответствии с порядком высоты. Причина в том, чтобы не иметь дело с промежуточными высотами (имея в виду уже вычисленные), учитывая, что промежуточная высота может изменить относительный порядок ранее вычисленных.

int[] height = new int[]{5, 3, 4};
int[] start =  new int[]{1, 3, 1};
int[] end =    new int[]{2, 4, 4};
System.out.println(Arrays.toString(new FlowerGarden().getOrdering(height, start, end)));

Это единственная оптимальная подструктура, которую я смог найти. Но учитывая, что подзадачи не пересекаются, этот алгоритм следует считать не DP, а жадным.

private static boolean intersects(final int[] starts, final int[] ends, int i1, int i2) {
    return !(ends[i1] < starts[i2] || ends[i2] < starts[i1]);
}

public int[] getOrdering(final int[] height, final int[] starts, final int[] ends) {

    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        public int compare(Integer i, Integer j) {
            return Integer.compare(height[i], height[j]);
        }
    }
    );
    for (int i = 0; i < height.length; i++) {
        minHeap.add(i);
    }
    LinkedList<Integer> list = new LinkedList<Integer>();
    while (minHeap.size() > 0) {
        Integer index = minHeap.poll();
        int p = 1;
        int pos = 0;
        for (Integer i : list) {
            if (intersects(starts, ends, i, index)) {
                pos = p;
            }
            p++;
        }
        list.add(pos, index);
    }
    int[] ret = new int[height.length];
    int j = 0;
    for (Integer i : list) {
        ret[j++] = height[i];
    }
    return ret;
}

Кстати, решения DP, которые я видел здесь, не подходят для этого примера.

Ваше здоровье

Я тоже пытался решить эту проблему. Основная идея моего подхода состоит в том, чтобы построить дерево, в котором каждый дочерний элемент хотя бы один раз перекрывается своим родителем.

Например, если у нас есть три типа цветов высотой 4, 2 и 1, которые растут и умирают в одни и те же дни, то результирующее дерево должно быть:

С другой стороны, если 4 и 2, 4 и 1 живут одновременно, но 2 и 1 не сосуществуют, то результирующее дерево должно быть:

Это создаст дерево, соответствующее ограничениям задачи. Тем не менее, постановка задачи также включает функцию стоимости, делающую одни решения лучше других.

...вы также хотите, чтобы цветы в рядах, расположенных ближе к переднему краю, были как можно выше.

Способ спроецировать это предпочтение в наше дерево состоит в том, чтобы упорядочить всех «братьев» (все узлы, имеющие одного и того же родителя) от высшего к низшему. Таким образом, 2 идет раньше, чем 1.

Я построил это дерево, используя следующий код:

#define INT_MOD(a,b) ((a<0)?(b+(a%b)):(a%b))
#define DIST(a,b) ((a-b>=0)?(a-b):(b-a))

//Prev: ForAll(i), bloom[i] < wilt[i]
inline bool isOverlap(vector<int> & bloom,
                      vector<int> & wilt,
                      vector<int> & height,
                      unsigned int idxPrev, unsigned int idxFollowing)
{
    int f1A = bloom[idxPrev];
    int f1B = wilt[idxPrev];
    int f2A = bloom[idxFollowing];
    int f2B = wilt[idxFollowing];

    bool notIntersecting = 
    f2A > f1B /* --[--]-(--)-- */ ||
    f1A > f2B /* --(--)-[--]-- */ ;

    return height[idxPrev] > height[idxFollowing] && !notIntersecting;
}


class CPreference {
public:
    static vector<int> * pHeight;
    static bool preference(int a, int b)
    {
        return (*pHeight)[a] > (*pHeight)[b];
    }
};
vector<int> * CPreference::pHeight = NULL;

vector<int> getOrdering(vector<int> height,
                        vector<int> bloom,
                        vector<int>  wilt)
{
    int l = height.size();
    vector<int> state = vector<int>(l, -1); /*  Tree where each leave points to its
                                                parent. Being that parent the first
                                                flower type that is forced to be
                                                after (backwards) its children */

    //This loop is the dynamic programming core.
    for(int i = 0; i < l; i++)
        for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
        {
            if(isOverlap(bloom, wilt, height, i, j) &&
                (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
            {
                state[j] = i;
            }
        }

    vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
    for(int i = 0; i < l+1; i++)
        groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

    for(int i = 0; i < l; i++)
    {
        int k = state[i];
  if(k < 0) k = l;
  groups[k].push_back(i);
}

CPreference::pHeight = &height;
for(vector<vector<int> >::iterator it = groups.begin(); it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

На этом этапе каждая строка (i) групп содержит в порядке от большего к меньшему все индексы типов цветка, которые должны быть размещены перед типом цветка с индексом i.

Остался последний шаг, чтобы объединить группы в выходной вектор. То есть, чтобы построить вектор, в котором за каждым элементом следует либо:

• Его родитель на дереве.
• Это следующий брат при сортировке по высоте.

Это можно сделать путем подробного посещения каждого узла группы. Я думаю, что это слабое место моего решения. У меня было не так много времени, поэтому я просто сделал наивную рекурсивную реализацию:

//PRE: each vector, v, in 'groups' is sorted using CPreference
void flattenTree(vector<vector<int> > & groups, vector<int> & out, int currentIdx /*parent*/, int l)
{
    int pIdx = currentIdx;
    if(pIdx < 0) pIdx = l;

    vector<int> & elements = groups[pIdx];
    vector<int> ret;

    for(vector<int>::iterator it = elements.begin(); it != elements.end(); it++)
    {
        flattenTree(groups, out ,*it, l);
    }

    if(currentIdx>=0)
        out.push_back(currentIdx);
}

Который используется для завершения функции getOrdering:

vector<int> getOrdering(vector<int> height,
            vector<int> bloom,
            vector<int>  wilt)
{
  int l = height.size();
  vector<int> state = vector<int>(l, -1); /* Tree where each leave points to its
                         parent. Being that parent the first
                         flower type that is forced to be
                         after (backwards) its children */
  for(int i = 0; i < l; i++)
    for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
      {
        if(isOverlap(bloom, wilt, height, i, j) &&
        (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
        {
            state[j] = i;
        }
      }

  vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
  for(int i = 0; i < l+1; i++)
    groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

  for(int i = 0; i < l; i++)
    {
      int k = state[i];
      if(k < 0) k = l;
      groups[k].push_back(i);
    }

  CPreference::pHeight = &height;
  for(vector<vector<int> >::iterator it = groups.begin();
      it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

   vector<int> ret;
   flattenTree(groups, ret, -1, l);
   for(unsigned int i = 0; i < ret.size(); i++)
    ret[i] = height[ret[i]];
    return ret; 
}

Пожалуйста, дайте мне знать, если вы нашли лучшее решение или знаете, как улучшить мое.

Подход топологической сортировки:

#include<stdio.h>
#include<stdlib.h>
#include <vector>  
#include <queue>  

using namespace std;

#define MAX_FLOWERS 50

struct flower
{
   int id;
   int height;
   int bloom;
   int wilt;
   bool visited;
   int ind;
};

struct flower_comp
{
  bool operator()(const struct flower* lhs, const struct flower* rhs) const
  {
    return rhs->height > lhs->height;
  }   
};

inline bool overlap(const struct flower& a, const struct flower& b)
{
    return !((a.bloom < b.bloom && a.wilt < b.bloom) || (a.bloom > b.bloom && a.bloom > b.wilt));
}

void getOrdering(int height[], int bloom[], int wilt[], int size)
{
    struct flower flowers[MAX_FLOWERS];

    for(int i = 0; i < size; i++)
    {
        flowers[i].id = i;
        flowers[i].height = height[i];
        flowers[i].bloom = bloom[i];
        flowers[i].wilt = wilt[i];
        flowers[i].visited = false;
        flowers[i].ind = 0;
    } 

    bool partial_order[MAX_FLOWERS][MAX_FLOWERS] = {false};

    for(int i = 0; i < size; i++)
    {
        for(int j = i + 1; j < size; j++)
        {
            if(overlap(flowers[i], flowers[j]))
            { 
               if(flowers[i].height < flowers[j].height)
               {
                  partial_order[i][j] = true;
                  flowers[j].ind++; 
               }
               else
               {
                  partial_order[j][i] = true;
                  flowers[i].ind++; 
               }
            }
        }
    }

    priority_queue<struct flower*, vector<struct flower*>, flower_comp> pq;

    for(int i = 0; i < size; i++)
    {
        if(flowers[i].ind == 0)
        {
           pq.push(&flowers[i]);
        }
    }

    printf("{");
    bool first = true;
    while(!pq.empty())
    {
        struct flower* tmp = pq.top();
        pq.pop(); 
        tmp->visited = true;
        if(!first)
        {
           printf(",");
        }
        first = false;
        printf("%d", tmp->height);
        for(int j = 0; j < size; j++)
        {
            if(!flowers[j].visited && partial_order[tmp->id][j])
            {
               flowers[j].ind--;
               if(flowers[j].ind == 0)
               {
                  pq.push(&flowers[j]);
               }
            }
        }
    }
    printf("}\n");
}

int main(int argc, char** argv)
{
    int height[] = {5,4,3,2,1};
    int bloom[] = {1,1,1,1,1};
    int wilt[] = {365,365,365,365,365};

    getOrdering(height, bloom, wilt, sizeof(height)/sizeof(height[0]));

    int height0[] = {5,4,3,2,1};
    int bloom0[] = {1,5,10,15,20};
    int wilt0[] = {4,9,14,19,24};

    getOrdering(height0, bloom0, wilt0, sizeof(height0)/sizeof(height0[0]));

    int height1[] = {5,4,3,2,1};
    int bloom1[] = {1,5,10,15,20};
    int wilt1[] = {5,10,15,20,25};

    getOrdering(height1, bloom1, wilt1, sizeof(height1)/sizeof(height1[0]));

    int height2[] = {5,4,3,2,1};
    int bloom2[] = {1,5,10,15,20};
    int wilt2[] = {5,10,14,20,25};

    getOrdering(height2, bloom2, wilt2, sizeof(height2)/sizeof(height2[0]));

    int height3[] = {1,2,3,4,5,6};
    int bloom3[] = {1,3,1,3,1,3};
    int wilt3[] = {2,4,2,4,2,4};

    getOrdering(height3, bloom3, wilt3, sizeof(height3)/sizeof(height3[0]));

    int height4[] = {3,2,5,4};
    int bloom4[] = {1,2,11,10};
    int wilt4[] = {4,3,12,13};

    getOrdering(height4, bloom4, wilt4, sizeof(height4)/sizeof(height4[0]));

}

То же, что и у Роба, но в Javascript (ES6):

function getOrdering(height, bloom, wilt) {
    var n = height.length;

    var idx = [];
    for (var i = 0; i < n; ++i) idx[i] = i;

    idx.sort( (a, b) => height[a] - height[b] );

    var intersect = (a, b) => !(bloom[a] > wilt[b] || bloom[b] > wilt[a]);

    for (var i = 1; i < n; ++i) {
        // assume they are ordered correctly till index (i-1),
        // start moving flower i to the left until it can't move because of intersection
        var j = i, flw = idx[i];
        while (j > 0 && !intersect(idx[j-1], flw)) {
            idx[j] = idx[j-1];
            idx[--j] = flw;
        }
    }

    return idx.map( x => height[x] );
}

Подобно Робу, снова на Python и слегка запутанной перекрывающейся проверке цветения/увядания.

H = 0
B = 1
W = 2

def getOrdering(heights, blooms, wilts):

    def _f1_after_f2(f1, f2):
        fs1 = set(range(f1[B], f1[W]+1))
        fs2 = set(range(f2[B], f2[W]+1))
        return f1[H] > f2[H] if fs2.intersection(fs1) != set([]) else False

    fs = zip(heights, blooms, wilts)
    fs.sort()
    ffs = []
    for f1 in fs:
        insert_at = len(ffs)
        for f2 in reversed(ffs):
            if _f1_after_f2(f1, f2): break
            insert_at -= 1
        ffs.insert(insert_at, f1)
    return [f[H] for f in ffs]

Графовый алгоритм решения задачи:

Создайте ориентированный граф (V, E): V -> типы цветов E -> отношения между двумя типами цветов

For all pairs (v_i, v_j)
  If v_i is smaller than v_j and v_j 'blocks' v_i
    draw an edge starting from v_i to v_j
For all nodes v_i
  Find the v_i with no incoming edges and the biggest height
   -> write it at the end of the result list
   -> remove v_i and all of its outgoing edges from graph

Дополнительные сведения можно найти на этом форуме: Форум Topcoder - FlowerGarden

Мой похож на сортировку вставками. Для каждого нового цветка он идет сзади вперед и проверяет, не блокирует ли его тот, что перед ним; если это так, это означает, что он должен быть помещен за ним. Точно так же он также ищет спереди назад и проверяет, не блокирует ли его тот, кто позади него; если это так, это означает, что он должен быть помещен перед ним. Если блоков нет, он просто ищет лучшее место по высоте.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>

#define uint32 uint32_t

static void
Swap(int *AIdx, int *BIdx)
{
    int Tmp = *AIdx;
    *AIdx = *BIdx;
    *BIdx = Tmp;
}

static void
SwapTo(int Start, int End, int *Array)
{
    while(Start != End)
    {
        Swap(&Array[Start], &Array[Start - 1]);
        --Start;
    }
}

static void
PrintTo(int End, int *Array)
{
    for(int Idx = 0;
        Idx < End;
        ++Idx)
    {
        printf("%d, ", Array[Idx]);
    }
    printf("\n");
}

/* Does A block B? */
static bool
Blocks(int AIdx, int BIdx, int *Heights, int *Blooms, int *Wilts)
{
    bool Result = (Heights[AIdx] > Heights[BIdx] &&
                   Wilts[AIdx] >= Blooms[BIdx] && 
                   Blooms[AIdx] <= Wilts[BIdx]);

    return Result;
}

static void
Order(int *Heights, int *Blooms, int *Wilts, 
      int FlowerCount)
{
    for(int FlowerIdx = 1;
        FlowerIdx < FlowerCount;
        ++FlowerIdx)
    {
        PrintTo(FlowerIdx, Heights);

        /* front to back */
        int MinIdx = -1;
        for(int Idx = 0;
            Idx < FlowerIdx;
            ++Idx)
        {
            if(Blocks(Idx, FlowerIdx, Heights, Blooms, Wilts))
            {
                MinIdx = Idx;
                break;
            }
        }

        /* back to front */
        int MaxIdx = -1;
        for(int Idx = (FlowerIdx - 1);
            Idx >= 0;
            --Idx)
        {
            if(Blocks(FlowerIdx, Idx, Heights, Blooms, Wilts))
            {
                MaxIdx = (Idx + 1);
                break;
            }
        }

        /* best height index */
        int BestHeightIdx = -1;
        if(MinIdx == -1 &&
           MaxIdx == -1)
        {
            for(int Idx = 0;
                Idx < FlowerIdx;
                ++Idx)
            {
                if(Heights[FlowerIdx] > Heights[Idx])
                {
                    BestHeightIdx = Idx;
                    break;
                }
            }

            if(BestHeightIdx == -1)
            {
                BestHeightIdx = FlowerIdx;
            }
        }

        int SwapToIdx = -1;
        if((MaxIdx == -1 && MinIdx != -1) ||
           (MinIdx == -1 && MaxIdx != -1) ||
           (MaxIdx != -1 && MinIdx != -1 && MaxIdx == MinIdx))
        {
            SwapToIdx = (MinIdx != -1) ? MinIdx : MaxIdx;
        }
        else if(BestHeightIdx != -1)
        {
            SwapToIdx = BestHeightIdx;
        }
        else
        {
            fprintf(stderr, "Spot-finding error:\n MinIdx: %d, MaxIdx: %d, BestHIdx: %d\n",
                    MinIdx, MaxIdx, BestHeightIdx);
            exit(1);
        }

        SwapTo(FlowerIdx, SwapToIdx, Heights);
        SwapTo(FlowerIdx, SwapToIdx, Blooms);
        SwapTo(FlowerIdx, SwapToIdx, Wilts);
    }
}

int
main(int argc, char *argv[])
{
    int Heights0[]  = {5,4,3,2,1};
    int Blooms0[]   = {1,1,1,1,1};
    int Wilts0[]    = {365,365,365,365,365};

    int Heights1[]  = {5,4,3,2,1};
    int Blooms1[]   = {1,5,10,15,20};
    int Wilts1[]    = {4,9,14,19,24};

    int Heights2[]  = {5,4,3,2,1};
    int Blooms2[]   = {1,5,10,15,20};
    int Wilts2[]    = {5,10,15,20,25};

    int Heights3[]  = {5,4,3,2,1};
    int Blooms3[]   = {1,5,10,15,20};
    int Wilts3[]    = {5,10,14,20,25};

    int Heights4[]  = {1,2,3,4,5,6};
    int Blooms4[]   = {1,3,1,3,1,3};
    int Wilts4[]    = {2,4,2,4,2,4};

    int Heights5[]  = {3,2,5,4};
    int Blooms5[]   = {1,2,11,10};
    int Wilts5[]    = {4,3,12,13};

    int *AllHeights[] = {Heights0, Heights1, Heights2, Heights3, Heights4, Heights5};
    int *AllBlooms[] = {Blooms0, Blooms1, Blooms2, Blooms3, Blooms4, Blooms5};
    int *AllWilts[] = {Wilts0, Wilts1, Wilts2, Wilts3, Wilts4, Wilts5};
    int AllFlowerCounts[] = {5, 5, 5, 5, 6, 4};

    printf("\n");
    for(int Idx = 0;
        Idx < 6;
        ++Idx)
    {
        int *Heights = AllHeights[Idx];
        int *Blooms = AllBlooms[Idx];
        int *Wilts = AllWilts[Idx];
        int FlowerCount = AllFlowerCounts[Idx];

        printf("Test %d\n", Idx);
        Order(Heights, Blooms, Wilts, FlowerCount);
        printf("{ ");
        for(int Idx = 0;
            Idx < FlowerCount;
            ++Idx)
        {
            printf("%d", Heights[Idx]);
            if(Idx != (FlowerCount - 1))
            {
                printf(", ");
            }
        }
        printf(" }\n\n");
    }
}

РЕДАКТИРОВАТЬ: это решение ужасно, и я придумал лучшее решение, которое на самом деле является DP; это так: для каждого цветка перебираем все остальные цветы, проверяя, какие из них он блокирует; для тех цветов, которые он блокирует, проверьте все цветы, которые он блокирует, и так далее, пока не доберетесь до цветка, который не блокирует другие. Поместите этот цветок в новый массив. Вернитесь назад и поместите каждый цветок перед ним в следующий слот этого нового массива. Если сделать это для каждого цветка, вы получите массив, полный цветов, которые не блокируют другие. Затем вы ставите каждый цветок как можно дальше вперед. Часть DP этого решения заключается в том, что иногда вы сталкиваетесь с одним и тем же цветком, который ранее уже был заблокирован другим цветком и уже был помещен в новый массив, поэтому мы пропускаем этот цветок вместо того, чтобы преследовать цветы, которые он блокирует.

У меня есть реализация на С++. Я использовал векторный тип данных для хранения высоты, цветения и увядания соответственно, а затем отсортировал его по высоте, после чего взял цветы один за другим и расположил их в соответствии со значениями, связанными с ними.

вот код: -

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

bool comp(pair<int, pair<int,int> >& a,pair<int, pair<int,int> >& b ){
    return (a.first > b.first);
}




bool justify(pair<int, pair<int,int> >& a,pair<int, pair<int,int> >& b, int k , int 
j,  vector<pair<int,pair<int,int> > >& v){
    if(((b.second.first <= a.second.first) && (b.second.second>= a.second.first)) || 
    ((b.second.first <= a.second.second) && (b.second.second>= a.second.second)) || 
    ((b.second.first > a.second.first) && (b.second.second < a.second.second) )){

            pair<int, pair<int,int> > temp = v[j];     
          int i = j-1;
       while(i >= k){

          v[i+1] = v[i];
          i--;


        }
        v[k] = temp;
        return true;
  }
  return false;
}




int main() {

  vector<pair<int,pair<int,int> > > v;
  int n,a,b,c;
  cin>>n;
  for(int i = 0;i < n;i++){
    cin>>a>>b>>c;
    v.push_back(make_pair(a,make_pair(b,c)));
 }


sort(v.begin(), v.end(), comp);



for(int j = 1;j < n;j++){
  for(int k = 0;k < j;k++){
    bool res = justify(v[k],v[j], k, j, v);
   if(res)
   break;
  }
 }

cout<<"output"<<endl;
for(int i = 0;i < n;i++){
    cout<<v[i].first<<" "<<v[i].second.first<<" "<<v[i].second.second<<endl;
}
return 0;

}