![](images/chestnut/misc/left.gif) |
Загадки Постим и отгадываем загадки. Флуд запрещён - только условия и обсуждение решений. |
25.12.2011, 16:41
|
#16
|
ПроЭктировщик
Регистрация: 10.05.2011
Сообщений: 104
Написано 49 полезных сообщений (для 170 пользователей)
|
Ответ: Олимпиада по программированию
Сообщение от Halk-DS
При этом нельзя использовать интернет и любые дополнительные материалы
|
Откуда ты взял Блиц?
|
(Offline)
|
|
25.12.2011, 16:46
|
#17
|
Бывалый
Регистрация: 16.09.2011
Сообщений: 863
Написано 257 полезных сообщений (для 546 пользователей)
|
Ответ: Олимпиада по программированию
Сообщение от Данил
все. о_О
откуда там столько кода? (лень разбирать код)
|
Входное число N (0<=N<= 100).
|
(Offline)
|
|
25.12.2011, 16:53
|
#18
|
Модератор
Регистрация: 11.07.2007
Сообщений: 2,910
Написано 686 полезных сообщений (для 1,694 пользователей)
|
Ответ: Олимпиада по программированию
Тебе же вроде бы сказали, что проверки на условия не нужны ![:)](images/smilies/smile.gif)
Ну поставь ты за место
for i=0 to 10
=>
for i=0 to 100
не беда
все равно, откуда-то у тебя СТОЛЬКО кода.
|
(Offline)
|
|
25.12.2011, 17:06
|
#19
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Ответ: Олимпиада по программированию
ну поставь. посмотри, что будет. вообще радиобатону респект, я бы так компактно не написал длинную арифметику
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо HolyDel за это полезное сообщение:
|
|
25.12.2011, 17:30
|
#20
|
Модератор
Регистрация: 11.07.2007
Сообщений: 2,910
Написано 686 полезных сообщений (для 1,694 пользователей)
|
Ответ: Олимпиада по программированию
вот, сказал бы сразу, теперь понял в чем подъё.... ![:)](images/smilies/smile.gif)
после 31 не выводит.
|
(Offline)
|
|
25.12.2011, 18:55
|
#21
|
Мастер
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений (для 790 пользователей)
|
Ответ: Олимпиада по программированию
ИМХО
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]
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
25.12.2011, 19:29
|
#22
|
Разработчик
Регистрация: 09.08.2006
Адрес: Украина
Сообщений: 431
Написано 65 полезных сообщений (для 53 пользователей)
|
Ответ: Олимпиада по программированию
Сообщение от Lowlet
Откуда ты взял Блиц?
|
Это было договорено с преподавателем. Я ему объяснил ситуацию и он разрешил только скачать блиц. п.с. Пока я качал блиц я не видел заданий, поэтому не мог воспользоваться нетом для их решения.
А вообще + к HolyDel. Я действительно когда все делал, писал в 2 раза больше кода.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
25.12.2011, 20:49
|
#23
|
Разработчик
Регистрация: 09.08.2006
Адрес: Украина
Сообщений: 431
Написано 65 полезных сообщений (для 53 пользователей)
|
Ответ: Олимпиада по программированию
Сообщение от Igor
ИМХО
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. Я думал сделать эту функцию рекурсивной, но не рисковал тратить лишнее драгоценное время.
|
(Offline)
|
|
25.12.2011, 21:36
|
#24
|
Мастер
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений (для 790 пользователей)
|
Ответ: Олимпиада по программированию
Если число N нечётное, то 3*N-тоже нечётное, то (3*N+1) - чётное, поэтому можно сразу найти (3*N+1)/2, но тогда надо счётчик повторений увеличить на два
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
29.12.2011, 21:38
|
#25
|
Нуждающийся
Регистрация: 08.05.2008
Сообщений: 87
Написано 9 полезных сообщений (для 15 пользователей)
|
Ответ: Олимпиада по программированию
Тогда свою задачу предложу тут
Она по типу задачи про фишку только чуть сложнее
Есть n автобусных остановок и m автобусных маршрутов каждый из которых задается начальной остановкой Si и конечно Ti
Это все вводится в программу в таком порядке
n m
S1 T1
S2 T2
------
Sm Tm
Вася приходит на остановку №1
он может сесть в i-ый автобус на любой его остановке о от Si до Ti-1 , но выйти только на конечной. Надо вывести количество способов добраться до n-ой остановки.
__________________
|
(Offline)
|
|
29.12.2011, 23:03
|
#26
|
Троллота
Регистрация: 09.07.2007
Сообщений: 1,829
Написано 554 полезных сообщений (для 1,772 пользователей)
|
Ответ: Олимпиада по программированию
|
(Offline)
|
|
Эти 4 пользователя(ей) сказали Спасибо Tadeus за это полезное сообщение:
|
|
06.01.2012, 05:33
|
#27
|
Разработчик
Регистрация: 09.08.2006
Адрес: Украина
Сообщений: 431
Написано 65 полезных сообщений (для 53 пользователей)
|
Ответ: Олимпиада по программированию
Сообщение от genroelgvozo
Тогда свою задачу предложу тут
Она по типу задачи про фишку только чуть сложнее
Есть n автобусных остановок и m автобусных маршрутов каждый из которых задается начальной остановкой Si и конечно Ti
Это все вводится в программу в таком порядке
n m
S1 T1
S2 T2
------
Sm Tm
Вася приходит на остановку №1
он может сесть в i-ый автобус на любой его остановке о от Si до Ti-1 , но выйти только на конечной. Надо вывести количество способов добраться до n-ой остановки.
|
Задача как на меня - сложная. Если я не ошибаюсь в ней нужно знать хорошо комбинаторику и всякие формулы для комбинаций. Но я на этих уроках не был внимательным, поэтому сделал все через заднее место. (при помощи рекурсивной функции) Которая очень даже может быть неправильной. Я просто не знаю даже как проверить результат... Короче вот код:
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 тысяч с копейками...
Ох, видели б вы киевскую районную
|
Первые три - ржач, вполне бы осилил.
Но в последней я даже смысл не понял ![:)](images/smilies/smile.gif)
|
(Offline)
|
|
16.01.2012, 01:12
|
#28
|
Чудо-кот
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений (для 1,471 пользователей)
|
Ответ: Олимпиада по программированию
Небольшой хинт для тех, кому прийдётся работать в богомерзком Pascal ABC - компилятор считает себя умнее прогера, поэтому чтобы разделить два числа, нужно перед этим поставить условие, пресекающее деление на ноль(!).
Но, к сожалению, умнее пользователя компилятор не является, поэтому тупо, не дав скомпилиться, пишет "ошибка - неверная вещественная операция".
А ещё у него Insert работает не так, как в справке написано.
Последний раз редактировалось Nerd, 16.01.2012 в 02:30.
|
(Offline)
|
|
19.01.2012, 11:29
|
#29
|
Оператор ЭВМ
Регистрация: 12.10.2011
Адрес: Воронеж
Сообщений: 46
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Олимпиада по программированию
задачи чуть ли не из класса простейших бактерий. кроме 4 задачи в шапке темы. я её недопонял.
то есть если у меня число n=1243 , то нужно переставить цифру так чтобы оно было больше n , но минимальным из всех таких ( которые больше n ) чисел , которые можно составить из этого набора цифр ???? я вас правильно понял ??
если так , то вот нетрудный алгоритм , число ...a..b.. - буква , это цифра (при перестановке только двух цифр) ищем две цифры максимально близкие к концу , чтобы b>a, и переставляем их . если несколько цифр ( число ..a..b..c..d..) переставить , то ищем a<d , ищем перестановку , этих цифр дающую чуть большее значение из всех возможных (например dbca) . расставляем на исходные позиции цифры ..d..b..c..a..
простите что не в виде кода , а в словесном алгоритме. Сейчас мне влом перегонять в код
Последний раз редактировалось bormotan, 19.01.2012 в 17:57.
|
(Offline)
|
|
20.01.2012, 19:59
|
#30
|
Чудо-кот
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений (для 1,471 пользователей)
|
Ответ: Олимпиада по программированию
![](images/chestnut/misc/citation.gif)
Кольцевая автодорога
Имя входного файла:
road.in
Имя выходного файла:
road.out
Максимальное время работы на одном тесте:
2 секунды
Максимальный объем используемой памяти:
64 мегабайта
Максимальная оценка:
100 баллов
К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим еще в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.
В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от нее. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.
![](http://informat.name/inf_tasks/201014.gif)
Дирекция по строительству города Флэтбурга, ответственная за постройку кольцевой автодороги, решила привлечь передовых программистов для выбора оптимального плана постройки дороги.
Требуется написать программу, которая вычислит число возможных планов постройки кольцевой автомобильной дороги с соблюдением указанных требований и найдет такой план, для которого длина дороги будет минимальной.
Формат входных данных
Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: 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
|
А как ЭТО решить?
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 05:08.
|