Задачка-закачка

[LiFo]

Мисля, че ще е добра идея, ако чат-пат си пускаме по някоя задачка-закачка.Който пръв даде правилен отговор на задачата, ще получи усмивка по телефона и потупване по рамото Ето я задачката:

Вървели си четирима приятели и стигнали до една пещера.Те били много любопитни и искали да влезнат и да разгледат пещерата.Така и направили...Влезнали и вървяли дълго време.Ставало все по-тъмно.След известно време те стигнали до един въжен мост, който висял над една много дълбока пропаст.Понеже мостът бил стар, четиримата приятели решили да минават НАЙ-МНОГО ПО ДВАМА на един път.Първият можел да премине по моста (в едната посока) за 1 минута, вторият - за 2 минути, третият - за 5 минути и четвъртият - за 10 минути.За да преминат успешно по моста, приятелите трябвало да използват единственото фенерче, което носели и което имало батерии само за 17 минути.По какъв начин четиримата приятели ще преминат успешно по моста?

(Задачата ИМА реално решение, а НЕ някакъв отговор от сорта на: "Еми като преминат първите двама ще хвърлят фенерчето обратно на другите двама и ще преминат и те!")
БТВ задачата мисля, че е от 4. клас...

[did]

Задачата (като и повечето подобни, мислени от "специалисти" НУП и ПУП) е некоректно поставена. Не е уточнено:
1. Трябва ли да се движат двойките приятели винаги ЗАЕДНО, за да се вижда къде светят;
2. Колко далеч (като относителна част от моста) може да свети фенерчето;
3. Като ти светят срещу теб в краката това за заслепяване ли се брои или за осветяване.

Ако приемем, че трябва ВИНАГИ да вървят по двойки с темпото на по-бавния (практическа логика), най-доброто решение изисква 19 минути, т.е. не става, освен ако някой не прави така .

Ясно е, че се налага разкъсване на двойките, което праща практическата логика по дяволите и остава абстрактния математически модел. В него решение може да се получи даже за 12мин., т.е. остават 5 мин батерии за следващия мост. Това, обаче при условие, че фенерчето е достатъчно силно да освети половината мост (здрав челник;) и е позволено да ти светят срещу очите, т.е. срещу теб, в краката ти). Едно от няколкото възможни решения е примерно това:

Да ги кръстим приятелите A, B, C и D, като съответно времената, с които минават по моста са A-1min, B-2min, C-5min, D-10min

1. Тръгват C и D, като всеки си върви с неговото темпо и задния (D) носи фенерчето и свети напред. След 5 мин D се намира по средата на моста, a C вече е преминал.
2. D си стои по средата и свети на A да премине за 1 минута. После свети на B да дойде за 1 мин. при него. До тук 7 мин.
3. Накрая, двамата B и D за 5 мин преминават, като пак D носи фенера и свети отзад.

Сигурно ако се приеме още по-силно фенерче и се оптимизира мястото на изчакване на D на моста ще се получат и по-кратки времена. Това обаче са математически глупости. Практическата логика изисква 19мин - последователно преминаване на B, C и D, придружавани от най-бързия - A и двете връщания на A да прибере следващия си приятел.

Това със 17-те минути си го е изсмукал някой от пръстите със самочувствието, че е успял да раздели на две магарета сено успешно, ама не си е направил труда да даде коректно условие на задачата.

EDIT:
Например, ако фенерчето може да освети 60% от моста, има и решение за 11.6min (LiFo, ще го откриеш ли?). Ако пък не е позволено да се свети срещу приятел, нещата стават съвсем различни... Абе затова отрано децата намразват математиката!!! Аз съм 99% сигурен, че тия 17 мин. идиота-съставител ги е получил, като е приел, че докато А се връща да вземе приятеля си, оня върви срещу него, възползвайки се от светлината на насрещно идващия приятел. Ама това изисква 100% покритие на моста от фенерчето, което пък веднага позволява далеч по-оптимално решение.

След всички тези забележки, обаче, остава открит въпроса колко е минималното време при 100% покритие на моста? LiFo, какво ще кажеш?

Edit на Edit-а:
Ако някой даде такава задача за домашно на дъщеря ми, когато тя е в четвърти клас, ще му:
1.
2.
3.
4.
5. :dgrin::dgrin:
и накрая

[Harka]

[quote="did"]

Задачата (като и повечето подобни, мислени от "специалисти" НУП и ПУП) е некоректно поставена. Не е уточнено:
1. Трябва ли да се движат двойките приятели винаги ЗАЕДНО, за да се вижда къде светят;
2. Колко далеч (като относителна част от моста) може да свети фенерчето;
3. Като ти светят срещу теб в краката това за заслепяване ли се брои или за осветяване.

Ако приемем, че трябва ВИНАГИ да вървят по двойки с темпото на по-бавния (практическа логика), най-доброто решение изисква 19 минути, т.е. не става.

Ясно е, че се налага разкъсване на двойките, което праща практическата логика по дяволите и остава абстрактния математически модел. В него решение може да се получи даже за 12мин., т.е. остават 5 мин батерии за следващия мост. Това, обаче при условие, че фенерчето е достатъчно силно да освети половината мост (здрав челник;) и е позволено да ти светят срещу очите, т.е. срещу теб, в краката ти). Едно от няколкото възможни решения е примерно това:

Да ги кръстим приятелите A, B, C и D, като съответно времената, с които минават по моста са A-1min, B-2min, C-5min, D-10min

1. Тръгват C и D, като всеки си върви с неговото темпо и задния (D) носи фенерчето и свети напред. След 5 мин D се намира по средата на моста, a C вече е преминал.
2. D си стои по средата и свети на A да премине за 1 минута. После свети на B да дойде за 1 мин. при него. До тук 7 мин.
3. Накрая, двамата B и D за 5 мин преминават, като пак D носи фенера и свети отзад.

Сигурно ако се приеме още по-силно фенерче и се оптимизира мястото на изчакване на D на моста ще се получат и по-кратки времена. Това обаче са математически глупости. Практическата логика изисква 19мин - последователно преминаване на B, C и D, придружавани от най-бързия - A и двете връщания на A да прибере следващия си приятел.

Това със 17-те минути си го е изсмукал някой от пръстите със самочувствието, че е успял да раздели на две магарета сено успешно, ама не си е направил труда да даде коректно условие на задачата.
[/quote]

Абсолютно си прав. Логически приятелите не могат да преминат за по-малко от 19 мин., а иначе теоритично всичко зависи от мощността на челника.

[Harka]

[quote="did"]
EDIT:
Абе затова отрано децата намразват математиката!!!
[/quote]

Така е, като се сетя в четвърти клас каква мъка ми бяха ребусите, от които почти нищо не рзбирах. Като че ли тогава само от кръговете на Ойлер имах някаква представа и чатках нещо.

[did]

А ето и една [b][color=red]коректно [/color][/b]поставена задача от същия вид:

Трима велосипедисти от София решават да ми дойдат на гости в Пловдив да покараме. Тримата имат колела, с които се движат по пътя София-Пловдив с 30км/ч. Групата разполага и с една двуместна кола-кабрио, отзад с багажник за два велосипеда, която се движи с позволената по магистралата скорост от 120км/ч. Разстоянието е 150км. За колко време [b][color=red]най-малко[/color][/b] може цялата група да се придвижи до Пловдив? А?

EDIT:
И колко ще им струва транспорта, ако колата гори 7.5 на сто бензин А95 на цена 1.52лв, а всеки от велосипедистите пие по една бутилка минерална вода от половин литър на всеки започнати 10км, като цената на водата е 0.40лв???

Тази задача наистина е за 4-5 клас, само че подобна си спомням бяха дали на трети кръг на математичаска олимпиада преди доста време и участниците много се озориха. Току що го сметнах набързо и отговорът е 2 часа 19 мин и 17 секунди. Как ще стане, обаче, тая работа - не казвам! За цената - също!

[Deimos]

Ми, трябва да е нещо такова: двама от колоездачите потеглят от София с кабриото, третия върти.
Когато двамата с кабриото минат 107 километра, 142 метра и 85 сантиметра, единия слиза и почва да върти към Пловдив. А другия тръгва обратно към София (с кабриото). Този с колата и колоездача дето тръгва от София на собствен ход ще се засекат на 42 километра, 857 метра и 14 сантиметра от София. След което и двамата настанени в кабриото потеглят отново към Пловдив.
И тримата колоездачи ще пристигнат едновременно в Пловдив (кой с кола, кой с колело) и това ще стане след 2 часа, 19 минути, 17 секунди и 142 хилядни , откакто всички едновременно са тръгнали от София.

Разходите са съответно:
колата е минала общо 278 километра, 571 метра и 42 сантиметра, което при дадения разход и цена на бензина прави 31 лева и 75 стотинки.
Тези дето са въртяли ще са изпили 10 бутилки минерална вода, което прави 4 лв.

Или общо - 35 лева и 75 стотинки.

Айде сега за награда искам да ме върнете отново в 4-5 клас , че онова време ми липсва .

[LiFo]

В задачата за четиримата приятели няма такива неща като разстоянието, на което свети фенерчето и заслепяването.Винаги се движат по двама с едно фенерче (едновременно, примерно един до друг - тръгват заедно и стигат заедно).Но остава следното условие:
Тръгват А (за 1 мин.) и Д (за 10 мин.) с единственото фенерче и те ще стигнат до другия край за 10 мин., защото бавният ще забави бързия, а те винаги трябва да са заедно.
Тук въпросът е кои двама ще тръгнат най-напред и кой ще се върне с фенерчето за да го даде на другите, които все още не са преминали по моста.

@Harka
Жокер: Четиримата преминават за ТОЧНО 17 минути!

[PtD]

Това е една стаааааара задачка , която изисква съвсем малко отклонение от пряката мисъл did не е прав, че минималното време е 19 мин, точно 17 си е. Hint: Създайте си запас от бързоходци на далечната страна :P

[Harka]

Ауу, може ли да съм толкова тера тъп? Решението наистина е ЕЛЕМЕНТАРНО, а именно:
Първо тръгват приятели А и B (съответно 1 и 2 мин.) и стигат за две минути. След това се връща А за още една минута и общото време до тук става 3 мин. След това тръгват С и D (съответно 5 и 10 мин.) и стигат за 10 мин. (общото време става 13 мин.). После от отсрещната страна тръгва B, който стига при А за две минути (времето става 15 мин.), след което A и B заедно преминават моста за 2 мин. и общото време става точно 17 мин.

did, ти си виновен, че ме подлъга :P.

[PtD]

[quote="Harka"]

Ауу, може ли да съм толкова тера тъп? Решението наистина е ЕЛЕМЕНТАРНО, а именно:
Първо тръгват приятели А и B (съответно 1 и 2 мин.) и стигат за две минути. След това се връща А за още една минута и общото време до тук става 3 мин. След това тръгват С и D (съответно 5 и 10 мин.) и стигат за 10 мин. (общото време става 13 мин.). После от отсрещната страна тръгва B, който стига при А за две минути (времето става 15 мин.), след което A и B заедно преминават моста за 2 мин. и общото време става точно 17 мин.

did, ти си виновен, че ме подлъга :P.
[/quote]


Ама и фенерчето как знае колко минути да свети, а? :P:P:D:D:D

[did]

Чукам си главата в стената:smash:!!!

[LiFo]

Бравоооо, хаиде сега някой друг да даде задачка...

[Alien]

There are 5 houses in five different colors. In each house lives a person with a different nationality. These five owners drink a certain drink, smoke a certain brand of cigar, and keep a certain pet no owners have the same pet, smoke the same brand of cigar or drink the same drink. The question is --- who owns the fish?

Hints:

- the Brit lives in the red house
- the Swede keeps dogs as pets
- the Dane drinks tea
- the green house is on the left of the white house
- the green house owner drinks coffee
- the person who smokes Pall Mal rears birds
- the owner of the yellow house smokes Dunhill
- the man living in the house right in the center drinks milk
- the Norwegian lives in the first house
- the man who smokes Blends lives next to the one who keeps cats
- the man who keeps horses lives next to the one who smokes Dunhill
- the owner who smokes Blue Master drinks beer
- the German smokes Prince
- the Norwegian lives next to the blue house
- the man who smokes Blend has a neighbor who drinks water

[kagami]

Няма да казвам отговора, защото не го измислих сама. Но все пак ще дам линк за тези, които като мен нямат търпение

[url=http://www.allaboutsymbian.com/forum/newreply.php?do=newreply&p=126161]ей го на[/url]

[velco]

Мд-а-а-а, в интерес на истината, отговора и аз не го измислих сам ...

... ами по стар навик си написах програма . И моля, без заяждания какво можело да се направи по-добре .

[code]
#include <stdio.h>

enum nat { Brit = 1, Swede, Dane, Norw, German };
static const char *nat[] = { 0, "Brit", "Swede", "Dane", "Norw", "German" };
static unsigned int nat_set;

enum color { red = 1, green, yellow, white, blue };
static const char *color[] = { 0, "red", "green", "yellow", "white", "blue" };
static unsigned int color_set;

enum pet { dogs = 1, birds, cats, horses, fish };
static const char *pet[] = { 0, "dogs", "birds", "cats", "horses", "fish" };
static unsigned int pet_set;

enum drink { tea = 1, coffee, milk, beer, water };
static const char *drink[] = { 0, "tea", "coffee", "milk", "beer", "water" };
static unsigned int drink_set;

enum smoke { PallMal = 1, Dunhill, Blends, BlueMaster, Prince };
static const char *smoke[] = { 0, "PallMal", "Dunhill", "Blends", "BlueMaster", "Prince" };
static unsigned int smoke_set;

struct house
{
enum nat nat;
enum color color;
enum pet pet;
enum drink drink;
enum smoke smoke;
};

#define N 5

static struct house house [N];

#define CHECK(a,b) ((a) && !(b) || !(a) && (b))

static int
feasibility_check ()
{
unsigned int i;

/* the Norwegian lives in the first house */
if (house [0].nat && house [0].nat != Norw)
return -1;

/* the man living in the house right in the center drinks milk */
if (house [N / 2].drink && house [N / 2].drink != milk)
return -1;

/* the Norwegian lives next to the blue house */
if (house [1].color && house [1].color != blue)
return -1;

for (i = 0; i < N; ++i)
{
/* the Brit lives in the red house */
if (house [i].nat && house [i].color
&& CHECK (house [i].nat == Brit, house [i].color == red))
return -1;

/* the Swede keeps dogs as pets */
if (house [i].nat && house [i].pet
&& CHECK (house [i].nat == Swede, house [i].pet == dogs))
return -1;

/* the Dane drinks tea */
if (house [i].nat && house [i].drink
&& CHECK (house [i].nat == Dane, house [i].drink == tea))
return -1;

/* the green house is on the left of the white house */
if (i < N - 1 && house [i].color && house [i + 1].color
&& CHECK (house [i].color == green, house [i + 1].color == white))
return -1;

/* the green house owner drinks coffee */
if (house [i].color && house [i].drink
&& CHECK (house [i].color == green, house [i].drink == coffee))
return -1;

/* the person who smokes Pall Mal rears birds */
if (house [i].smoke && house [i].pet
&& CHECK (house [i].smoke == PallMal, house [i].pet == birds))
return -1;

/* the owner of the yellow house smokes Dunhill */
if (house [i].color && house [i].smoke
&& CHECK (house [i].color == yellow, house [i].smoke == Dunhill))
return -1;

/* the man who smokes Blends lives next to the one who keeps cats */
if (house [i].smoke == Blends
&& (i == 0 && house [1].pet && house [1].pet != cats
|| i == N - 1 && house [N - 2].pet && house [N - 2].pet != cats
|| (house [i - 1].pet && house [i + 1].pet
&& house [i - 1].pet != cats && house [i + 1].pet != cats)))
return -1;

/* the man who keeps horses lives next to the one who smokes Dunhill */
if (house [i].pet == horses
&& (i == 0 && house [1].smoke && house [1].smoke != Dunhill
|| i == N - 1 && house [N - 2].smoke && house [N - 2].smoke != Dunhill
|| (house [i - 1].smoke && house [i + 1].smoke
&& house [i - 1].smoke != Dunhill && house [i + 1].smoke != Dunhill)))
return -1;

/* the owner who smokes Blue Master drinks beer */
if (house [i].smoke && house [i].drink
&& CHECK (house [i].smoke == BlueMaster, house [i].drink == beer))
return -1;

/* the German smokes Prince */
if (house [i].nat && house [i].smoke
&& CHECK (house [i].nat == German, house [i].smoke == Prince))
return -1;

/* the man who smokes Blend has a neighbor who drinks water */
if (house [i].smoke == Blends
&& (i == 0 && house [1].drink && house [1].drink != water
|| i == N - 1 && house [N - 2].drink && house [N - 2].drink != water
|| (house [i - 1].drink && house [i + 1].drink
&& house [i - 1].drink != water && house [i + 1].drink != water)))
return -1;
}

return 0;
}


static int try_house (unsigned int);
static int try_nat (unsigned int);
static int try_color (unsigned int);
static int try_pet (unsigned int);
static int try_drink (unsigned int);
static int try_smoke (unsigned int);

static int
print_solution ()
{
unsigned int i;
for (i = 0; i < N; ++i)
printf ("House %d - nat: %s\tcolor: %s\tpet: %s\tdrink: %s\tsmoke: %s\n",
i,
nat [house [i].nat],
color [house [i].color],
pet [house [i].pet],
drink [house [i].drink],
smoke [house [i].smoke]);
puts ("===");
}

static int
try_house (unsigned int i)
{
if (i == N)
{
print_solution ();
return 0;
}
else
return try_nat (i);
}

static int
try_nat (unsigned int i)
{
enum nat nat;
for (nat = Brit; nat <= German; ++nat)
{
if ((nat_set & (1 << nat)) == 0)
{
nat_set |= 1 << nat;
house [i].nat = nat;
if (feasibility_check () == 0 && try_color (i) == 0)
return 0;
nat_set &= ~ (1 << nat);
}
}
house [i].nat = 0;
return -1;
}

static int
try_color (unsigned int i)
{
enum color color;
for (color = red; color <= blue; ++color)
{
if ((color_set & (1 << color)) == 0)
{
color_set |= 1 << color;
house [i].color = color;
if (feasibility_check () == 0 && try_pet (i) == 0)
return 0;
color_set &= ~ (1 << color);
}
}
house [i].color = 0;
return -1;
}

static int
try_pet (unsigned int i)
{
enum pet pet;
for (pet = dogs; pet <= fish; ++pet)
{
if ((pet_set & (1 << pet)) == 0)
{
pet_set |= 1 << pet;
house [i].pet = pet;
if (feasibility_check () == 0 && try_drink (i) == 0)
return 0;
pet_set &= ~ (1 << pet);
}
}
house [i].pet = 0;
return -1;
}

static int
try_drink (unsigned int i)
{
enum drink drink;
for (drink = tea; drink <= water; ++drink)
{
if ((drink_set & (1 << drink)) == 0)
{
drink_set |= 1 << drink;
house [i].drink = drink;
if (feasibility_check () == 0 && try_smoke (i) == 0)
return 0;
drink_set &= ~ (1 << drink);
}
}
house [i].drink = 0;
return -1;
}

static int
try_smoke (unsigned int i)
{
enum smoke smoke;
for (smoke = PallMal; smoke <= Prince; ++smoke)
{
if ((smoke_set & (1 << smoke)) == 0)
{
smoke_set |= 1 << smoke;
house [i].smoke = smoke;
if (feasibility_check () == 0 && try_house (i + 1) == 0)
return 0;
smoke_set &= ~ (1 << smoke);
}
}
house [i].smoke = 0;
return -1;
}


int
main ()
{
try_house (0);
return 0;
}
[/code]

[did]

Велко, :agree::agree::agree::agree:!!!

Точно това е идеята - при толкова малко възможности (под 65536 даже) няма смисъл нищо да се оптимизира - остави компютъра да си харчи безплатното компютърно време, пък ти си спести твоето!!!

Поздравления! Брилянтен подход с големия чук!

[Alien]

Вие очевидно сте на принципа - "защо да го направим по лесния, като може да го направим по трудния начин." Трябваше ли да се пише цяла програма за тази задача? :D

[PtD]

Аз щях да пиша за моста и фенерчето, ама ме домързя

[Harka]

Тъй като тази задача явно вече се дешифрира ето и една логическа задача:
Един човек бил заключен в стая, цялата в бетон, с желязна врата, която може да се отключи единствено с топче за пинг-понг, което трябвало да се пусне в един малък процеп.В този процеп можело да се пусне ЕДИНСТВЕНО топче за пинг-понг, за да се отвори вратата. И така, човекът можел да избяха от стаята, едва когато се отвори желязната и неразбиваема врата, а тя се отваряла само когато пусне топчето за пинг-понг. Човекът бил напълно гол и нямало нищо друго в стаята. Единствената му надежда била в забитата в пода (и херметически затворена отдолу) 30 см висока и тънка точно колкото да влезе топче за пинг-понг тръба, но и точно колкото да не може да бръкне и да извади топчето. На дъното действително имало топче за пинг-понг, но човека нямало как да го извади. Как ще излезе човека?

[velco]

[quote="Harka"]
На дъното действително имало топче за пинг-понг, но човека нямало как да го извади. Как ще излезе човека?
[/quote]

Да пикае в тръбата .

[MOD]

:rofl::rofl::rofl:

[Harka]

[quote="velco"]
Да пикае в тръбата .
[/quote]

Еее velco, разби ми всичките мечти. Но трябва да призная, че отговорът е напълно верен. Нищо, следващия път няма да е толкова лесно:dgrin:.

[did]

[quote="velco"]

[quote="Harka"]
На дъното действително имало топче за пинг-понг, но човека нямало как да го извади. Как ще излезе човека?
[/quote]

Да пикае в тръбата .
[/quote]


Я кажи с какъв софтуер достигна до решението! Предполагам нещо обектно ориентирано, обекти човек, врата, тръба, топче, предават си съобщения под форма на жълтеникави флуиди...

[tuba]

a eto i reshenieto
shte krystim horatat taka
A - 1min
B - 2min
C - 5min
D - 10min
i reshenieto e A i B minavat toav sa 2min
A se vryshta stavt 3min
dava fenercheto i minavat C i D 10 min =>
do tuka sa 13 min obshto B se vryshta s fenercheto 2min
15 obshto i zaedno s A minavat 17 obshto
QED.
Inache kakvo shte pravqt chetirimata sled mosta bez fener shtoto
sa mui svyrshili bateriikite matematikata ne se interesuva.

[M1010X]

[quote="tuba"]

a eto i reshenieto
shte krystim horatat taka
A - 1min
B - 2min
C - 5min
D - 10min
i reshenieto e A i B minavat toav sa 2min
A se vryshta stavt 3min
dava fenercheto i minavat C i D 10 min =>
do tuka sa 13 min obshto B se vryshta s fenercheto 2min
15 obshto i zaedno s A minavat 17 obshto
QED.
Inache kakvo shte pravqt chetirimata sled mosta bez fener shtoto
sa mui svyrshili bateriikite matematikata ne se interesuva.


[/quote]


а ето кой не чете предишните постове
което ме подсеща и за нещо друго, а именно:

Вече имаме работещ скрипт за писане на кирилица, без да е необходимо наличието на кирилизация в операционната система.

При писането на пост в долния десен ъгъл на полето има лого на "KREDOR" и до него е иконката за смяна на клавиатурните подредби - достъпни са фонетична и БДС.

Моля Ви, пишете на кирилица!

tnx to КапитанПланета (и MOD )

[tuba]

Бе аз по принцип на кирилица си пиша ама от в lynx ако си мислиш
че, този кредор работи жестоко се лъжеш

[did]

И да продължим добрата традиция:

[img]http://free.bol.bg/ddiidd/1/manque_morceau.gif[/img]


Малко подсказвам:

[img]http://free.bol.bg/ddiidd/1/math.jpg[/img]

[bikerider]

тва е брадато направо... :8D:

и в двата случая двата малки триъгълника дефинират еднозначно един и същи голям триъгълник, но площта която остава да се запълни с другите фигури е различна.

малкия тръгълник: катети А=2, B=5
голямия триъгълник: катети C=3,D=8

разликата идва оттам, че A*D != B*C, или по точно A*D-B*C=1

[did]

[quote="bikerider"]

тва е брадато направо... :8D:

и в двата случая двата малки триъгълника дефинират еднозначно един и същи голям триъгълник, но площта която остава да се запълни с другите фигури е различна.

малкия тръгълник: катети А=2, B=5
голямия триъгълник: катети C=3,D=8

разликата идва оттам, че A*D != B*C, или по точно A*D-B*C=1
[/quote]


Напипваш нещо почти вярно, но има далеч по-убедително обяснение.

[Vladimir]

Абе всъщност големия триъгълник е четириъгълник, ама е под прикритие
Прикрил се е с два по-малки триъгълника, които обаче не са с еднакви ъгли.