Школьная олимпиадная задача

[TinMan]

Сообщение от New man

TinMan, ваша программа должна выдавать ошибку при k > n

Моя прога кому-то что-то задолжала?.. и не отдает?? во, зараза!.. ))
Вот протокол ее работы при некотором k>n

Running "c:\_\dropbox\pas\pf\pf12k15\pf12k15.exe "
5 8
1 3 5 4 2
5

Где и что я делаю неправильно?
New man, обрати внимание на четвертую с конца строчку в моем коде )).
Ромаха, спасибо за поддержку ). Согласен, критика должна быть более предметной (или хотя бы проверенной).

Хорошо, а если так :

Ром, пара слов общего характера, если ты не против..
Мой код - это просто полный перебор. Он не требует никаких "соображений в защиту", все, что ему надо - быть написанным без ошибок (на это я в данном случае надеюсь, но не гарантирую).
Если же пытаться использовать какой-то общий _алгоритм_, то прежде всего, следует привести некоторые соображения математического характера, на которых он будет основан. Типа - вот такое преобразование упрощает ситуацию, не меняя результата. После беглого ознакомления с условием я такого алгоритма придумать не смог, потому использовал рекурсию (как способ полного перебора). Возможно, тут следует делать слияние соседних грядок (как ты делаешь, Ромаха, если я правильно тебя понял). Но, как я сказал выше, это требует строгого подтверждения.
Ромаха, не отвлекайся давай, делай дело )

[Poma][a]

Утро доброе.

Найдем (ну хоть попытаемся найти) инвариант. На его роль подходит сумма времязатраности по выполнения дачного долга. Тоесть сумма всех значений массива t. Мы можешь делать с массивом t всё что захотим, лишь бы сумма всех его элементов не стала бы меньшей, или большей..Она должна сохранить совё изначальное значение.
Т.к. мы мы имеем право назначать только соседние грядки, то после нахождения минимума мы просто загоним значение t[min] в t[min+1] (разумеется сложив 2 значения t[min] и t[min+1])
Теперь сумма элементов массива больше ровно на t[min]. И что бы злобный инвариант не выкинул нас из цикла мы должны "выкинуть" t[min]. Как это сделать? Вернемся к вопросам реализации, ну наверное или запихнуть в другой массив, но тогда как быть в цикле? => снова перезапись элементов в массив t, или побайтовый сдвиг(или побитовый сдвиг или пошаговый, не помню).
Инвариант, остается инвариантом. Кол-во элементов массива уменьшается на 1. Но времязатратность грядкокопания остается не изменной. (Ведь тоже рекурсия )

как ты делаешь, Ромаха, если я правильно тебя понял

Ага-ага. Всё верно

Ромаха, не отвлекайся давай, делай дело )

Эх да, надо-надо возвращаться к этому циклу Штайнхауса, причем документация на него есть только на английском языке, ужас!

[TinMan]

Ром, я не совсем понимаю твою тягу к инвариантам. Помимо сохранения, в них еще должен быть какой-то смысл..
Короче, вот тебе пример:
5 4
2 3 9 1 9
Минимум - 1. Эту единицу ты, видимо, объединишь с одной из девяток. И получишь ответ 10, что явно неверно..
Так? или я во что-то не врубаюсь?

[Poma][a]

Ром, я не совсем понимаю твою тягу к инвариантам

Не какой тяги нет, просто показалось, что тут он может помочь

Помимо сохранения, в них еще должен быть какой-то смысл..

Агась.

Короче, вот тебе пример:

Ага. Понял. Осознал. Больше не повториться.

Так?

Ага.

или я во что-то не врубаюсь?

а это уже ересь

Да-да, я напортачил. Огроменное спасибо, что нашел (фи, как не культурно) контр-пример для ей идеи.

[Аватар]

Есть подозрение, что это частный случай задачи коммивояжера. И алгоритм точного решения - только перебор вариантов. Обосновать это предположение в приемлемое время слабо, скорее всего вообще слабо