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

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

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

 
 Ответить  Открыть новую тему 
> Свежие олимпиадные задачи (10.12.2006)
сообщение
Сообщение #1





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

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


Задача А. Спор (100 баллов)

Ввод: с клавиатуры
Вывод: на экран
Ограничение по времени: 5 секунд
Ограничение по памяти: 64 мегабайта


Вася и Петя поспорили, можно ли с помощью монетки построить такую игру, чтобы вероятность выиграша была равна заданной дроби p/q. Разрешается кидать монету произвольное количество раз, и каждый раз монета выпадает любой из сторон с вероятностью равной 1/2. Эта последовательность записывается, и некоторые конечные последовательности объявляются выигрышными, а некоторые - проигрышными. При этом независимо от хода игры она должна закончиться не более чем за некоторое КОНЕЧНОЕ число бросаний, не зависящее от конкретной последовательности выпавших сторон.
Вам требуется написать программу, которая разрешит спор.

Формат входного файла
Заданы два целых числа p и q (0<=p<=q<=10^9, q<>0).
Формат выходного файла
Выведите YES, если такую игру можно построить, NO в противном случае (заглавными буквами).

Пример

Ввод
9 24
Вывод
YES


Ввод
1 3
Вывод
NO

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





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

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


Задача B. Строчка (60 баллов)

Имя входного файла: string.in
Имя выходного файла: string.out
Ограничение по времени: 5 секунд
Ограничение по памяти: 64 мегабайта

На день рождения родители подарили Васе набор кубиков, на которых написаны разные английские буквы. Он тут же начал выкладывать из кубиков разные слова, но все они ему не нравились. Наконец он понял, что ему нравятся слова-палиндромы, которые читаются справа налево так же, как и слева направо. Например, abba, bcb, k - палиндромы, а abaa, ab, acccb - нет. Теперь Вася хочет убрать некоторые кубики из последнего выложенного им слова так, чтобы остался палиндром. Причем на самом первом кубике Вася уже построил железную дорогу, поэтому он может убирать кубики только начиная с последнего и дальше по порядку. То есть, из слова abcde он сначала получит abcd, затем - abc, затем - ab, и, наконец, - a. Помогите Васе узнать, какой полиндром максимальной длинны он сможет получить из своего слова описанным образом!

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

Пример

strin.in
aba

string.out
aba

string.in
aaaba

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





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

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


Задача С. n-мерные сундуки (150 баллов)

Имя входного файла: chest.in
Имя выходного файла: chest.out
Ограничение по времени: 10 секунд
Ограничение по памяти: 64 мегабайта

n-мерному котенку Мурзику посчастливилось найти тайник с сокровищем древних Тинков. Однако, сокровище оказалось упаковано в n крепких сундуков, занумерованных числами от 1 до n. Сундуки могут находиться внутри друг друга. Для каждого сундука существует уникальный ключ, который необходим, чтобы его открыть. Ключ может находиться внутри некоторого сундука, либо просто висеть на стене в тайнике. Сокровище находится в сундуке K.

Мурзику не терпится, что же внутри. Но замки сундуков очень старые и изрядно заржавели. Так что на открытие каждого сундука тратится около часа времени. Помогите Мурзику добраться до сундуков, открыв как можно меньше сундуков.


Формат входного файла
Первая строчка входного файла содержит натуральное число [/b]n (1 < n < 1024). Во второй строке записаны n чисел a(i), определяющих положение сундуков. a(i) - номер сундука, внутри которого находится i-й сундук. Если i-й сундук не находится внутри другого, а просто стоит на полу в тайнике, то a(i) равно 0. В третьей строке аналогично описывается положение ключей. i-й сундук можно открыть только с помощью i-го ключа. Последняя строка входного файла содержит число K - номер сундука, где лежит сокровище.
Формат выходного файла
В первой строке выходного файла выведите M - минимальное количество сундуков, которые придется открыть Мурзику. Во второй строке выведите номера этих сундуков в том порядке, в котором он должен их открывать. Если оптимальных решений несколько, разрешается выводить любое.
Если Мурзик не сможет добраться до сокровища, выведите в выходной файл единственное слово IMPOSSIBLE (заглавными буквами).

Пример

chest.in
3
2 0 0
0 0 1
3

chest.out
3
2 1 3

chest.in
3
2 1 0
1 2 1
3

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


Perl. Just code it!
******

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

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


Если я правильно понял условие, то вторая решается достаточно просто:

uses crt;

type

TType = Char;

TFile = file of TType;

PArray = ^TArray;

TArray = array [1..1] of TType;

procedure CreateTestFile(file_name: string; size: Integer);
var
f: TFile;
i: Integer;
T: Byte;

begin

assign(f, file_name);

rewrite(f);

randomize;

for i := 0 to size - 1 do begin
T := 97 + Random(3);
write(chr(T));
write(f, char(T));
end;

close(f);

end;

function ReadFile(file_name: String; var arr: PArray): Integer;
var
f: TFile;
i: Integer;
T: TType;
begin

assign(f, file_name);

reset(f);

GetMem(arr, FileSize(f) * sizeof(TType));

i := -1;

while not(eof(f)) do begin
read(f, T);
inc(i);
arr^[i] := T;
end;

ReadFile := FileSize(f);

close(f);

end;

function isPolindrom(const arr: PArray; const n: Integer): Boolean;
var
i: Integer;
begin

i := 0;

while (i <= n div 2) and (arr^[i] = arr^[n - i - 1]) do inc(i);

isPolindrom := (i > n div 2);

end;

procedure WriteToFile(file_name: String; const arr: PArray; n: Integer);
var
f: TFile;
i: Integer;
begin

assign(f, file_name);

rewrite(f);

for i := 0 to n - 1 do begin
write(arr^[i]);
write(f, arr^[i]);
end;

close(f);
end;

procedure Free(var arr: PArray; size: Integer);
begin
FreeMem(arr, size * sizeof(TType));
end;

var
A: PArray;
n, size: Integer;
begin

clrscr;

CreateTestFile('c:\string.in', 10);

// на случай если файл руками заполнять, а так размер можно задать в CreateTestFile
size := ReadFile('c:\string.in', A);

n := size;

while not(isPolindrom(A, n)) do dec(n);

writeln;

WriteToFile('c:\string.out', A, n);

Free(A, size);

readln;
end.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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