|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 23 Dec 2001 06:35:42
To : "Medvedev Michael"
Subject : Re: Помогите найти решение
--------------------------------------------------------------------------------
До меня дошли слухи, что *22.12.01* *0:41:58* пролетало сообщение
от Medvedev к *All* про *"Помогите найти решение"*. И я решил вмешаться.
U> Может кто-то подскажет мне идею решения задачи 1142 Relation с сайта
U> acm.timus.ru - ну хотя бы математическую идею.
U> -------------- Дано натуральное n, 2 <= n <= 10 За заданным n строются
U> всевозможные отношения со знаками <, >, =. Hадо для заданного n найти
U> количество таких отношений.
U> Hапример, для n = 2 ответ 3. Всевозможные отношения: a = b, a < b, b < a.
U> Для n = 3 ответ 13. Всевозможные отношения: a = b = c, a = b < c, c < a =
U> b, a < b = c, b = c < a, a = c < b, b < a = c, a < b < c, a < c < b, b < a
U> < c, b < c < a, c < a < b, c < b <a
ИМХО перебор. Да и ограничения на это указывают, при этом ставить надо либо
<, либо =, т.к. a > b <=> b < a. Плюс = между симоволами надо ставить только
когда
первый из них лексикографически меньше воторого, что бы не возникало, что
a=b, и b=a
разные.
А вообще есть один небольшой прикол, можно написать тупое решение, которое
будет работать час, но в силу того что n <= 10, можно это посчитать дома для
всех n,
а отсылать, что-то вроде:
const a: array[2..10] of longint = (3,13,...);
begin
readln(n);
writeln(a[n]);
end;
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Metal Invaders. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
