Олимпиадная задачка... хехе... я чуть не повесился =)

← →
DillerXX © (2004-10-13 20:35) [0]

Вот текст:

Рассмотрим сумму Sn =1/(1 * 2)+2/(1 * 2 *3)+3/(1 * 2 * 3 *4)+:+( n -1)/(1 * 2 *3 * : * n ). Требуется написать программу, которая по заданным n и k определяет k -ю цифру десятичного разложения дробной части числа Sn . Технические требования: Входной файл: INPUT . TXT Выходной файл: OUTPUT . TXT Ограничение по времени тестирования: по 5 секунд на один тест. Формат входных данных: Входной текстовый файл INPUT.TXT содержит две строки. В первой записано число n (2 ? n ? 2147483647), во второй k (1 ? k ? 5000). Формат выходных данных: Выходной файл OUTPUT . TXT должен содержать найденную цифру. Пример файла входных данных: 3 100 Пример файла выходных данных (для приведенного выше входного файла): 3
блин, в голову ваще ничё путного не приходит... может поможете? посто интересно как ЭТО ваще решить... конечно у меня относительно маленький уровень навыков решения задач потобного типа, но всё равно по мойму очень сложная

← →
Defunct © (2004-10-13 20:39) [1]

умножением в столбик

← →
debuger © (2004-10-13 21:32) [2]

может длинная арифметика? 5 секунд - времени предостаточно :)

← →
YurikGL © (2004-10-13 21:37) [3]

Может к единому знаменателю привести?

← →
TUser © (2004-10-13 21:50) [4]

Задача не на программирование, а на математику. Надо придумать, как быстро находить
trunc(k/((n+1)(n-1)!)

← →
Neoff (2004-10-13 21:52) [5]

Sn=1-1/(n+1)!

ну вот примерно вычисляет с малой точностью...

program diller;

{$APPTYPE CONSOLE}

var
k, n: integer;
i, k0: integer;
x: extended;
res: integer;

begin
ReadLn(n, k);
i:=2;
x:=1;
k0:=0;
while (i<=n) do
begin
x:=x/i;
Inc(i);
if x<1 then
begin
x:=x*10;
inc(k0);
if k0>k then
begin
res:=9;
Break;
end;
end;
end;
if (i>n) and not (k0>k) then
begin
while k0<k do
begin
x:=frac(x);
x:=x*10;
inc(k0);
end;
res:=(10-trunc(x+0.999999999999999999)) mod 10;
end;
WriteLn(res);
readln;
// readln;
end.

← →
TUser © (2004-10-13 21:59) [6]

> Sn=1-1/(n+1)!

Я в математике не силен, но
S(n) = n/(n+1)! = 1/((n+1)*(n-1)!)

Как это привести к вашему уравнению, я не понял ...

← →
Alx2 © (2004-10-13 22:03) [7]

Sn=1-1/n!

← →
pasha_golub © (2004-10-13 23:51) [8]

Alx2 © (13.10.04 22:03) [7]
C тобой не интересно. :0)

← →
Defunct © (2004-10-14 00:08) [9]

> Sn=1-1/n!

вот вот, [1] как раз об этом.
посчитайте 1000!
задачу можно решить только умножением в столбик больших массивов как в школе учили.

← →
pasha_golub © (2004-10-14 00:19) [10]

Defunct © (14.10.04 00:08) [9]
К примеру, я на олимпиадах всегда "жульничал", когда дело касалось времени. Всегда какую-то дополнительную информацию подсчитывал при запуске программы. Так что...

← →
Defunct © (2004-10-14 02:23) [11]

pasha_golub © (14.10.04 00:19) [10]

А я бывал в комиссии на таких олимпиадах, и там где видел жульничество ставил 0 баллов вместо 25. ;)

← →
Alx2 © (2004-10-14 06:28) [12]

>Defunct © (14.10.04 00:08)

Мне кажется, должен быт итеративный метод получения десятичных цифр.

>посчитайте 1000!
>задачу можно решить только умножением в столбик больших
>массивов как в школе учили.

В условии задачи сказано, что n in [2..2^31];
Как вы в столбик будете считать (2^31)! - не представляю.

← →
TUser © (2004-10-14 07:27) [13]

> Мне кажется, должен быт итеративный метод получения десятичных
> цифр.

Вообще, если вычитслить порядок этого факториала (что просто), то можно сразу будет сказать, что определенное (и большое) кол-во самых первых десятичных цифр - это 9.

← →
SergP. (2004-10-14 08:33) [14]

> [13] TUser © (14.10.04 07:27)

Что-то я не уверен в этом...

← →
Alx2 © (2004-10-14 09:03) [15]

>Defunct © (14.10.04 00:08)
Хотя возможно попробовать и "столбиком".
если n>1775 (следует из форулы Стирлинга) то для любого k in [1..5000] k-я цифра = 9.

А факториалы 1! .. 1775! имеют более-менее разумные значения :)

← →
Neoff (2004-10-14 09:31) [16]

ЗАЧЕМ считать вам n=2^32-1? да при n>1000 уже ясно что 5000-символ не будет меняться.
an=n/(n+1)! причем = 1/(n+1)(n-1)! как сказал товарищ :)
n/(n+1)! = (n+1)/(n+1)! - 1/(n+1)! = 1/n!-1/(n+1)!
отсюда когда мы возьмём сумму, сократится всё, кроме
1-1/(n+1)! а не 1-1/n!.

Я могу доделать эту задачу с длинной арифметикой но честно скажу - мне лень, у меня ещё стопка задач лежит. Считаем эту задачу полностью разобранной.

← →
Alx2 © (2004-10-14 09:32) [17]

Вот условие, когда считать частное не нужно:

if (n>1775) or (k=< trunc ( ((1/2+n)*ln(n)-n+1/2*ln(2*Pi))/ln(10) )) then
Result := 9; // k-я цифра = 9

← →
Alx2 © (2004-10-14 09:42) [18]

>Neoff (14.10.04 09:31)

Я брал сумму k/(k+1)!, k = 1 .. n - 1 (в условии последний член = (n-1)/n! ) ; Получилось Sn = 1 - 1/n!

← →
Veinamond (2004-10-14 09:59) [19]

а производящие функции тут не подойдут? можно, в принципе, попробовать это через exp выразить. вопрос только в том, откуда взять вычисленное число е с точностью до 5000 знаков после запятой.
вообще, мне кажется, возможно, ошибочно, что невелика будет разница, вычислять это число или определять случайным образом при больших n и k:)

← →
Veinamond (2004-10-14 10:03) [20]

упс. и правда, ошибочно. ясно.

← →
TUser © (2004-10-14 11:02) [21]

> откуда взять вычисленное число е с точностью до 5000 знаков
> после запятой

Да не жалко, запоминай :)))
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320 030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841 675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067 371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644 549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625 094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930 416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021 609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101 157477041718986106873969655212671546889570350354021234078498193343210681701210056278802351930332247450158539047304199577 770935036604169973297250886876966403555707162268447162560798826517871341951246652010305921236677194325278675398558944896 970964097545918569563802363701621120477427228364896134225164450781824423529486363721417402388934412479635743702637552944 483379980161254922785092577825620926226483262779333865664816277251640191059004916449982893150566047258027786318641551956 532442586982946959308019152987211725563475463964479101459040905862984967912874068705048958586717479854667757573205681288 459205413340539220001137863009455606881667400169842055804033637953764520304024322566135278369511778838638744396625322498 506549958862342818997077332761717839280349465014345588970719425863987727547109629537415211151368350627526023264847287039 207643100595841166120545297030236472549296669381151373227536450988890313602057248176585118063036442812314965507047510254 465011727211555194866850800368532281831521960037356252794495158284188294787610852639813955990067376482922443752871846245 780361929819713991475644882626039033814418232625150974827987779964373089970388867782271383605772978824125611907176639465 070633045279546618550966661856647097113444740160704626215680717481877844371436988218559670959102596862002353718588748569 652200050311734392073211390803293634479727355955277349071783793421637012050054513263835440001863239914907054797780566978 533580489669062951194324730995876552368128590413832411607226029983305353708761389396391779574540161372236187893652605381 558415871869255386061647798340254351284396129460352913325942794904337299085731580290958631382683291477116396337092400316 894586360606458459251269946557248391865642097526850823075442545993769170419777800853627309417101634349076964237222943523 661255725088147792231519747780605696725380171807763603462459278778465850656050780844211529697521890874019660906651803516 501792504619501366585436632712549639908549144200014574760819302212066024330096412704894390397177195180699086998606636583 232278709376502260149291011517177635944602023249300280401867723910288097866605651183260043688508817157238669842242201024 950551881694803221002515426494639812873677658927688163598312477886520141174110913601164995076629077943646005851941998560 162647907615321038727557126992518275687989302761761146162549356495903798045838182323368612016243736569846703785853305275 833337939907521660692380533698879565137285593883499894707416181550125397064648171946708348197214488898790676503795903669 672494992545279033729636162658976039498576741397359441023744329709355477982629614591442936451428617158587339746791897571 211956187385783644758448423555581050025611492391518893099463428413936080383091662818811503715284967059741625628236092168 075150177725387402564253470879089137291722828611515915683725241630772254406337875931059826760944203261924285317018781772 960235413060672136046000389661093647095141417185777014180606443636815464440053316087783143174440811949422975599314011888 683314832802706553833004693290115744147563139997221703804617092894579096271662260740718749975359212756084414737823303270 330168237193648002173285734935947564334129943024850235732214597843282641421684878721673367010615094243456984401873312810 107945127223737886126058165668053714396127888732527373890392890506865324138062796025930387727697783792868409325365880733 988457218746021005311483351323850047827169376218004904795597959290591655470505777514308175112698985188408718564026035305 583737832422924185625644255022672155980274012617971928047139600689163828665277009752767069777036439260224372841840883251 848770472638440379530166905465937461619323840363893131364327137688841026811219891275223056256756254701725086349765367288 605966752740868627407912856576996313789753034660616669804218267724560530660773899624218340859882071864682623215080288286 359746839654358856685503773131296587975810501214916207656769950659715344763470320853215603674828608378656803073062657633 469774295634643716709397193060876963495328846833613038829431040800296873869117066666147

← →
Neoff (2004-10-14 11:39) [22]

Alx2, thx, действительно 1-1/n! но в программе у меня так и есть :) можешь проверить.

← →
Veinamond (2004-10-14 13:02) [23]

TUser
вот спасибо:) как бы я жил дальше без этого знания:) запоминаю:)

http://pfish.rcdem.ru/09.06.2004/1

Alx2 © (14.10.04 06:28) [12]
> Мне кажется, должен быть итеративный метод получения десятичных цифр.

Конкретно эту задачу раньше не встречал. Видел подобную:
k-ую цифру из n! за ограниченное время. Решалась умножением в столбик. И тестовое задание было кажись n={3,10, 40, 375, 1000}, k=1.

PS: на время при проверке задания особо никто не смотрел, 5 сек. или 30 сек, все понимали, что время больше зависит от машины и от компилятора.

>Defunct © (15.10.04 00:17) [27]
Оно уже стало не интерсно. Осталась рутина. Сорри за то, что я не учел сразу диапазон допустимых величин k и n.

← →
паша_голубь (из другого места) (2004-10-15 01:26) [29]

Defunct © (14.10.04 02:23) [11]
Хе-хе, дай то Бог... Не то что бы я жульничал, часто у меня естество бурлило...

Ну, например, задача вывести все простые числа в таком-то диапазоне, не используя операций деления и умножения.

Мне известно решето Эратосфена, но извините, мудрить с массивом на 100000 элементов это против моей природы. С другой стороны, задача очень уж специфическая. Один знает, а другой - нет. Я счиатю, что задача должна быть полем для поиска, а не беговой дорожкой шииной в 40 см.

ЗЫ Во как... :0)

> мудрить с массивом на 100000 элементов это против моей природы.

1000! - всего 2568 десятичных цифр.
10000! - 35660 десятичных цифр.

так что не так уж много элементов массива.
С другой стороны без массива вы не скажете цифру k1=2 для 10000! ;)

> Я считаю, что задача должна быть полем для поиска, а не беговой дорожкой шииной в 40 см.

А чем не поле для поиска?
Умножение в столбик имеет столько разных реализаций, аж глаза разбегаются.

> Один знает, а другой - нет.
И главное все его знают (проходят в кажется в 3-ем классе на уроках математики)

> ЗЫ Во как... :0)
Вот так ;)

Defunct © (15.10.04 01:49) [30]
Я имел ввиду задачу
Ну, например, задача вывести все простые числа в таком-то диапазоне, не используя операций деления и умножения.

Именно ее. И про нее я разглагольствовал. Наверно, не четкао вырвзил мысль.

Олимпиадная задачка... хехе... я чуть не повесился =) Найти похожие ветки