/* Задача B1. БАНКИ Дадени са N банки, номерирани с числата 1, 2, ..., N, където N е цяло положително число, не по-голямо от 30000. В продължение на един работен ден банките трябва да извършат многобройни преводи една към друга, според желанията на техните клиенти. Естествено, не е необходимо при всеки превод да се извършва релно превеждане на съответната сума. Достатъчно е в края на деня всяка от банките да е “на чисто”. Това ще рече, ако сумата на превежданите от нея към другите банки пари е по-голяма от сумата на превежданите от другите банки към нея пари, банката да извърши реален превод (или няколко превода) за разликата на двете суми, а ако съотношението е обратното – да получи реален превод (или няколко превода) за разликата от двете суми. А ако двете суми са еднакви – банката нито изпраща, нито получава преводи. Напишете програма BANK.EXE, която намира какви преводи реално трябва да се направят в края на деня така, че всички банки да са “на чисто”, а сумата на реално извършваните преводи да е минимална. Входните данни трябва да се четат от стандартния вход. Първият ред на входа ще съдържа числото N. Всеки от следващите редове описва един превод поискан от клиент и се състои от три цели положителни числа I, J и S – номерът на изпращащата банка, номерът на получаващата банка и превежданата сума, съответно. Край на данните ще бъде ред с три нули. Сумата на всички преводи от или към отделна банка няма да е по-голяма от 1 000 000 000 лева. Полученият резултат трябва да се изведe на стандартния изход. Първият ред на резултата е цялото число K – броят на реално необходимите преводи. Ако K е положително, всеки от следващите K реда описва един реален превод между банки и се състои от три цели положителни числа I, J и S – номерът на изпращащата банка, номерът на получаващата банка и превежданата сума, съответно. Ако никакъв реален превод не се налага програмата трябва да изведе само един ред с числото 0. ПРИМЕР 1 ПРИМЕР 2 Вход: Вход: 5 5 1 2 100 1 3 100 2 3 101 2 4 101 3 4 101 3 5 100 4 5 101 4 2 101 5 1 100 5 1 100 0 0 0 0 0 0 Изход: Изход: 1 0 2 5 1 Решение на задача В1 – Банки От Иван Анев За всяка банка в задачата ще направим баланс. А именно ще изчислим сумата пари, която банката трябва да получи или да даде в края на деня. Ако балансът е положителен то банката трябва да преведе сума пари равна на съответната стойност на баланса. Ако балансът е отрицателен то банката трябва да получи сума пари равна на абсолютната стойност на баланса. Всеки превод прибавя или изважда от баланса, съответно когато се направи заявка, при която банката трябва да даде или да получи пари. Трябва да се забележи, че сумата от балансите на всички банки е нула, тоест сумата пари, която трябва да се получи и даде е една и съща. Това е така, защото в началото балансът на всички банки е нула и всяка заявка за превод прибавя и изважда едно и също число от два различни баланса. Тоест сумата остава една и съща, а именно нула. Веднъж изчислили балансите на всяка банка можем, по произволен начин, да прехвърляме пари от банките, който трябва да дават към банките, който трябва да получават. Разбира се без да надвишаваме парите, които конкретна банка трябва да даде, или които друга трябва да получи. Тоест превеждаме пари от конкретна банка докато не дадем толкова пари, колкото ни сочи баланса и после продължаваме да взимаме пари от друга банка. Аналогично прехвърляме в конкретна банка, докато не преведем точно толкова пари колкото банката трябва да получи спрямо баланса и после се прехвърляме на следващата банка, която трябва да получава. В един момент ще се окаже, че няма банка която трябва да дава, нито такава, която да получава. */ /* NAME: Ivan Anev PROG: bank LANG: C++ */ #include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn = 30000; class Banks { private: int n, tc; int b[maxn]; int t[maxn][3]; public: void solve() { int i, j, x, y, s; memset(b, 0, sizeof(b)); scanf("%d", &n); while (1) { scanf("%d%d%d", &x, &y, &s); if (x == 0 && y == 0 && s == 0) break; b[x-1] += s; b[y-1] -= s; } i = j = tc = 0; while (1) { while (i < n && b[i] <= 0) i++; while (j < n && b[j] >= 0) j++; if (i == n) break; t[tc][0] = i + 1; t[tc][1] = j + 1; if (b[i] >= abs(b[j])) { t[tc++][2] = -b[j]; b[i] += b[j]; b[j] = 0; } else { t[tc++][2] = b[i]; b[j] += b[i]; b[i] = 0; } } printf("%d\n", tc); while (tc-- > 0) printf("%d %d %d\n", t[tc][0], t[tc][1], t[tc][2]); } }; Banks banks; int main() { banks.solve(); return 0; }