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

Обсуждение задачи 1115. Корабли

is this TEST10 ?
Послано esbybb 12 окт 2016 21:40
6 2
2 10 11 16 16 21
32
33
Re: is this TEST10 ?
Послано esbybb 12 окт 2016 22:22
maybe this?
8 3
2 10 10 11 16 16 18 21
39
32
33
     10 11       18
           16 16
2 10                21
Re: is this TEST10 ?
Послано esbybb 12 окт 2016 22:56
AC java 0.14 =

for (int i=0; i<R; i++) {
 int retcode = s(i);
 if (retcode==-1) {
  i=-1;
 }
}

int s(int row) {
 ..
  //some backtracking call bt(list_of_added, left, r)
 ..
 if (errorwith_this_row) {//error row will be processed first, reprocess all rows
  int reg = L[r];
  for (int i=r; i>0; i--) {
   L[i]=L[i-1];
  }
  L[0]=reg;
  return -1;
 }
 ..
 return 0;
}

bt(list_of_added, left, r) {
 if (list_of_added.size=0) return -1;
 index=list_of_added.removelast
 left+=l[index];
 //greedy adding itemd to list_of_added, decrease 'left'

 if (left>0) bt(list_of_added, left, r);

}

also i use marked[] with indexes of rows were needed,
i use Lorig[], L[] (sorted Lorig[]) and id[], and ID[] (indexes of original lengths in Lorig)