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

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

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

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

Ответ
 
Опции темы
Старый 06.12.2012, 17:27   #46
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Олимпиада по программированию

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

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

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

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

3(2) другой вариант шага 3: создаем временный список из всех элементов основного списка кроме элемента рассматриваемого заказчика знакомств. далее случайным выбором выбирает элемент из списка, знакомим, увеличиваем счетчик, удаляем из списка этот элемент. продолжаем пока непознакомим с требуемым числом.
__________________
(Offline)
 
Ответить с цитированием
Старый 11.07.2013, 16:10   #47
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

http://forum.boolean.name/showpost.p...0&postcount=30
Кто-нибудь знает, как решается данная задача?
Данное описание довольно полезно, однако непонятно, как узнать координаты центра окружности? Не перебирать же все варианты, точность 10^-5 вряд ли это позволит.
(Offline)
 
Ответить с цитированием
Старый 12.07.2013, 00:52   #48
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Олимпиада по программированию

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

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

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

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

зы. я походу ошибся, как то слишком простая задача для олимпиады.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Nikich (12.07.2013)
Старый 12.07.2013, 02:06   #49
radiobutton
Бывалый
 
Регистрация: 16.09.2011
Сообщений: 863
Написано 257 полезных сообщений
(для 546 пользователей)
Ответ: Олимпиада по программированию

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

выложите самое трудное если не трудно.
(Offline)
 
Ответить с цитированием
Старый 15.07.2013, 19:45   #50
EvilOkta
Знающий
 
Аватар для EvilOkta
 
Регистрация: 31.07.2008
Сообщений: 321
Написано 108 полезных сообщений
(для 229 пользователей)
Ответ: Олимпиада по программированию

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

Задачку решил быстро, точка бодро скачет в прямоугольнике. После прохождения олимпиады препод в шутку сказал оставшимся ученикам - а слабо сделать реализацию отскока точки не в прямоугольнике, а в сфере и чтобы стартовый угол можно было задать произвольно на 360 градусов?
Над этой задачей бились до вечера и так и не решили. До сих пор мечтаю увидеть реализацию на QBasic.
__________________
Области Хаоса - мой новый Youtube проект
(Offline)
 
Ответить с цитированием
Старый 15.07.2013, 20:00   #51
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Олимпиада по программированию

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

если x^2 + y^2 > r^2, мы столкнулись с окружностью,
перпендикуляр к окружности = atan(y, x)
угол падения = перпендикуляр к окружности - arc
угол отражения = перпендикуляр к окружности - 180 + угол падения
arc = угол отражения
примерно так, конечно операции с углами должны правильно обрабатывать отрицательные углы, и углы превышающие 360 градусов
__________________
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
EvilOkta (16.07.2013)
Старый 11.09.2013, 00:37   #52
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

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

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

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

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



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

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

В выходной файл OUTPUT.TXT выведите одно число - количество способов.
Можете помочь с данной задачей? Скорее всего, есть сугубо математическое решение, так как лучшее решение данной задачи в 121 символ на C++.
(Offline)
 
Ответить с цитированием
Старый 12.11.2013, 22:34   #53
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо 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 выведите наименьшую сумму, которую придется выплатить в качестве выигрыша


есть идеи? на ум приходит только обычное дерево, что вряд ли выдержит по скорости.
(Offline)
 
Ответить с цитированием
Старый 22.11.2013, 18:14   #54
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

Допилил таки. Оказалось, что беда была с 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);
}
(Offline)
 
Ответить с цитированием
Старый 15.12.2013, 23:46   #55
genroelgvozo
Нуждающийся
 
Регистрация: 08.05.2008
Сообщений: 87
Написано 9 полезных сообщений
(для 15 пользователей)
Ответ: Олимпиада по программированию

Сообщение от Nikich Посмотреть сообщение
Допилил таки. Оказалось, что беда была с 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);
}
Обозначать тип за букву x, это жесть . Хотя бы lli, более понятное и используемое сокращение для long long int. хотя дело вкуса. но я ужаснулся взглянув на код))
__________________
(Offline)
 
Ответить с цитированием
Старый 16.12.2013, 01:51   #56
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

Слишком дорогое удовольствие, такое длинное название.
P.S. пишите "X", чтобы выиграть.
(Offline)
 
Ответить с цитированием
Старый 16.12.2013, 16:58   #57
genroelgvozo
Нуждающийся
 
Регистрация: 08.05.2008
Сообщений: 87
Написано 9 полезных сообщений
(для 15 пользователей)
Ответ: Олимпиада по программированию

Сообщение от Nikich Посмотреть сообщение
Слишком дорогое удовольствие, такое длинное название.
P.S. пишите "X", чтобы выиграть.
нифига. в скорости написания программы lld пишется также быстро, думаю разницы во времени общем не заметишь, потому что дольше думаешь над какими то алгоритмическими моментами, это раз. но зато сокращается время дебага, когда смотришь на сложный алгоритм (лично на олимпиаде такие писали, где было много всего) и хрен поймешь че это такое. тем более занимать букву x тоже неудобно, под нее обычно координаты в геом. задачах. По поводу разбора после написания, сам убедился на acm, что надо называется пусть и коротко но более понятно)
__________________
(Offline)
 
Ответить с цитированием
Старый 16.12.2013, 17:18   #58
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

Итоговый код(как говорилось ранее, требуется самое короткое решение)
Какое быстро?
(Offline)
 
Ответить с цитированием
Старый 16.12.2013, 21:11   #59
genroelgvozo
Нуждающийся
 
Регистрация: 08.05.2008
Сообщений: 87
Написано 9 полезных сообщений
(для 15 пользователей)
Ответ: Олимпиада по программированию

Там у кого код меньше по количеству букв, тот и выиграл?? это че за олимпиада? во всех которых участвовал, рейтинг по количеству задач, плюс по штрафному времени (время сдачи задачи и штрафные очки за провальные попытки) там играет роль в быстроте набора программы, но о чем я уже сказал здесь x или lld не сыграет роли. Конечно если важен размер текста программы, но я честно удивлен что так могли придумать... Важно насколько программа быстро работает (это кстати тоже во всех олимпиадах есть ограничения для каждой задачи) ну это мое мнение. раз надо было так, то беру слова назад.
__________________
(Offline)
 
Ответить с цитированием
Старый 17.12.2013, 00:35   #60
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Олимпиада по программированию

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


Опции темы

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

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


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


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