LINUX.ORG.RU

Jednakost - олимпиадное программирование

 ,


0

4

Есть задача. Коротенько о том, что надо сделать: на вход даётся строчка A и строчка B. Пример для А: «143175», для В: «120». Нужно между символами в строчке А вставить минимальное количество знаков «+» чтобы получить В. В данном случае: 14 + 31 + 75 = 120. На выходе программа должна возвращать минимальное количество плюсов. Количество символов в А не больше 1000, значение В не больше 5000. Время работы программы должно быть меньше 1 секунды.

Пример 2: А=«5025», В=«30». 5 + 25 = 30. Минимальное количество плюсов: 1.

Пример 3: А=«999899», В=«125». 9 + 9 + 9 + 89 + 9 = 125. Минимальное количество плюсов: 4.

Я написал такую программу:

checkPluses :: Int -> Int -> Int -> String -> String -> Bool
checkPluses result pVal 0 "" xs = pVal + (read xs :: Int) == result
checkPluses result pVal plusCount "" xs =
  checkPluses result pVal plusCount [head xs] (tail xs)
checkPluses result pVal plusCount xs xs'
  | pVal > result = False
  | (length xs' < plusCount) = False
  | (checkPluses result (pVal + (read xs :: Int)) (plusCount - 1) "" xs') ==
    False = checkPluses result pVal plusCount (xs ++ [head xs']) (tail xs')
  | otherwise = True

checkPlus :: String -> String -> Int -> Bool
checkPlus xs res pluses =
  checkPluses (read res :: Int) 0 pluses "" xs

searchPlusesIter :: Int -> String -> String -> Int
searchPlusesIter pluses xs res
  | checkPlus xs res pluses == True = pluses
  | otherwise = searchPlusesIter (pluses + 1) xs res

searchPluses :: String -> String -> Int
searchPluses = searchPlusesIter 0
Пример работы программы:
λ> searchPluses "143175" "120"
2
Моя программа по сути наивно перебирает количество плюсов и смотрит на выход. Для первого примера она проверяет 1 + 43175 != 120, потом проверяет 14 + 3175 != 120, и т.д. Потом проверяет два плюса: 1 + 4 + 3175 != 120, 1+ 43 + 175 != 120, ..., 14 + 3 + 175 != 120, 14 + 31 + 75 == 120. И возвращает количество плюсов. Программа работает, но очень медленно.

Прошу идей по алгоритму.


Пример 2: А=«5025», В=«30». 5 + 25 = 30. Минимальное количество плюсов: 1.

Почему 1?

По условиям у меня меньше 2 не получается:

5 + 0 + 25 == 30

P.S.

5 + 025 что ли?

или как?

fsb4000 ★★★★★ ()
Последнее исправление: fsb4000 (всего исправлений: 1)
Ответ на: комментарий от Lzzz

Перепиши на С++ и выполняй проверки параллельно.

С/С++ должны дать прирост в производительности, но обычно грамотный алгоритм позволяет укладываться в ограничения практически любым языкам.

czan ()

Динамическое программирование -> запоминать деревья вариантов которые дают подстроки и выполнять перебор по дереву для отрезков, а для строк хэш-таблицы

AKonia ★★ ()

Что-то в вашем языке без поллитры не разобраться… Вы исключаете тривиальные случаи? Нужно бить сразу на строки, длина каждой из которых не больше чем длина суммы. Поэтому 1+43175 проверять не нужно. С начальным нулем может быть хитрость, тем не менее. И тому подобные оптимизации. Подозреваю, это должно порядочно подсократить количество перебираемых вариантов.

sshestov ()
import Data.Char

checkPluses :: Int -> Int -> Int -> String -> String -> Bool
checkPluses result pVal 0 "" xs = pVal + read1 xs pVal 0 == result
checkPluses result pVal plusCount "" xs =
  checkPluses result pVal plusCount [head xs] (tail xs)
checkPluses result pVal plusCount xs xs'
  | pVal > result = False
  | pVal + r > result = False
  | checkLength xs' plusCount = False
  | (checkPluses result (pVal + r) (plusCount - 1) "" xs') ==
    False = checkPluses result pVal plusCount (xs ++ [head xs']) (tail xs')
  | otherwise = True
  where r = read xs :: Int

checkLength [] r = True
checkLength x 0 = False
checkLength (x:xs) r = checkLength xs (r-1)

read1 [] res acc = acc
read1 (x:xs) res acc
  | acc > res = res + 1
  | otherwise = read1 xs res (acc * 10 + digitToInt x)

Чтобы всю строку не перебирал, а раньше останавливался.

monk ★★★★★ ()

Обрати внимание на «значение В не больше 5000». Подстрока от А никогда не будет длиннее 4, или она превысит Б. А если «количество символов в А не больше 1000», редкость будет найти место без плюсов, чем с ними. :) Разбивай на отдельные числа и конденсируй их. Правда, я сам этого до конца не продумал, так как на работу скоро. :/ Во время конденсации хитрый алгоритм нужен, наверное.

anonymous ()

что это за параша вообще, хаскель чтоли?

во-первых ты можешь сгенерировать все варианты чисел заранее и не парсить строки каждый раз: «143175» -> «1», «14», «143», «1431» и т.д.

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

может и с хаскелем сможешь как-то выкрутиться, например 1 + 4 + 3175 - это заведомо неверное выражение, 1+ 43 + 175 - тоже можно не считать. оба выражения не могут быть равны 120, они заведомо больше. но лучше бы ты переписал на с++. возьми ренжи какие-нибудь и сделай на них.

anonymous ()

Есть задача.

#dynamic-programming

Моя программа по сути наивно перебирает количество плюсов и смотрит на выход

Тебе чёрным по белому написали, что это задача на динамическое программирование, нет ты всё равно перебором захреначил. Где ты видел олимпиадную задачу, которая перебором решалась бы? Всегда размерность входов подбирают таким образом, чтобы решение перебором фейлилось, иначе неинтересно было бы.

dsxl ()
Ответ на: комментарий от anonymous

возьми ренжи какие-нибудь и сделай на них.

В этой шняге максимум поддерживается C++14. (я хз gnu или обычный, написано gcc 8.3 c++14), и сторонние библиотеки нельзя использовать…

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

ренжи - header only, можешь попробовать просто через препроцессор пропустить перед отправкой решения. но это наверное читинг если нельзя использовать сторонние библиотеки, могут забанить наверное.

anonymous ()

наивно перебирает

Отсекай комбинации, например если хотя бы одно из чисел больше результата - фтопку, если хотя бы в одном из чисел больше знаков чем в результаате - фтопку.

ya-betmen ★★★★★ ()
Ответ на: комментарий от czan

В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.

Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1

Потом обходим все подстроки и заполняем матрицу.

Вот отрывок:

// ...
for (j = i - 1; j >= i - 4 && j >= 0; j--) {
    x = parse_substring(full_string, len - i, len - j);
    for (k = 0; k + x <= n; k++) {
        if (dp[k + x][i] > dp[k][j] + 1)
        {
            dp[k + x][i] = dp[k][j] + 1;
        }
    // ....
    }
}

Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL

Но это не всё, дальше ещё нужно будет решить вопрос с нулями…

Если решишь, кинь потом в тему своё решение на хаскеле…

fsb4000 ★★★★★ ()
Последнее исправление: fsb4000 (всего исправлений: 2)
Ответ на: комментарий от fsb4000

Таки хаскель недостаточно быстр для данной задачи. Пытался сделать с помощью UArray. Но производительность хромает.

import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad
import Control.Monad.ST

memoArray :: UArray (Int,Int) Int
memoArray = array ((0,1),(999,5000))
            [((i,j),(-1)) | i <- [0..999], j <- [1..5000]]

main = do
  print (memoArray ! (999,5000))
Здесь создаётся массив размерами 1000 на 5000, инициализируется значением -1 и печатается значение из массива по координатам 999 и 5000. На это дело на моём компьютере уходит три с лишним секунды:
time ./uArray
-1

real	0m3,399s
user	0m3,268s
sys	0m0,105s
Возможно есть способы ускорить, но я не нашёл.

czan ()
Последнее исправление: czan (всего исправлений: 1)
Ответ на: комментарий от fsb4000

Наклепал такой вариант:

{-# LANGUAGE FlexibleContexts #-}
import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad
import Control.Monad.ST

memoArray :: UArray (Int,Int) Int
memoArray = array ((0,1),(999,5000))
            [((i,j),(-1)) | i <- [0..999], j <- [1..5000]]

main = do
  print (howManyPluses (take 1000 (repeat '1')) 1000)

howManyPluses :: String -> Int -> Int
howManyPluses nums sum
  | sum > 5000 = 1000
  | otherwise = (searchAnswer nums sum) ! (0,sum)

searchAnswer :: String -> Int -> UArray (Int, Int) Int
searchAnswer numbers sum = runSTUArray $ do
  memoArr <- newArray ((0,0), (999,5000)) (-1) :: ST s (STUArray s (Int,Int) Int)
  evaluated <- newArray ((0,0), (999,5000)) False :: ST s (STUArray s (Int,Int) Bool)
  searchInner ((take 1 numbers), (tail numbers)) sum memoArr 0 evaluated

searchInner (nums, nums') sum memoArr len evaluated = do
  isEval <- readArray evaluated (len,sum)
  if isEval == True
    then return memoArr
    else do
    if ((read nums :: Int) > sum) || (((read nums :: Int) /= sum) && (nums' == ""))
      then do
      writeArray memoArr (len,sum) 1000
      writeArray evaluated (len,sum) True
      return memoArr
      else do
      if ((read nums :: Int) == sum) && (nums' == "")
        then do
        writeArray memoArr (len,sum) 0
        writeArray evaluated (len,sum) True
        return memoArr
        else do
        searchInner ((take 1 nums'),(tail nums')) (sum - (read nums :: Int)) memoArr (len + (length nums)) evaluated
        pluses <- readArray memoArr ((len + (length nums)),(sum - (read nums :: Int)))
        searchInner ((nums ++ (take 1 nums')),(tail nums')) sum memoArr len evaluated
        pluses' <- readArray memoArr (len,sum)
        writeArray memoArr (len,sum) (min (pluses + 1) pluses')
        writeArray evaluated (len,sum) True
        return memoArr
Работает пошустрее, но всё же не укладывается в ограничение по времени.

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

динамика динамикой

но стоит «метод ветвей и границ» ака отсечки тож уважить.

  1. перебор( после инициализации 0 плюсов слоя интами подсрок длины не более длина B) -

постоянно при поиске оставшегося слагаемо делай отсечку на то что искомое уже должно быть равно В минус уже найденная подсумма : тогда возможное число перебора быстреt

т.е просто перебор с отсечками достаточен.

qulinxao3 ()
Последнее исправление: qulinxao3 (всего исправлений: 1)
Ответ на: комментарий от qulinxao3

++

общая отсечка

завести вектор частичных сумм цифр участка [,i] если сумма больше искомого остатка - уменьшение числа плюсов не изменить отношение больше следовательно найденая расстановка плюсов на участке [i+1,] заведомо не часть решения.

и нужна очередь(приоритетная)(вытаскивающая следующим частичное решение с наименьшим в очереди числом плюсов- итерация расстановка следующего плюса(на всех которые «левее») проверка на полное решение и проверка на заведомое выход из области возможного решения - тут как нить можно мемоизировать[вот и динамика]- что-бы слить повторные рекурсии) что-бы перебирать варианты с наименьшим числом + в решениях - тем самым совместив нахождение решения с нахождением решения с минимально возможным числом +

зы: ab = (a+b)*10-b

anonymous ()

Решение на c++:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Part {
  int sum;
  vector<int> path;
};

using Table = vector<vector<Part>>;

vector<int> MinAdditions(const string& a, int b) {
  Table table(a.size());
  for (size_t i = 0; i < a.size(); ++i) {
    for (size_t j = i + 1; j != 0; --j) {
      const size_t k = j - 1;
      if (a[k] == '0') {
        continue;
      }
      int c = stoi(a.substr(k, i - k + 1));
      if (c > b) {
        break;
      }
      if (k == 0) {
        table[i].push_back(Part{c, {c}});
      }
      else {
        for (const auto& [s, p] : table[k - 1]) {
          const auto r = c + s;
          if (r <= b) {
            auto newp = p;
            newp.push_back(c);
            table[i].push_back(Part{c + s, move(newp)});
          }
        }
      }
    }
  }
  const auto& lastRow = table[a.size() - 1];
  auto m = min_element(begin(lastRow), end(lastRow),
             [b](const Part& lhs, const Part& rhs) {
               return lhs.sum == b && (rhs.sum != b ||
                      lhs.path.size() < rhs.path.size());
             });
  return m->path;
}

pair<string, int> ReadInput(istream& in) {
  string input;
  getline(in, input);
  const auto i = find(begin(input), end(input), '=');
  string a {begin(input), i};
  int b = stoi(string{i + 1, end(input)});
  return make_pair(move(a), b);
}

ostream& operator<<(ostream& out, const vector<int>& v) {
  char delim[] = {'\0', '+', ' ', '\0'};
  for (int x : v) {
    out << delim << x;
    delim[0] = ' ';
  }
  return out;
}

int main() {
  const auto& [a, b] = ReadInput(cin);
  const auto& p = MinAdditions(a, b);
  cout << p.size() - 1 << endl;
  cerr << p << endl;
}

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

Исправлено:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Part {
  int sum;
  vector<int> path;
};

using Table = vector<vector<Part>>;

vector<int> MinAdditions(const string& a, int b) {
  Table table(a.size());
  for (size_t i = 0; i < a.size(); ++i) {
    for (size_t j = i + 1; j != 0; --j) {
      const size_t k = j - 1;
      if (a[k] == '0') {
        if (k == i) {
          table[i].insert(table[i].end(), begin(table[i-1]), end(table[i-1]));
        }
        continue;
      }
      int c = stoi(a.substr(k, i - k + 1));
      if (c > b) {
        break;
      }
      if (k == 0) {
        table[i].push_back(Part{c, {c}});
      }
      else {
        for (const auto& [s, p] : table[k - 1]) {
          const auto r = c + s;
          if (r <= b) {
            auto newp = p;
            newp.push_back(c);
            table[i].push_back(Part{c + s, move(newp)});
          }
        }
      }
    }
  }
  const auto& lastRow = table[a.size() - 1];
  auto m = min_element(begin(lastRow), end(lastRow),
             [b](const Part& lhs, const Part& rhs) {
               return lhs.sum == b && (rhs.sum != b ||
                      lhs.path.size() < rhs.path.size());
             });
  return m->path;
}

pair<string, int> ReadInput(istream& in) {
  string input;
  getline(in, input);
  const auto i = find(begin(input), end(input), '=');
  string a {begin(input), i};
  int b = stoi(string{i + 1, end(input)});
  return make_pair(move(a), b);
}

ostream& operator<<(ostream& out, const vector<int>& v) {
  char delim[] = {'\0', '+', ' ', '\0'};
  for (int x : v) {
    out << delim << x;
    delim[0] = ' ';
  }
  return out;
}

int main() {
  const auto& [a, b] = ReadInput(cin);
  const auto& p = MinAdditions(a, b);
  cout << p.size() - 1 << endl;
  cerr << p << endl;
}

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

Спасибо, конечно, за решение на C++. Но на C я уже решение сделал.

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 1000

int array [1000] [5050]; /* 
			    first index -- length
			    second index -- value
			    array contains pluses
			 */
int search (int, int, int) ;
int minimum (int, int) ;

int calculated[1000][5050] ;

char a[1000] ;

int main () {
  char *line = NULL ;
  size_t len = 0 ;
  ssize_t read ;
  read = getline (&line, &len, stdin) ;

  if (-1 == read) { return (0) ;}

  memset (calculated, 0, 1000 * 5050 * sizeof (int)) ;
  memset (array, 0, 1000 * 5050 * sizeof (int)) ;
  void processInput (char *, int) ;
  processInput (line, len) ;
  free (line) ;
  return (0) ;
}

void processInput (char *c, int len) {
  int i ;
  int nulls = 0 ;
  int index = 0 ;
  for (i = 0 ; i < len ; i++) {
    if ('=' == c[i]) { break ; }
    a[index] = c[i] ;
    if ('0' == c[i]) {
      if (nulls < 4) {
	nulls++ ;
      }
    } else {
      nulls = 0 ;
    }
    if (4 != nulls) { index++ ; }
  }

  int length = 4 == nulls ? index + 1 : index ;

  int value = 0 ;
  i++ ;
  for ( ; i < 1010 ; i++) {
    if (c[i] >= '0' && c[i] <= '9') {
      value = value * 10 + c[i] - '0' ;
    } else { break ; }
  }
  
  printf ("%d\n", (search (value, length, 0) - 1)) ;
}

int search (int value, int length, int index) {
  if (index == length) {
    if (0 == value) { return (0) ; }
    else { return (INF) ; }
  }

  if (1 == calculated[index][value]) {
    return (array[index][value]) ;
  }
  
  int pluses_count = (INF) ;
  int current_value = 0 ;
  for (int i = index ; i < length ; i++) {
    current_value = current_value * 10 + a[i] - '0' ;
    if (current_value > value) { break ; }
    pluses_count = minimum (pluses_count,
			    1 + search (value - current_value,
					length, i + 1)) ;
  }

  array[index][value] = pluses_count ;
  calculated[index][value] = 1 ;
  return (pluses_count) ;
}

int minimum (int a, int b) {
  if (a < b) { return (a) ;}
  return (b) ;
}
Это уже не интересно. Гораздо интересней сделать решение на хаскелле.

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

А не логичней пойти от обратного?
Парсишь строку А в массив интов по возможным комбинациям (не длиннее В и соотв не больше В).
Сортируешь массив интов.
Берёшь самый большой инт из массива, вычитаешь его из В, смотришь с другой стороны массива есть ли результат вычитания в массиве - если есть то решение в один плюс из этих двух интов, если нет то берёшь следующий по величине инт.
Когда дойдёшь до В/2, возвращаешься в начало и начинаешь искать не результат вычитания а как его собрать из двух интов с младшей стороны массива - это будет решение в 2 плюса

Вообщем логика в том что при большой длине А у тебя внизу массива будет полно простых цифр, из которых ты легко соберёшь нужный остаток, для Олимпиадой задачи наверняка будут проблемы с тем что максимальный инт в А будет сильно меньше В, но на рандомной строке - шансы получить максимальный инт рядом с В - огромны и тогда задача решается (после подготовки интов) в мизер тактов

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

Решение на c++:

Эх… Вот почему так много всего тормозит. Не нужны здесь вложенные векторы (тут мало что нужно).

#include <iostream>
#include <string>

static int
solve(const std::string &a, int offset, int b)
{
    if (offset == a.length()) {
        return (b == 0 ? 0 : -1);
    }

    int x = 0;
    int i;
    for (i = offset; i < a.length() && x <= b; ++i) {
        x = (x*10) + a[i] - '0';
    }

    if (x > b) {
        --i;
        x /= 10;
    }

    if (i == offset) {
        return -1;
    }

    for (int j = i; j > offset; --j) {
        const int r = solve(a, j, b - x);
        if (r >= 0) {
            return (j == a.length() ? 0 : r + 1);
        }
        x /= 10;
    }
    return -1;
}

int
main(void)
{
    std::string line;
    std::cin >> line;

    const int pos = line.find('=');

    const std::string aStr(line.cbegin(), line.cbegin() + pos);
    const std::string bStr(line.cbegin() + pos + 1, line.cend());

    const int b = std::stoi(bStr);

    std::cout << aStr << std::endl;
    std::cout << b << std::endl;
    std::cout << solve(aStr, 0, b) << std::endl;

    return 0;
}

На сайте не проверял. Похоже, что эту задачу удалили или переименовали. В любом случае, я уже говорил выше, что подход неправильный, отсюда и тормоза. Вариант на хаскеле аналогичен, хотя написать его сложнее (т.к. это хаскель). Тут ТС уже должен справиться.

xaizek ★★★★★ ()

так задача же изейшая, для школьников. секунда — это дофига даже для бейсика.

числа надо брать с конца строки, умножать на степени десятки и последовательно вычитать из суммы. но считать надо не рекурсивно, а для каждой цифры:

def sub(state, digit, maxpow=4):
    new_state = {}
    for n,(pow,x) in state.items():
        n1  = n - digit
        n10 = n - digit * 10**pow
        if (n1 >= 0):
            new_state[n1] = [1, x+1]
        if (n10 >= 0) and (pow > 0) and (pow <= maxpow):
            new_state[n10] = [pow+1, x]
    return new_state

def find_x(A, B):
    state = {B: [0,-1]}
    for digit in reversed(A):
        state = sub(state, digit)
    x = state.get(0, [None,None])[1]
    return x

test_set = [
    ([9,9,9,8,9,9], 125), 
    ([5,0,2,5], 30), 
    ([1,4,3,1,7,5], 120)
]

for A,B in test_set:
    print(B, A, ': x =', find_x(A, B))

from random import randint
A1000 = [randint(1,9) for _ in range(1000)]
B1000 = sum(A1000)

print(f'{len(A1000)} digits: x =', find_x(A1000, B1000))
$ time python shkola.py
125 [9, 9, 9, 8, 9, 9] : x = 4
30 [5, 0, 2, 5] : x = 1
120 [1, 4, 3, 1, 7, 5] : x = 2
1000 digits: x = 999

python shkola.py  0.21s user 0.00s system 99% cpu 0.215 total
anonymous ()