ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1005. Куча камней

PrankMaN Why WA1 [1] // Задача 1005. Куча камней 13 апр 2012 04:06
This is my code, it works good on the sample test, but I get WA1

#include <stdio.h>

unsigned int w[20], s, i, n, max, h, j, k, r[20], l[20];
bool a[50001]={1}, u[50001][20];

int main (void){
    scanf("%u", &n);
    for(i = 0; i < n; i++){
        scanf("%u", &w[i]);
        h += w[i];
    }
    for(i = 1; i <= h/2; i++)
        for(j = 0; j < n; j++){
            if(u[i - w[j]][j] == 0 && a[i - w[j]] && i - w[j] >= 0){
                a[i]++;
                for(k = 0; k < n; k++)
                    u[i][k] = u[i-w[j]][k];
                u[i][j]++;
                max = i;
                j = n;
            }
        }
    printf("%i", h - 2*max);
    return 0;
}
Bogatyr Re: Why WA1 // Задача 1005. Куча камней 15 сен 2012 18:55
It's not clear what your algorithm is (all the single letter variables make for unreadable code), but to quote from another thread about this question, "all polynomial time algorithms are wrong."    You must consider all possible combinations, because otherwise there will be an input somewhere that will cause your solution to fail.