LINUX.ORG.RU
решено Форум — Development  

Задачка


0

1

Возможно, задача покажется вам легкой, но не обессудьте: я не могу ее решить уже 6 часов. Это не домашнее задание, как многие подумают, просто факультативное шевеление мозгами.

На некотором острове Тритландия есть валюта. В хождении имеются купюры в 1 трит, 3 трита, 9 тритов, 27 тритов, ... 3^k тритов, k ∈ N (бесконечность). Однажды в ресторане, после предъявления счета в n тритов, (n ∈ N , вводится с клавиатуры), программист Васечкин обнаружил., что в наличии у него имеется ровно по одной купюре каждого достоинства. Официант забирает всю сдачу в качестве чаевых, оставить его без сдачи нельзя. Официанту нравится получать в качестве чаевых сумму, которую можно оплатить таким набором купюр, чтобы каждая встретилась не более 1 раза.

Нужно так оплатить счет, чтобы угодить официанту.

Вывести сумму, которую нужно уплатить, согласно кошельку Васечкина, и чаевые.

★★★★

 ← 1 2 →

Брутфорсный терм в FOL:

∃ n ∈ ℕ                       -- n — счёт.
  ∃ m ∈ {n + 1, n + 2, ...}   -- m — сколько платим, заведомо больше n (чаевые > 0).
    norm₃(m) ∧ norm₃(m - n)    -- то что платим (m) и чаевые (m - n) должны быть записаны 0-ями и 1-цами в 3-чной СС
                              -- (т.е. содержать не больше одной купюры данной ценности).

то же самое на хаскеле:


answer :: Integer -> Integer
answer n = fromJust $ find ok [n + 1 ..]
  where ok m = norm m && norm (m - n)
        norm x
          | x `mod` 3 == 2 = False
          | x `div` 3 == 0 = True
          | otherwise      = norm (x `div` 3)

showAnswer :: Integer -> String
showAnswer n = printf "n = %i, m = %i, m - n = %i" n m (m - n)
  where m = answer n

-- * I/O.

main :: IO ()
main = interact $ showAnswer . read

-- * Yet I/O.

printAnswers :: [Integer] -> IO ()
printAnswers = mapM_ $ putStrLn . showAnswer

hundred :: IO ()
hundred = printAnswers [1 .. 100]


*Main> hundred
n = 1, m = 4, m - n = 3
n = 2, m = 3, m - n = 1
n = 3, m = 4, m - n = 1
n = 4, m = 13, m - n = 9
n = 5, m = 9, m - n = 4
n = 6, m = 9, m - n = 3
n = 7, m = 10, m - n = 3
n = 8, m = 9, m - n = 1
n = 9, m = 10, m - n = 1
n = 10, m = 13, m - n = 3
...

и это (fix me) оптимальные числа — наименьшая плата при которой официант получает ненулевую сдачу по одной купюре и мы эту сумму можем оплатить (у нас ведь тоже только по одной купюре).

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

> и это (fix me) оптимальные числа — наименьшая плата при которой официант получает ненулевую сдачу по одной купюре и мы эту сумму можем оплатить (у нас ведь тоже только по одной купюре).

э... т.е. ты считаешь, что при n=1 m=4 оптимальнее m=3, а при n=4 m=13 оптимальнее m=9? о_О

arsi ★★★★★
()
Ответ на: комментарий от arsi

при n=1 m=4 оптимальнее m=3

Обед стоит 1 (∈ N, не обязательно степень тройки). Можем заплатить 1? Нет - официант хочет чаевых. Заплатить 2? Нет - у нас нет двух купюр стоимостью 1. Заплатить 3? Тогда официант получит 3 - 1 = 2 чаевых, а это не «сумма, которую можно оплатить таким набором купюр, чтобы каждая встретилась не более 1 раза» (условие).

quasimoto ★★★★
()
Ответ на: комментарий от arsi

Кстати, у меня n - выставленный счёт, m - что в итоге заплатим (> n), а m - n (> 0) - чаевые/сдача.

Т.е. (n = 1, m - n = 3) и (n = 4, m - n = 9) - может это имелось ввиду?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

тьфу, фигово я читал условие… считал, что только сумма вместе чаевыми должна попадать под требование. а если так, то да, всё верно.

arsi ★★★★★
()

у многих так жмёт что-то отдавать официанту, что даже нормально постановку задачи воспринять не могут ))

yyk ★★★★★
()
Ответ на: комментарий от quasimoto

Приведу и я свое корявенькое решение:

-module(billandtip).

-export([find_solution/1]).

to_ternary(N) when N > 0 ->
    [N rem 3 | to_ternary(N div 3)];

to_ternary(_) -> [].

to_decimal([X | Tl]) ->
    X + 3*to_decimal(Tl);

to_decimal(_) -> 0.

add(L) ->
    case L of
        [2 | Tl] -> [0 | add(Tl)];
        [X | Tl] -> [X+1 | Tl];
        _ -> [1]
    end.

solve(L) ->
    case L of
        [2 | Tl] -> [0 | solve(add(Tl))];
        [X | Tl] -> [X | solve(Tl)];
        _ -> []
    end.

find_solution(N) when N > 0->
    case to_decimal(solve(to_ternary(N))) - N of
        0 -> io:fwrite("Solution: ~p~n", [1]);
        Res -> io:fwrite("Solution: ~p~n", [Res])
    end;

find_solution(_) ->
    io:fwrite("There is no solutions").
delete83 ★★
()

решение на хаскеле выглядит красиво, но без бутылки не разобраться :)

вот набыдлокодил (доработанный код арси):

    public static int triplification(int check) {
        int cache = 0, tips = 0;
        boolean tips_need = true;
        int product = 1;
        while (check > 0) {
            switch (check % 3) {
                case 0:
                    if (tips_need && tips == 0)
                        tips = product;
                    break;
                case 1:
                    cache += product;
                    break;
                case 2:
                    ++check;
                    if (tips_need) {
                        tips = product;
                        tips_need = false;
                    } else
                        tips += product;
                    break;
            }
            product *= 3;
            check /= 3;
        }
        if (tips_need) cache += (tips > 0 ? tips : product);
        return cache;
    }
yyk ★★★★★
()
Ответ на: комментарий от yyk

решение на хаскеле выглядит красиво, но без бутылки не разобраться :)

Хаскель там можно не читать. Это «решение» - прямая запись условия задачи:

∃ (n ∈ ℕ, m ∈ {n + 1, n + 2, ...}) (norm₃(m) ∧ norm₃(m - n))

высказывание = тип, доказательство = программа. Т.е. это executable высказывание. Тут квантификаторы ∃ (теорема о существовании) так что, вычислительно, ответ легко получается. Вот в FLT есть квантификаторы ∀ - там так просто не получится ;)

quasimoto ★★★★
()
Ответ на: комментарий от yyk

Для кого как. Для меня код на Си, который тут кто-то приводил, выглядит дремучим лесом. Разобраться можно, но совершенно не хочется при виде такой каши.

delete83 ★★
()
Ответ на: комментарий от quasimoto

Ещё более лаконичный вариант на haskell:

-- * hs.hs

import Data.List ( find )
import Data.Maybe ( fromJust )

test :: Integer -> Bool
test x = not (m == 2) && (d == 0 || test d)
  where (d, m) = x `divMod` 3

solve :: Integer -> Integer
solve n = fromJust $ find ok [n + 1 ..]
  where ok m = test m && test (m - n)

main :: IO ()
main = mapM_ (putStrLn . show . solve) [1 .. 50000]

на си:

/* c.c */

#include <stdio.h>

#define OVERFLOW    2147483647
#define N           50000

int
test(int x)
{
  for (;;) {
    int m = x % 3;
    x /= 3;
    if (m == 2)
      return 0;
    else if (x == 0)
      return 1;
  }
}

int
solve(const int n)
{
  for(int m = n + 1; m < OVERFLOW; m++)
    if (test(m) && test(m - n))
      return m;

  return -1;
}

int
main ()
{
  for(int i = 1; i <= N; i++)
    printf("%i %i\n", i, solve(i));

  return 0;
}

бенч:

$ gcc -std=c99 -O2 c.c -o c
$ ghc -O2 --make hs.hs

# n = 1 .. 10000

$ time ./c > /dev/null

real	0m0.149s
user	0m0.148s
sys	0m0.000s

$ time ./hs > /dev/null

real	0m1.265s
user	0m1.264s
sys	0m0.000s

# n = 1 .. 50000

$ time ./c > /dev/null

real	0m8.156s
user	0m8.153s
sys	0m0.000s

$ time ./hs > /dev/null

real	1m11.768s
user	1m11.640s
sys	0m0.112s

# n = 1 .. 100000

$ time ./c > /dev/null

real	0m24.800s
user	0m24.782s
sys	0m0.004s

$ time ./hs > /dev/null

...
quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

вот по этому ещё бенчмарк сделай, а то мне лень на ночь глядя :)

#include <stdio.h>

static unsigned solve(unsigned n) {
    unsigned m3 = 0, m = 0, t3 = 1, c, p;
    for (++n, p = 0; n; n /= 3, p += 2)
        m3 += (n % 3) << p;
    while (((m3 | t3) & 0xAAAAAAAA)) {
        for (++m3; (c = m3 & (m3 >> 1) & 0x55555555) != 0; m3 += c);
        for (++t3; (c = t3 & (t3 >> 1) & 0x55555555) != 0; t3 += c);
    }
    for (p = 1; m3; m3 >>= 2, p *= 3)
        m += p * (m3 & 3);
    return m;
}

int main() {
    unsigned n;
    for (n = 1; n <= 50000; ++n) {
        unsigned m = solve(n);
        printf("n = %u, m = %u, m - n = %u\n", n, m, m - n);
    }
    return 0;
}
arsi ★★★★★
()
Ответ на: комментарий от arsi 
+--------------+--------------+--------------+--------------+
| n            | my.hs        | my.c         | arsi.c       |
|              |              |              |              |
+--------------+--------------+--------------+--------------+
| 10.000       | 0.1.265      | 0.0.149      | 0.0.114      |
+--------------+--------------+--------------+--------------+
| 50.000       | 1.11.768     | 0.8.156      | 0.5.930      |
+--------------+--------------+--------------+--------------+
| 100.000      | ...          | 0.24.800     | 0.18.295     |
+--------------+--------------+--------------+--------------+
| 500.000      | ...          | 1.22.157     | 0.59.100     |
+--------------+--------------+--------------+--------------+
quasimoto ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2 →
Development