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 (Сообщение 215171)

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

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

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

Цитата:

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

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

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

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

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

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

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

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

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

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

ИМХО

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]

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

Цитата:

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

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

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

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

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

Цитата:

Сообщение от 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. Я думал сделать эту функцию рекурсивной, но не рисковал тратить лишнее драгоценное время.

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

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

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

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

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

Ох, видели б вы киевскую районную (голосеевский р-н)
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
Извиняюсь, что мне впадлу было переводить на русский, ну пусть хоть знающие мову поржут.

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

Цитата:

Сообщение от 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 тысяч с копейками...

Цитата:

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

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

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

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

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

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

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

Цитата:

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

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

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

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