/* Задача 1.3 СОРТИРАНЕ Сортирането не винаги е лесна задача. Представете си, че съществуват K (4<K<200) непразни сортирани редици от неотрицателни цели числа не надвишаващи 2000000000, като редиците са номерирани от 1 до K, а дължините им не са известни. Задачата е да напишете програма SORK.EXE, която да сортира всички числа от K-те редици. За целта ще може да използвате подпрограма srv с три формални параметъра – първите два codе и value са цели стойности, които предавате в подпрограмата, а третият е цяла променлива answ, в която да получавате отговора на подпрограмата, когато такъв отговор е смислен. Възможни са 4 стойности за параметъра codе със следния смисъл: Инициализация (codе=0): извикването с този код трябва да се извърши еднократно и преди всички други извиквания на подпрограмата srv. В този случай стойността на параметъра value е без значение. Като резултат подпрограмата srv връща в параметъра answ стойността на K. Заявка за поредно число (codе=1): извикването с този код може да се извърши многократно, но само след инициализация. В този случай стойността на параметъра value е номерът на редицата, от която искате поредното число. Като резултат подпрограмата srv връща в параметъра answ исканото число, ако числата в редицата не са свършили. Ако числата в указаната редица са свършили, подпрограмата srv връща –1 в параметъра answ. Не е позволено да правите тази заявка за редица, за която вече знаете, че числата са свършили. Изпращане на сортирано число (codе=2): извикването с този код може да се извърши многократно, но само след инициализация. В този случай стойността на параметъра value трябва да е поредното число в сортираната редица на всички числа. В този случай подпрограмата srv не връща стойност в параметъра answ. Във всеки момент от работата на програмата, разликата между броя на изпълнените заявки за поредно число (codе=1) и изпратените сортирани числа (codе=2) не бива да надвишава 250000. Край (codе=3): извикването с този код трябва да се извърши еднократно и след всички други извиквания на подпрограмата srv. В този случай стойността на параметъра value е без значение, подпрограмата не връща стойност в параметъра answ и прекратява изпълнението на програмата. РЕШЕНИЕ от Иван Анев Условието на задачата изказано накратко е: да се обединят в сортиран вид K сортирани редици. Как обединяваме 2 сортирани редици. Взимаме по-малкия пореден елемент от двете редици и го прибавяме към новостроящата се редица, като отстраняваме елемента от първата редица. Аналогично за K редици, ситуацията ще изглежда по-следния начин. Разглеждаме поредните елементи в K-те редици, избираме най-малкия от тях и го прибавяме към новата редица. На следващата стъпка в редицата с отстранения елемент разглеждаме следващия елемент. Изпълняваме тази операция докато елементите във всички редици свършат. Описания алгоритъм може ефективно да се реализира използвайки структурата “пирамида”. За всяка редица ще сме прибавили поредния елемент в пирамидата. На всяка стъпка ще отстраняваме най-малкия елемент от пирамидата и ще прибавяме следващия елемент от редицата, на която е принадлежал отстранения елемент. Така на всяка стъпка ще знаем редицата с най-малкия елемент и своеобразно ще обновяваме структурата. Когато числата в някоя редица свършат, ще "отстраняваме" редицата от пирамидата. */ /* NAME: Ivan Anev PROG: sork LANG: C++ */ #include <stdio.h> #define MAXK 256 int heap[MAXK], heapsize; int seq[MAXK]; int k; extern void srv(int, int, int*); void solve(void); int main(void) { solve(); return 0; } void solve(void) { int i; int answ; void add(int s); void movedown(int v); srv(0, 0, &k); for (i = 1; i <= k; ++i) { srv(1, i, &answ); if (answ != -1) { seq[i] = answ; add(i); } } while (heapsize > 0) { srv(2, seq[heap[0]], NULL); srv(1, heap[0], &answ); if (answ != -1) seq[heap[0]] = answ; else heap[0] = heap[--heapsize]; if (heapsize > 0) movedown(0); } srv(3, 0, NULL); } void add(int s) { void moveup(int v); heap[heapsize] = s; moveup(heapsize++); } void moveup(int v) { int p, t; t = heap[v]; while (v > 0) { p = (v - 1) / 2; if (seq[heap[p]] > seq[t]) { heap[v] = heap[p]; v = p; } else break; } heap[v] = t; } void movedown(int v) { int c, t; t = heap[v]; while ((c = 2 * v + 1) < heapsize) { if (c + 1 < heapsize && seq[heap[c]] > seq[heap[c+1]]) ++c; if (seq[heap[c]] < seq[t]) { heap[v] = heap[c]; v = c; } else break; } heap[v] = t; }