Задачки для программистов

[Ghost]

EvroStandart
Попробовал твой алгоритм на числе 99. Должно получиться 120 (копи+паст + изменение пары чисел - я их подчеркнул):

После цифры 10 в каждой десятке одно число выбрасываем. Значит: если нужна позиция 99,
1) из восьми десятков выкидываем по числу
2) имеем 107 (99+8) и до цифры 91 включительно всё проверено.
3) проверяем от 92 до 107 перебором, выкидываем 99, 100, 101
4) ответ: 110 (107+3)

Не получается... Или я что-то неправильно понял?

lalexa100
Эээ... Опять-таки, можно пример? Скажем с числом 123 (№100). Или хотя бы формулы по-подробнее расписать и без ошибок (две скобки открываем - одну закрываем)

И кстати, насчет "n1 = 10 0-9": последовательность состоит из положительных чисел, т.е. 0 в нее не входит.

[lalexa100]

Насчет ошибок - я подал только идею, ее еще до ума довести нужно.
число 123 № 100
итак
n1=10 - не катит
n2=10+81=91 - не катит
n3=91+91*8 > 100 катит значит 3 цифры
ищем первую 100-91=9
100-199 9*8=72 > 9 катит - значит цифра 1
ищем вторую
100-109 = 8 (первая 1 вторая 0 третья 2-9) не катит
110-119 выпадает из рассмотрения (первая = второй)
120-129 = 8+8 катит вторая 2
ну а последняя цифра 9 - 8 = 1
из списка 0.2.3.4.5.6.7.8.9 первая

[Ghost]

Гыхм... Я уже ухожу сегодня, появлюсь теперь не знаю когда. Так что выкладываю свое решение. В процессе решения мне на ум приходили оба предложенных решения (и еще парочка), но первое я сразу отмел из-за наличия перебора, второе - не сумел довести до ума, не хватило терпения (или соображалки).

Может мои рассуждения вам покажутся чересчур сложными, но решал задачу я именно так (на подобные выкладки меня натолкнули воспоминания о прочитанном от корки до корки "Искусстве программирования" Кнута).

Итак. Для начала строим дерево следующего вида: корень (уровень №0) - некий пустой элемент, из него выходят девять ветвей к узлам 1, 2, ..., 8, 9 - уровень №1; из каждого эелемента 1-го уровня также выходят ветви т.о., чтобы путь к ним по узлам (цифрам в узлах) не содержал повторяющихся цифирей, например, из узла (1) 1-го уровня выходят ветви к узлам 0, 2, 3, ..., 8, 9. И т.д. - всего 10 уровней, что очевидно - не может существовать десятичное число с неповторяющимися цифрами длиной более 10. Т.о., при проходе сверху-вниз по этому дереву всегда получается "разноциферное" число.

Само это дерево в программе не потребуется, и строить его не нужно будет. Важны некоторые характеристики уровней. А именно:

1. T - количество ветвей, спускающихся в текущий уровень из любого элемента предыдущего уровня. Т.е., фактически, какое количество цифр можно добавить к уже существующему "разноциферному" числу, не нарушая его. Это число легко определяется следующим образом:
   T[1] = 9;
   T[i] = 11 - i, 1<i<=10.
2. F - общее число узлов в уровне, т.е., в приложении к данной задаче, - количество 1-, 2-, 3-значных "разноциферных" чисел и т.д. Это число тоже легко вычисляется:
   F[1] = T[1];
   F[i] = T[i] x F[i - 1], 1<i<=10.
3. S - общее число узлов в дереве по текущий уровень включительно или, другими словами, количество "разноциферных" чисел длины не более 2, 3, и т.д.:
   S[1] = F[1];
   S[i] = F[i] + S[i - 1], 1<i<=10.

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

Далее, зная N (номер искомого числа), легко вычисляется K - количество разрядов в нем: сперва записываем в K единицу, а потом увеличиваем, пока S[K] < N.

После этого я запоминал номера узлов каждого уровня (начиная с K-го и вверх), через которые нужно пройти, чтобы получить искомое. В результате получил массив A из K элементов.

Теперь, зная номера узлов в каждом уровне, легко определить путь прохода дерева с одновременным формированием числа. Для этого я просматривал массив A в прямом порядке (от 1 до K) и находил номера цифр ((A[i] - 1) mod T[i]) из строки W (в начале, перед первым шагом = '123456789'), добавляя их к результирующей строке Z и удаляя из W.

На первый взгляд все кажется громоздким, но на деле выходит достаточно коротенькая программка:

uses
  crt;

var
  i, k, n:    longint;
  a, t, f, s: array [1..10] of longint;
  w, z:       string;

begin
  clrscr;
  write('n = '); readln(n);
  if (n > 9) then begin
    fillchar(t, sizeof(t), 0); t[1] := 9;
    fillchar(f, sizeof(f), 0); f[1] := t[1];
    fillchar(s, sizeof(s), 0); s[1] := f[1];
    for i := 2 to 10 do begin
      t[i] := 11 - i;
      f[i] := t[i] * f[pred(i)];
      s[i] := f[i] + s[pred(i)];
    end;
    if n > s[10] then z := 'no solutions' else begin
      k := 1;
      while s[k] < n do inc(k);
      fillchar(a, sizeof(a), 0);
      for i := k downto 1 do begin
        if i = k then a[i] := n - s[i - 1]
                 else a[i] := succ(pred(a[i + 1]) div t[i + 1]);
      end;
      w := '123456789';
      z := '';
      for i := 1 to k do begin
        z := z + w[succ(pred(a[i]) mod t[i])];
        delete(w, succ(pred(a[i]) mod t[i]), 1);
        if i = 1 then w := '0' + w;
      end;
    end;
  end else if n > 0 then str(n, z) else z := 'no solutions';
  writeln('r = ', z);
  readkey;
end.

К вопросу о uninheritable class

Я бы лично тоже решил задачку с private конструктором, но как видно это не то что задумывалось. Конечно можно воспользоваться языковыми примочками типа final (PHP), sealed (C#), NonInheritable (VB), но я так думаю что уважаемый Фей-Мод Dimm хочет другое решение. К сожалению решения я ещё не нашел, но пока баловался, пришел к интересной штуке с вложенными классами. Вот пример:

class A1
{
public: 
	A1(){};
private:
	class A2
	{
	public:
		A2(){};
	};
};

От класса А2 не только нельзя унаследовать (что собственно отвечает условиям задачи) но и создать вне класса А1 тоже нельзя. А может это и был ответ? /ooc crosses fingers

[stastan]

Дорогие форумчане, помогите решить такую простую задачу.
А то просто ум за разум заходит , арешения нет ...
Нам дано несколько букв (любое количество , по порядку, и каждая только по одному разу) нужно выдать все возможные варианты перебора по позициям.
Например:
A,B,C.

получаем
A,C,B
C,A,B
C,B,A
B,A,C
B,C,A

и так с любым количеством.

[ЕЖ]

stastan
Это называется перестановками. Смотри алгоритм и пример решения тут
http://opensource.com.ua/contents/978546900444p.html

[Ghost]

stastan

uses
  crt;

var
  s: string;

procedure write_all (s, p: string); far;
var
  i: integer;
begin
  if length (p) = length (s)
    then writeln (p)
    else for i := 1 to length (s) do
      if pos (s[i], p) = 0 then write_all (s, p + s[i]);
end;

begin
  clrscr;
  write ('input string: '); readln (s);
  write_all (s, '');
  write ('press any key to exit...');
  readkey;
end.

З.Ы. ЕЖ - может займемся синхронным плаванием? У нас хорошо получается.

[Crazy_kettle]

to StPatrick
Не знаю, но на моей Visual Studio .NET скомпилировался следующий код:

class A1
{
public: 
A1(){};
private:
       class A2
      {
			public:
			A2(){};
		};

	   class A2_new:public A2{
	   public:
		   A2_new(){}
	   } param;
};

[GOre01]

to Crazy_kettle
Ту нет ничего удивительного. Внутри класса А1, А2 можно использовать как угодно. Попробуй так:

class A1{...};
int main()
{
    A1 *tmpA1 = new A1();
    A2 *tmpA2 = new A2(); // вот так не выйдет !
}

[Crazy_kettle]

GOre01:
Ту нет ничего удивительного. Внутри класса А1, А2 можно использовать как угодно. Попробуй так

А задача, какая была?

P.S. Если я ничего не путаю, то достукиваться до класса A2, нужно через A1::A2.

[GOre01]

Началась регистрация участников конкурса Google Code Jam Europe 2006. Зарегиться можно всем желающим с Monday, May 1 по Tuesday, May 23. Само собой, будут призы. Код можно писать на Java, C++ или C#.
Подробности здесь

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

PPS: Конкурс еще не начался, но различные задачи разного уровня сложности можно решать уже сейчас. Если не ошибаюсь, то за это начисляются балы.

Вообщем, читаем правила, регистрируемся и пробуем выйти в призеры. Всем удачной игры

Совсем вылетело из головы. Участие могут принимать All individuals who are legal residents of Europe, Africa and the Middle East may register and compete in the Google Code Jam Europe 2006 provided they physically reside in an eligible country from May 1 through June 29, 2006. В том числе и жители Росии.