На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Что за интерес просто код публиковать? Даже никаких коментариев... Лучше б идеи расказали или подводные камни в некоторых задачах. Вот например в чем этот самый камешь в задаче Фейлрур? Моя программа набрала только 8/20 балов:(
Поза форумом
Area
Program Area; {$R+} Type TPoint=record x,y:integer end; Var LN1,PV1,LN2,PV2:TPoint; K,i:integer; s:string; Procedure Swap(var a,b:integer); var t:integer; begin t:=a; a:=b; b:=t; end; Begin Assign(Input,'D:\users\332.in'); reset(Input); Read(K); s:=''; For i:=1 to K-1 do begin Read(LN1.x,LN1.y,PV1.x,PV1.y,LN2.x,LN2.y,PV2.x,PV2.y); If LN1.x>PV1.x then begin Swap(LN1.x,PV1.x); Swap(LN1.y,PV1.y) end; If LN2.x>PV2.x then begin Swap(LN2.x,PV2.x); Swap(LN2.y,PV2.y) end; If LN1.y>PV1.y then Swap(LN1.y,PV1.y); If LN2.y>PV2.y then Swap(LN2.y,PV2.y); If LN2.x<LN1.x then begin Swap(LN1.x,LN2.x); Swap(LN1.y,LN2.y); Swap(PV1.x,PV2.x); Swap(PV1.y,PV2.y) end; If (LN2.y>PV1.y) or (LN2.x>PV1.x) or (PV2.y<LN1.y) Then s:=s+'0' Else If ((LN2.x=PV1.x)and(LN2.y=PV1.y)) or ((LN2.x=PV1.x)and(PV2.y=LN1.y)) Then s:=s+'1' Else If (LN2.y=PV1.y) or (LN2.x=PV1.x) or (PV2.y=LN1.y) Then s:=s+'2' Else s:=s+'3'; end; Readln(LN1.x,LN1.y,PV1.x,PV1.y,LN2.x,LN2.y,PV2.x,PV2.y); If LN1.x>PV1.x then begin Swap(LN1.x,PV1.x); Swap(LN1.y,PV1.y) end; If LN2.x>PV2.x then begin Swap(LN2.x,PV2.x); Swap(LN2.y,PV2.y) end; If LN1.y>PV1.y then Swap(LN1.y,PV1.y); If LN2.y>PV2.y then Swap(LN2.y,PV2.y); If LN2.x<LN1.x then begin Swap(LN1.x,LN2.x); Swap(LN1.y,LN2.y); Swap(PV1.x,PV2.x); Swap(PV1.y,PV2.y) end; If (LN2.y>PV1.y) or (LN2.x>PV1.x) or (PV2.y<LN1.y) Then s:=s+'0' Else If ((LN2.x=PV1.x)and(LN2.y=PV1.y)) or ((LN2.x=PV1.x)and(PV2.y=LN1.y)) Then s:=s+'1' Else If (LN2.y=PV1.y) or (LN2.x=PV1.x) or (PV2.y=LN1.y) Then s:=s+'2' Else s:=s+'3'; Writeln(s); End.
Dictionary
{$R+} Program Tarabar; Const Fact:array [0..12] of longint=(1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600); Var N,k,i,j,cur:longint; s:string; T:set of byte; Begin Readln(N,K); Dec(k); T:=[]; s:=''; For i:=1 to N do begin Cur:=K div Fact[N-i]; K:=K mod Fact[N-i]; j:=1; While (j in T) or (Cur<>0) do begin If not (j in T) then dec(cur); Inc(j); end; Include(T,j); s:=s+Chr(Ord('a')-1+j); end; Writeln(s); End.
Failure
{$R+} Program Trains; Var T,i:byte; V1,V2,L1,L2,X1,Y1,X2,Y2,VG1,VG2,VH1,VH2,sw:real; s:string; nocrash:boolean; Begin s:=''; Read(T); For i:=1 to T-1 do begin Read(V1,V2,L1,L2,X1,Y1,X2,Y2); nocrash:=false; If Y1<>0 Then begin X1:=X2; Y2:=Y1; X2:=0; Y1:=0; sw:=L1; L1:=L2; L2:=sw; sw:=V1; V1:=V2; V2:=sw; end; If V1<>0 Then begin VG1:=X1/V1; VH1:=(X1+L1)/V1 end Else nocrash:=true; If V2<>0 Then begin VG2:=Y2/V2; VH2:=(Y2+L2)/V2 end Else nocrash:=true; If (VH1<=VG2) or (VH2<=VG1) or nocrash Then s:=s+'0' Else s:=s+'1'; end; Readln(V1,V2,L1,L2,X1,Y1,X2,Y2); nocrash:=false; If Y1<>0 Then begin X1:=X2; X2:=0; Y2:=Y1; Y1:=0; sw:=L1; L1:=L2; L2:=sw; sw:=V1; V1:=V2; V2:=sw; end; If V1<>0 Then begin VG1:=X1/V1; VH1:=(X1+L1)/V1 end Else nocrash:=true; If V2<>0 Then begin VG2:=Y2/V2; VH2:=(Y2+L2)/V2 end Else nocrash:=true; If (VH1<=VG2) or (VH2<=VG1) or nocrash Then s:=s+'0' Else s:=s+'1'; Writeln(s); End.
Pool
{$N+} program Pool; const _eps=1e-30; type TPoint=record x,y:double end; var S,P1,P2,Sym:TPoint; min,dst:double; function Eq(a,b:double):boolean; begin Eq:=Abs(a-b)<=_eps end; function More(a,b:double):boolean; begin More:=a-b>_eps end; function Less(a,b:double):boolean; begin Less:=(Not Eq(a,b)) and (Not More(a,b)) end; begin Readln(S.x,S.y,P1.x,P1.y,P2.x,P2.y); If Eq(P1.x,P2.x) Then begin If More(P1.y,P2.y) then begin min:=P1.x; P1.x:=P2.x; P2.x:=min; min:=P1.y; P1.y:=P2.y; P2.y:=min end; If Less(S.y+S.y-P1.y-P2.y,P1.y+P2.y) Then min:=S.y+S.y-P1.y-P2.y Else min:=P1.y+P2.y; Sym.x:=S.x+S.x-P1.x; Sym.y:=P1.y; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; Sym.x:=-P1.x; Sym.y:=P1.y; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; end Else begin If Eq(P1.y,P2.y) Then begin If More(P1.x,P2.x) then begin min:=P1.x; P1.x:=P2.x; P2.x:=min; min:=P1.y; P1.y:=P2.y; P2.y:=min end; If Less(S.x+S.x-P1.x-P2.x,P1.x+P2.x) Then min:=S.x+S.x-P1.x-P2.x Else min:=P1.x+P2.x; Sym.y:=S.y+S.y-P1.y; Sym.x:=P1.x; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; Sym.y:=-P1.y; Sym.x:=P1.x; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; end Else begin Sym.y:=S.y+S.y-P1.y; Sym.x:=P1.x; min:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); Sym.y:=-P1.y; Sym.x:=P1.x; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; Sym.x:=S.x+S.x-P1.x; Sym.y:=P1.y; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; Sym.x:=-P1.x; Sym.y:=P1.y; dst:=Sqrt(Abs((Sym.x-P2.x)*(Sym.x-P2.x)+(Sym.y-P2.y)*(Sym.y-P2.y))); If Less(dst,min) then min:=dst; end; end; Writeln(min); end.
Supernet
program Supernet; Var R,N,i:integert; K:longint; begin Readln(R,N); K:=0; For i:=3 to N do If (2*R mod i)=0 then Inc(K,i*(i-1) shr 1); Writeln(K); end.
Прошло на полный балл всё, кроме Pool (он - на 12). Если уж кто просит идеи... чуть позже.
Поза форумом
Snake написав:
Что за интерес просто код публиковать? Даже никаких коментариев... Лучше б идеи расказали или подводные камни в некоторых задачах. Вот например в чем этот самый камешь в задаче Фейлрур? Моя программа набрала только 8/20 балов:(
Задачу придумал я. Никаких камней нет абсолютно. Скорости заданы по модулю, потому находишь 4 значения времени - когда головы и хвосты проедут точку(0,0). Тогда если время головы одного больше(либо равно) времени хвоста другого, то трагедии не будет, иначе - капец. Смотри мое авторское решение(отдельный топ) - там все прозрачно и очевидно.
Поза форумом
Может, кто-то не учёл, что скорость может быть нулевой?
Поза форумом
Ну во-первых, там вроде в тестах вообще нет нулевой скорости, а во-вторых у меня русским по белому написано, если скорость1 или скорость2=0 то выводим ноль иначе решаем как-то по другому... А впрочем зачем объяснять, вот я сейчас свой глючный код выложу:
здесь:
tg1 - время когда голова 1-го поезда находится в точке 0.0
tg2 - время когда голова 2-го поезда находится в точке 0.0
th1 - время когда хвост 1-го поезда находится в точке 0.0
th2 - время когда хвост 1-го поезда находится в точке 0.0
program Failure;
var v1,v2,l1,l2,x1,y1,x2,y2,th1,tg1,th2,tg2,i:real;
t,test:integer;
s:string;
tr:boolean;
begin
read(t);
s:='';
for test:=1 to t do
Begin
read(v1,v2,l1,l2,x1,y2,x2,y2);
if (v1=0)or(v2=0)then s:=s+'0'else
Begin
tg1:=x1/v1;
if tg1<y1/v1 then tg1:=y1/v1;
tg2:=x2/v2;
if tg2<y2/v2 then tg2:=y2/v2;
th1:=(x1+l1)/v1;
if th1<(y1+l1)/v1 then th1:=(y1+l1)/v1;
th2:=(x2+l2)/v2;
if th2<(y2+l2)/v2 then th2:=(y2+l2)/v2;
tr:=false;
if(th1<=th2)and(th1>=tg2)and(th1<>tg2)
or(th2<=th1)and(th2>=tg1)and(th2<>tg1)
then
begin
s:=s+'1';
tr:=true;
end;
if(tr=false)then s:=s+'0';
End;
end;
write(s);
end.
Відредаговано Snake (2006-10-29 20:54:57)
Поза форумом
Skiminok написав:
Может, кто-то не учёл, что скорость может быть нулевой?
Скорость не может быть нулевой
Поза форумом
Snake написав:
Ну во-первых, там вроде в тестах вообще нет нулевой скорости, а во-вторых у меня русским по белому написано, если скорость1 или скорость2=0 то выводим ноль иначе решаем как-то по другому... А впрочем зачем объяснять, вот я сейчас свой глючный код выложу:
здесь:
tg1 - время когда голова 1-го поезда находится в точке 0.0
tg2 - время когда голова 2-го поезда находится в точке 0.0
th1 - время когда хвост 1-го поезда находится в точке 0.0
th2 - время когда хвост 1-го поезда находится в точке 0.0
program Failure;
var v1,v2,l1,l2,x1,y1,x2,y2,th1,tg1,th2,tg2,i:real;
t,test:integer;
s:string;
tr:boolean;
begin
read(t);
s:='';
for test:=1 to t do
Begin
read(v1,v2,l1,l2,x1,y2,x2,y2);
if (v1=0)or(v2=0)then s:=s+'0'else
Begin
tg1:=x1/v1;
if tg1<y1/v1 then tg1:=y1/v1;
tg2:=x2/v2;
if tg2<y2/v2 then tg2:=y2/v2;
th1:=(x1+l1)/v1;
if th1<(y1+l1)/v1 then th1:=(y1+l1)/v1;
th2:=(x2+l2)/v2;
if th2<(y2+l2)/v2 then th2:=(y2+l2)/v2;
tr:=false;
if(th1<=th2)and(th1>=tg2)and(th1<>tg2)
or(th2<=th1)and(th2>=tg1)and(th2<>tg1)
then
begin
s:=s+'1';
tr:=true;
end;
if(tr=false)then s:=s+'0';
End;
end;
write(s);
end.
Сложно проверяешь, произойдет ли катастрофа. Возможно там и сплужил. Проще гораздо можно(смотри мое решение - там только 2 условия(у тебя аж 6)).
Поза форумом
Fizteh написав:
Skiminok написав:
Может, кто-то не учёл, что скорость может быть нулевой?
Скорость не может быть нулевой
Может, в тестах и не может (каламбур), а в условии об этом сказано ничего не было.
Поза форумом
Skiminok написав:
Fizteh написав:
Skiminok написав:
Может, кто-то не учёл, что скорость может быть нулевой?
Скорость не может быть нулевой
Может, в тестах и не может (каламбур), а в условии об этом сказано ничего не было.
В условии поезда мчатся навстречу друг к другу. Мчатся и стоять на месте - разные вещи. Аналогично, что длина поезда равна нулю. Я таких поездов не видел...
Поза форумом
Я рассматривал 4 варианта расположения поездов (т.е. свел задачку к любимой задаче виннице по вычеслению наложения отрезков):
здесь:
tg1 - время когда голова 1-го поезда находится в точке 0.0
tg2 - время когда голова 2-го поезда находится в точке 0.0
th1 - время когда хвост 1-го поезда находится в точке 0.0
th2 - время когда хвост 1-го поезда находится в точке 0.0
************************************
* 1 Вариант *
* *
* tg1 th1 *
* О-------------О *
* tg2 th2 *
* *
* tg2 th2 *
* O-------------------O *
* tg1 th1 *
* *
************************************
************************************
* 2 Вариант *
* *
* tg1 th1 *
* О---------------------------О *
* tg2 th2 *
* *
* tg2 th2 *
* O-----------------O *
* tg1 th1 *
* *
************************************
************************************
* 3 Вариант *
* *
* tg1 th1 *
* О-------------О *
* tg2 |th2 *
* | *
* | *
* tg2| th2 *
* O----------O *
* tg1 th1 *
* *
************************************
************************************
* 4 Вариант *
* *
* tg1 th1 *
* О-------------О *
* tg2 th2 *
* *
* *
* tg2 th2 *
* O----------O *
* tg1 th1 *
* *
************************************
Поезда сталкиваются только в 1-ом и 2-ом случаях, причем 2 случай является подслучаем 1-го, потом надо исключить 3 вариант. Вот и выходит 6 условий. Шесть а не три ведь мы не знаем какой поезд первый а какой второй.
Вот мое условие столкновения
if(th1<=th2)and(th1>=tg2)and(th1<>tg2)
or(th2<=th1)and(th2>=tg1)and(th2<>tg1)
then
begin
s:=s+'1';
tr:=true;
end;
Но это решение проходит 4/10 тестов.
Відредаговано Snake (2006-10-30 10:55:52)
Поза форумом
тут все проще. Столкновения не будет в 2 случаях:
1. конец 1го поезда пересек перекресток раньше, чем начало 2го.
2. конец 2го поезда пересек перекресток раньше, чем начало 1го.
Отсюда получаем короткий код с 2мя условиями:
#include <cstdio> using namespace std; int main() { int t; double v1,v2,l1,l2,x1,y1,x2,y2; double tbeg1,tend1,tbeg2,tend2; // freopen("failure.in","r",stdin); for(scanf("%d",&t);t;t--) { scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&v1,&v2,&l1,&l2,&x1,&y1,&x2,&y2); tbeg1=(x1+y1)/v1; tend1=(x1+y1+l1)/v1; tbeg2=(x2+y2)/v2; tend2=(x2+y2+l2)/v2; if(tbeg1>=tend2||tbeg2>=tend1)printf("0"); else printf("1"); } printf("\n"); return 0; }
Поза форумом
Snake, у тебя случайно не Галина Петровна преподает? Если да, то тебе очень повезло. По поводу задачи - забей и реши эту задачу заново, просто заново. Не ищи ошибок - порой это гиблое дело. Возможно у тебя глюк в приоритетах, не знаю точно, лень в чужом алгоритме копаться. Совет - сделай заново!
Поза форумом
Fizteh написав:
Snake, у тебя случайно не Галина Петровна преподает? Если да, то тебе очень повезло. По поводу задачи - забей и реши эту задачу заново, просто заново. Не ищи ошибок - порой это гиблое дело. Возможно у тебя глюк в приоритетах, не знаю точно, лень в чужом алгоритме копаться. Совет - сделай заново!
Ха-ха! Пропалили Снейка! Как ты узнал?
Поза форумом
FireTiger, та ладно пропалили, ... она и у тебя преподает, мы ж заполняем анкету откуда и где учимся. А на счет повезло то это действительно так и есть. Но еще больше повезло десятому классу. Она у них будет изначально вести, а не как у нас - только с 11 класса. А на счет задачи так и сделаю как посоветовал физтех... хотя я так и не понял где у меня ошибка:(
Поза форумом
Snake написав:
FireTiger, та ладно пропалили, ... она и у тебя преподает, мы ж заполняем анкету откуда и где учимся. А на счет повезло то это действительно так и есть. Но еще больше повезло десятому классу. Она у них будет изначально вести, а не как у нас - только с 11 класса. А на счет задачи так и сделаю как посоветовал физтех... хотя я так и не понял где у меня ошибка:(
ХА-ха-ха-ха-ха!!!!!!!!!!!!!!!!!!!
Обоих пропалили хаааааааааааааааааааааа!!!!!!!!
Поза форумом
Ivan написав:
А вы имеете отношение к хакерской группе gpd?
Не починайте тут дитсадок, коли мені було 10 я думав що я ніндзя.
Відредаговано Юрко Савеленко (2006-10-30 18:38:19)
Поза форумом
Snake написав:
Женя, и ты себя спалил... ты тоже с нами:-)
Я студент первого курса, в прошлом году закончил винницкую гимназию. У меня информатику преподовала Галина Петровна. Замечательный человек, гениальный педагог. Мы с ней не раз на всякие олимпиады ездили. В общем че рассказывать - сами увидите. Знаю, что она в этом году в Донецк работать уехала, а у Snake подписано, что из Донецка. Вот и предположил, а наверняка не знал. Передавайте ей огромный привет. Пусть, если сможет, напишет что-то нам на bot32@rambler.ru, а то мы ее адреса не знаем. Это, если что, из МФТИ.
Поза форумом
Fizteh написав:
Snake написав:
Женя, и ты себя спалил... ты тоже с нами:-)
Я студент первого курса, в прошлом году закончил винницкую гимназию. У меня информатику преподовала Галина Петровна. Замечательный человек, гениальный педагог. Мы с ней не раз на всякие олимпиады ездили. В общем че рассказывать - сами увидите. Знаю, что она в этом году в Донецк работать уехала, а у Snake подписано, что из Донецка. Вот и предположил, а наверняка не знал. Передавайте ей огромный привет. Пусть, если сможет, напишет что-то нам на bot32@rambler.ru, а то мы ее адреса не знаем. Это, если что, из МФТИ.
Хорошо, будем передавать привет!!!!!!!Обязательно!!!!!!!
Поза форумом
((((((((((((((( Что-то я ничего понять не могу.... Вот моё решение задачи Failure, логика решения та же, что и у FizTeh'а, но прошло критически мало тестов. Если не ошибаюсь - 5/20. Может быть ошибка в том, что надо было бы добавить еще один else? Я не знаю. Если кто-то увидит ошибку, скажите, пожалуйста:
var
tests,i: byte;
v1,v2,l1,l2,x1,y1,x2,y2: extended;
procedure Exchange(var a,b: extended);
var c: extended;
begin
c:=a;
a:=b;
b:=c;
end;
function Solve(v1,v2,l1,l2,x1,y1,x2,y2: extended): char;
var t,t1,t2: extended;
begin
if (v1=0)or(v2=0)
then Solve:='0'
else
begin
t:=y1/v1; {голова 1го - в начале координат}
t1:=l1/v1; {время проезда длины первого поезда}
t2:=(x2-v2*t)/v2; {время проезда длины второго поезда + расстояние его от начала координат в то время, когда первый был в точке 0,0}
if (t<0)or(t1<0)or(t2<0)
then solve:='0'
else
if t1>t2
then solve:='1'
else
begin {аналогичный код, только поезда поменяем местами}
t:=x2/v2;
t2:=l2/v2;
t1:=(y1-v1*t)/v1;
if t2>t1
then solve:='1'
else solve:='0'
end;
end;
end;
begin
read(tests); {no comments}
for i:=1 to tests do
begin
read(v1,v2,l1,l2,x1,y1,x2,y2);
if y1=0 {меняем координаты поездов так, чтобы первый}
then {"мчался" по оси OY, а второй - по оси OX}
begin
Exchange(x1,x2);
Exchange(y1,y2);
Exchange(v1,v2);
Exchange(l1,l2);
end;
write(solve(v1,v2,l1,l2,x1,y1,x2,y2));
end;
end.
Відредаговано Timchenko (2006-11-02 19:10:37)
Поза форумом
Timchenko написав:
if y1=0
Условие y1=0 означает:
Первый поезд едет по оси ординат или первый поезд едет по оси абсцисс и его голова в начальный момент времени находится в начале координат.
Вроде тут глюк у тебя... но у меня тоже 8/20, так что не принимай мои слова за непреложную истину...
У меня чуть не такой алгоритм... я нахожу время когда поезд въезжает на переезд и когда выезжает с него для каждого поезда и нахожу наложение двух отрезков времени...
Поза форумом
У вас такі складні коди мозги можна звернути
моя прога на 100% пройшла тест.
#include<stdio.h> #define CRASH 1 #define ALLRIGHT 0 main() { int T,i,j; float mas[10][10]; float t1_1,t1_2,t2_1,t2_2,s1,s2; scanf("%d",&T); for(j=1;j<=T;j++) for(i=1;i<=8;i++) scanf("%f",&mas[i][j]); for(j=1;j<=T;j++) { s1=(mas[5][j]>mas[6][j])?mas[5][j]:mas[6][j]; s2=(mas[7][j]>mas[8][j])?mas[7][j]:mas[8][j]; t1_1=s1/mas[1][j]; t1_2=(s1+mas[3][j])/mas[1][j]; t2_1=s2/mas[2][j]; t2_2=(s2+mas[4][j])/mas[2][j]; if((t1_1>=t2_1)&&(t1_1<t2_2)||(t2_1>=t1_1)&&(t2_1<t1_2)) printf("%d",CRASH); else printf("%d",ALLRIGHT); } }
Поза форумом
Це моя єдина ідеальна задача.А в решті напартачив.
Відредаговано Vladislav (2006-11-04 09:55:47)
Поза форумом
Vladislav написав:
У вас такі складні коди мозги можна звернути
моя прога на 100% пройшла тест.Код:
#include<stdio.h> #define CRASH 1 #define ALLRIGHT 0 main() { int T,i,j; float mas[10][10]; float t1_1,t1_2,t2_1,t2_2,s1,s2; scanf("%d",&T); for(j=1;j<=T;j++) for(i=1;i<=8;i++) scanf("%f",&mas[i][j]); for(j=1;j<=T;j++) { s1=(mas[5][j]>mas[6][j])?mas[5][j]:mas[6][j]; s2=(mas[7][j]>mas[8][j])?mas[7][j]:mas[8][j]; t1_1=s1/mas[1][j]; t1_2=(s1+mas[3][j])/mas[1][j]; t2_1=s2/mas[2][j]; t2_2=(s2+mas[4][j])/mas[2][j]; if((t1_1>=t2_1)&&(t1_1<t2_2)||(t2_1>=t1_1)&&(t2_1<t1_2)) printf("%d",CRASH); else printf("%d",ALLRIGHT); } }
Всё гениальное просто.... А я умудрился на 8 баллов её сделать....
Поза форумом