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)

Halk-DS

24.12.2011 22:28

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

Проснулся вчера утром от звонка моего друга. Он зная меня, сказал что у нас олимпиада по программированию. На олимпиаде были в приоритете 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"...

radiobutton

25.12.2011 00:24

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

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

Reks888

25.12.2011 00:36

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

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

Nerd	25.12.2011 00:57

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

Поссоны!

Код:

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

Фишка.

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

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

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

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

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

1,1,1

1,2

2,1

Ответ: 3.

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

FireOwl

25.12.2011 01:40

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

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

radiobutton

25.12.2011 01:51

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

Цитата:

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

Поссоны!

Код:

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

Фишка.

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

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

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

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

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

1,1,1

1,2

2,1

Ответ: 3.

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

Reks888

25.12.2011 01:57

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

Цитата:

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

Поссоны!

Код:

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

Фишка.

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

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

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

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

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

1,1,1

1,2

2,1

Ответ: 3.

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

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

Halk-DS

25.12.2011 04:51

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

Цитата:

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

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

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

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

Данил

25.12.2011 09:49

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

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

h1dd3n

25.12.2011 10:44

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

Цитата:

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

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

radiobutton

25.12.2011 11:31

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

Цитата:

Сообщение от 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

Halk-DS

25.12.2011 15:02

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

Цитата:

Радуйся

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

Цитата:

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

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

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

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

Цитата:

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

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

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

И кроме того!

Цитата:

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

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

Данил

25.12.2011 15:34

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

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

Цитата:

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, какие работы со стрингами в коде выше?!

radiobutton

25.12.2011 15:48

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

Цитата:

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

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

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

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

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

Данил

25.12.2011 16:33

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

Цитата:

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

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

Lowlet

25.12.2011 16:41

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

Цитата:

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

При этом нельзя использовать интернет и любые дополнительные материалы

Откуда ты взял Блиц?

radiobutton

25.12.2011 16:46

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

Цитата:

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

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

Входное число N (0<=N<=100).

Данил

25.12.2011 16:53

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

Тебе же вроде бы сказали, что проверки на условия не нужны :)
Ну поставь ты за место
for i=0 to 10
=>
for i=0 to 100
не беда :)
все равно, откуда-то у тебя СТОЛЬКО кода.

HolyDel

25.12.2011 17:06

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

ну поставь. посмотри, что будет. вообще радиобатону респект, я бы так компактно не написал длинную арифметику

Данил

25.12.2011 17:30

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

вот, сказал бы сразу, теперь понял в чем подъё.... :)
после 31 не выводит.

Igor	25.12.2011 18:55

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

ИМХО

1)написать функцию, перемножающие числа в виде строк.+ с её помощью считать факториал.
2)в чём подвох? В нереально большой матрице? Вроде всё просто
3)

Цитата:

Если число N- парное, то делить его на два. (N=N/2)
Если число N- не парное, то умножать его на три и +1 (N=N*3+1)

маленькая оптимизация:
парное - делить на два
непарное - N:=((n*3+1) div 2)
вроде ничего сложного. Опять же, возможно очень плохое большое N, придётся взять из первой задачи функцию умножения числа (представленного строкой из цифр), добавить деление на 2 и прибавление единицы)
4) хз как
5) вроде ничего трудного
Кстати да, я в паре олимпиад участвовал - проверять то что вводится на правильность не надо. Но обычно задачи располагаются в порядке возрастания сложности - а тут хз как. Первый тип задач - тупо математика, комбинаторика. Второй тип- делается упор на скорость выполнения - не более двух секунд, и за правильное решение задачи можно потерять баллы потому что программа не успевает посчитать какой-нибудь трудный случай.
Схема проверки - есть тесты с вопросами и тем, что должна выдать программа. За каждый правильные ответ дают баллы. Суть: если непонятно как решать, можно написать для какого-нибудь частного, вырожденного случая (а они в тестах тоже проверяются) и получить немножко баллов. Код никто не смотрит, рассматривается только результат работы программы. Если ответ рандомный, то жюри считает его неправильным

Цитата:

Задача 2. (30 баллов) Фишка. Фишка может двигаться только вперед по полю длины N. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца. Пример. N=3, K=2 Возможные пути: 1,1,1 1,2 2,1 Ответ: 3.

количество способов попасть на клетку N = сумма способов попасть на n-1, n-2, .. n-k.
var x:array [-k..N] of integer;
x[1]:=1;
for i:=1 to N do
for j:=1 to k do
x[i]:=x[i]+x[i-j];
ответ - x[n]

Halk-DS

25.12.2011 19:29

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

Цитата:

Сообщение от Lowlet (Сообщение 215213)

Откуда ты взял Блиц?

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

А вообще + к HolyDel. Я действительно когда все делал, писал в 2 раза больше кода.

Halk-DS

25.12.2011 20:49

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

Цитата:

Сообщение от Igor (Сообщение 215225)

ИМХО
2)в чём подвох? В нереально большой матрице? Вроде всё просто
3)маленькая оптимизация:
парное - делить на два
непарное - N:=((n*3+1) div 2)
вроде ничего сложного. Опять же, возможно очень плохое большое N, придётся взять из первой задачи функцию умножения числа (представленного строкой из цифр), добавить деление на 2 и прибавление единицы)
5) вроде ничего трудного

2) Действительно подвога нет. Во всяком случае я не нашел. Задача предельно проста.
3) Не уверен правильно ли я тебя понял, я выложу свой вариант:

Код:

Function Formula(N)

Local Interations%

.start

If Not (N Mod 2) N=N/2 Else N=N*3+1

Interations=Interations+1

If N=1 Return Interations Else Goto start

End Function

Ну я не знаю подвох ли это, но прогер студент при виде этой задачи должен не понять как так N=N*3+1 и из этого в конце выйдет единица.
пс. Функция по идее должна стремится к бесконечности. Но в итоге она превращается в единицу.
В качестве примера почему то руководитель ввел число 5000000. И когда вышел ответ 144 он сказал правильно...
п.с.2. Я думал сделать эту функцию рекурсивной, но не рисковал тратить лишнее драгоценное время.

Igor	25.12.2011 21:36

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

Если число N нечётное, то 3*N-тоже нечётное, то (3*N+1) - чётное, поэтому можно сразу найти (3*N+1)/2, но тогда надо счётчик повторений увеличить на два

genroelgvozo

29.12.2011 21:38

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

Тогда свою задачу предложу тут
Она по типу задачи про фишку только чуть сложнее
Есть n автобусных остановок и m автобусных маршрутов каждый из которых задается начальной остановкой Si и конечно Ti
Это все вводится в программу в таком порядке
n m
S1 T1
S2 T2
------
Sm Tm
Вася приходит на остановку №1
он может сесть в i-ый автобус на любой его остановке о от Si до Ti-1 , но выйти только на конечной. Надо вывести количество способов добраться до n-ой остановки.

Tadeus

29.12.2011 23:03

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

Ох, видели б вы киевскую районную (голосеевский р-н)
http://cs9505.vkontakte.ru/u8747076/-3/w_74408c57.jpg
http://cs9505.vkontakte.ru/u8747076/-3/w_aa82ad4e.jpg
http://cs9505.vkontakte.ru/u8747076/-3/z_5b6cbca3.jpg
http://cs9505.vkontakte.ru/u8747076/-3/z_8f06195d.jpg
Извиняюсь, что мне впадлу было переводить на русский, ну пусть хоть знающие мову поржут.

Halk-DS

06.01.2012 05:33

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

Цитата:

Сообщение от genroelgvozo (Сообщение 215704)

Задача как на меня - сложная. Если я не ошибаюсь в ней нужно знать хорошо комбинаторику и всякие формулы для комбинаций. Но я на этих уроках не был внимательным, поэтому сделал все через заднее место. (при помощи рекурсивной функции) Которая очень даже может быть неправильной. Я просто не знаю даже как проверить результат... Короче вот код:

Код:

Graphics 800,600,32,2

SetBuffer BackBuffer()



Global Time=MilliSecs()

Global Ansver=Funk(5,2)

Time=(MilliSecs()-time)*.001

Dim S(1)

Dim T(1)



Repeat

Cls

Text 10,10,"Operation time: "+Time

Text 10,20,Ansver

Flip

If KeyHit(1) End

Forever



Function Funk(N,M)

Local Ansver=0

Dim S(M)

Dim T(M)

For I=1 To M

S(I)=Rand(1,N-2)

T(I)=Rand(S(I)+1,N)

Next

For J=1 To m

If S(J)=1 Ansver=Ansver+Check(1,J,M,N)

Next

Return Ansver

End Function



Function Check(N,I,M_Max,N_Last)

Local Ansver

For X=N To T(I)

If N=N_Last Return 1

For Y=1 To M_Max

If X>=S(Y) And X<T(Y) Ansver=Ansver+Check(X+1,Y,M_Max,N_Last)

Next

Next

Return Ansver

End Function

Я проверял на варианте:
N=5
M=2
S1=2 T1=5
S2=1 T2=3
Ответ програмы - 8
Посчитал вручную - 8
Но все равно не уверен что правильно.
Кстати запустил вариант
N=10
M=15
Программа думала 104 секунды и выдала результат в 29 тысяч с копейками...

Цитата:

Ох, видели б вы киевскую районную

Первые три - ржач, вполне бы осилил.
Но в последней я даже смысл не понял :)

Nerd	16.01.2012 01:12

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

bormotan

19.01.2012 11:29

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

задачи чуть ли не из класса простейших бактерий. кроме 4 задачи в шапке темы. я её недопонял.
то есть если у меня число n=1243 , то нужно переставить цифру так чтобы оно было больше n , но минимальным из всех таких ( которые больше n ) чисел , которые можно составить из этого набора цифр ???? я вас правильно понял ??

если так , то вот нетрудный алгоритм , число ...a..b.. - буква , это цифра (при перестановке только двух цифр) ищем две цифры максимально близкие к концу , чтобы b>a, и переставляем их . если несколько цифр ( число ..a..b..c..d..) переставить , то ищем a<d , ищем перестановку , этих цифр дающую чуть большее значение из всех возможных (например dbca) . расставляем на исходные позиции цифры ..d..b..c..a..

простите что не в виде кода , а в словесном алгоритме. Сейчас мне влом перегонять в код

Nerd	20.01.2012 19:59

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

Цитата:

Кольцевая автодорога

Имя входного файла:

road.in

Имя выходного файла:

road.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

Максимальная оценка:

100 баллов

К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим еще в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.

В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от нее. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.

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

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

Формат входных данных

Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: xi и yi — координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая — вторую, третья — третью, четвертая — четвертую. Никакие две достопримечательности не находятся в одной точке.

Все числа во входном файле не превосходят 100 по абсолютной величине.

Формат выходных данных

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

На второй строке требуется вывести координаты центра дороги минимальной длины и ее радиус. Если существует несколько разных способов построить дорогу минимальной длины, необходимо вывести любой из них. Координаты центра и радиус дороги должны быть выведены с точностью не хуже 10-5.

Пример входных и выходных данных

road.in||road.out
0 0|||||7
0 1|||||1.5 0.5 1.4412281
1 0
2 2

road.in|||road.out
0 0|||||||Infinity
0 1|||||||0.5 0.5 0
1 0
1 1

А как ЭТО решить?

Igor	20.01.2012 20:17

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

Идеи:
1) Круг неспроста. Пусть x,y-координаты середины кольца с радиусом R. Тогда для любой точки S=sqrt((X-Xточки)^2+(Y-Yточки)^2), модуль разности |S-R| должен быть одинаковым для всех точек-тогда мы решили задачу.
2) Если через эти четыре точки можно провести окружность, то ответ - Infinity, координаты центра окружности и радиус=0
В пункте 2 мы исключили варианты, когда все точки либо снаружи либо внутри.
3) Возможный вариант: Три точки лежат снаружи (или 3 внутри), а четвёртая - с другой стороны от дороги.
Берём три точки, ищем центр проходящей через них окружности, (радиус Ra), расстояние от центра до четвёртой точки Rb, возможный вариант решения (R=(Ra+Rb)/2)
смотрим для всех вариантов троек (их 4) и выбираем наименьший R
4) Последний вариант - две точки снаружи и две внутри. Пусть у нас две пары (1 и 2) и (3 и 4). проводим прямую равноудалённую от 1 и 2 (между ними), и прямую, равноудалённую от 3 и 4. Пересечение прямых - центр окружности. R=среднее арифметическое расстояний от центра до т. 1 и до т. 3
Для всех вариантов пар точек ищем наименьший R.
5) Ответ- вариант с наименьшим R из пунктов 3 и 4 если не прокатило со вторым

Igor	23.01.2012 21:05

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

Вложений: 8

Московская область, олимпиада. Ограничение по времени - 2 секунды на тест, занимать не более 256 мб оперативки.
1,2,5 задач нет потому что они простые

Задача 3. Имя входного файла xml.in, выходного- xml.out. Есть xml строка типа такой: "<a><ab></ab><c></c></a>" Длина - до 1000 символов. (строчные латинские буквы, <, > и /). Один символ поменялся((( Выходной файл должен содержать корректную xml строку, которая получается путем замены одного символа на другой в исходной строке. Если вариантов ответа несколько, подойдёт любой.

О самой олимпиаде: Проводилось два тура. Задачи (1-4) и (5-8), каждый тур 5 часов. Литературой пользоваться нельзя, программировать можно на паскале, делфи, си++, питоне, джаве. Какой-то парень писал на бейсике, но официально так делать нельзя.
Всё очень хитро. Каждому даётся бумажка с фамилией, паролем и логином. По ним логинишься на сервере олимпиады. всё по-честному, олимпиада у всех начинается одновременно и заканчивается тоже. Пароль заранее неизвестен, условие задач тоже. Тем не менее участники олимпиады сидят в одном здании.(точнее, в двух, но разницы никакой) Доступ в интернет вроде закрыт, хотя я не проверял. Код отправляется на сервер с указанием компилятора, на сервере компилируется и выполняется, проверка заданий автоматизирована. На компе тоже есть компилятор, можно писать и тестировать, но отсылается только код. Есть пара тестовых вариантов проверки (они в примерах к задачам)- если программа на них адекватно реагирует то принимается на проверку, и где-то через день можно узнать свои результаты.

задачи лень переписывать, выкладываю фотки.

h1dd3n

23.01.2012 21:19

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

Цитата:

Сообщение от Igor (Сообщение 217585)

Это вам так на разборе задач сказали?

Igor	23.01.2012 21:32

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

Цитата:

Это вам так на разборе задач сказали?

да.
Но я решал по-другому, (300 строчек кода набежало), получил 85 баллов из 100. Я искал символ, в котором ошибка, потом исправлял... пару нехороших случаев исправлять не научился, но тем не менее заработал много баллов)

h1dd3n

23.01.2012 21:36

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

Цитата:

Сообщение от Igor (Сообщение 217588)

Это и есть "правильный" способ. Неправильный символ либо тот который "неожидался", либо предыдущий, вот и весь перебор.

Igor	23.01.2012 22:02

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

далеко не всегда. вот например
<a></a><ab></x><x><sab>

P.S. Увидел результаты. Пичаль. Провалил второй тур - во второй задаче получил бы 100 баллов а не 4 если бы не перепутал m и n в ответе, за третью получил только 18 баллов(( Знал бы решил для частного случая за десять минут и получил бы 40 баллов(((. За четвёртую 30 - знал как решить на 100, но не успел

h1dd3n

23.01.2012 22:54

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

Цитата:

Сообщение от Igor (Сообщение 217594)

далеко не всегда. вот например
<a></a><ab></x><x><sab>

А какой правильный вариант то?

Igor	23.01.2012 23:01

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

<a></a><ab></x><x><sab>
<a></a><ab></x><x></ab>
ой. я </x> и <x> перепутал
копипастю самые сложные тесты

Nerd	25.01.2012 14:16

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

Цитата:

Литературой пользоваться нельзя, программировать можно на паскале, делфи, си++, питоне, джаве.

А по Краснодарскому краю одобрили только cpр и паскаль.

Цитата:

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

А у нас всё просто - нате комп, нате компилятор, нате 5 часов.
---
Да ну блин... Каким образом решение 8 задачи (которая про супрефиксы) могло пройти только 6 тестов из 20,
если входные данные по условию имеют одинкавую структуру - оно либо ни один не пройдёт, либо пройдёт все.
6 тестов мне пририсовали не сразу - на предварительных результатах было по нулям, это показалось мне странным, потому пошёл на апелляцию (и пририсовали уже потом, без моего присутствия).
Там же я узнал, что каким-то волшебным образом в обоих турах все мои решения, кроме первой задачи у проверяющих вылетали на всех тестах, хотя у меня работали с разными инпутами (т.е. хоть часть тестов должны были пройти).
Это... как объяснить? (кроме того, что я криворукий мудак =D)

Igor	25.01.2012 21:23

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

хз. В городской олимпиаде можно было прийти и посмотреть, как проверяют работу. Я этой возможностью всегда пользовался - сразу узнавал баллы и вообще на душе спокойней было. У нас на области можно посмотреть результаты работы тестирующей системы - все тесты, ввод, вывод программы, время выполнения и свой код. Сами тесты я условно разбиваю на три типа -
1)простейшие (маленькие числа, к производительности никаких требований), 2)частные и крайние случаи - (в них можно потерять баллы),
3)маньяческие тесты на быстродействие. Иногда совсем непонятно как получить максимум баллов.
В 8 задаче получил 30 баллов - не успел сделать сортировку - для остальных 70 баллов нужна оптимизация

Matt Merkulov

26.01.2012 11:49

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

Код:

import java.math.BigInteger;



public class CFactorial {

        public static void main( String[] args ) {

                System.out.println( Factorial( BigInteger.valueOf( 100 ) ).toString() );

        }

        

        private static BigInteger Factorial( BigInteger N ) {

                if( N.equals( BigInteger.ONE ) ) return BigInteger.ONE; else return N.multiply( Factorial( N.subtract( BigInteger.ONE ) ) );

        }

}

Вот, кстати, вам еще задача:
Даны два дробных числа, представленные 8-байтовым значением типа long следующим образом: старшие 4 байта - это целая часть, младшие - дробная. Т. е. это число "поделено" на 0x100000000. Реализовать сложение и вычитание просто, но попробуйте реализовать умножение, деление и вывод на экран не прибегая к другим типам данных.

Matt Merkulov

31.01.2012 15:24

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

Оказывается более расширенная задача такого типа довольно часто возникает при программировании микроконтроллеров, бизнес- и математических систем: http://habrahabr.ru/blogs/programming/131171/

shybovycha

08.02.2012 01:19

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

Раньше трава была зеленее олимпиады были сложнее и интереснее =)

Gogich

10.08.2012 23:14

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

Цитата:

Сообщение от Igor (Сообщение 217585)

Московская область, олимпиада. Ограничение по времени - 2 секунды на тест, занимать не более 256 мб оперативки.
1,2,5 задач нет потому что они простые

Хах, классно. Я тоже их решал, но я с Ростова)

У нас была ситуация другая: c++, c, pascal, python. Вроде был еще один чувак на VB, но я не уверен. Были несколько восьмиклассников, но в основном в первые места прошли 11 классы.

Задачи интересные, но местами туповатые. Тесты отправляются на сервер (к админу локальной сети), проводилась олимпиада в ЮФУ Мехмата.

Кстати уже PDF файлы появились..

Nerd	06.12.2012 16:22

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

Вложений: 1

hm? o_O
Решал подбором наугад, а есть ли нормальный алгоритм?

SBJoker

06.12.2012 17:27

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

Элементарно,

если человечек желает познакомится с числом превышающим общее число участников минус один то наш ответ НЕТ.

Решать можно как последовательно так и поэтапно.

Например:
1 - отсортировать список по убыванию
2 - проверить первую запись возможно ли это выполнить если нет, то сразу отвечаем NO и завершаемся.
3 - если всё отлично, то на этом этапе знакомим чувачка со всеми кто в списке ниже его до тех пор пока непознакомим с необходим числом учасников, или достигнем конца списка, тогда снова начинаем просматривать список с начала.

3(2) другой вариант шага 3: создаем временный список из всех элементов основного списка кроме элемента рассматриваемого заказчика знакомств. далее случайным выбором выбирает элемент из списка, знакомим, увеличиваем счетчик, удаляем из списка этот элемент. продолжаем пока непознакомим с требуемым числом.

Nikich

11.07.2013 16:10

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

http://forum.boolean.name/showpost.p...0&postcount=30
Кто-нибудь знает, как решается данная задача?
Данное описание довольно полезно, однако непонятно, как узнать координаты центра окружности? Не перебирать же все варианты, точность 10^-5 вряд ли это позволит.

dsd	12.07.2013 00:52

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

Цитата:

Сообщение от Nikich (Сообщение 263222)

Ну выбираем три точки, смотрим не лежат ли они на одной прямой, ибо тогда провести окружность через них невозможно.
Потом к любым двум линиям соединяющим точки в середине отрезка ищем уравнения прямых перпендикулярных отрезку, ищем точку пересечения этих двух прямых. Это центр окружности. Считаем расстояние от центра до любой из трех точек, это радиус. Считаем растояние от центра до 4-й точки, вычитаем из получившегося значения радиус, делим на два. Это то значение на которое нужно изменить величину радиуса окружности с найденным раньше центром.

Повторяем для все возможных вариантов выбора трех точек из четырех.

Так как через три точки можно провести только одну окружность то по идее в итоге будут перебраны все варианты.

зы. я походу ошибся, как то слишком простая задача для олимпиады.

radiobutton

12.07.2013 02:06

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

есть у кого с последней олимпиады список заданий на русском?

выложите самое трудное если не трудно.

EvilOkta

15.07.2013 19:45

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

вспомнил случай, который был на олимпиаде классе в седьмом (давнооооо).
Задача тривиальная, реализация - QBasic.
Условие (дословно не помню):
Реализовать перемещение точки внутри прямоугольника с размерами n x m. под любым из углов, кратным 45 градусов (задается цифрой от 0 до 7), с отскакиванием от стенки по закону угла падения/отражения
Входные условия -
n,m, x,y (стартовые координаты точки), стартовый угол

Задачку решил быстро, точка бодро скачет в прямоугольнике. После прохождения олимпиады препод в шутку сказал оставшимся ученикам - а слабо сделать реализацию отскока точки не в прямоугольнике, а в сфере и чтобы стартовый угол можно было задать произвольно на 360 градусов?
Над этой задачей бились до вечера и так и не решили. До сих пор мечтаю увидеть реализацию на QBasic.

SBJoker

15.07.2013 20:00

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

Цитата:

Для удобства окружность в нулях, радиус - r
Перемещение точки:
x = x + cos(arc) * speed
y = y + sin(arc) * speed

если x^2 + y^2 > r^2, мы столкнулись с окружностью,
перпендикуляр к окружности = atan(y, x)
угол падения = перпендикуляр к окружности - arc
угол отражения = перпендикуляр к окружности - 180 + угол падения
arc = угол отражения

примерно так, конечно операции с углами должны правильно обрабатывать отрицательные углы, и углы превышающие 360 градусов

Nikich

11.09.2013 00:37

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

Цитата:

У Сени есть шоколадка, составленная из нескольких прилегающих друг к другу плиточек в форме правильных треугольников. Его брат Женя нашел эту шоколадку и решил сделать ее треугольной, съев все лишнее (ведь треугольные шоколадки намного вкуснее). Сколькими способами он может это сделать?

Например, из такой шоколадки:

можно сделать треугольную шоколадку со стороной 1 шестью способами или шоколадку со стороной 2 двумя способами. Итого восемь способов.

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

Форма шоколадки задается ее границей в порядке обхода по часовой стрелке. Первая строка входного файла INPUT.TXT содержит число n - количество отрезков на границе (1 ≤ n ≤ 5000). Далее n чисел от 1 до 6, задающих направление движения по границе (см. рисунок).

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

В выходной файл OUTPUT.TXT выведите одно число - количество способов.

Можете помочь с данной задачей? Скорее всего, есть сугубо математическое решение, так как лучшее решение данной задачи в 121 символ на C++.

Nikich

12.11.2013 22:34

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

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K–1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A1 рублей. Те, у кого совпали первые две цифры числа — получают A2 рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A3 рублей. И так далее. Угадавшие все число полностью получают AM рублей. При этом если игрок угадал t первых цифр, то он получает At рублей, но не получает призы за угадывание t–1, t–2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

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

В первой строке входного файла INPUT.TXT задаются числа N (количество телезрителей, сделавших свои ставки, 1<=N<=100000), M (длина чисел 1<=M<=10) и K (основание системы счисления 2<=K<=10). В следующей строке записаны M чисел A1, A2, …, AM, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1<=A1<=A2<=…<=AM<=100000). В каждой из следующих N строк либо в одной строке через пробел записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

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

В выходной файл OUTPUT.TXT выведите наименьшую сумму, которую придется выплатить в качестве выигрыша

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

Nikich

22.11.2013 18:14

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

Допилил таки. Оказалось, что беда была с vector, а именно с его медлительностью.
Итоговый код(как говорилось ранее, требуется самое короткое решение):

Код:

#include <fstream>



using namespace std;



typedef long long x;

x N,M,K,j,I,A[11];



char p[2<<17][10];



x z(x i, x l, x r)

{

x m=x(2)<<35,t;

if (i>=M || l>=r)

m=0;

else

{

x L=l,R;

for (x c=48;c<K;c++)

{

for (R=L;R<r && p[R][i]==c; R++)

;

if (t=z(i+1,L,R), t<m)

m=t;

L=R;

}

}

return m+A[i]*(r-l);

}



int main()

{

fstream i("input.txt"),o("output.txt");

i>>N>>M>>K;

K+=48;

for (;I<M;I++)

i>>A[I+1];

for (;I>1;I--)

A[i]-=A[I-1];

for (;j<N;j++)

i>>p[j];

o<<z(0,0,N);

}

genroelgvozo

15.12.2013 23:46

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

Nikich

16.12.2013 01:51

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

Слишком дорогое удовольствие, такое длинное название.
P.S. пишите "X", чтобы выиграть.

genroelgvozo

16.12.2013 16:58

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

Цитата:

Сообщение от Nikich (Сообщение 271490)

Слишком дорогое удовольствие, такое длинное название.
P.S. пишите "X", чтобы выиграть.

нифига. в скорости написания программы lld пишется также быстро, думаю разницы во времени общем не заметишь, потому что дольше думаешь над какими то алгоритмическими моментами, это раз. но зато сокращается время дебага, когда смотришь на сложный алгоритм (лично на олимпиаде такие писали, где было много всего) и хрен поймешь че это такое. тем более занимать букву x тоже неудобно, под нее обычно координаты в геом. задачах. По поводу разбора после написания, сам убедился на acm, что надо называется пусть и коротко но более понятно)

Nikich

16.12.2013 17:18

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

Код:

Итоговый код(как говорилось ранее, требуется самое короткое решение)

Какое быстро?

genroelgvozo

16.12.2013 21:11

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

Там у кого код меньше по количеству букв, тот и выиграл?? это че за олимпиада? во всех которых участвовал, рейтинг по количеству задач, плюс по штрафному времени (время сдачи задачи и штрафные очки за провальные попытки) там играет роль в быстроте набора программы, но о чем я уже сказал здесь x или lld не сыграет роли. Конечно если важен размер текста программы, но я честно удивлен что так могли придумать... Важно насколько программа быстро работает (это кстати тоже во всех олимпиадах есть ограничения для каждой задачи) ну это мое мнение. раз надо было так, то беру слова назад.

Nikich

17.12.2013 00:35

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

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

genroelgvozo

17.12.2013 21:07

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

На всех тех где участвовал (а я думаю acm это почти что стандарт олимпиадного проганья) побеждает тот у кого меньше штрафное время (время сдачи задачи + штрафные попытки) и это по мне логично, чем быстрее ты додумался и написал, и как можно меньше ошибок совершил то и лучше ты значит. а не сидеть и думать как же мне еще на символ программу укоротить)

Часовой пояс GMT +4, время: 11:40.