Участник:Morgachev/ADACOINS

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADACOINS/

Версия проходящяя по времени: С++14 (clang8.0)

#include <bitset>
 
int main() {
    int n;
    int q;
    scanf("%d%d",&n,&q);
 
    std::bitset<100001> bs;
    bs[0]=1;
    for(int i=0;i<n;++i)
    {
        int x;
        scanf("%d",&x);
        bs|=bs<<x;
    }
 
    int s[100005]={0};
 
    for(int i=1;i<=100001;++i)
        s[i]=s[i-1]+bs[i];
    while(q--)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        printf("%d\n", s[b]-s[a-1]);;
    }
    return 0;
}


Версия на питоне, не прошедшая по времени

 
def get_valid_sums_vector(coins, end):
    """
    Find all valid sums from zero to end using dynamic programming.
    """
    prev = [False for _ in range(end + 1)]
    cur = [False for _ in range(end + 1)]
    prev[0] = True
    cur[0] = True
 
    for coin_idx in range(1, len(coins)+1):
        for sum_v in range(1, end + 1):
            if sum_v < coins[coin_idx-1]:
                cur[sum_v] = prev[sum_v]
            if sum_v >= coins[coin_idx-1]:
                cur[sum_v] = \
                    (prev[sum_v] or
                     prev[sum_v - coins[coin_idx-1]])
 
        prev, cur = cur, prev
        cur = [False for _ in range(end + 1)]
        cur[0] = True
 
    return prev
 
 
n_coins, n_queries = map(int, input().split())
coins = [int(x) for x in input().split()]
 
starts = []
ends = []
for i in range(n_queries):
    start, end = [int(x) for x in input().split()]
    starts.append(start)
    ends.append(end)
 
# We use max(ends) to not repeat computations.
v = get_valid_sums_vector(coins, max(ends))
for start, end in zip(starts, ends):
    print(sum(v[start:end + 1]))
 


Чисто по приколу написал на Kotlin, тоже не проходит(

private fun readLn() = readLine()!!
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
 
fun getValidSums(coins: List<Int>, start: Int, end: Int): BooleanArray {
    var prev = BooleanArray(end+1) { false }
    var cur = BooleanArray(end+1) { false }
    prev[0] = true
    cur[0] = true
 
    for (coinIdx in 1..coins.lastIndex+1){
        for (sum_v in 1..end){
            if (sum_v < coins[coinIdx-1])
                cur[sum_v] = prev[sum_v]
            if (sum_v >= coins[coinIdx-1])
                cur[sum_v] = prev[sum_v] or prev[sum_v - coins[coinIdx-1]]
        }
        prev = cur.also { cur = prev }
        cur.fill(false, 1)
    }
 
    return prev
}
 
fun main(args: Array<String>) {
    var res = readInts()
    val nQueries = res[1]
 
    val starts = arrayListOf<Int>()
    val ends = arrayListOf<Int>()
    val coins = readInts()
 
    for (i in 1..nQueries){
        res = readInts()
        starts += res[0]
        ends += res[1]
    }
 
    val v = getValidSums(coins, starts.min()!!, ends.max()!!)
    println((starts zip ends)
        .map {(start, end) -> v.slice(start..end).count{ x -> x} }
        .joinToString("\n"))
}