IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Числовая последовательность, вписанная окружность, разрезание прямоугольника, сумма двух чисел, укладка плиток
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Задачи олимпиадного типа. Хочу нормально подготовиться, а не выходит. Многое не могу решить. Помогите, пожалуйста, хоть чем-нибудь)
Буду очень благодарна!

Задача 1 “Числовая последовательность »

Имя входного файла: numseq.in
Имя выходного файла: numseq.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Дима недавно поступил на работу в научно-исследовательский институт «Числовые Последовательности». Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей. Недавно руководитель отдела, где начал работать Дима, при решении одной из проблем столкнулся с весьма интересной последовательностью чисел a1, a2, …, an, …, которая определяется следующим образом: a1 = 0 и каждое последующее число a i-тое (1 < i ≤ n) определяется как наименьшее большее натуральное число, десятичная запись которого не содержит цифр, представленных в десятичной записи a i-1.
Требуется написать программу, которая по значению числа n вычисляет величину an.
Формат входных данных
Входной файл содержит целое число n (1 ≤ n ≤ 500).
Формат выходных данных
В выходной файл необходимо вывести ответ на задачу.
Примеры входных и выходных файлов
numseq.in numseq.out
1 ***0***
28 ***911***




Задача 2« Вписанная окружность »
Имя входного файла: polygon.in
Имя выходного файла: polygon.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Требуется написать программу, которая определяет, можно ли в заданный выпуклый многоугольник вписать окружность, и, если это можно сделать, то вычисляет координаты ее центра и радиус.
Формат входных данных
Первая строка входного файла количество вершин многоугольника n (3 ≤ n ≤ 8). Последующие n строк содержат координаты вершин многоугольника в порядке обхода против часовой стрелки, каждая i-ая из них содержит два целых числа: xi и yi, значения которых не превосходят 1000 по абсолютной величине.
Формат выходных данных
Если окружность, вписанная в заданный многоугольник, существует, необходимо вывести в первой строке выходного файла слово YES, иначе – слово NO. В случае положительного ответа выведите во второй строке координаты центра окружности и ее радиус. При проверке решения задачи все величины будут сравниваться с точностью до 10^-6.
Примеры входных и выходных файлов
polygon.in polygon.out
4
0 0 *** YES ***
1 0 ***0.5 0.5 0.5 ***
1 1
0 1


4 *** NO ***
0 0
1 0
1 2
0 2

Задача 3 « Разрезание прямоугольника »
Имя входного файла: rect.in
Имя выходного файла: rect.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

На координатной плоскости задан прямоугольник, высота которого h, а ширина — w. Внутри прямоугольника заданы отрезки, параллельные осям координат и с концами, имеющими целочисленные координаты.
Прямоугольник планируется разрезать на несколько частей горизонтальными или вертикальными разрезами. За один шаг разрешается разрезать на две непустые прямоугольные части только один из имеющихся на этом шаге прямоугольников. При этом запрещается при разрезе пересекать, хотя бы один из заданных отрезков.
Требуется написать программу, позволяющую найти количество способов разрезания исходного прямоугольника на k частей вертикальными и горизонтальными разрезами. Способы, отличающиеся порядком проведения разрезов, считаются различными.

Формат входных данных
Первая строка входного файла содержит размеры прямоугольника – целые числа h и w (1 ≤ h, w ≤ 8). Вторая строка входного файла содержит целое число k – количество частей, на которые требуется разрезать прямоугольник (1 ≤ k ≤ hw). Третья строка содержит целое число cnt (0 ≤ cnt ≤ 10) — количество заданных внутри прямоугольника отрезков. Последующие cnt строк содержат описания этих отрезков, то есть, каждая строка содержит четыре целых числа x1, y1, x2, y2 (0 ≤ x1 ≤ x2 ≤ w, 0 ≤ y1 ≤ y2 ≤ h) — координаты концов отрезка. Все числа в строках разделены пробелом.

Формат выходных данных
В выходной файл необходимо вывести одно целое число — искомое количество способов разрезания исходного прямоугольника. Ответ должен быть представлен по
модулю 230.

Пример входного и выходного файлов
rect.in rect.out
2 2 ***4***
4
0

8 8 *** 767625216***
20
0

4 4 ***3***
2
2
2 0 2 3
2 3 4 3



Задача 4 "Сумма двух чисел"
Имя входного файла: sum.in
Имя выходного файла: sum.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.

Формат входных данных
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.

Формат выходных данных
Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом.
Примеры входных и выходных файлов
sum.in sum.out
12 31 25 ***YES***
***12 13***


12 31 26 ***NO***



Задача 5 «Укладка плиток»
Имя входного файла: tiling.in
Имя выходного файла: tiling.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Вы являетесь одним из разработчиков нового архитектурного пакета прикладных программ CadArch. Одной из его функций является проектирование укладки половых плиток. В настоящее время вы занимаетесь программной реализацией модуля, который отвечает за укладку плиток в прямоугольных помещениях.

Для простоты будем считать, что пол помещения представляет собой прямоугольник размером n на m метров, разбитый на m∙n квадратиков со стороной по 1 метру. Кроме этого, будем считать, что имеется четыре типа плиток, показанные в таблице. Каждая из плиток представляет собой квадрат размером 2 на 2 метра, из которого вырезан один квадратик размером 1 на 1 метр.


Прикрепленное изображение


Проектируемый модуль должен работать следующим образом. На вход модуля подается набор команд, каждая из которых обозначает, в какое место и какого типа плитку необходимо положить. Команда обрабатывается следующим образом: если ни один из квадратиков, который должна занимать текущая плитка, не занят и плитка полностью помещается внутри прямоугольника, то плитка размещается в указанном месте, в противном случае – нет.

Требуется написать программу, которая определяет, какая площадь в соответствии с заданным набором команд будет покрыта плитками.

Формат входных данных
Первая строка входного файла содержит два числа m и n — размеры пола помещения (1 ≤ m, n ≤ 50). Вторая строка содержит число k — количество команд, которые необходимо обработать (0 ≤ k ≤ 1000). Каждая из последующих k строк содержит описание одной команды из набора команд. Описание команды состоит из трех чисел. Первое число определяет тип плитки (число от 1 до 4), а два других - координаты левого верхнего квадрата размером 2 на 2, в который вписана соответствующая плитка.

Формат выходных данных
В выходной файл необходимо вывести одно число, определяющее площадь, покрытую плитками после выполнения заданной во входном файле последовательности команд.

Примеры входных и выходных файлов
tiling.in tiling.out
4 4 ***6***
4
4 1 1
2 2 2
3 1 1
1 3 3



P.S. ***0*** - обозначают, что числа и выражения, находящиеся внутри, относятся к выходному файлу (не получилось нормально написать)

Сообщение отредактировано: Ирбис377 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата(Правила)
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
Либо ты приводишь тему в соответствие, либо правило срабатывает... Это первое.

Второе: а если ЭТО - задачи текущей олимпиады, тогда как? Тогда помощи не жди...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Цитата(volvo @ 15.01.2010 16:27) *

Второе: а если ЭТО - задачи текущей олимпиады, тогда как? Тогда помощи не жди...

Врядли. Район был до НГ. Скорее всего город. А это совершенно не городские задачи(по крайней мере первая) и условий 100пудово никто не знает. Хотя на районах такое часто бывает yes2.gif
Цитата
Это первое
Ирбис377, переименуй тему - выложу решение.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


1. Это задачи республиканского этапа еще 2007 года. (единственный архив, который нашла в школе, даже за 2008 год не было).

2. Такое название темы вас устроит?

Сообщение отредактировано: Ирбис377 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
Район был до НГ. Скорее всего город.
То есть, интернет-туров как бы не существует по-твоему?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Это не интернет-тур.
Это всего лишь личная подготовка. Так сказать, пересмотр прошлых олимпиад. Не больше.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Цитата
2. Такое название темы вас устроит?
Люди, пожалуйста, помогите!) вот это еще убери и наверное устроит.
Цитата
То есть, интернет-туров как бы не существует по-твоему?
Я в такое не играл)))
У меня завтра город. Вот в который раз убеждаюсь, что я дурак дураком... Для решения первой задачи достаточно (даже вручную) перебрать хотя бы 50 первых таких чисел, заметить закономерность, и ее записать. И не надо ничего считать итд.

Добавлено через 3 мин.
Файлы доделать, я думаю, не проблема.
var
i,n:integer;
c:extended;
sp,sc:string;
q:char;

label
label1;

begin
n:=500;
c:=0;
for i:=2 to n do
begin
str(round©,sp);
c:=c+1;
label1:
str(round©,sc);
for q:='0' to '9' do
while (pos(q,sp)<>0)and(pos(q,sc)<>0) do
begin
c:=(round© div round(exp((length(sc)-pos(q,sc))*ln(10)))+1)*round(exp((length(sc)-pos(q,sc))*ln(10)));
goto label1;
end;
writeln(round©);//вывод всех подряд
end;
writeln(round©);
readln;
end.

Ну а с условиями делать не хочу - леньки)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Переименовала)


Сообщение отредактировано: Ирбис377 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Вторую задачу я бы решал с помощью аналитической геометрии:
Достаточно найти точку пересечения двух биссектрис углов многоугольника и проверить расстояние от нее до каждой из сторон (они должны быть равными).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Ммм...А ведь действительно! я попробую)
Спасибо!)


... А вот что за тип "extended" ?
при запуске в Pascal ABC вылезает ошибка типа.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Цитата
Задачи олимпиадного типа. Хочу нормально подготовиться, а не выходит. Многое не могу решить. Помогите, пожалуйста, хоть чем-нибудь)
Ты действительно думаешь, что готовое решение ПОМОЖЕТ тебе подготовиться? Подсказка - возможно, но не решение. amega, прими к сведению...

Цитата
ри запуске в Pascal ABC вылезает ошибка типа.
Pascal ABC можно запустить только в мусорку... Больше он ни для чего не годится. Большинство олимпиад его просто не разрешают. И онлайн-серверы, кстати, тоже... А вообще надо указывать сразу, чем ты пользуешься...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Готовое решение мне нужно для того, чтоб понять КАК. потому что я самоучка, и мне не очень легко разбираться во всем этом. А на готовом примере сделать это гораздо легче.



А при запуске в Turbo вылазит ошибка 116. на позиции 12:7




P.S. пользуюсь я не только Pascal ABC, но и FreePascal, Turbo Pascal.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Цитата(Ирбис377 @ 15.01.2010 18:25) *
А при запуске в Turbo вылазит ошибка 116. на позиции 12:7

http://tpdn.ru/guide/errors/detail.php?id=5717
Цитата
amega, прими к сведению...
Это, наверное, мне? smile.gif
Кстати, я понял в чем еще прикол первой задачи)
вот в этой строке
c:=(round© div round(exp((length(sc)-pos(q,sc))*ln(10)))+1)*round(exp((length(sc)-pos(q,sc))*ln(10)));
изначально я ставил inc©; так оно уже на н=70 тормозило)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


?
***

Группа: Пользователи
Сообщений: 283
Пол: Мужской

Репутация: -  4  +


Цитата
Это, наверное, мне?

нет, Это мне.

зы скачал книгу Turbo_Assembler_2nd_Ed_Tom_Swan_rus зделал сам(хоть не очень и качетвенно) и получил 104 и 100 возможных smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Могу поделиться собственными соображениями по решению задач 4 и 5...

Задача 4: прекрасно решается непосредственно моделированием (т.к. число перестановок равно N!, то общее число итераций будет невелико).

Детали реализации:
1) имхо, удобнее всего хранить числа в строках.
2) т.к. максимальная длина чисел a, b, c не может превышать трех, то удобно сразу привести их к длине 3 (путем добавления ведущих нулей).

Собственно, в решении необходимо перебрать все возможные комбинации перестановок чисел a и b ( двумя вложенными циклами), и если на какой-то итерации выполняется условие с = a + b, то вывести YES.

Задача 5: опять - таки решается моделированием. Заведем двумерный массив D с элементами типа boolean (изначально должен быть заполнен false). Соответственно, если в этом массиве D[i, j] = true, то часть пола с координатами (i, j) размерами 1 на 1 метр занята, иначе - свободна. Далее все очевидно - в цикле от 1 до k будем пытаться добавлять поступающие плитки (здесь необходима только аккуратность и ничего более). Для того, чтобы вычислить ответ, делаем так:

Код
result :=0;
for i := 1 to n do
  for j := 1 to m do
    if D[i, j] then inc(result);


Ответ будет лежать в переменной result.

Сообщение отредактировано: Tony -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Посмотри обсуждение 4ой задачи в соседней теме. Там и решение.


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Сделал 5ю. Типов только, кажется, понаописал чересчур.. Только там, в условии, приведённом ТС, вроде как неверно указано соответствие входных и выходных данных...

const p=50;

type
plit = array[1..2,1..2] of boolean;
plits=record
vid:byte;
typ:plit;
x,y:integer;
end;
prom = array[1..4] of boolean;

var pol:array[1..p,1..p] of boolean;
f:text;
m,n,z1,z2:byte;
i,j,v,b,k,itogo:integer;
pl:array[1..50] of plits;
typs:array[1..4] of prom;

begin
itogo:=0;
fillchar(pol,p*p,false);
typs[1][1]:=false;typs[1][2]:=true;typs[1][3]:=true;typs[1][4]:=true;
typs[2][1]:=true;typs[2][2]:=false;typs[2][3]:=true;typs[2][4]:=true;
typs[3][1]:=true;typs[3][2]:=true;typs[3][3]:=false;typs[3][4]:=true;
typs[4][1]:=true;typs[4][2]:=true;typs[4][3]:=true;typs[4][4]:=false;
assign(f,'tiling.in');
reset(f);
readln(f,m,n);
readln(f,k);
for i:=1 to k do
readln(f,pl[i].vid,pl[i].x,pl[i].y);
close(f);
for i:=1 to k do
begin
z1:=1;z2:=1;
for j:=1 to 4 do
begin
pl[i].typ[z1,z2]:=typs[pl[i].vid][j];
if (z2=2) then begin
inc(z1);
z2:=0;
end;
inc(z2);
end;
end;
for i:=1 to k do
begin
v:=1;b:=1;
for z1:=pl[i].x to pl[i].x+1 do
for z2:=pl[i].y to pl[i].y+1 do
begin
if (pl[i].typ[v,b]) and (not(pol[z1,z2])) then begin
inc(itogo);
pol[z1,z2]:=true;
end else
if (pl[i].typ[v,b]) and ((pol[z1,z2])) then
begin
assign(f,'tiling.out');
rewrite(f);
write(f,'0');
close(f);
halt;
end;
if (b=2) then begin
inc(v);
b:=0;
end;
inc(b);
end;
end;
assign(f,'tiling.out');
rewrite(f);
write(f,itogo);
close(f);
end.




На олимпиаде я фиг бы успел решить такое..

Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Спасибо большое!
Вы мне очень помогли)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 15:46
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name