Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения: Учебное издание. Часть 2
Подождите немного. Документ загружается.
достоинством в a1,a2,:,ak единиц, имеющимися в неограниченном
количестве. Числа N,a1,:,ak целые.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 5 секунд
Формат входных данных:
В первой строке входного файла содержатся числа N и K. Далее в
каждой строке файла содержатся достоинства имеющихся купюр.
Формат выходных данных:
Первая строка выходного файла должна содержать YES, если можно
представить и NO, если нельзя представить.
Пример входного и выходного файла:
INPUT.TXT
13 3
3
7
11
OUTPUT.TXT
NO
Алгоритм решения
Алгоритм простой - перебор всех возможных комбинаций из данных
купюр.
Program Plz3;
{Автор Колбешкин Д.М.}
Var fin,fout :text;
i,N,K :integer;
a :array[1..100]of integer;
bool :boolean;
Procedure NextS(Sum,t:integer); {Sum - сумма денег, которую мы
собрали}
var j,i:integer; {t - номер купюры }
begin
if sum=N then
begin
bool:=true {Мы набрали нужную сумму денег}
end else begin
if sum < N then
begin
for j:=t to K do {Выбираем купюку}
if (a[j]>0) then
begin
i:=1; {i - кол-во купюр, которые мы
добавляем}
while (sum+a[j]*i <= N) and (not bool) do
begin
NextS(sum+a[j]*i,j+1);
i:=i+1;
end;
end;
end;
end;
end;
BEGIN
writeln (' Задача про деньги ');
assign(fin,'input.txt');
assign(fout,'output.txt');
reset(fin);
rewrite(fout);
read(fin,N,K);
bool:=false;
for i:=1 to K do
begin
read(fin,a[i]);
if a[i]>0 then if (N/a[i])=trunc(N/a[i]) then bool:=true;
end;
NextS(0,1); {Начинаем собирать сумму денег с первой
купюры}
if bool then write(fout,'YES')
else write(fout,'NO');
close(fin);
close(fout);
END.
Задача 10. " Партии "
Задача предлагалась на первом (заочном)туре Открытой региональной
студенческой школы-олимпиады по программированию и компьютерному
моделированию 17-19 сентября 2001 года .
Автор решения: Бурнаев Константин Евгеньевич , один из призеров
первого тура олимпиады, студент 4 курса Факультета автоматизации
производств и информационных технологий Белгородской технологической
академии строительных материалов (специальность 22.04.00 "Программное
обеспечение автоматизированных систем и вычислительной техники")
e-mail: const@mail.belgorod.ru
Компиляторы: gcc.exe, cl.exe (VC6.0)
На острове BORLAND каждый из его жителей организовал партию, которую сам и
возглавил. В каждой партии – не менее двух человек. По Конституции острова в парламент
должны войти главы всех партий, но финансовые трудности не позволяют это сделать. На
референдуме граждане острова решили , что каждую партию в парламенте достаточно
представлять одним членом партии.
Требуется сформировать парламент как можно меньшей численности , в котором были бы
представлены все партии.
Технические требования .
Все главы партий (и партии) перенумерованы от 1 до N (4<=N<=150).
Входные данные. Первая строка входного текстового файла input.txt содержит N - число
партий, в каждой из последующих строк перечисляются через пробел порядковые номера
граждан – членов соответствующей партии.
Выходные данные. Выходной текстовый файл output.txt содержит порядковые номера глав
партий, вошедших в парламент.
Пример .
Input.txt output.txt
N 4 2
1 2 3 4
2 3
3 1 4 2
4 2
#include <stdlib.h>
#include <stdio.h>
#ifdef DEBUG
#define DBG(params) printf params
#else
#define DBG(params)
#endif
/* ===== Коды возврата функций ===== */
#define ERR_OK 0
#define ERR_PARAM 1
#define ERR_MEMORY 2
#define ERR_FILE 3
#define ERR_FILEFORMAT 4
#define ERR_FAILED 5
/* ===== Работа с матрицами ===== */
#define MATR_BASETYPE unsigned char
#define VECT_BASETYPE unsigned int
struct t_vect {
VECT_BASETYPE *m_ptr;
unsigned int m_size;
};
/* создание нового вектора
Выходные данные: x --- длина вектора
Выходные данные: vect --- структура, описывающая вектор */
int alloc_vect (unsigned int x, struct t_vect *vect) {
/* проверка правильности входных данных */
if (x==0) {
DBG(("Error calling 'alloc_vect': x=%u\n", x));
return ERR_PARAM;
};
/* выделение памяти */
vect->m_ptr = calloc(sizeof(VECT_BASETYPE), x);
vect->m_size = x;
/* проверка */
if ( vect->m_ptr == NULL ) {
DBG(("Error allocating memory in 'alloc_vect':
x=%u\n",x));
return ERR_MEMORY;
};
DBG(("Successful call to 'alloc_vect': x=%u,
vect=%p\n",x,vect));
return ERR_OK;
}
/* Удаление старого вектора */
void free_vect(struct t_vect *vect) {
if (vect->m_ptr == NULL) {
DBG(("Trying to free memory more than once in
'free_vect': vect=%p\n",
vect));
return;
};
free(vect->m_ptr);
vect->m_ptr=NULL;
vect->m_size=0;
DBG(("Successful call to 'free_vect': vect=%p\n",vect));
}
/* Получение указателя на элемент вектора */
VECT_BASETYPE* at_vect(unsigned int x, struct t_vect *vect) {
/* проверка корректности аргументов */
if (x >= vect->m_size) {
DBG(("Error calling 'at_vect': x=%u, vect-
>m_size=%u\n",x, vect->m_size));
return NULL;
};
DBG(("Successful call to 'at_vect': x=%u, vect=%p\n",x,vect));
return &vect->m_ptr[ x ];
}
struct t_matr {
MATR_BASETYPE *m_ptr;
unsigned int m_xsize, m_ysize;
};
/* Создание новой матрицы.
Входные данные: x,y --- размеры матрицы
Выходные данные: matr --- матрица
Примечание: начальное значение всех элементов равно 0; если память
под матрицу уже выделена, она не освобождается */
int alloc_matr(unsigned int x, unsigned int y, struct t_matr *matr) {
/* проверка корректности входных данных */
if ((x==0) || (y==0)) {
DBG(("Error calling 'alloc_matr': x=%u, y=%u\n",x,y));
return ERR_PARAM;
};
/* выделение памяти */
matr->m_ptr = calloc(sizeof(MATR_BASETYPE), x*y);
matr->m_xsize = x;
matr->m_ysize = y;
/* проверка */
if ( matr->m_ptr == NULL ) {
DBG(("Error allocating memory in 'alloc_matr': x=%u,
y=%u\n",x,y));
return ERR_MEMORY;
};
DBG(("Successful call to 'alloc_matr': x=%u, y=%u,
matr=%p\n",x,y,matr));
return ERR_OK;
}
/* Удаление старой матрицы */
void free_matr(struct t_matr *matr) {
if (matr->m_ptr == NULL) {
DBG(("Trying to free memory more than once in
'free_matr': matr=%p\n",
matr));
return;
};
free(matr->m_ptr);
matr->m_ptr=NULL;
matr->m_xsize=0;
matr->m_ysize=0;
DBG(("Successful call to 'free_matr': matr=%p\n",matr));
}
/* Получение указателя на элемент "двумерной" матрицы */
MATR_BASETYPE* at_matr(unsigned int x, unsigned int y, struct t_matr
*matr) {
/* проверка корректности аргументов */
if ((x >= matr->m_xsize) || (y >= matr->m_ysize)) {
DBG(("Error calling 'at_matr': x=%u, y=%u, matr-
>m_xsize=%u, matr->m_ysize=%u\n",x,y, matr->m_xsize, matr->m_ysize));
return NULL;
};
DBG(("Successful call to 'at_matr': x=%u, y=%u,
matr=%p\n",x,y,matr));
return &matr->m_ptr[ y*matr->m_xsize + x ];
}
/* ===== Работа с файлами ===== */
/* чтение исходных данных.
Входные данные: filename --- имя файла
Выходные данные: matr --- матрица принадлежности граждан
партиям */
int ReadInput (const char *filename, struct t_matr *matr) {
FILE *fh;
unsigned int N;
unsigned int ibuffer;
int i;
int result;
char buffer[10000];
char *cur_pos;
int offset;
fh=fopen(filename, "r");
/* проверка результата */
if (fh == NULL) {
DBG(("Error opening file in 'ReadInput':
filename=%s\n",filename));
return ERR_FILE;
};
if (fscanf(fh,"%u",&N) != 1) {
DBG(("Error reading table size in 'ReadInput':
filename=%s\n",filename));
fclose(fh);
return ERR_FILEFORMAT;
};
/* выделение новой матрицы */
alloc_matr(N,N,matr);
fgets(buffer, 10000, fh);
for (i=0; i<N; i++) {
if (fgets(buffer, 10000, fh) != NULL) {
offset=0;
cur_pos=buffer;
while (sscanf(cur_pos,"%u%n",&ibuffer,&offset) ==
1) {
/* внимание: нумерация элементов в матрице --
- с нуля, нумерация
партий --- с единицы! */
*at_matr(i,ibuffer-1,matr)=1;
cur_pos += offset;
};
} else {
DBG(("Failed to read line %u in 'ReadInput':
filename=%s\n",i,filename));
fclose(fh);
return ERR_FILEFORMAT;
};
};
fclose(fh);
DBG(("Successful call to 'ReadInput':
filename=%s\n",filename));
return ERR_OK;
}
int WriteOutput(const char *filename, struct t_vect *vect) {
int x,y;
FILE *fh;
fh=fopen(filename, "w+");
/* проверка результата открытия файла */
if (fh == NULL) {
DBG(("Error creating file in 'WriteOutput':
filename=%s\n", filename));
return ERR_FILE;
};
for (x=0; x<vect->m_size; x++) {
fprintf(fh, "%u ", (*at_vect(x,vect))+1);
};
fclose(fh);
DBG(("Successful call to 'WriteOutput': filename=%s\n",
filename));
return ERR_OK;
}
/* ===== собственно решение задачи ===== */
/* оболочка "решателя"
Входные данные: matr --- бинарная матрица, которую необходимо
покрыть
Выходные данные: vect (изначально неинициализирован) ---
вектор
результатов */
int GenCombination(unsigned int n, unsigned int k, struct t_vect
*vect) {
int i;
i=vect->m_size-1;
(*at_vect(i,vect))++;
while ((*at_vect(i,vect) > n-1) && (i>0)) {
(*at_vect(i-1,vect))++;
i--;
};
for (; i+1<vect->m_size; i++) {
*at_vect(i+1,vect) = *at_vect(i,vect)+1;
};
if (*at_vect(i,vect) < n) return ERR_OK;
return ERR_FAILED;
}
int TestCombination(struct t_matr *matr, struct t_vect *vect) {
int x,p;
struct t_vect excluded;
int excl_size;
alloc_vect(matr->m_xsize,&excluded);
excl_size=0;
for (p=0; p<vect->m_size; p++) {
for (x=0; x<matr->m_xsize; x++) {
if (*at_matr(x,*at_vect(p,vect),matr)) {
if (!*at_vect(x,&excluded)) {
excl_size++;
(*at_vect(x, &excluded)) ++;
};
};
};
};
free_vect(&excluded);
if (excl_size < matr->m_xsize) {
return ERR_FAILED;
} else {
return ERR_OK;
};
}
int SolvePrecise(struct t_matr* matr, struct t_vect* vect) {
int k,i;
alloc_vect(matr->m_ysize, vect);
for (k=1; k<matr->m_ysize; k++) {
vect->m_size=k;
for (i=0; i<k; i++) {
*at_vect(i,vect)=i;
};
do {
if (TestCombination(matr,vect)==ERR_OK) {
DBG(("Successful call to 'Solve'\n"));
return ERR_OK;
};
} while (GenCombination(matr->m_ysize, k, vect) ==
ERR_OK);
};
vect->m_size=0;
DBG(("Successful call to 'Solve'; no solution found!\n"));
return ERR_FAILED;
}
int CalcMarks(struct t_matr *matr, struct t_vect *vect, struct t_vect
*excl) {
int x,y;
int max, imax;
max=0;
imax=0;
for (y=0; y<matr->m_ysize; y++) {
for (x=0; x<matr->m_xsize; x++) {
if (*at_vect(x,excl) == 0) {
*at_vect(y,vect) += *at_matr(x,y,matr);
if (*at_vect(y,vect) > max) {
max=*at_vect(y,vect);
imax=y;
};
};
};
};
return imax;
}
int Solve(struct t_matr* matr, struct t_vect* vect) {
struct t_vect marks, excluded;
unsigned int excl_num;
int i,pos;
int solve_size;
alloc_vect(matr->m_ysize, vect);
alloc_vect(matr->m_ysize, &marks);
alloc_vect(matr->m_xsize, &excluded);
excl_num=0;
solve_size=0;
while (excl_num < matr->m_xsize) {
for (i=0; i<marks.m_size; i++) *at_vect(i,&marks)=0;
pos=CalcMarks(matr, &marks, &excluded);
*at_vect(solve_size, vect)=pos;
solve_size++;
for (i=0; i<matr->m_xsize; i++) {
if (*at_matr(i,pos,matr)) {
if (!*at_vect(i,&excluded)) {
excl_num++;
};
(*at_vect(i,&excluded))++;
};
};
};
vect->m_size = solve_size;
free_vect(&excluded);
free_vect(&marks);
DBG(("Successful call to 'Solve'\n"));
return ERR_OK;
}
/* ===== входная точка программы ===== */
int main(int argc, char *argv[]) {
struct t_matr matr;
struct t_vect solution;
ReadInput("input.txt",&matr);
if (matr.m_xsize > 60) {
Solve(&matr, &solution);
} else {
SolvePrecise(&matr, &solution);
};
free_matr(&matr);
WriteOutput("output.txt",&solution);
free_vect(&solution);
return ERR_OK;
}
Задача 11. " Переселение "
Задача предлагалась на первом (заочном)туре Открытой региональной
студенческой школы-олимпиады по программированию и компьютерному
моделированию 17-19 сентября 2001 года .
Автор решения: Козлов Юрий Станиславович, один из призеров первого
тура олимпиады, студент 1 курса РТФ ВИ МВД РФ 16гр
На Компьютерной улице живут в собственных домах только семьи Паскалёвых и
Сиплюсплюсовых. Они решили переселиться так , чтобы все Паскалёвы жили в начале улицы ,
а все Сиплюсплюсовы - в конце . Известно общее количество домов на улице и кто живет в
каждом доме.
Требуется разработать модель и алгоритм (программу) переселения, при условии, что
каждая семья должна переезжать не более одного раза, а в каждом обмене должны участвовать
только две семьи .
Uses Crt,Dos;
const n=30;
delayy=200;{ <= измените, если тормозит заставка}
Var street,street2:array[1..n] of integer;
i,s,left,right,j,k,a,b,q,f:integer;
Procedure HideCursor;
Var regs: registers;
Begin
regs.ah:=1;
regs.ch:=$20;
regs.cl:=0;
regs.bh:=0;
Intr($10,regs);
End;
Procedure Introduction; {заставка}
var i,x,y,cx,cy,ctx,cty,textn,maxx,maxy:byte;
text:array[1..20] of string;
index:char;
Begin
HideCursor;
cx:=42;
cy:=13;
maxx:=32;
maxy:=8;
ctx:=cx-maxx+1;
cty:=cy-maxy-1;
Text[1]:=' Козлов Юрий Станиславович';
Text[2]:=' ВИ МВД России';
Text[3]:=' 394065, г.Воронеж Прспект Патриотов, 53,';
Text[4]:=' тел. 33-18-67 ';
Text[5]:='';
Text[6]:=' Радиотехнический факультет';
Text[7]:='Информационная безопасность телекоммуникационных систем ';
Text[8]:='(обеспечение информационной безопасности
телекоммуникационных';
Text[9]:=' систем в ОВД)';
Text[10]:=' дневная форма обучения';
Text[11]:=' Потанин Виталий Евгеньевич ';
Text[12]:='';
Text[13]:=' Енина Зоя Ивановна (Лицей №1)';
Text[14]:='';
Text[15]:=' 394016, г.Воронеж Московский пр-т д.82, кв.236';
Text[16]:=' тел. 74-91-12 ';
textn:=16;
TextBackGround(Blue);
TextColor(White);
For y:=0 to maxy do
begin
GotoXy(cx-1,cy-1-y);Write('г¬');
GotoXy(cx-1,cy-y); Write('¦¦');
GotoXy(cx-1,cy-1+y);write('¦¦');
GotoXy(cx-1,cy+y); Write('L-');
Delay(delayy);
end;
For x:=0 to maxx do
begin
GotoXy(cx-1-x,cy-1-maxy);Write('г');
GotoXy(cx-1-x,cy+maxy); Write('L');
GotoXy(cx+x,cy-1-maxy); Write('¬');
GotoXy(cx+x,cy+maxy); Write('-');
for y:=1 to 2*maxy do
begin
GotoXy(cx-x,cy-1-maxy); Write('=');
GotoXy(cx-1+x,cy-1-maxy);Write('=');
GotoXy(cx-x,cy-1-maxy+y); Write(' ');
GotoXy(cx-1+x,cy-1-maxy+y);Write(' ');
GotoXy(cx-x,cy+maxy); Write('=');
GotoXy(cx-1+x,cy+maxy);Write('=');
GotoXy(cx-1-x,cy-1-maxy+y);Write('¦');
GotoXy(cx+x,cy-1-maxy+y); Write('¦');
end;
Delay(delayy);
end;
for index:=chr(40) to chr(255) do
begin
For y:=1 to textn do
begin
x:=1;
While length(text[y])>=x do
begin
if Text[y][x]=index then begin
case y of
1:textcolor(LightRed);
2:textcolor(LightGreen);
3..5:textcolor(LightGray);
6..9:textcolor(Yellow);
10:textcolor(Green);
11,12:textcolor(LightGray);
13,14:textcolor(LightBlue);
15..17:textcolor(LightRed);
end;
gotoxy(ctx+x,cty+y);
write(text[y][x]);