forum.boolean.name
Страница 4 из 5 < 123 4 5 >
Показывать 64 сообщений этой темы на одной странице

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)

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

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

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
Ответ: Олимпиада по программированию
 
Время тоже учитывается. Просто суть в том, что время зависит от используемого алгоритма, поэтому, в идеале, у всех с одной и той же идеей должно быть одно и то же время. Поэтому и оценивают по кол-ву символов. Если прошло лимит скорости - значит алгоритм оптимальный, а значит, победитель тот, кто смог его максимально ужать.


Часовой пояс GMT +4, время: 11:42.
Страница 4 из 5 < 123 4 5 >
Показывать 64 сообщений этой темы на одной странице

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot