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

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

Why WA1
Послано PrankMaN 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;
}
Re: Why WA1
Послано Bogatyr 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.