Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Общие темы > Загадки

Загадки Постим и отгадываем загадки. Флуд запрещён - только условия и обсуждение решений.

Ответ
 
Опции темы
Старый 25.12.2011, 16:41   #16
Lowlet
ПроЭктировщик
 
Регистрация: 10.05.2011
Сообщений: 104
Написано 49 полезных сообщений
(для 170 пользователей)
Ответ: Олимпиада по программированию

Сообщение от Halk-DS Посмотреть сообщение
При этом нельзя использовать интернет и любые дополнительные материалы
Откуда ты взял Блиц?
(Offline)
 
Ответить с цитированием
Старый 25.12.2011, 16:46   #17
radiobutton
Бывалый
 
Регистрация: 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 пользователей)
Ответ: Олимпиада по программированию

Тебе же вроде бы сказали, что проверки на условия не нужны
Ну поставь ты за место
for i=0 to 10
=>
for i=0 to 100
не беда
все равно, откуда-то у тебя СТОЛЬКО кода.
(Offline)
 
Ответить с цитированием
Старый 25.12.2011, 17:06   #19
HolyDel
 
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений
(для 2,707 пользователей)
Ответ: Олимпиада по программированию

ну поставь. посмотри, что будет. вообще радиобатону респект, я бы так компактно не написал длинную арифметику
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо HolyDel за это полезное сообщение:
BlackDragon (29.12.2011), Hulk-DS (25.12.2011), radiobutton (25.12.2011)
Старый 25.12.2011, 17:30   #20
Данил
Модератор
 
Аватар для Данил
 
Регистрация: 11.07.2007
Сообщений: 2,910
Написано 686 полезных сообщений
(для 1,694 пользователей)
Ответ: Олимпиада по программированию

вот, сказал бы сразу, теперь понял в чем подъё....
после 31 не выводит.
(Offline)
 
Ответить с цитированием
Старый 25.12.2011, 18:55   #21
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 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)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Reks888 (25.12.2011)
Старый 25.12.2011, 19:29   #22
Halk-DS
Разработчик
 
Аватар для Halk-DS
 
Регистрация: 09.08.2006
Адрес: Украина
Сообщений: 431
Написано 65 полезных сообщений
(для 53 пользователей)
Ответ: Олимпиада по программированию

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

А вообще + к HolyDel. Я действительно когда все делал, писал в 2 раза больше кода.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Lowlet (25.12.2011)
Старый 25.12.2011, 20:49   #23
Halk-DS
Разработчик
 
Аватар для Halk-DS
 
Регистрация: 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
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений
(для 790 пользователей)
Ответ: Олимпиада по программированию

Если число N нечётное, то 3*N-тоже нечётное, то (3*N+1) - чётное, поэтому можно сразу найти (3*N+1)/2, но тогда надо счётчик повторений увеличить на два
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Hulk-DS (27.12.2011)
Старый 29.12.2011, 21:38   #25
genroelgvozo
Нуждающийся
 
Регистрация: 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
Tadeus
Троллота
 
Регистрация: 09.07.2007
Сообщений: 1,829
Написано 554 полезных сообщений
(для 1,772 пользователей)
Ответ: Олимпиада по программированию

Ох, видели б вы киевскую районную (голосеевский р-н)
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
Извиняюсь, что мне впадлу было переводить на русский, ну пусть хоть знающие мову поржут.
(Offline)
 
Ответить с цитированием
Эти 4 пользователя(ей) сказали Спасибо Tadeus за это полезное сообщение:
Dream (31.12.2011), Hulk-DS (06.01.2012), Lowlet (30.12.2011), Reks888 (30.12.2011)
Старый 06.01.2012, 05:33   #27
Halk-DS
Разработчик
 
Аватар для Halk-DS
 
Регистрация: 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 тысяч с копейками...

Ох, видели б вы киевскую районную
Первые три - ржач, вполне бы осилил.
Но в последней я даже смысл не понял
(Offline)
 
Ответить с цитированием
Старый 16.01.2012, 01:12   #28
Nerd
Чудо-кот
 
Аватар для Nerd
 
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений
(для 1,471 пользователей)
Ответ: Олимпиада по программированию


Небольшой хинт для тех, кому прийдётся работать в богомерзком Pascal ABC - компилятор считает себя умнее прогера, поэтому чтобы разделить два числа, нужно перед этим поставить условие, пресекающее деление на ноль(!).
Но, к сожалению, умнее пользователя компилятор не является, поэтому тупо, не дав скомпилиться, пишет "ошибка - неверная вещественная операция".
А ещё у него Insert работает не так, как в справке написано.
__________________


Последний раз редактировалось Nerd, 16.01.2012 в 02:30.
(Offline)
 
Ответить с цитированием
Старый 19.01.2012, 11:29   #29
bormotan
Оператор ЭВМ
 
Регистрация: 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
Nerd
Чудо-кот
 
Аватар для Nerd
 
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений
(для 1,471 пользователей)
Ответ: Олимпиада по программированию

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

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

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
А как ЭТО решить?
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


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


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com