Задача 316 (НСфасулска)

[pimpirlit]

Инспириран от злободневната тематика, реших и аз да се включа в борбЪта с пиратлъка и да помогна с каквото мога. Или по-скоро разчитам на вас да помогнете на органите на държавата в този сюблимен момент. Проблемът е следния:

NSBEAN е надушил супер-хипер-ултра-мега Топ Ъплоудъра на всички времена с прякор Tup_Loader и установил следните особености в неговото криминално поведение:

1. Tup_Loader разполага със 17 конспиративни квартири, от които осъществява противозаконната си дейност. Във всяка от тях той разполага с компютър с различен IP адрес. Тези IP адреси са поредни – напр. xxx.xxx.xxx.1 до xxx.xxx.xxx.17

2. Всеки божи ден той задължително сменя квартирата, респ. IP адреса , от който осъществява пъклените си дела, с цел да не го заловят.

3. По крайно неясни за NSBEAN причини, но абсолютно сигурно, той сменя квартирата с такава, чийто IP адрес на компютъра е съседен на текущия. Без значение дали с едно по-малък или с едно по-голям (напр. 8->9 или 8->7). Ако стигне началото, респ. края на масива адреси трябва да се върне обратно, т.е. не може от 17 да продължи с 1.

От своя страна експертите на NSBEAN разполагат с ресурс да проследяват и проверяват по две квартири на ден. Те нямат никакви ограничения кои две от тях да бъдат проверени. Целта е да го хванат докато е в съответната квартира на компютъра в “работен режим”.

Задачата е да се изготви план за проверка на квартирите, който в най-кратък срок да гарантира 100% залавянето на Tup_Loader. Най-краткия план печели правото да ъплоудне условието на следващата задача без да бъде закачан от NSBEAN!*

Пример: Ако NSBEAN проверява квартирите в реда (1 и 2), (2 и 3), (3 и 4)....(16 и 17), това ще гарантира, че Tup_Loader ще бъде окошарен след не повече от 16 дни. Но NSBEAN трябва да отчете дейност по-рано…

[kamenf]

На първи поглед, ако проверяват (1,17), (2,16), (3,15),... (8,10) със сигурност ще го засекат за 8 дена, като ако на осмият ден не го хванат нито в 8, нито в 10, то със сигурност е в 9.

PS//
На второ четене, един йезуитски вариант. Първият ден никъде да не ходят, ми да вземат да проверят в логовете от къде е осъществявал пъклените си дела, а на другия ден просто да проверят двете съседни квартири - гаранция, че на втория ден го закърфичват...

[MitkoS]

Камене, нещо бъркаш
Tup_Loader е в квартира 2 първия ден , втория ден е в квартира 1 , после пак в 2, после пак в 1 и т.н. ... и твоя алгоритъм не работи.

[Wise]

От своя страна експертите на NSBEAN разполагат с ресурс да проследяват и проверяват по две квартири на ден. Те нямат никакви ограничения кои две от тях да бъдат проверени. Целта е да го хванат докато е в съответната квартира на компютъра в “работен режим”.

Какво значи проследяват и проверяват?? Има ли следа, че е бил там предния ден или нещо подобно?

[kamenf]

Камене, нещо бъркаш
Tup_Loader е в квартира 2 първия ден , втория ден е в квартира 1 , после пак в 2, после пак в 1 и т.н. ... и твоя алгоритъм не работи.

Абе знаех си аз, че първият поглед винаги лъже...
Все пак - независимо какъв е алгоритъма, ми се струва, че трябва да се гони отговор някъде там - около 8.

PS://
Засега виждам работещ вариант за 15 дена:
1 . 3
1 . . 4
. 2 . . 5
. . 3 . . 6
. . . 4 . . 7
. . . . 5 . . 8
. . . . . 6 . . 9

. . . . . . . . . . . . . 13 . . 16
. . . . . . . . . . . . . . 14 . 16

ПП2: Бях объркал една-две цифри

[MitkoS]

На първи поглед, ако проверяват (1,17), (2,16), (3,15),... (8,10) със сигурност ще го засекат за 8 дена, като ако на осмият ден не го хванат нито в 8, нито в 10, то със сигурност е в 9.

Това може да се редактира малко така:
Ако не са го хванали до осмия ден, то това означава едното от двете неща:
1-ви случай - получило се е разминаване
2-ри случай - Tup_Loader е в квартира номер 9
Тогава на деветия пак проверяват (8,10).
Ако имаме 2-рия случай, то сега задължително ще хванат Tup_Loader
Ако е имало разминаване, то тръгват по обратен ред (7, 11), (6, 12), ..., (1,17). Сега вече разминаване не може да се получи, тъй като "четността се е сменила" (сами си го проумейте за какво става въпрос ). За съжаление, тоя алгоритъм гарантира хващане на 17-тия ден (8 + 1 + 8)

[MitkoS]

Абе знаех си аз, че първият поглед винаги лъже...
Все пак - независимо какъв е алгоритъма, ми се струва, че трябва да се гони отговор някъде там - около 8.

PS://
Засега виждам работещ вариант за 15 дена:
1 . 3
1 . . 4
. 2 . . 5
. . 3 . . 6
. . . 4 . . 7
. . . . 5 . . 7
. . . . . 6 . . 8

. . . . . . . . . . . . . 13 . . 16
. . . . . . . . . . . . . . 14 . 16

Пак буриш (лъжеш), при тоя вариант дните са шестнадесет
1 . 3 t .
1 . t 4
. 2 . t 5
. . 3 . t 6
. . . 4 . t 7
. . .
Обаче при тоя вариант
.23....
.2.4...
.2..5...
..3..6...
...4..7...
.......
...............12..15..
................13..16.
................14.16.
Дните вече са петнадесет - даже четиринадесет

[kamenf]

Не ми се спори, ама брой пак.

[MitkoS]

Сега виждам, че и аз малко послъгвам. Ама съвсеем малко* . Освен това твоя метод наистина е петнадесет

Окончателно
.2.4...
.2..5...
..3..6...
...4..7...
.......
...............12..15..
................13..16.
................14.16.
Дните вече са четиринадесет

[kamenf]

Изпревари ме - тамън и аз комбинирах твоят и моят метод

[Edin_Lud]

За 15 дни варианти много...

. 2 . 4 .
. 2 . . 5
. . 3 . 5

в първите 3 дни ни гарантира със сигурност, че на 3тия ден не е в нито една от квартирите от 1 до 5. Сега с (5,6) (6,7) и т.н. за 15 дни го хващаме (както и при още 2-3 различни продължения)...

Ако продължим с
(5,7) (5,8) (6,9) (7,10) ... до (13,16) са още 10 дни кто на този 13ти ден Tup_loader е в 15 или 17 => на 14тия ден (14,16) и капанът щраква

Засега толкова...

//Докато го напиша и двама сте ме изпреварили

[pimpirlit]

Какво значи проследяват и проверяват??* Има ли следа, че е бил там предния ден или нещо подобно?

Не, няма следа. В условието няма уловки - просто съм се отнесъл малко в "по-литературна" посока при формулирането.

14 дни не е лош резултат, но почти сигурно гарантира уволнението на шефа на NSBEAN...
А 8 ми се струва малко амбициозно - ще ми бъде много любопитно ако някой може да постигне такъв резултат. Макар, че не е далече от това, което мисля, че е най-доброто.

BTW, задачката има много елегантно и красиво решение. Затова реших да я споделя с вас.

[Yasen6275]

PS//
На второ четене, един йезуитски вариант. Първият ден никъде да не ходят, ми да вземат да проверят в логовете от къде е осъществявал пъклените си дела, а на другия ден просто да проверят двете съседни квартири - гаранция, че на втория ден го закърфичват...

Какво му е лошото на този вариант?

[pimpirlit]

Какво му е лошото на този вариант?

От urina.gb не оказват подобаващо съдействие - или не дават логовете, или ги дават, но със закъснение, или с непълно и/или невярно съдържание... Момъците от NSBEAN изобщо не могат да разчитат на подобна "специална" техника за залавянето на ИнТерориста - само на логиката и сивото си вещество*. И понеже имат лек дефицит на тези артикули, разчитат изцяло на вас!

*Не става дума за цимент или бетон...

[kamenf]

. x . . . . . . . . . . . . . . .
. x . x . . . . . . . . . . . . .
. x . x . x . . . . . . . . . . .
. . . x . x . x . . . . . . . . .
. . . . . x . x . x . . . . . . .
. . . . . . . x . x . x . . . . .
. . . . . . . . . x . x . x . . .
. . . . . . . . . . . x . x . x .
. . . . . . . . . . . . . x . x .
. . . . . . . . . . . . . . . x .

При тази решетчица няма да му се размине за 10 дена.

ПП: Глупости говоря.....