задача

← →
Chcnger (2004-03-19 19:29) [0]

Conductors
Ограничение времени: 2.0 секунды
Ограничение памяти: 1 000 КБ

Вступление
Everyone making translations from English to Russian knows an English phrase "Naked conductor runs along the bus". It has two very different meanings.

Задача
Какое может быть минимальное число жителей города, где кондукторы составляют строго более P%, но строго менее Q% населения? Ограничения: 0.01 <= P, Q <= 99.99. Числа P и Q могут быть заданы с точностью до сотых долей.

Исходные данные
Числа P и Q в десятичной записи, разделенные пробелом или переводом строки.

Результат
Программа должна выдать искомое число в десятичной записи.

Пример исходных данных
13
14.1

Пример результата
15

Может кто подскажет с решением, а то даже мысли нет, не могу понять ее :(

← →
Cosinus © (2004-03-19 19:56) [1]

Перебором :)

← →
Chcnger (2004-03-19 20:38) [2]

Я даже не могу понять про что эта задача :(

← →
nikkie © (2004-03-19 20:39) [3]

ты с факториалами уже разобрался?

← →
Chcnger (2004-03-19 20:41) [4]

Да :)

← →
Mox Fulder © (2004-03-19 20:43) [5]

Переходим к задаче о кондукторах. Когда я публиковал условие этой задачи, у меня уже было моё
решение, в котором я был почти уверен. Получив несколько Ваших решений, моя уверенность несколько
уменьшилась, в связи с этим, публикую на всеобщее обозрение и моё решение, и решение, которое на мой
взгляд наиболее близко к "правде". Жду с нетерпением Вашей критики опять же мне на e-mail. Итак,
решение присланное kryll"ом (он прислал его первым):

{$q-,e+,r-,t+,i-,o-,p-,a+,s+,d-,f+,g-,l-,x+,v+,b-,n+}
{$m 65520,0,655360}
var
n:integer;
m,p,q:real;
f1,f2:boolean;
begin
assign(input,"input.txt");
assign(output,"output.txt");
reset(input);
rewrite(output);
read(p,q);
p:=p/100;
q:=q/100;
m:=1.0;
n:=0;
if p=0 then
begin
m:=m/q;
n:=trunc(m)+1;
write(n);
close(input);
close(output);
exit;
end;
if frac(m/p)=0 then
f1:=true
else
f1:=false;
if frac(m/q)=0 then
f2:=true
else
f2:=false;
while (not f1 and not f2 and (trunc(m/p)<=trunc(m/q))) or
(f1 and not f2 and (trunc(m/p)-1<=trunc(m/q)))
or (not f1 and f2 and (trunc(m/p)<=trunc(m/q)+1)) or
(f1 and f2 and (trunc(m/p)-1<=trunc(m/q)+1)) do
begin
m:=m+1;
if frac(m/p)=0 then
f1:=true
else
f1:=false;
if frac(m/q)=0 then
f2:=true
else
f2:=false;
end;
m:=m/q;
n:=trunc(m)+1;
write(n);
close(input);
close(output);
end.

Подобное же решение (одинаковые выходные данных на одинаковых входных) прислали: Kr@b и Зайцев
Евгений.
Тесты, в которых расходятся наши решения:

input.txt
50
50.1
input.txt
12
12.03

На данные входные данные их программа выводит 501 и 158 соответственно, с чем я не согласен
(рассудите пожалуйста). Например, я не смог найти для первого теста такое кол-во кондукторов (целое
число), чтобы их было строго больше 50% и строго меньше 50.1% от 501. Теперь привожу своё решение
(надеюсь, именно оно наиболее правильно), которое на данные входные данные выдаёт 557 и 208
соответственно:

var
p,q,x1,x2:real;
n,x:LongInt;
begin
assign (input,"input.txt");
reset (input);
readln (p,q);
close (input);
n:=1;
p:=p+0.01;
q:=q-0.01;
while x=0 do begin
x1:=(100*n)/p;
x2:=(100*n)/q;
if (trunc(x1)) > (trunc(x2)) then
if trunc(x2) <> x2 then x:=trunc (x2)+1
else if (trunc (x2) + 1) < (trunc (x1)) then x:= trunc (x2) + 1;
n:=n+1;
end;
assign (output,"output.txt");
rewrite (output);
writeln (x);
close (output);
end.

ЗЫ: из рассылки Subscribe.ru Олимпиадные задачи на Turbo Pascal с решениями.

← →
Chcnger (2004-03-19 20:56) [6]

Не могу понять :(
В условии сказано: строго более P%, но строго менее Q%, так как узнать сколько всего жителей в городе? Что-то я въехать не могу

← →
nikkie © (2004-03-19 21:05) [7]

даны 2 числа P и Q
0.01 <= P < Q <= 99.99
найти минимальное натуральное N такое, что в открытом интервале
(P*N, Q*N) есть хотя бы одно натуральное число.

← →
Chcnger (2004-03-19 21:53) [8]

Как я понял тогда для чисел: 13 и 14.1 ответ будет 2?
На интервале есть натуральное число (P*2, Q*2) (13*2, 14.1*2)
В чем я не прав??

>13 и 14.1
>Пример результата
>15

извиняюсь. речь о процентах.

в открытом интервале (P*N/100, Q*N/100) есть хотя бы одно натуральное число.

← →
Chcnger (2004-03-19 22:12) [10]

Thx

классная задачка. имхо, интереснее, чем счастливые билеты и прочие комбинаторные. решение очень простое и красивое, если использовать ряды Фарея. короче, если хотите хорошо выступать в олимпиадах по программированию - учите математику. вне школьной программы. :)

[5]: в приведенной программе от kryll-а эта идея не прослеживается, но может она была у Kr@b-а или Зайцева Евгения. по-крайней мере у меня ответы совпали с их. получается, что решение автора рассылки неверное.

задача Найти похожие ветки