Финален (подборен) кръг от националната
олимпиада по информатика - София 1999
тема 8-11 клас, ден
2, зад. 3Везна (40 точки)
Фиг.1
На Фиг.1 можете да видите сложна везна с перфектен баланс (Това означава, че има баланс за всяко рамо от сложната везна). Везната има пет тежести съответно от 1 кг.,2 кг., … , 5 кг. Разстоянието между две връзки е 1м. Можете да проверите баланса чрез следните изчисления :
-3*3 + (-1)*5 + 2*(1+2+4) = 0 (горно рамо) ,
-2*1 + (-1)*2 + 1*4=0
(долно рамо) .Структурата на сложната везна е зададена чрез низ. Тази от Фиг.1 се описва по следния начин :
(-3,-1,2(-2,-1,1)) (*)
Намерете такива тежести, така че сложната везна да бъде в перфектен баланс, и запишете отговора в друг низ. Решението на примера от фиг.1 е:
(3,5,(1,2,4)) (**)
Съставете програма, която да прочита структура на сложна везна от входен текстов файл, изчислява тежестите и записва резултата в изходен файл.
ВХОД
В единствения ред на входния файл
MOBILE.IN е записан един низ - структура на сложна везна. Всички числа са цели и са между -50 и 50 (включително).Примерен вход :
виж *ИЗХОД
В изходния файл
MOBILE.OUT запишете изходния низ без никакви интервали.
Други примери:
ВХОД
(файл MOBILE.IN)(-3(-1(-1(-1,1,2),3),2),3(-2,1,2),6(-2,3))
ИЗХОД
(файл MOBILE.OUT)((((8,6,1),5),10),(9,4,7),(3,2))
ВХОД
(файл MOBILE.IN)(-8,-4(-5,-3,-1,1),-2(-1,1,3),2(-1(-3,-2,1(-2,1,3)),1,3),6)
ИЗХОД
(файл MOBILE.OUT)(10,(1,2,4,15),(14,5,3),((6,8,(16,11,7)),9,13),12)
РЕШЕНИЕ:
Зададените ограничения са достатъчно малки за да "открием" че задачата се решава с метода на пълното изчерпване.
Везната можем да представяме като дърво – забелязва се че самата везна има такава стуктура.
Всяко рамо ще представлява един възел на дървото, а поддърветата ще бъдат съотвентите "подрамена".
Ще използваме структурата
MTree за представяне на дървото, като в полето count ще пазим броя на тежестите на това рамо, в масива mulV[] – с колко умножаваме съответните тежести, масива v[] ще попълваме по време на работа и това ще са тежестите които трябва да сложим на това рамо, а в масива child[] ще пазим съответните "подрамена" или NULL.И така прочитането на дървото става със функцията
makeTree(), а извеждането със printTree().Тези функции са достатъчно ясни затова няма да бъдат описвани по-подробно. Само трябва да добавя че при прочитането на везната всяко рамо се съхранява в масива
mobs[], a mcount е броя на рамената.Идеята е следната:
Проверяваме всички комбинации от тежести който можем да сложим на едно рамо и така рекурсивно за всички рамена във везната, като започваме от първото (главното) рамо, и за това рамо първо намираме такова разположение на тежестите върху неговите подрамена че да се получи баланс за всяко рамо. Това се върши от рекурсивната функция
makePerfect(int treeNum, int k), kъдето treeNum е текущо разглежданото рамо, а k е текущо разглежданата тежест в това рамо. makePerfect прави следното:докато има още тежести за слагане на това рамо се опитва рекурсивно да ги слага. Ако са сложени тежестите на това рамо тогава проверяваме дали рамото е в перфектен баланс – това се прави от функцията
check() , и ако е така продължаваме рекурсивно със следващото рамо, а ако няма повече не разглеждани рамена – тогава сме намерели решение. Функцията check() прави следното: използва nodeSum(), която рекурсивно намира каква е тежеста на дадено рамо (всички рамена имат вече поставени тежести), след което пресмята дали даденото рамо (заедно със всички подрамена) е в перфектен баланс.makePerfect()
изглежда така:void makePerfect(int treeNum, int k) {
if (k <
броя на тежестите за слагане) {if (
рамото treeNum е идеално балансирано) {if (
ако рамото treeNum не е последно)makePerfect(treeNum+1, 0);
// обработваме следващото рамоelse
O
тпечатваме решението и прекъсваме програмата;}
return;
}
if (това рамо няма подрамена
) {makePerfect(treeNum, k+1);
// обработваме следващото рамо} else
for (i=1..
броя на тежестите за слагане(N)) {if (
тежеста i е свободна) {маркираме тежеста i като заета
поставяме тежеста на k-то място в това рамо
makePerfect(treeNum, k+1);
маркираме тежеста i като свободна
}
}
ПРОГРАМА (
C++):
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
struct MTree {
int count;
int mulV[10], v[10];
MTree *child[10];
};
FILE *F;
MTree *mobile, *mobs[17];
int used[18];
int n=0, mcount=0;
MTree *makeTree() {
MTree *tmp;
int v;
char c;
tmp = new MTree;
tmp->count=0;
while (1) {
fscanf(F, "%d%c", &v, &c);
n++;
tmp->mulV[tmp->count] = v;
if (c == '(') {
n--;
tmp->child[tmp->count] = makeTree();
fscanf(F, "%c", &c);
} else
tmp->child[tmp->count] = NULL;
tmp->count++;
if (c == ')') break;
}
mobs[mcount++] = tmp;
return tmp;
}
int nodeSum(MTree *t) {
int sum=0;
for (int i=0; i<t->count; i++) {
if (t->child[i] == NULL) sum += t->v[i];
else sum += nodeSum(t->child[i]);
}
return sum;
}
void printTree(MTree *t) {
fprintf(F,"(");
for (int i=0; i<t->count; i++) {
if (t->child[i] == NULL)
fprintf(F,"%d", t->v[i]);
else
printTree(t->child[i]);
if (i<t->count-1) fprintf(F,",");
}
fprintf(F,")");
}
void printSol() {
F = fopen("MOBILE.OUT", "wt");
printTree(mobile);
fclose(F);
exit(0);
}
int check(MTree *t) {
int sum=0;
for (int i=0; i<t->count; i++)
if (t-> child[i] == NULL) sum += t->mulV[i] * t->v[i];
else sum += nodeSum(t->child[i]) * t->mulV[i];
return (sum==0);
}
void makePerfect(int treeNum, int k) {
if (k == mobs[treeNum]->count) {
if (check(mobs[treeNum])) {
if (treeNum < mcount-1)
makePerfect(treeNum+1, 0);
else
printSol();
}
return;
}
if (mobs[treeNum]->child[k] != NULL) {
makePerfect(treeNum, k+1);
} else
for (int i=1; i<=n; i++)
if (!used[i]) {
used[i] = 1;
mobs[treeNum]->v[k] = i;
makePerfect(treeNum, k+1);
used[i] = 0;
}
}
void solve() {
makePerfect(0, 0);
}
void main() {
F = fopen("mobile.in", "rt");
fgetc(F);
mobile = makeTree();
solve();
fclose(F);
}
Васил Поповски
студент - СУ