2. Обмануть обманщика icon

2. Обмануть обманщика




Скачати 193.62 Kb.
Назва2. Обмануть обманщика
Дата конвертації29.11.2012
Розмір193.62 Kb.
ТипДокументи
1. /Семинар_16_11_2010/Винница2009/Solution_1.docx
2. /Семинар_16_11_2010/Сайты подготовки.docx
3. /Семинар_16_11_2010/Ярославль2009/Теоретическая часть.doc
4. /Семинар_16_11_2010/Ярославль2009/Условие.doc
Задания и решения1-го тура Netoi-2009
Олимпиады по программированию, г. Москва Олимпиады в области точных наук, г. Санкт-Петербург Олимпиады по информатике, г. Санкт-Петербург
2. Обмануть обманщика
2009 г. Теоретическая часть

1. Алгоритм

Алгоритм ДУМА возвращает в переменную n квадрат числа k, так как на каждом шаге цикла переменная n увеличивается на (2*i+1).

(2*i+1) – это разница между квадратом i и i+1.


2. Обмануть обманщика

2.1. a=1, b=30 (a,b – целочисленные переменные), где a – это начало интервала возможных вариантов, b – конец этого интервала.

2.2. Если a=b то переходим к пункту 2.5., в противном случае спрашиваем 2 раза содержится ли данное число в интервале от a до ((a+b) div 2).

2.3. Если оба ответа одинаковы, то Коля не солгал,

при положительном ответе b=((a+b) div 2);

при отрицательном ответе a=(((a+b) div 2)+1);

и возвращаемся к пункту 2.2.

В противном случае, значит Коля солгал, еще раз задаем тот же вопрос: содержится ли данное число в интервале от a до ((a+b) div 2).

при положительном ответе b=((a+b) div 2);

при отрицательном ответе a=(((a+b) div 2)+1);

2.4. Если a=b переходим к пункту 2.5.

В противном случае задаем вопрос один раз: содержится ли данное число в интервале от a до ((a+b) div 2).

при положительном ответе b=((a+b) div 2);

при отрицательном ответе a=(((a+b) div 2)+1);

Выполняем пункт 2.4 ещё раз.

2.5. Искомое число равно a.

Дублировать вопрсы необходимо, так мы узнаем правду ли сказал Коля.

На пункт 2.4 алгоритм переходит в случае, если Коля солгал. И повторяется только этот пункт, пока не будет найден ответ. Больше нет необходимости в дублировании вопросов, так как солгать Коля может только раз или ни одного раза.

Минимальное количество вопросов 7 если Коля солжет на первой паре вопросов;

Максимальное количество вопросов 11, если Коля солжет на последней паре вопросов (Петя гарантиравано назовет число загаданное Колей за 11 вопросов).


3. Зазеркалье

Все точки множества находятся в двумерном массиве А;

3.1.Проходом по массиву А находим 2 точки:

  • с минимальной координатой по оси абцисс (если таких несколько,то выбираем с минимальной по координате ординат)

  • с максимальной координатой по оси абцисс (если таких несколько,то выбираем с максимальной по координате ординат).

((X1;Y1) - min и (X2;Y2) - max)

3.2.Находим центр отрезка с концами в найденных точках.

Xц=(X1+ X2)/2;

Yц=(Y1+ Y2)/2;

(Xц;Yц) – это координаты цента симметрии.

Удаляем точки (X1;Y1) и (X2;Y2) из массива A.

3.3.Проходом по массиву A все точки у которых Xi>Xц (если Xi=Xц, то Yi> Yц) записываем в массив B и удаляем из массива A.

Если точка (Xi, Yi) совпадает с центром симметрии (Xц;Yц), то удаляем ее из массива А, так как она сама себе центрально-симметрична.

3.4.Для каждой точки массива A находим координаты ее симметричной точки относительно центра (Xц, Yц):

X0=(2*Xц-Xi);

Y0=(2*Yц-Yi);

и ищем точку (X0;Y0) в массиве B.

3.5.Если для каждой точки массива А в массиве B есть точка центральносимметричная, то множество центральносимметрично, в противном случае множество не центральносимметрично.

Листинг программы, написанной на языке Паскаль:

Var a,b:array[1..20,1..2] of real;

i,n,j,min,max,bcol,akol:integer;

xc,yc,x0,y0:real;

exit:boolean;


procedure deletea(i:integer); {циклическим сдвигом удаляем i-ый элемент из массива А}

var j:integer;

begin

for j:=i to akol do

begin

a[j,1]:=a[j+1,1];

a[j,2]:=a[j+1,2];

end;

akol:=akol-1;

end;


begin

min:=1; max:=1;

Writeln('Введите количество точек ');

Readln(n);

akol:=n;

for i:=1 to n do {Вводим в строку последовательно координаты всех точек}

Read(a[i,1],a[i,2]);

for i:=1 to n do {Определяем min, max}

begin

if (a[i,1]
min:=i;

if (a[i,1]>a[max,1]) or ((a[i,1]=a[max,1]) and (a[i,2]>a[max,2])) Then

max:=i;

end;

xc:=((a[min,1]+a[max,1])/2); {Находим центр симметрии}

yc:=((a[min,2]+a[max,2])/2);

if min>max Then {Удаляются точки min и max из массива А}

begin

deletea(min);

deletea(max);

end

else

if min<>max Then

begin

deletea(max);

deletea(min);

end;

i:=1;

while i<=akol do {Формирование массива В и корректировка массива А}

begin

if ((a[i,1]>xc) or ((a[i,1]=xc) and (a[i,2]>yc))) Then

begin

inc(bcol);

b[bcol,1]:=a[i,1];

b[bcol,2]:=a[i,2];

deletea(i);

i:=i-1;

end;

i:=i+1;

end;

i:=0;

while not exit and (i
begin

inc(i);

x0:=2*xc-a[i,1];

y0:=2*yc-a[i,2];

exit:=True;

for j:=1 to bcol do

if (b[j,1]=x0) and (b[j,2]=y0) Then

exit:=False;

end;

if exit Then

Writeln('Нет')

else

Writeln('Да');

end.


4. Коллективный разум.

Всего 8 дней.


1

2

3

4




1

1,2

3,4

4

5

6

7

8




5

5,6

7,8

8

9

10

11

12




9

9,10

11,12

12

13

14

15

16




13

13,14

15,16

16




























1

1,2

1-4

4




1

1,2

1-4

4

5

5,6

5-8

8




5

5,6

1-8

8

9

9,10

9-12

12




9

9,10

9-16

12

13

13,14

13-16

16




13

13,14

13-16

16




























1

1,2

1-4

4




1

1,2

1-4

4

5

5,6

1-16

8




5

5,6

1-16

8

9

9,10

9-16

12




9

9,10

1-16

12

13

13,14

13-16

16




13

13,14

13-16

16




























1

1,2

1-16

4




1

1-16

1-16

4

5

5,6

1-16

8




5

1-16

1-16

8

9

9,10

1-16

12




9

1-16

1-16

12

13

13,14

1-16

16




13

1-16

1-16

16




























1-16

1-16

1-16

1-16
















1-16

1-16

1-16

1-16
















1-16

1-16

1-16

1-16
















1-16

1-16

1-16

1-16


















5. Шестеренки

В данной задаче мы будем считать, что все шестеренки объединены в один механизм. Шестеренки могут двигаться в двух направлениях: по часовой и против часовой стрелки. Две связанные шестеренки должны вращаться в разных направлениях (рисунок 1).




Рис.1

Например: в первых двух механизмах (рисунок 2, 3)шестеренки будут вращаться свободно. А в третьем механизме (рисунок 4) есть две связанные шестеренки, которые должны вращаться в одинаковом направлении, поэтому на рисунке 4 механизм не будет двигаться.


Рис. 2 Рис. 3 Рис. 4

Данный механизм можно представить в виде графа. Для этого нужно построить матрицу смежности. Построим матрицу смежности для примера на рисунке 3.

В матрице отмечаем в строке с номером текущей шестеренки все ее связи с другими шестеренками. Например, если шестеренка 4 соединена с шестеренками 3 и 2, то мы в поля m[4,3] и m[3,4] и m[4,2] и m[2,4] ставим единицы. И так для каждой шестеренки.




1

2

3

4

1

0

1

1

0

2

1

0

0

1

3

1

0

0

1

4

0

1

1

0


Матрица смежности для примера с рисунка №3

По матрице смежности формируем одномерный массив, хранящий раскраску исходного графа в два цвета (1 – движение по часовой стрелке,2 – движение против часовой стрелки).


  1. 1

2

3

4

  1. 1









Покажем пошаговую раскраску:

1 шаг. Для первой шестеренки ставим направление 1.



    1. 1

    2

    3

    4

    1. 1

    2

    2



    шаг. Выбираем последовательно все шестеренки и пытаемся раскрасить шестеренки, связанные сними
    Если выбраны не все шестеренки, то выбираем текущую. Раскрашиваем шестеренки, связанные с текущей.

Иначе переходим к пункту 5 с ответом “Да”.

3 шаг. Если в массиве связанная шестеренка уже раскрашена, то надо проверить ее правильность раскраски в соответствии с текущей шестеренкой.

  1. шаг. Если ранее установленный цвет шестеренки совпал с цветом, который мы хотим поставить на новом шаге, то вершина раскрашена правильно. Выбираем следующую текущую шестеренку и переходим к шагу 2.

Иначе (если цвета оказываются разные) заканчиваем работу программы: переходим к пункту 5 с ответом “Нет”.


    1. 1

    2

    3

    4

    1. 1

    2

    2

    1
    шаг. Вывод полученного ответа.


Мы получили ответ. Пример №3: “Да”.


  1. 1

2

3

4

5

1

2

2

1

1
А вот раскраска для примера с рисунка №4. Попытка раскрасить шестеренку 5, связанную с шестеренкой 4 приведет к конфликту цветов и передаст на конец программы ответ “Нет”.

Алгоритм Раскраска (целое n)

Начало алгоритма

i, j - целочисленные

i:=1

j:=1

Flag:=False {все раскрашены правильно}

Цикл: пока i
Цикл: пока j
Если m[i,j]=1 тогда

Если kras[j]<>0 и kras[i]=kras[j] тогда

Flag:=True {раскрашены не правильно}

Иначе kras[j]:=3-kras[i]

Если flag=true то вывод(“Нет”)

Иначе вывод(“Да”)

Конец алгоритма


6. Нить Ариадны

Входные данные: строка символов из набора (С, В, Ю, З), хранящая путь от входа до клада.

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

Движение по лабиринту похоже на граф, в котором комнаты – вершины, переход из комнаты в комнату – ребро.

1 шаг. Сперва формируем двухмерную матрицу А, состоящую из двух столбцов и строк, равным по количеству посещенным комнатам. Первый столбец матрицы отвечает за движение на запад или восток (добавляется -1, т.е. движение на запад, добавляется +1, т.е. движение на восток). Второй столбец отвечает за движение на север (+1) или на юг
(-1). Каждая строчка – новая комната, не проверяя повторения.

Рассмотрим пример движения по лабиринту. Входная строка: СССЗЮЮВССЗЮЗ.

Матрица А будет выглядеть так: 0, 0 1 Вход

0, 1 2 комната

0, 2 3 комната

0, 3 4 комната

-1, 3 5 комната

-1, 2 6 комната

-1, 1 7 комната

0, 1 8 комната

0, 2 9 комната

0, 3 10 комната

-1, 3 11 комната

-1, 2 12 комната

-2, 2 Клад

2 шаг. Имея матрицу А, сформируем матрицу М, являющейся матрицей смежности для данного пути. При этом, в случае повторного прохода комнат новые вершины графа не создаются.

Первая строка матрицы А содержит 0, 0. Начиная со второй строки, т.е комнаты № 2, для данных проверяются все переходы в предыдущие комнаты (проверяются все предыдущие строки матрицы А на совпадение с текущей строкой).

Если такого сочетания нет, то создаем новую вершину у графа и записываем путь ( в матрицу М с индексами: Номер предыдущей вершины и Номер новой вершины, ставим 1, а также в ячейку матрицы с противоположными индексами: Номер новой вершины и Номер предыдущей вершины, ставим 1, определяя обратный путь.

Если сочетание уже есть (8 комната – 0, 1; 2 комната – 0, 1), то формируется путь из предыдущей вершины (для 8 – 7) в ту, которая имеет такой же путь (7 комната связывается со 2). При этом новая вершина графа не создается, а соответствующая строка из матрицы А удаляется (строка для 8 комнаты удаляется)

В матрицу М ставятся единицы не только в порядке движения кладоискателя, но и обратно (7 – 2, 2 – 7, 1 – 2, 2 – 1, и т.д.).

После просмотра всей матрицы А, она будет иметь вид:


0

0

0

1

0

2

0

3

-1

3

-1

2

-1

1

-2

2



И матрица М будет иметь вид:




1

2

3

4

5

6

7

8

1

0

1

0

0

0

0

0

0

2

1

0

1

0

0

0

1

0

3

0

1

0

1

0

0

0

0

4

0

0

1

0

1

0

0

0

5

0

0

0

1

0

1

0

0

6

0

0

0

0

1

0

1

1

7

0

1

0

0

0

1

0

0

8

0

0

0

0

0

1

0

0

3 шаг. Используя алгоритм Дейкстры, по матрице М находим кратчайший путь из первой вершины в последнюю. При этом используется вспомогательная матрица Ром логического типа для пометки вершин, из которых ищется текущий кратчайший путь.

После выполнения алгоритма Дейкстры получим одномерную матрицу Mar, хранящую для каждой вершины ее предыдущую вершину в кратчайшем пути.

Для данного примера матрица Mar будет иметь вид:

1

2

3

4

5

6

7

8

индексы

0

1

2

3

4

7

2

6

значения матрицы


4 шаг. Просматривая последний массив Mar от конца к началу строим кратчайший путь выхода из лабиринта. При этом направление движения при переходе из комнаты в комнату формируется по матрице А.

Из 8 вершины переходим в шестую, при этом (-2, 2) преобразовывается в (-1, 2). Значит необходимо движение на восток. Далее из 6 вершины переходим в 7, (-1, 2) преобразовано в (-1, 1). Значит движение на юг. Далее из 7 вершины движемся во 2, (-1, 1) переходит в (0, 1). Значит движемся опять на восток. И, из 2 вершины переходим в 1, (0, 1) изменяется на (0, 0), а, значит, опять движение на юг.

Соответствующие направления формируются из списка (С, В, Ю, З) в виде выходной строки, которая и выводится на экран.

Для данного примера выходная строка будет иметь вид: СЗСЗ.

Алгоритм выполняется даже тогда, когда кладоискатель, возможно из-за рассеянности, проходит через комнату с кладом и потом опять к нему возвращается.

Листинг программы на языке Паскаль:

var s:string;

i,j,k,l,p:integer;

x,y,n:integer;

A:array[1..252,1..2] of integer;

M:array[1..250,1..250] of byte;

Pom:array[1..50] of boolean;

Mar:array[1..50] of integer;

f:text;

b,b1,b2:boolean;

begin

assign(f,'input.txt');

reset(f);

readln(f,s);

x:=0; y:=0;

for i:=1 to length(s) do {Формирование матрицы А}

begin

case s[i] of

'С':begin

y:=y+1;

a[i+1,1]:=x;

a[i+1,2]:=y;

end;

'Ю':begin

y:=y-1;

a[i+1,1]:=x;

a[i+1,2]:=y;

end;

'З':begin

x:=x-1;

a[i+1,1]:=x;

a[i+1,2]:=y;

end;

'В':begin

x:=x+1;

a[i+1,1]:=x;

a[i+1,2]:=y;

end;

end;

end;

{Формирование матрицы М}

i:=2;

j:=1;

n:=length(s)+1;

for l:=2 to n+1 do

begin

k:=1;

while (k<=i-1) and ((a[k,1]<>a[i,1]) or (a[k,2]<>a[i,2])) do

k:=k+1;

if k<=i-1 then

begin

{Циклический сдвиг}

for p:=i to n-1 do

begin

a[p,1]:=a[p+1,1];

a[p,2]:=a[p+1,2];

end;

n:=n-1;

{}

m[k,j]:=1;

m[j,k]:=1;

i:=i-1;

j:=k;

end

else

begin

m[i,j]:=1;

m[j,i]:=1;

j:=i;

end;

i:=i+1;

end;

n:=j;

{Deykstra 1 -- n}


if a[1,n]=1 then

begin

mar[1]:=1;

mar[2]:=n;

end

else

begin

b:=true;

pom[1]:=true;

i:=1;

while b and (i<=n) do

begin

b1:=false;

while (i<=n) and ((pom[i]=true) or (m[1,i]=0)) do

i:=i+1;

if i=n+1 then

b:=false

else

begin

if (m[1,i]<>0) and b then

begin

if (mar[i]=0) then

mar[i]:=1;

pom[i]:=true;

for j:=1 to n do

if (m[i,j]<>0) and ((m[1,i]+11))) then

begin

m[1,j]:=m[1,i]+1;

mar[j]:=i;

b1:=true;

end;

if mar[n]<>0 then

begin

b2:=true;

for i:=1 to n do

if (pom[i]=false) and (i<>n) then

b2:=false;

if b2 then

b:=false;

i:=1;

end

else

begin

if b1 then

i:=1

else

i:=i+1;

end;

end;

end;

end;

if (mar[n]<>0) then {Формирование выходной строки}

begin

i:=n;

s:='';

x:=a[n,1];

y:=a[n,2];

while i<>1 do

begin

i:=mar[i];

if x<>a[i,1] then

begin

if x
s:=s+'В'

else

s:=s+'З';

x:=a[i,1];

end

else

begin

if y
s:=s+'С'

else

s:=s+'Ю';

y:=a[i,2];

end;

end;

end;

end;

writeln(s); {Вывод кратчайшего пути из лабиринта}

end.



Схожі:

2. Обмануть обманщика iconНовелла Проспера Мериме «Таманго» это рассказ
Даже когда продажа людей была запрещена властями, многие судовладельцы не пожелали отказаться от столь доходной статьи своего бизнеса....
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи