Задания для олимпеады.

[Alex1347]

1)Среди 13 монет есть одна отличающаяся по весу.Как за 3 смешивания на чашечных вечах без гирь найти эту монету?
2)ПрограмированиеДля любого целого числа N>7 найти все такие пары целых чисел X и Y ,что 3х+5y=N.Исполнить программу для N=16,25,155???
3)Продолжить следующую последовательность:110,20,12,11,10 .....
4)Самое тяжёлое....В двумерном масиве А[NxN] в ячейке А[1;1]расположенна черепаха.Она мечтает попасть в ячейку А[N;N].Всё поле заполнено числами-это количество еды в данной клетке.И ей ещё нужно собрать максимальное количество еды.Причём черепашка может двигаться только на одну клетку по горизонтали вправо или на одну клетку по вертикали вниз.Составьте алгоритм(программу) для выполнения этой задачи.
Входной файл: Выходной файл:??
5
0........35......66 ...10.....0
1........22......12....11.....75
43......0 .......26.....24.....1
125.....234 ...1......120....1
0........1 .......261...1......120


Помогите пожалуйста решить эти задания.Задания похожи с теми которые будут.И мне бы очень хотелось точно узнать как они решаются..)Заранее спасибо

[LeBron]

Не называйте это олимпиадными задачами. Последнее - 2мерная динамика, ее новичкам как раз так и показывают (в виде "черепашки").

Первая: делим 4/4/5, сравниваем 4ки, потом уже смотрим по результату. Мы будем знать, где фальшивка, в первой 8ке, или среди оставшихся 5. Если в первой, то... в общем, долго писать метод состояний, копирну с гугли

Взвешивание 1. Поместим на I чашу весов 1,2,3,4, на II - 5,6,7,8. Возможно два варианта(вообще-то три, но два варианта принципиально ничем не отличаются)
а)Одна из чаш перевесила, значит фальшивая монета одна из восьми первых монет.
б)Равновесие - фальшивая монета находится среди 9,10,11,12,13.

Взвешивание 2а(фальшивка - одна из первых восьми). На I кладем 1(то есть оставляем на месте) и три заведомо нормальных монеты, пусть это будет 10,11,12. На II - 2,3,4,8. Возможны три варианта.
а) Равновесие. Значит фальшивка среди 5,6,7 (при этом выявляется отношение веса фальшивой монеты к нормальной: если в первое взвешивние II перевешивала, то фальшивка тяжелее, если нет, то легче, а значит согласно 2ой аксиоме за третье взвешивание находится фальшивка).
б) Положение чаш не изменилось. Фальшивка либо 1, либо 8. Согласно 1ой аксиоме за третье взвешивание находим фальшивку.
в) Весы перебросились, то есть более легкая чаша стала более тяжелой и наоборот. Значит фальшивая находится среди 2,3,4 и становится известно: тяжелее она или легче. Опять же, благодаря 2ой аксиоме за третье взвешивание находим фальшивку.

Взвешивание 2б(фальшивка - одна из последних пяти).
На I кладем 1 и 9, на II - 10, 11. Возможны два варианта.
а) Равновесие. Фальшивка либо 12,13. Согласно 1ой аксиоме за третье взвешивание находим фальшивку.
б) Неравновесие. Фальшивка среди 9,10,11.

Взвешивание 3(фальшивка среди 9,10,11).
На I кладем 1 и 2, на II - 9, 10. Возможны три варианта.
а) Равновесие. Фальшивка 11.
б) Положение чаш не изменилось. Фальшивка 10.
в) Весы перебросились. Фальшивка 9.

Это чтоб не было лишних вопросов, нормальное решение.

Второе задание: если маленькие ограничения, то поступаем, как вегда в случае пародии на задачу - пишем полный перебор. Если бы было сказано что-то о числах поольше, чем 155, то используем или динамику, или (если числа еще больше) строгое матрешение.

Сейчас еще подумаю, что за последовательность в 3ей, а то она визуально лишена логики.

[eoln]

3)

110 is base2(binary)
20 is base3
12 is base4
11 is base5
10 is base6
6 is base7
6 is base8(octal)
6 is base9
6 is base10(decimal)

http://www.gamescore.com/forum/viewtopic.php?t=1295

[LeBron]

Понятно. Вот и на послелнюю ответ.
А что за олимпиада, к которой Вы готовитесь? По универу?

[Alex1347]

Сообщение от LeBron

Понятно. Вот и на послелнюю ответ.
А что за олимпиада, к которой Вы готовитесь? По универу?

Да не,я школьник,11 класс,и мне сказали срочно на олимпеаду,в последний момент,и учитель дал похожие задания ,и вот стараюсь их сделать,но без вашей помощи,я бы наврядли сделал....

Спасибо большое за помощь...если будет возможность помочь остольные,я жду,спасибо всем)))

[LeBron]

Остальные? Все, указанные в этой теме, общими усилиями уже решили. По поводу школьных олимпиад - в России уже недавно прошли региональные последнего уровня, дальше только ВсеРосы будут, в Украине и значительной части других постсоветских стран регионалки еще только будут. Но если вам на регионалку, то вынужден расстроить - почти нигде не дают такие "задачи". Разве что в тех регионах, где оимпиада с информатики включает в себя тесты на знание Майкрософт Офис Из всех перечисленных может быть разве что последняя, но, во-первых, она слишком простая для региональной олимпиады, во-вторых, - если и будет, то не в столь старой и всем известной формулировке.
А у Вас что, не было городской/районной олимпиады? Ведь участники олимпиад более высокого уровня определяются именно там.

[Alex1347]

Я сам из ПМР,у меня щас районая,но первые 3 места едут на городскую...так уже сложнее будет..Ну а остольные я имел виду 4.Но эт кто может))

[LeBron]

Я уже писал, в 4ой - 2мерная динамика. Суть в том, чтоб хранить в каждом елементе матрицы с ответами максимальную сумму, которую можно набрать до этой клетки. И определять ее, как максимум из сумм ответа для левой клетки и значения основной матрицы в текущей клетке и ответа для верхней клетки и значения основной матрицы в текущей клетке.
Если только район, то может быть, на районе задачи давать вряд ли будут, только вот такие упражнения.

[Serge_Bliznykov]

по поводу 4-й задачи посмотрите, похожие задачи уже неоднократно разбирались на форуме.

например:
http://www.programmersforum.ru/showthread.php?t=65954
http://programmersforum.ru/showthread.php?t=60512
http://www.programmersforum.ru/showthread.php?t=60880