Арифметические забавы

[vak]

Задачка из математического кружка:

Три фермера продавали куриц на местном рынке. У одного было 10 куриц, у второго — 16, у третьего — 26. Чтобы не конкурировать между собой, они договорились продавать куриц по одной цене. К обеду они решили, что продажи идут не так уж хорошо, поэтому они все одинаково понизили цену. К концу дня они продали всех куриц. Оказалось, что каждый из фермеров за этот день выручил 35 долларов. Какова была цена за курицу до обеда и после обеда?

Програмка на SQL от Vladimir Begun:

SQL> WITH
2 c$ AS (SELECT /*+ MATERIALIZE */ ROWNUM v FROM dual CONNECT BY LEVEL <= 3500)
3 , c1 AS (SELECT /*+ MATERIALIZE */ v - 1 v FROM c$ WHERE v <= 11)
4 , c2 AS (SELECT /*+ MATERIALIZE */ v - 1 v FROM c$ WHERE v <= 17)
5 , c3 AS (SELECT /*+ MATERIALIZE */ v - 1 v FROM c$ WHERE v <= 27)
6 , cr1 AS (
7 SELECT c.v f, (10 - c.v) s, c$1.v x, c$2.v y
8 FROM c$ c$1, c$ c$2, c1 c
9 WHERE c.v * c$1.v + (10 - c.v) * c$2.v = 3500 AND c$1.v >= c$2.v
10 )
11 , cr2 AS (
12 SELECT c.v f, (16 - c.v) s, c$1.v x, c$2.v y
13 FROM c$ c$1, c$ c$2, c2 c
14 WHERE c.v * c$1.v + (16 - c.v) * c$2.v = 3500 AND c$1.v >= c$2.v
15 )
16 , cr3 AS (
17 SELECT c.v f, (26 - c.v) s, c$1.v x, c$2.v y
18 FROM c$ c$1, c$ c$2, c3 c
19 WHERE c.v * c$1.v + (26 - c.v) * c$2.v = 3500 AND c$1.v >= c$2.v
20 )
21 SELECT /*+ USE_HASH(cr1 cr2 cr3) LEADING(cr1 cr2 cr3) */
22 cr1.f c1_f, cr1.s c1_s, cr2.f c2_f, cr2.s c2_s
23 , cr3.f c3_f, cr3.s c3_s, cr1.x / 100 x$, cr1.y / 100 y$
24 FROM cr1, cr2, cr3
25 WHERE cr1.x = cr2.x AND cr1.y = cr2.y AND cr2.x = cr3.x AND cr2.y = cr3.y
26 /

Находит решение за 34 секунды на процессоре 2.7 ГГц.

Есть также варианты на Паскале и Go. Да, я знаю что программу можно лёгким движение ускорить на пару порядков, но тогда она не будет годиться для измерения скорости разных языков и компиляторов.

Comments

[aafin.livejournal.com]

Это задача про систему диофантовых уравнений?

[vak]

Не совсем.
То есть да, это система полиномиальных уравнений в целых числах, но не полная.

[aafin.livejournal.com]

Метод ветвей и границ применять надо однако.

[vak]

Вот решение в стиле Ландау от bigwhitefish (физтехи оценят).

3.75 и 1.25
a — продажи до, b — продажи после.
Прямая a*p1+b*p2=35 должна пересекать прямые a+b=10,16,26 в целых точках
(условие неделимости куриц).
Для наклона k получаем, что 6/(k–1) и 16/(k–1) должны быть целые, откуда k=3.
Из условия неотрицательности куриц получаем три варианта цены.
Другие варианты (7/6, 7/2) и (35/26, 105/26) но они не делятся на центы.

[aafin.livejournal.com]

Круто! Восхитительная олимпиадная задача.

[papa-lyosha.livejournal.com]

Вот программа на Хаскеле, считает 0.26 сек
[(a,a+b) | a<-[1..3500 `div` 26], b<-[350-a..3500-26*a], all (\t-> (3500-t*a) `mod` b ==0) [10,16,26] ]
ответ [(125,375)]

[vak]

Красиво, однако!

[papa-lyosha.livejournal.com]

На Хаскеле все получается красиво

[tim-caper.livejournal.com]

Сссылка на facebook приводит к "Something Went Wrong"

[vak]

Странно, у меня нормально открывается.

[pito-32.livejournal.com]

Not too much precise results, but done in excel in ~2 minutes, no programming, no thinking, just entering few values while watching the TV :) :)

price
morning 3.5
afternoon 1.2


10 16 26

10 7 2
0 9 24

35 35.3 35.8

[cross-join.livejournal.com]

Добавил туда же тесты для Си, Дельфи и пошарапанного Си.
http://arbinada.com/pmk/node/1164

[morontt.livejournal.com]

У меня вышло 2 миллисекунды на Intel Core 1.8GHz, так что можно ускорить на 4 порядка, а не на пару :)