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

Обсуждение задачи 1152. Кривые зеркала

What's wrong!
Послано Miguel Angel 22 дек 2001 06:56
I think it was so easy, but what's wrong on my program?

#include<iostream.h>

int N;
int how[21];
int total;

void main()
{
int i, j, max, pos, hints, sum;
  cin>>N;
  total=0;
  for (i=0; i<N; i++)
  {
     cin>>how[i];
     total+=how[i];
  }
  if (N<=3)
  {
      cout<<0;
     return;
  }
  max = 1;
  hints=0;
  while ( total>0 )
  {
        max = 0;
        pos =-1;
        for (i=0; i<N; i++)
        {
            sum = 0;
            for (j=0; j<3; j++)
                sum += how[(i+j)%N];
            if (sum>max)
            {
                pos=i;
                max=sum;
            }
        }
        if ( pos < 0 )
          break;
        for (j=0; j<3; j++)
            how[(pos+j)%N]=0;
        total -= max;
        hints+=total;
  }
  cout<<hints<<endl;
}
Re: What's wrong!
Послано Christopher Moh 23 дек 2001 11:53
Your algorithm is incorrect.

Consider the following test case:

7
6 6 6 7 5 1 1

Your algorithm will remove the middle (6 6 7) first, then remove the
end (1 1 6), thus incurring a total of
13 + 5 = 18 damage.

The correct solution is to remove the start (6 6 6) first, then
remove (7 5 1), thus incurring a total of
14 + 1 = 15 damage.