forum.boolean.name - Олимпиада по программированию

forum.boolean.name (http://forum.boolean.name/index.php)

- Загадки (http://forum.boolean.name/forumdisplay.php?f=87)

- - Олимпиада по программированию (http://forum.boolean.name/showthread.php?t=16088)

Олимпиада по программированию

Проснулся вчера утром от звонка моего друга. Он зная меня, сказал что у нас олимпиада по программированию. На олимпиаде были в приоритете Turbo Pascal, Delphi, C++. Я немного знал Паскаль, но мой основной и относительно небольшой опыт припадает на Блиц. Естественно у них на компах его не было. А я с собой его не взял. С момента начала олимпиады я минут 30-40 времени убил на поиск/закачку/установку блица, он ска еще и сначала не включался у них на семерке. А далее пошли задачи. Их было 6. Но я их точно не помню. Опишу только 5, а то одну уже забыл. Просто может кто захочет себя проверить:

Если возникнут какие то вопросы, или вы уже слышали о таких задачах и увидели ошибку в описании задачи, обязательно пишите, все выправим. В качестве ответа можете выкладывать исходники. Если кто захочет подсмотреть, так у него появится возможность...

Задача 1:

Написать функцию которая будет возвращать факториал числа N. Входное число N (0<=N<=100).

Задача 2:

Написать функцию "Сапер". В входном файле есть 2 числа М,N и матрица расположения бомб на карте. Где М и N размерность матрицы. На выходе функция должна вывести на экран обработанную матрицу, на которой в каждой ячейке стоит цифра обозначающая количество рядом стоящих бомб. Пример:

Входной файл:

4
4
....
.*..
*...
..*.

Вывод на экран обработанной вашей функцией матрицы:

1110
2*10
*321
12*1
(цвет в программе значения не имеет, это толька для описания на форуме.)

Внимание!!!
Есть кое что, что вам стоит знать, это сэкономит ваше время, а то я сначала этого не знал. Если в условии задачи сказано что входное число 0<=N<=100 это означает, что вам не стоит беспокоится об других вариантах. Вам не следует делать проверку, на случай если входными данными будут: N="Noob", N="15.684", N="-1" или N="101". Или например если в задаче сапер во входном файле будут ошибки. Считается что входная информация изначально правильная и подходит под данные условия задачи.
П.с. Попробуйте воспользоваться вашей функцией факториала и введите в качестве проверки входное число 100. Она должна вывести верный ответ...

Задача 3:

Называется она: "3*N+1"
Нужно написать функцию. В какой входное число N (где N>0) будет постоянно обрабатываться по принципу:
Если число N- парное, то делить его на два. (N=N/2)
Если число N- не парное, то умножать его на три и +1 (N=N*3+1)
В итоге функция должна выводить количество итераций какие прошло число N когда оно стало равно единице.

Задача 4:

В входном файле есть НАТУРАЛЬНОЕ число, которое может уместить в себе до 1000 цифр. Нужно написать функцию, которая в єтом огромном числе ПЕРЕСТАВИТ (а тут проблема, я точно не помню одну или больше) цифру так, что выйдет число больше за данное, но оно будет наименьшим из всех возможных больших. (скорей всего одну цифру, но я думаю, что от єтого сложность задачи не уменьшится)

Задача 5:

За точность не ручаюсь, я ее вообще не сделал, не знал нужной терминологии. А именно, что такое Jolly Jumpers, но я нашел в интернете похожую задачу:

Последовательность п > 0 целых чисел называется jolly jumper, если абсолютные значения разностей последовательных элементов принимают все возможные значения от 1 до п - 1. К примеру,

14 2 3 это jolly jumper, потому что абсолютные разности равны 3, 2 и 1 соответственно. Определение подразумевает, что любая последовательность из одного числа - это jolly jumper. Напишите программу, которая определяет, является ли каждая из введенных последовательностей jolly jumper.

Входные данные:

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

Выходные данные:

Для каждой строки входных данных выведите строку, говорящую "Jolly" или "Not jolly"...

Ответ: Олимпиада по программированию

Это олимпиада для 5тых классов?)

Ответ: Олимпиада по программированию

Таких задач over9000 в интернетах.
Ещё и по каталогам разбитые

Ответ: Олимпиада по программированию

Поссоны!

Код:

Задача 2. (30 баллов)

Фишка.

Фишка может двигаться только вперед по полю длины N.

Длина хода фишки не более K.

Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Пример. N=3, K=2

Возможные пути:

1,1,1

1,2

2,1

Ответ: 3.

Не справился с этой на олимпиаде.
Пример загнал меня в глубокое непонимание.
Присутствовал инструктор, спросил у него - он ничего полезного не ответил.

Ответ: Олимпиада по программированию

Путь-то по видимому один, просто фишка проходит его различными комбинациями шагов разной длины.

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Nerd96 (Сообщение 215156)

Поссоны!

Код:

Задача 2. (30 баллов)

Фишка.

Фишка может двигаться только вперед по полю длины N.

Длина хода фишки не более K.

Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Пример. N=3, K=2

Возможные пути:

1,1,1

1,2

2,1

Ответ: 3.

То что длина шага обязательно целая не говорится в условии.(поэтому можно отсудить балы xD) А так задача по типа тех что в 1 посту.

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Nerd96 (Сообщение 215156)

Поссоны!

Код:

Задача 2. (30 баллов)

Фишка.

Фишка может двигаться только вперед по полю длины N.

Длина хода фишки не более K.

Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Пример. N=3, K=2

Возможные пути:

1,1,1

1,2

2,1

Ответ: 3.

Я так понял здесь следующее:

И да, количество способов продвижения фишки n+1 будет равно сумме предыдущих k способов.

Ответ: Олимпиада по программированию

Цитата:

Сообщение от radiobutton (Сообщение 215153)

Это олимпиада для 5тых классов?)

Ну они явно не на столько простые как ты говоришь. Задачи эти для студентов университета 1-4 курс(возможно и 5, но ни одного не видел) + школьники старших классов, которые на таких олимпиадах большая редкость. Эта олимпиада - один из этапов отбора участников на всеукраинскую олимпиаду. Поэтому, как на 1-й этап могу согласится, что задачи 2 и 3 весьма простые. Но задачи 1 и 4, если они для тебя в первой(что для студентов часто бывает) достаточно сложны. А если учесть что на написание 6 таких задач отведено 3 часа, олимпиаду не можно назвать детской. При этом нельзя использовать интернет и любые дополнительные материалы.

radiobutton я был б рад увидеть хотя б 1-ю задачу в твоем исполнении...:-D

Ответ: Олимпиада по программированию

а меня больше удивило, что тебе позволили юзать блиц. о_О

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Halk-DS (Сообщение 215171)

Ты шутишь, да? Олимпиада для "5 классов". На региональной олимпиаде для 10-11 классов задачи в 10 раз сложнее. И ты действительно считаешь что написать функцию "факториал" сложно?

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Halk-DS (Сообщение 215171)

Ну они явно не на столько простые как ты говоришь. Задачи эти для студентов университета 1-4 курс(возможно и 5, но ни одного не видел) + школьники старших классов, которые на таких олимпиадах большая редкость. Эта олимпиада - один из этапов отбора участников на всеукраинскую олимпиаду. Поэтому, как на 1-й этап могу согласится, что задачи 2 и 3 весьма простые. Но задачи 1 и 4, если они для тебя в первой(что для студентов часто бывает) достаточно сложны. А если учесть что на написание 6 таких задач отведено 3 часа, олимпиаду не можно назвать детской. При этом нельзя использовать интернет и любые дополнительные материалы.

radiobutton я был б рад увидеть хотя б 1-ю задачу в твоем исполнении...:-D

Радуйся

Код:

Graphics3D 1024,768

SetBuffer BackBuffer() 



st$ = FAKTORIAL(100)



Repeat

Text 10,10,st

Flip 

Until KeyHit(1)

End 



Function FAKTORIAL$(n)

If n=0 Or n=1

        Return "1"

End If

s$="1"

For i=2 To n

        s$=ololo(s,Str(i))

Next

Return s

End Function



Function ololo$(a$,b$)

If b="10" 

        Return a+"0"

End If

If b="100"

        Return a+"00"

End If

If Right(b,1)="0"

        b=Left(b,1)

        a=a+"0"

End If

If Len(b)=1

        Return ololo2(a,b)

End If



s1$=ololo2(a,Right(b,1))

s2$=ololo2(a+"0",Left(b,1))

Return ololo3(s2,s1)

End Function



Function ololo2$(a$,b$)

        d=Int(b)

        p=0

        lena=Len(a)

        s$=""

        For i=1 To lena

                c=Int(Mid(a,lena-i+1,1))*d+p

                p=c/10

                s=Str(c Mod 10)+s

        Next

        If p>0

                s=Str(p)+s

        End If

Return s

End Function



Function ololo3$(a$,b$)

p=0

s$=""

For i=1 To Len(a)

        If i>Len(b)

                d=0

        Else

                d=Int(Mid(b,Len(b)-i+1,1))

        End If

        c=Int(Mid(a,Len(a)-i+1,1))+d+p

        p=c/10

        s=Str(c Mod 10)+s

Next

If p>0

        s=Str(p)+s

End If

Return s

End Function

Ответ: Олимпиада по программированию

Цитата:

Радуйся

Не пойми меня неправильно. Я просто сказал это, что б увидеть, правильно ли ты понял сложность задач, что б обозвать олимпиаду детской.

Цитата:

Сообщение от h1dd3n (Сообщение 215178)

региональной олимпиаде для 10-11 классов задачи в 10 раз сложнее. И ты действительно считаешь что написать функцию "факториал" сложно?

Ну во первых эта олимпиада не регионального уровня. Перед тем как стать участником олимпиады за регион, нужно пройти еще 1-2 отбора. Так вот эта олимпиада, это 1-й отбор участников.

На счет того что написать функцию факториала сложно.

Цитата:

Но задачи 1 и 4, если они для тебя в первой(что для студентов часто бывает) достаточно сложны

Этим я имел ввиду, что я на 1-ю задачу (+ установку блица) убил половину времени что отводилось на олимпиаду. А за другую половину времени я успел написать еще всего 2 задачи. Из 6 задач я сделал 3. В то время как победитель сделал 5. Поэтому я считаю эти задачи достаточно сложными для олимпиады такого уровня. Я не знаю уровень вашего программирования, может вы гении мироздания которые поработят этот мир. Но мне было достаточно трудно решить эту задачу.

Кроме того, как бы это не было, изначально я написал именно этот вариант::-D

И кроме того!

Цитата:

На региональной олимпиаде для 10-11 классов задачи в 10 раз сложнее

Откуда такая точная инфа?

Ответ: Олимпиада по программированию

что-то я не знаю о факториали, или это вообще смешно:

Цитата:

Print n(3)
Function n:Int(in:Int)
Local l:Int=1
For i=1 To in
l=l*i
Next
Return l
End Function

Факториа́л числа n = произведение всех натуральных чисел до n включительно:

Какие Len, какие работы со стрингами в коде выше?!

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Данил (Сообщение 215201)

что-то я не знаю о факториали, или это вообще смешно:

Факториа́л числа n = произведение всех натуральных чисел до n включительно:

Какие Len, какие работы со стрингами в коде выше?!

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800 ...

Ответ: Олимпиада по программированию

Цитата:

Local s$
For i=1 To 10
If i<>1 Then s=s+" , "+n(i) Else s=s+n(i)
Next
Print s

Function n:Int(in:Int)
Local l:Int=1
For i=1 To in
l=l*i
Next
Return l
End Function

все. о_О
откуда там столько кода? (лень разбирать код)