Cytuj:
Ostatnimi czasy Święty Mikołaj trochę przytył i nie mieści się już w niektórych kominach, przez które wchodził do domów, by zostawić prezenty. Co gorsza, przestał mieścić się w niektórych oknach, a nawet drzwiach. Mikołaj zgodnie ze swoimi Zasadami Dyskrecji, jeśli mieści się w kominie, to wchodzi do domu przez komin. Jeśli nie mieści się w kominie i mieści się w oknie, to wybiera wejście przez okno. Przez drzwi wchodzi tylko wtedy, gdy nie mieści się ani w kominie, ani w oknie, a w drzwiach się mieści. W kominie Mikołaj mieści się, gdy obwód w pasie Mikołaja jest mniejszy od obwodu otworu komina. Podobnie, Mikołaj mieści się w oknie (drzwiach), gdy obwód w pasie Mikołaja jest mniejszy od obwodu otworu okna (drzwi). W tym roku Mikołaj ma jeszcze do odwiedzenia wiele domów i szkoda mu tracić czas na różne próby wejścia do nich. Obawia się też, że podczas niektórych prób wejścia mógłby się zaklinować.
Napisz program, który mając podany obwód w pasie Mikołaja, obwody otworów kominów, okien i drzwi domów, wyznaczy sposób wejścia Mikołaja (zgodnie z jego Zasadami Dyskrecji) do każdego z tych domów.
Wejście
Pierwsza linia zawiera oddzielone pojedynczą spacją dwie liczby całkowite N oraz M (1 ≤ N ≤ 1000; 80 ≤ M ≤ 200), określające odpowiednio liczbę domów, które ma odwiedzić Mikołaj, oraz obwód w pasie Mikołaja mierzony w centymetrach. W każdej z kolejnych N linii wejścia znajduje się opis jednego domu. Opis domu składa się z trzech liczb całkowitych rozdzielonych pojedynczymi spacjami: Ki, Oi, Di (50 ≤ Ki, Oi, Di ≤ 800), oznaczających mierzone w centymetrach obwody odpowiednio otworu komina, otworu okna i otworu drzwi i-tego domu.
Wyjście
W kolejnych liniach dla każdego opisu domu należy wypisać jeden wyraz oznaczający sposób wejścia Mikołaja, zgodnie z jego Zasadami Dyskrecji, do domu:
* komin - jeśli Mikołaj ma wejść do domu przez komin,
* okno - jeśli ma wejść przez okno,
* drzwi - jeśli ma wejść przez drzwi,
* brak - jeśli Mikołaj nie mieści się ani w kominie, ani w oknie, ani w drzwiach.
Przykład
Dla danych wejściowych:
6 150
180 600 600
120 130 140
150 155 400
135 140 500
120 150 650
140 200 145
poprawną odpowiedzią jest:
komin
brak
okno
drzwi
drzwi
okno
Napisz program, który mając podany obwód w pasie Mikołaja, obwody otworów kominów, okien i drzwi domów, wyznaczy sposób wejścia Mikołaja (zgodnie z jego Zasadami Dyskrecji) do każdego z tych domów.
Wejście
Pierwsza linia zawiera oddzielone pojedynczą spacją dwie liczby całkowite N oraz M (1 ≤ N ≤ 1000; 80 ≤ M ≤ 200), określające odpowiednio liczbę domów, które ma odwiedzić Mikołaj, oraz obwód w pasie Mikołaja mierzony w centymetrach. W każdej z kolejnych N linii wejścia znajduje się opis jednego domu. Opis domu składa się z trzech liczb całkowitych rozdzielonych pojedynczymi spacjami: Ki, Oi, Di (50 ≤ Ki, Oi, Di ≤ 800), oznaczających mierzone w centymetrach obwody odpowiednio otworu komina, otworu okna i otworu drzwi i-tego domu.
Wyjście
W kolejnych liniach dla każdego opisu domu należy wypisać jeden wyraz oznaczający sposób wejścia Mikołaja, zgodnie z jego Zasadami Dyskrecji, do domu:
* komin - jeśli Mikołaj ma wejść do domu przez komin,
* okno - jeśli ma wejść przez okno,
* drzwi - jeśli ma wejść przez drzwi,
* brak - jeśli Mikołaj nie mieści się ani w kominie, ani w oknie, ani w drzwiach.
Przykład
Dla danych wejściowych:
6 150
180 600 600
120 130 140
150 155 400
135 140 500
120 150 650
140 200 145
poprawną odpowiedzią jest:
komin
brak
okno
drzwi
drzwi
okno
I rozwiązanie które wysłałem i dostałem maksymalną ilość punktów czyli 10. Program napisałem w Pascalu. Kod podany przez mnie jest pełnym kodem , więc wystarczy tylko wkleić wkleić i skompilować.
Kod:
program WejscieMikolaja;
{ WejscieMikolaja }
{ Michał Komasa }
{ bigkom@gmail.com}
var
IloscDom: Integer;
ObwodPas: Integer;
Kom: Integer;
Okn: Integer;
Drz: Integer;
Odpowiedz: String = '';
DanePodst,DaneDodatt: String;
ik: integer;
procedure PobierzDanePodst(DanePodst: String);
var
ii : Integer; { Długość danych}
IlDom,Obw: String;
Pierwsza: Boolean;
begin
Pierwsza := true;
IlDom := '';
Obw := '';
for ii:= 1 to Length(DanePodst) do
begin
if (DanePodst[ii] <> ' ') and (Pierwsza = true) then
begin
IlDom := IlDom + DanePodst[ii];
end
else
begin
Pierwsza := false;
Obw := Obw + DanePodst[ii];
end;
end;
IloscDom := StrToInt(IlDom);
ObwodPas := StrToInt(Obw);
end;
procedure PobierzDaneDodat(DaneDodat: String);
var
ii : Integer; { Długość danych}
K,O,D: String;
Pierwsza: integer = 0;
begin
{ii := Length(DanePodst);}
Pierwsza := 1;
K := '';
O := '';
D := '';
for ii:= 1 to Length(DaneDodat) do
begin
if (DaneDodat[ii] = ' ')then
begin
Pierwsza := Pierwsza + 1;
end
else
begin
case Pierwsza of
1:
begin
K := K + DaneDodat[ii];
end;
2:
begin
O := O + DaneDodat[ii];
end;
3:
begin
D := D + DaneDodat[ii];
end ;
end;
end;
end;
Kom := StrToInt(K);
Okn := StrToInt(O);
Drz := StrToInt(D);
end;
procedure Sprawdz;
begin
if Odpowiedz <> '' then
begin
Odpowiedz := Odpowiedz + #10;
end;
if ObwodPas <>
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali.
Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne. To niech się podzieli z tym na forum LivePC.pl
http://www.livepc.pl/viewtopic.php?f=43&t=1060
Kolejne zadanie nosi nazwę Ciastka a jego treść to :
Ten problem również rozwiązałem w Pascalu. Dostałem za niego 8/10 Pkt , a oto pełny kod:
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali. Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne. To niech się podzieli z tym na forum LivePC.pl
http://www.livepc.pl/viewtopic.php?f=43&t=1061
Kolejne zadanie nosi tytuł Detektyw , z którym wydawoło mi się , że szybko sobie poradziłem , ale okazał się mały zonk , bo aczkolwiek na testowych danych program działał poprawnie to mimo przyjęcia go do oceny nie dostałem za niego żadnych punktów, argumuntując że w kążdym z dziesięciu testów była otrzymana zła odpowiedź. Więc nie wiem co źle zrobiłem, pewnie jakaś mała pierdółka jest i przez. Treść zadania :
Kompletny kod programu :
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali. Bo moje rozwiązanie rozwiązanie posiada widocznie jakieś błędy. Może ktoś potrafi wskazać mi te błędy ?? To niech się podzieli z tym na forum LivePC.pl
http://www.livepc.pl/viewtopic.php?f=43&t=1063
Kolejnym zadaniem z którym miałem spore problemy, bo głównie bo znów zrobiłem gdzieś mały w kodzie błąd i nie mogę dojść do tego dlaczego . W końcu udało się go przeskoczyć , rozwiązać problem. Program dobrze rozwiązuje testowe zadanie , i pozostałe również ale dostałem tylko jeden ponieważ w pozostałych 9 zadaniach testowych został przekroczony limit czasu na wykonywania programu. A oto treść zadania :
Komplety kod programu napisanego w Pascalu. Program działa:
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali. Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne. To niech się podzieli z tym na forum LivePC.pl
http://www.livepc.pl/viewtopic.php?f=43&t=1064
Zadaniem 5 i zarazem ostatnim za jakie się zabrałem by je rozwiązać , jest zadanie pierwsze z 3 tury czyli Suma dzielników. A o to treść :
Zadanie wydaje się być totalnie banalnie, i słusznie. No ale co robi tak proste zadanie w 3 turze , ano jeżeli zadanie się wykonało w standardowy sposób jak odrazu przychodzi na myśl , czyli sprawdzeniu wszystkich liczb z zakresu od 1 do n czy są dzielnikami liczby , i sumowaniu ich po drodze, a następnie sprawdzić jaka jest reszta z dzielna tej sumy przez M. No ale taki program dla liczb w granicach miliona liczy około 13 do 15 sekund a max limit w zależności od zestawu danych gdzie jeden zestaw mógł zawierać 500 takich liczb , wynosił od 0.05 s do 2.00 s . Więc co teraz ?? A no należało albo znać , jeżeli się nie zna to zapoznać z jakimś trikiem. No i w poszukiwaniu jakiś skrótów , natrafiłem na takie założenia że, dzielników wystarczy szukać dla części całkowitej pierwiastka z danej liczby i brać do sumy zarówno ten dzielnik, jak i wynik dzielenia liczby przez niego (jeżeli dzielnik jest równy temu pierwiastkowi, to bierze się tylko jego). No więc zrobienie czegoś takiego to nic prostszego . Ale okazało się że to jeszcze za mało. Bo dostałem 5/10 pkt. w 4 miałem przekroczony limit wykonania i w jednym błędną odpowiedź.
Dla porównania daję wpierw rozwiązanie dłużnej liczące :
A teraz z wykorzystaniem opisanego triku :
Jak widać kod nie znacznie się zmienił za to czasy wykonywania spadły nawet 1000 krotnie dla dużych zestawów danych. Ale to i tak okazało się za mało.
Więc jeżeli ktoś zrobił to inaczej lub w innym języku niech się pochwali. Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne.To niech się podzieli z tym na forum LivePC.pl
http://www.livepc.pl/viewtopic.php?f=43&t=1065
{ WejscieMikolaja }
{ Michał Komasa }
{ bigkom@gmail.com}
var
IloscDom: Integer;
ObwodPas: Integer;
Kom: Integer;
Okn: Integer;
Drz: Integer;
Odpowiedz: String = '';
DanePodst,DaneDodatt: String;
ik: integer;
procedure PobierzDanePodst(DanePodst: String);
var
ii : Integer; { Długość danych}
IlDom,Obw: String;
Pierwsza: Boolean;
begin
Pierwsza := true;
IlDom := '';
Obw := '';
for ii:= 1 to Length(DanePodst) do
begin
if (DanePodst[ii] <> ' ') and (Pierwsza = true) then
begin
IlDom := IlDom + DanePodst[ii];
end
else
begin
Pierwsza := false;
Obw := Obw + DanePodst[ii];
end;
end;
IloscDom := StrToInt(IlDom);
ObwodPas := StrToInt(Obw);
end;
procedure PobierzDaneDodat(DaneDodat: String);
var
ii : Integer; { Długość danych}
K,O,D: String;
Pierwsza: integer = 0;
begin
{ii := Length(DanePodst);}
Pierwsza := 1;
K := '';
O := '';
D := '';
for ii:= 1 to Length(DaneDodat) do
begin
if (DaneDodat[ii] = ' ')then
begin
Pierwsza := Pierwsza + 1;
end
else
begin
case Pierwsza of
1:
begin
K := K + DaneDodat[ii];
end;
2:
begin
O := O + DaneDodat[ii];
end;
3:
begin
D := D + DaneDodat[ii];
end ;
end;
end;
end;
Kom := StrToInt(K);
Okn := StrToInt(O);
Drz := StrToInt(D);
end;
procedure Sprawdz;
begin
if Odpowiedz <> '' then
begin
Odpowiedz := Odpowiedz + #10;
end;
if ObwodPas <>
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali.
Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne. To niech się podzieli z tym na forum LivePC.plhttp://www.livepc.pl/viewtopic.php?f=43&t=1060
Kolejne zadanie nosi nazwę Ciastka a jego treść to :
Cytuj:
Zorganizowane zostało ogromne całodniowe przyjęcie, na które zaproszono wiele osób. Każda zaproszona osoba mogła przyjść na przyjęcie i wyjść, kiedy tylko zechciała. Zaproszony został też pan Marek, właściciel cukierni, który często obdarowuje swoich znajomych ciastkami. Na przyjęcie zabrał ze sobą C ciastek, a kiedy tylko dotarł na miejsce, od razu rozdał wszystkim obecnym (nie licząc siebie) jak najwięcej z tych C ciastek i każdemu po tyle samo. Ciastka, które po rozdaniu mu zostały, zjadł, bo bardzo je lubi. Napisz program, który obliczy, ile ciastek zjadł pan Marek.
Wejście
Pierwsza linia zawiera liczbę całkowitą D (1 ≤ D ≤ 10), określającą liczbę zestawów danych. W następnych liniach opisane są kolejno po sobie zestawy danych. W pierwszej linii zestawu danych znajduje się liczba całkowita N (1 ≤ N ≤ 100). Druga linia zestawu danych zawiera N liczb całkowitych rozdzielonych pojedynczymi spacjami: x1, x2, x3, ..., xN (-10 ≤ xi ≤ 10 oraz xi ≠ 0 dla 1 ≤ i ≤ N) oznaczających kolejne zmiany liczby obecnych osób na przyjęciu. Dodatnie xi oznacza, że na przyjęcie przyszło xi osób. Ujemne xi oznacza, że z przyjęcia wyszło -xi osób. Przed pierwszą zmianą liczby obecnych, czyli przed x1, na przyjęciu nie było jeszcze nikogo. Po wszystkich N zmianach liczby obecnych, czyli po xN, na przyjęcie przyszedł pan Marek. W trzeciej linii zestawu danych znajduje się liczba całkowita C (1 ≤ C ≤ 1000) oznaczająca liczbę ciastek, z którymi pan Marek przyszedł na przyjęcie.
Wyjście
W kolejnych liniach dla każdego zestawu danych należy wypisać jedną liczbę całkowitą oznaczającą liczbę ciastek, jakie zjadł pan Marek.
Przykład
Dla danych wejściowych:
3
4
1 3 -4 2
7
3
4 2 -5
8
1
9
14
poprawną odpowiedzią jest:
1
0
5
Wejście
Pierwsza linia zawiera liczbę całkowitą D (1 ≤ D ≤ 10), określającą liczbę zestawów danych. W następnych liniach opisane są kolejno po sobie zestawy danych. W pierwszej linii zestawu danych znajduje się liczba całkowita N (1 ≤ N ≤ 100). Druga linia zestawu danych zawiera N liczb całkowitych rozdzielonych pojedynczymi spacjami: x1, x2, x3, ..., xN (-10 ≤ xi ≤ 10 oraz xi ≠ 0 dla 1 ≤ i ≤ N) oznaczających kolejne zmiany liczby obecnych osób na przyjęciu. Dodatnie xi oznacza, że na przyjęcie przyszło xi osób. Ujemne xi oznacza, że z przyjęcia wyszło -xi osób. Przed pierwszą zmianą liczby obecnych, czyli przed x1, na przyjęciu nie było jeszcze nikogo. Po wszystkich N zmianach liczby obecnych, czyli po xN, na przyjęcie przyszedł pan Marek. W trzeciej linii zestawu danych znajduje się liczba całkowita C (1 ≤ C ≤ 1000) oznaczająca liczbę ciastek, z którymi pan Marek przyszedł na przyjęcie.
Wyjście
W kolejnych liniach dla każdego zestawu danych należy wypisać jedną liczbę całkowitą oznaczającą liczbę ciastek, jakie zjadł pan Marek.
Przykład
Dla danych wejściowych:
3
4
1 3 -4 2
7
3
4 2 -5
8
1
9
14
poprawną odpowiedzią jest:
1
0
5
Ten problem również rozwiązałem w Pascalu. Dostałem za niego 8/10 Pkt , a oto pełny kod:
Kod:
program Ciastka;
{ Ciastka }
{ Michał Komasa }
{ bigkom@gmail.com}
var
IlZest , N , IlGosc , LiCiast: Integer; { Ilość zestawów danych do wprowadzenia } { Ilość wejść wyjść} { Ilość gości } { Liczba ciastek do dyspozycji }
Rotacja, Odpowiedz : String; { Zapisana historia rotacji } { Odpowiedź dla wszystkich zestawów}
Rob: String;
ik,Rob2 : integer;
procedure ObliczIloscGosci;
var
ii,jj : Integer; { Długość danych}
K: array[1..100] of String ;
Pierwsza: integer = 1;
begin
{ii := Length(DanePodst);}
IlGosc := 0;
K[1] := '';
for ii:= 1 to Length(Rotacja) do
begin
if (Rotacja[ii] = ' ')then
begin
Pierwsza := Pierwsza + 1;
K[Pierwsza] := '';
end
else
begin
K[Pierwsza] := K[Pierwsza] + Rotacja[ii];
end;
end;
for jj := 1 to N do begin
IlGosc := IlGosc + StrToInt(K[jj]);
end;
end;
begin
Odpowiedz := '';
readln(IlZest);
for ik := 1 to IlZest do
begin
readln(N);
readln(Rotacja);
ObliczIloscGosci;
readln(LiCiast);
Rob2 := LiCiast mod IlGosc;
Rob := IntToStr(Rob2);
if Odpowiedz <> '' then begin
Odpowiedz := Odpowiedz + #10 + Rob;
end
else begin
Odpowiedz := Rob;
end;
end;
writeln(Odpowiedz);
end.
{ Ciastka }
{ Michał Komasa }
{ bigkom@gmail.com}
var
IlZest , N , IlGosc , LiCiast: Integer; { Ilość zestawów danych do wprowadzenia } { Ilość wejść wyjść} { Ilość gości } { Liczba ciastek do dyspozycji }
Rotacja, Odpowiedz : String; { Zapisana historia rotacji } { Odpowiedź dla wszystkich zestawów}
Rob: String;
ik,Rob2 : integer;
procedure ObliczIloscGosci;
var
ii,jj : Integer; { Długość danych}
K: array[1..100] of String ;
Pierwsza: integer = 1;
begin
{ii := Length(DanePodst);}
IlGosc := 0;
K[1] := '';
for ii:= 1 to Length(Rotacja) do
begin
if (Rotacja[ii] = ' ')then
begin
Pierwsza := Pierwsza + 1;
K[Pierwsza] := '';
end
else
begin
K[Pierwsza] := K[Pierwsza] + Rotacja[ii];
end;
end;
for jj := 1 to N do begin
IlGosc := IlGosc + StrToInt(K[jj]);
end;
end;
begin
Odpowiedz := '';
readln(IlZest);
for ik := 1 to IlZest do
begin
readln(N);
readln(Rotacja);
ObliczIloscGosci;
readln(LiCiast);
Rob2 := LiCiast mod IlGosc;
Rob := IntToStr(Rob2);
if Odpowiedz <> '' then begin
Odpowiedz := Odpowiedz + #10 + Rob;
end
else begin
Odpowiedz := Rob;
end;
end;
writeln(Odpowiedz);
end.
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali.
Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne. To niech się podzieli z tym na forum LivePC.pl http://www.livepc.pl/viewtopic.php?f=43&t=1061
Kolejne zadanie nosi tytuł Detektyw , z którym wydawoło mi się , że szybko sobie poradziłem , ale okazał się mały zonk , bo aczkolwiek na testowych danych program działał poprawnie to mimo przyjęcia go do oceny nie dostałem za niego żadnych punktów, argumuntując że w kążdym z dziesięciu testów była otrzymana zła odpowiedź. Więc nie wiem co źle zrobiłem, pewnie jakaś mała pierdółka jest i przez. Treść zadania :
Cytuj:
Pewien znany, najbardziej skuteczny detektyw Opsslandii prowadzi własne śledztwo w kolejnej kryminalnej sprawie. Podejrzanych jest wielu, a wśród nich dokładnie jeden winny. Każdy z podejrzanych może złożyć (nie musi) kilka zeznań. W jednym zeznaniu podejrzany może wskazać winnego bądź potwierdzić lub zaprzeczyć złożone wcześniej zeznanie dowolnego podejrzanego. Detektyw swoją skuteczność zawdzięcza własnemu systemowi wyszukiwania winnego. Według tego systemu osobą uznaną za winną zostaje ta osoba spośród podejrzanych, dla której liczba osób, które skłamały przy założeniu, że winna jest ta osoba, jest najmniejsza.
Należy wziąć pod uwagę fakt, że dany podejrzany może złożyć wykluczające się zeznania - np. raz twierdzi że winna jest pewna osoba, drugi raz że inna, albo twierdzi że każdy z podejrzanych jest niewinny - wtedy taki podejrzany kłamie.
Napisz program, który wskaże osobę uznaną przez system detektywa za winną. Jeśli jego system uznaje wiele osób za winne, program powinien wskazać wszystkie te osoby.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita D określająca liczbę zestawów danych (1 ≤ D ≤ 10). W kolejnych liniach wejścia występują opisy kolejnych zestawów danych. W pierwszej linii zestawu danych znajdują się oddzielone pojedynczym odstępem dwie liczby całkowite: N, Z (1 ≤ N ≤ 10000, 1 ≤ Z ≤ 20000), określające odpowiednio: liczbę podejrzanych (podejrzanych numerujemy kolejnymi liczbami naturalnymi od 1 do N) oraz liczbę wszystkich złożonych zeznań. W kolejnych Z liniach zestawu występują opisy zeznań w kolejności ich składania - każde w oddzielnej linii. Zeznanie składa się z oddzielonych od siebie pojedynczym odstępem: liczby całkowitej P, znaku C, oraz liczby całkowitej K (1 ≤ P ≤ N). Znak C określa typ zeznania:
znak C równy "W" - oznacza, że podejrzany o numerze P stwierdził, że osoba o numerze K jest winna,
znak C równy "P" - oznacza, że podejrzany P stwierdził, że zeznanie złożone jako K-te jest prawdziwe,
znak C równy "F" - oznacza, że podejrzany P stwierdził, że zeznanie złożone jako K-te jest fałszywe.
Wyjście
W kolejnych liniach, dla każdego zestawu danych, należy wypisać w porządku rosnącym numery osób podejrzanych uznanych przez system jako winne.
Przykład
Dla danych:
2
3 4
1 W 3
2 P 1
3 W 1
2 F 3
3 3
1 W 2
2 W 3
3 W 1
poprawną odpowiedzią jest:
3
1 2 3
Należy wziąć pod uwagę fakt, że dany podejrzany może złożyć wykluczające się zeznania - np. raz twierdzi że winna jest pewna osoba, drugi raz że inna, albo twierdzi że każdy z podejrzanych jest niewinny - wtedy taki podejrzany kłamie.
Napisz program, który wskaże osobę uznaną przez system detektywa za winną. Jeśli jego system uznaje wiele osób za winne, program powinien wskazać wszystkie te osoby.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita D określająca liczbę zestawów danych (1 ≤ D ≤ 10). W kolejnych liniach wejścia występują opisy kolejnych zestawów danych. W pierwszej linii zestawu danych znajdują się oddzielone pojedynczym odstępem dwie liczby całkowite: N, Z (1 ≤ N ≤ 10000, 1 ≤ Z ≤ 20000), określające odpowiednio: liczbę podejrzanych (podejrzanych numerujemy kolejnymi liczbami naturalnymi od 1 do N) oraz liczbę wszystkich złożonych zeznań. W kolejnych Z liniach zestawu występują opisy zeznań w kolejności ich składania - każde w oddzielnej linii. Zeznanie składa się z oddzielonych od siebie pojedynczym odstępem: liczby całkowitej P, znaku C, oraz liczby całkowitej K (1 ≤ P ≤ N). Znak C określa typ zeznania:
znak C równy "W" - oznacza, że podejrzany o numerze P stwierdził, że osoba o numerze K jest winna,
znak C równy "P" - oznacza, że podejrzany P stwierdził, że zeznanie złożone jako K-te jest prawdziwe,
znak C równy "F" - oznacza, że podejrzany P stwierdził, że zeznanie złożone jako K-te jest fałszywe.
Wyjście
W kolejnych liniach, dla każdego zestawu danych, należy wypisać w porządku rosnącym numery osób podejrzanych uznanych przez system jako winne.
Przykład
Dla danych:
2
3 4
1 W 3
2 P 1
3 W 1
2 F 3
3 3
1 W 2
2 W 3
3 W 1
poprawną odpowiedzią jest:
3
1 2 3
Kompletny kod programu :
Kod:
program Detektyw;
var
D,N,Z,jj: integer; { D określająca liczbę zestawów danych (1 ≤ D ≤ 10) } {liczbę podejrzanych (podejrzanych numerujemy kolejnymi liczbami naturalnymi od 1 do N) } {liczbę wszystkich złożonych zeznań.}
Rob : array[1..20000] of record
Kto : integer ;
Co : Char;
Komu : integer;
end;
Oskarzeni : array[1..10000] of record
Winny : Boolean ;
IlOsk : Integer;
Oskarzyl : Integer;
IlPotwier : Integer;
ZaCo : array[1..100] of integer;
end;
Odpowiedz : array[1..10] of String;
NiZ : string;
procedure KasWinny;
var
ii : integer;
begin
for ii := 1 to N do
begin
Oskarzeni[ii].Winny := false;
Oskarzeni[ii].IlOsk := 0;
Oskarzeni[ii].Oskarzyl := 0;
Oskarzeni[ii].IlPotwier := 0;
end;
end;
procedure PobierzDaneNiZ(DanePodst: String);
var
ii : Integer; { Długość danych}
nn,zz: String;
Pierwsza: Boolean;
begin
Pierwsza := true;
nn := '';
zz := '';
for ii:= 1 to Length(DanePodst) do
begin
if (DanePodst[ii] <> ' ') and (Pierwsza = true) then
begin
nn := nn+ DanePodst[ii];
end
else
begin
Pierwsza := false;
zz := zz + DanePodst[ii];
end;
end;
N := StrToInt(nn);
Z := StrToInt(zz);
end;
procedure PobierzZeznania;
var
ii,NrZez : Integer; { Długość danych}
Zez1,Zez3,ZezCzyt: String;
Pierwsza,Druga,Trzecia: Boolean;
begin
for NrZez := 1 to Z do
begin
readln(ZezCzyt);
Pierwsza := true;
Druga := false;
Trzecia := false;
Zez1 := '';
Zez3 := '';
for ii:= 1 to Length(ZezCzyt) do
begin
if (ZezCzyt[ii] <> ' ') and (Pierwsza = true) and (Trzecia = false) and (Druga = false) then
begin
Zez1 := Zez1+ ZezCzyt[ii];
end
else if (ZezCzyt[ii] = ' ') and (Druga = false) and (Trzecia = false) and (Pierwsza = true) then
begin
Druga := true;
end ;
if (ZezCzyt[ii] <> ' ') and (Druga = true) and (Trzecia = false) and (Pierwsza = true) then
begin
Rob[NrZez].Co := ZezCzyt[ii];
Trzecia := true;
end else
if (ZezCzyt[ii] <> ' ') and (Trzecia = true) and (Druga = true) and (Pierwsza = true)then
begin
Zez3 := Zez3 + ZezCzyt[ii];
end;
end;
Rob[NrZez].Kto := StrToInt(Zez1);
Rob[NrZez].Komu := StrToInt(Zez3);
end;
end;
procedure SprawdzZez;
var
ii,kk : integer;
begin
for ii := 1 to Z do
begin
case Rob[ii].Co of
'W':
begin
if (Oskarzeni[Rob[ii].Kto].Oskarzyl <> Rob[ii].Komu) and (Oskarzeni[Rob[ii].Kto].Oskarzyl > 0) then
begin
Oskarzeni[Rob[ii].Kto].Winny:=true;
end
else
begin
Oskarzeni[Rob[ii].Kto].Oskarzyl := Rob[ii].Komu;
Oskarzeni[Rob[ii].Kto].IlPotwier := Oskarzeni[Rob[ii].Kto].IlPotwier + 1;
Oskarzeni[Rob[ii].Kto].ZaCo[Oskarzeni[Rob[ii].Kto].IlPotwier] := ii ;
end;
end;
'P':
begin
Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier := Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier + 1;
Oskarzeni[Rob[Rob[ii].Komu].Kto].ZaCo[Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier] := Rob[ii].Komu ;
end;
'F':
begin
for kk := 1 to Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier do
if Oskarzeni[Rob[Rob[ii].Komu].Kto].ZaCo[kk] = Rob[ii].Komu then
begin
Oskarzeni[Rob[Rob[ii].Komu].Kto].ZaCo[kk] := 0;
end;
end;
end;
end;
for ii := 1 to Z do
begin
if Rob[ii].Co = 'W' then
for kk := 1 to Oskarzeni[Rob[ii].Kto].IlPotwier do
begin
if Oskarzeni[Rob[ii].Kto].ZaCo[kk] > 0 then
begin
Oskarzeni[Rob[ii].Komu].Winny:=true;
end;
end;
end;
end;
procedure ZapiszOdpow( Odp : integer);
var
ii : integer;
begin
for ii := 1 to N do
begin
if Oskarzeni[ii].Winny then
if Odpowiedz[odp] = '' then
begin
Odpowiedz[odp] := IntToStr(ii);
end
else
begin
Odpowiedz[odp] := Odpowiedz[odp] + ' ' + IntToStr(ii);
end;
end;
end;
begin
readln(D);
for jj := 1 to D do
begin
readln(NiZ);
KasWinny;
PobierzDaneNiZ(NiZ);
PobierzZeznania;
SprawdzZez;
ZapiszOdpow(jj);
end;
for jj := 1 to D do
begin
writeln(Odpowiedz[jj]);
end;
end
.var
D,N,Z,jj: integer; { D określająca liczbę zestawów danych (1 ≤ D ≤ 10) } {liczbę podejrzanych (podejrzanych numerujemy kolejnymi liczbami naturalnymi od 1 do N) } {liczbę wszystkich złożonych zeznań.}
Rob : array[1..20000] of record
Kto : integer ;
Co : Char;
Komu : integer;
end;
Oskarzeni : array[1..10000] of record
Winny : Boolean ;
IlOsk : Integer;
Oskarzyl : Integer;
IlPotwier : Integer;
ZaCo : array[1..100] of integer;
end;
Odpowiedz : array[1..10] of String;
NiZ : string;
procedure KasWinny;
var
ii : integer;
begin
for ii := 1 to N do
begin
Oskarzeni[ii].Winny := false;
Oskarzeni[ii].IlOsk := 0;
Oskarzeni[ii].Oskarzyl := 0;
Oskarzeni[ii].IlPotwier := 0;
end;
end;
procedure PobierzDaneNiZ(DanePodst: String);
var
ii : Integer; { Długość danych}
nn,zz: String;
Pierwsza: Boolean;
begin
Pierwsza := true;
nn := '';
zz := '';
for ii:= 1 to Length(DanePodst) do
begin
if (DanePodst[ii] <> ' ') and (Pierwsza = true) then
begin
nn := nn+ DanePodst[ii];
end
else
begin
Pierwsza := false;
zz := zz + DanePodst[ii];
end;
end;
N := StrToInt(nn);
Z := StrToInt(zz);
end;
procedure PobierzZeznania;
var
ii,NrZez : Integer; { Długość danych}
Zez1,Zez3,ZezCzyt: String;
Pierwsza,Druga,Trzecia: Boolean;
begin
for NrZez := 1 to Z do
begin
readln(ZezCzyt);
Pierwsza := true;
Druga := false;
Trzecia := false;
Zez1 := '';
Zez3 := '';
for ii:= 1 to Length(ZezCzyt) do
begin
if (ZezCzyt[ii] <> ' ') and (Pierwsza = true) and (Trzecia = false) and (Druga = false) then
begin
Zez1 := Zez1+ ZezCzyt[ii];
end
else if (ZezCzyt[ii] = ' ') and (Druga = false) and (Trzecia = false) and (Pierwsza = true) then
begin
Druga := true;
end ;
if (ZezCzyt[ii] <> ' ') and (Druga = true) and (Trzecia = false) and (Pierwsza = true) then
begin
Rob[NrZez].Co := ZezCzyt[ii];
Trzecia := true;
end else
if (ZezCzyt[ii] <> ' ') and (Trzecia = true) and (Druga = true) and (Pierwsza = true)then
begin
Zez3 := Zez3 + ZezCzyt[ii];
end;
end;
Rob[NrZez].Kto := StrToInt(Zez1);
Rob[NrZez].Komu := StrToInt(Zez3);
end;
end;
procedure SprawdzZez;
var
ii,kk : integer;
begin
for ii := 1 to Z do
begin
case Rob[ii].Co of
'W':
begin
if (Oskarzeni[Rob[ii].Kto].Oskarzyl <> Rob[ii].Komu) and (Oskarzeni[Rob[ii].Kto].Oskarzyl > 0) then
begin
Oskarzeni[Rob[ii].Kto].Winny:=true;
end
else
begin
Oskarzeni[Rob[ii].Kto].Oskarzyl := Rob[ii].Komu;
Oskarzeni[Rob[ii].Kto].IlPotwier := Oskarzeni[Rob[ii].Kto].IlPotwier + 1;
Oskarzeni[Rob[ii].Kto].ZaCo[Oskarzeni[Rob[ii].Kto].IlPotwier] := ii ;
end;
end;
'P':
begin
Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier := Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier + 1;
Oskarzeni[Rob[Rob[ii].Komu].Kto].ZaCo[Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier] := Rob[ii].Komu ;
end;
'F':
begin
for kk := 1 to Oskarzeni[Rob[Rob[ii].Komu].Kto].IlPotwier do
if Oskarzeni[Rob[Rob[ii].Komu].Kto].ZaCo[kk] = Rob[ii].Komu then
begin
Oskarzeni[Rob[Rob[ii].Komu].Kto].ZaCo[kk] := 0;
end;
end;
end;
end;
for ii := 1 to Z do
begin
if Rob[ii].Co = 'W' then
for kk := 1 to Oskarzeni[Rob[ii].Kto].IlPotwier do
begin
if Oskarzeni[Rob[ii].Kto].ZaCo[kk] > 0 then
begin
Oskarzeni[Rob[ii].Komu].Winny:=true;
end;
end;
end;
end;
procedure ZapiszOdpow( Odp : integer);
var
ii : integer;
begin
for ii := 1 to N do
begin
if Oskarzeni[ii].Winny then
if Odpowiedz[odp] = '' then
begin
Odpowiedz[odp] := IntToStr(ii);
end
else
begin
Odpowiedz[odp] := Odpowiedz[odp] + ' ' + IntToStr(ii);
end;
end;
end;
begin
readln(D);
for jj := 1 to D do
begin
readln(NiZ);
KasWinny;
PobierzDaneNiZ(NiZ);
PobierzZeznania;
SprawdzZez;
ZapiszOdpow(jj);
end;
for jj := 1 to D do
begin
writeln(Odpowiedz[jj]);
end;
end
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali.
Bo moje rozwiązanie rozwiązanie posiada widocznie jakieś błędy. Może ktoś potrafi wskazać mi te błędy ?? To niech się podzieli z tym na forum LivePC.pl http://www.livepc.pl/viewtopic.php?f=43&t=1063
Kolejnym zadaniem z którym miałem spore problemy, bo głównie bo znów zrobiłem gdzieś mały w kodzie błąd i nie mogę dojść do tego dlaczego . W końcu udało się go przeskoczyć , rozwiązać problem. Program dobrze rozwiązuje testowe zadanie , i pozostałe również ale dostałem tylko jeden ponieważ w pozostałych 9 zadaniach testowych został przekroczony limit czasu na wykonywania programu. A oto treść zadania :
Cytuj:
Rozważmy kwadratową planszę z polami o standardowych współrzędnych. Pole o współrzędnych (1, 1) jest zawsze polem startowym. Każde pole ma miejsce na etykietę oznaczającą kierunek (góra, prawo, dół, lewo), lub w przypadku pola końcowego etykietę koniec. Pola na planszy począwszy od pola startowego do pola końcowego tworzą ścieżkę w taki sposób, że pierwszym polem ścieżki jest pole startowe, następnym polem jest pole znajdujące się na planszy najbliżej w kierunku opisanym etykietą pola startowego, i tak dalej aż do pola końcowego (zobacz rysunek 1.).
rysunek 1.
Dwa złośliwe chochliki postanowiły trochę namieszać na planszy. Pierwszy z nich usunął część etykiet z pól należących do ścieżki. Na szczęście usuwał on etykiety w taki sposób, że z dowolnych dwóch sąsiednich (przylegających do siebie bokami) pól ścieżki zniknęła co najwyżej jedna etykieta. Dodatkowo na pewno nie zniknęły etykiety z pól: startowego i końcowego oraz pól które mają więcej niż dwa sąsiednie pola należące do ścieżki.
Drugi złośliwy chochlik wprowadził etykiety na wszystkie pola planszy nienależące do ścieżki w taki sposób, że jeśli w polu z usuniętą (przez pierwszego chochlika) etykietą wstawimy inną etykietę niż usunięta, to idąc w kierunku przez nią wskazywanym wejdziemy na fałszywą ścieżkę, czyli taką, która nie prowadzi do pola końcowego (idąc po niej albo wyjdziemy poza planszę, albo wpadniemy w nieskończoną pętlę - zobacz rysunek 2.).
rysunek 2.
Zadanie
Napisać program, który dla danej planszy z etykietami (będącej wynikiem działania złośliwych chochlików) odtworzy ścieżkę, z której usunięto etykiety.
Wejście
Pierwsza linia wejścia zawiera liczbę zestawów danych C (1 ≤ C ≤ 50). W kolejnych wierszach wejścia znajdują się zestawy danych. Każdy z C zestawów danych składa się z jednego wiersza zawierającego liczbę naturalną N (2 ≤ N ≤ 1000) określającą rozmiar planszy oraz N wierszy składających się z N znaków reprezentujących planszę. Każde pole planszy reprezentowane jest przez jeden ze znaków: g, p, d, l, k (pierwsza litera etykiety pola) lub znaku . (kropki), oznaczającego pole scieżki pozbawione etykiety.
Dane wejściowe składają się co najwyżej z 5000 wierszy.
Dla przykładu plansza z rysunku 2. reprezentowana jest przez zestaw postaci:
4
pplg
.pdg
gd.g
gdpk
Wyjście
Dla każdego zestawu danych należy wypisać K+1 wierszy: w pierwszym powinna się znaleźć liczba K oznaczająca długość ścieżki, a w K kolejnych wierszach powinny zostać wypisane po dwie liczby oznaczające wpółrzędne kolejnych punktów ścieżki.
Przykład
Dla danych wejściowych:
2
4
pplg
.pdg
gd.g
gdpk
6
gldl.k
pgppgg
gpp.pd
.p.ddl
glddpd
p.gppp
poprawną odpowiedzią jest:
8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
4 1
13
1 1
2 1
2 2
1 2
1 3
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
rysunek 1.
Dwa złośliwe chochliki postanowiły trochę namieszać na planszy. Pierwszy z nich usunął część etykiet z pól należących do ścieżki. Na szczęście usuwał on etykiety w taki sposób, że z dowolnych dwóch sąsiednich (przylegających do siebie bokami) pól ścieżki zniknęła co najwyżej jedna etykieta. Dodatkowo na pewno nie zniknęły etykiety z pól: startowego i końcowego oraz pól które mają więcej niż dwa sąsiednie pola należące do ścieżki.
Drugi złośliwy chochlik wprowadził etykiety na wszystkie pola planszy nienależące do ścieżki w taki sposób, że jeśli w polu z usuniętą (przez pierwszego chochlika) etykietą wstawimy inną etykietę niż usunięta, to idąc w kierunku przez nią wskazywanym wejdziemy na fałszywą ścieżkę, czyli taką, która nie prowadzi do pola końcowego (idąc po niej albo wyjdziemy poza planszę, albo wpadniemy w nieskończoną pętlę - zobacz rysunek 2.).
rysunek 2.
Zadanie
Napisać program, który dla danej planszy z etykietami (będącej wynikiem działania złośliwych chochlików) odtworzy ścieżkę, z której usunięto etykiety.
Wejście
Pierwsza linia wejścia zawiera liczbę zestawów danych C (1 ≤ C ≤ 50). W kolejnych wierszach wejścia znajdują się zestawy danych. Każdy z C zestawów danych składa się z jednego wiersza zawierającego liczbę naturalną N (2 ≤ N ≤ 1000) określającą rozmiar planszy oraz N wierszy składających się z N znaków reprezentujących planszę. Każde pole planszy reprezentowane jest przez jeden ze znaków: g, p, d, l, k (pierwsza litera etykiety pola) lub znaku . (kropki), oznaczającego pole scieżki pozbawione etykiety.
Dane wejściowe składają się co najwyżej z 5000 wierszy.
Dla przykładu plansza z rysunku 2. reprezentowana jest przez zestaw postaci:
4
pplg
.pdg
gd.g
gdpk
Wyjście
Dla każdego zestawu danych należy wypisać K+1 wierszy: w pierwszym powinna się znaleźć liczba K oznaczająca długość ścieżki, a w K kolejnych wierszach powinny zostać wypisane po dwie liczby oznaczające wpółrzędne kolejnych punktów ścieżki.
Przykład
Dla danych wejściowych:
2
4
pplg
.pdg
gd.g
gdpk
6
gldl.k
pgppgg
gpp.pd
.p.ddl
glddpd
p.gppp
poprawną odpowiedzią jest:
8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
4 1
13
1 1
2 1
2 2
1 2
1 3
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
Komplety kod programu napisanego w Pascalu. Program działa:
Kod:
program Sciezka;
{$mode objfpc}{$H+}
uses
Classes, SysUtils
{ you can add units after this };
var
Plansza : array[1..1000,1..1000] of record
WartPol : string;
Odwiedzone : boolean;
end;
C,N : Integer; {Liczba zestawów} {Rozmiar Planszy}
kk,ss:integer;
Odpowiedz : array[1..50] of record
LibK : Integer;
Hist : array[1..5000] of record
ii,jj : Integer;
OstOper : String;
end;
end;
Koniec2 : Boolean;
lc1,lc2 : integer;
Byl : array[1..1000,1..1000] of record
BylJuz : Boolean;
end;
procedure WczytajDane;
var
ii,jj : Integer;
Linia: String = '';
begin
readln(N);
if (N >= 2) and (N <= 1000) then begin for ii := 0 to N-1 do begin readln(Linia); for jj := 1 to N do begin Plansza[N - ii,jj].WartPol := Linia[jj]; Plansza[N - ii,jj].Odwiedzone := false; end; end; end; end; function SprawdzSciezke(ii,jj : integer) : boolean; begin SprawdzSciezke := false; Koniec2 := false; for lc1 := 1 to N do for lc2 := 1 to N do Byl[lc1,lc2].BylJuz:= false; REPEAT case (Plansza[ii,jj].WartPol[1]) of 'g' : begin if (ii < byljuz =" false)"> 1) and (Byl[ii-1,jj].BylJuz = false) then
begin
ii := ii - 1;
end
else
begin
SprawdzSciezke := false;
Koniec2 := true;
end;
end;
'l' :
begin
if (jj > 1) and (Byl[ii,jj-1].BylJuz = false) then
begin
jj := jj - 1;
end
else
begin
SprawdzSciezke := false;
Koniec2 := true;
end;
end;
'p' :
begin
if (jj < byljuz =" false)" odwiedzone =" true" koniec2 =" True;" boolean =" false;"> 1) and (Plansza[ii - 1,jj].Odwiedzone = false) and (SprawdzSciezke(ii-1,jj)) then
begin
ii := ii - 1;
end
else if (ii< odwiedzone =" false)"> 2) and (Plansza[ii,jj - 1].Odwiedzone = false) and SprawdzSciezke(ii,jj-1) then
begin
jj := jj - 1;
end
else if (jj < odwiedzone =" false)" koniec =" false" koniec =" True;">= 1) and (C <= 50) then begin; for kk := 1 to C do begin WczytajDane; if ( N >= 2) and (N <= 1000) then ZnajdzKoniec(kk); end; for kk := 1 to C do begin writeln(Odpowiedz[kk].LibK); for ss := 1 to Odpowiedz[kk].LibK do begin writeln(Odpowiedz[kk].Hist[ss].jj,' ',Odpowiedz[kk].Hist[ss].ii); end; end; end; end.
{$mode objfpc}{$H+}
uses
Classes, SysUtils
{ you can add units after this };
var
Plansza : array[1..1000,1..1000] of record
WartPol : string;
Odwiedzone : boolean;
end;
C,N : Integer; {Liczba zestawów} {Rozmiar Planszy}
kk,ss:integer;
Odpowiedz : array[1..50] of record
LibK : Integer;
Hist : array[1..5000] of record
ii,jj : Integer;
OstOper : String;
end;
end;
Koniec2 : Boolean;
lc1,lc2 : integer;
Byl : array[1..1000,1..1000] of record
BylJuz : Boolean;
end;
procedure WczytajDane;
var
ii,jj : Integer;
Linia: String = '';
begin
readln(N);
if (N >= 2) and (N <= 1000) then begin for ii := 0 to N-1 do begin readln(Linia); for jj := 1 to N do begin Plansza[N - ii,jj].WartPol := Linia[jj]; Plansza[N - ii,jj].Odwiedzone := false; end; end; end; end; function SprawdzSciezke(ii,jj : integer) : boolean; begin SprawdzSciezke := false; Koniec2 := false; for lc1 := 1 to N do for lc2 := 1 to N do Byl[lc1,lc2].BylJuz:= false; REPEAT case (Plansza[ii,jj].WartPol[1]) of 'g' : begin if (ii < byljuz =" false)"> 1) and (Byl[ii-1,jj].BylJuz = false) then
begin
ii := ii - 1;
end
else
begin
SprawdzSciezke := false;
Koniec2 := true;
end;
end;
'l' :
begin
if (jj > 1) and (Byl[ii,jj-1].BylJuz = false) then
begin
jj := jj - 1;
end
else
begin
SprawdzSciezke := false;
Koniec2 := true;
end;
end;
'p' :
begin
if (jj < byljuz =" false)" odwiedzone =" true" koniec2 =" True;" boolean =" false;"> 1) and (Plansza[ii - 1,jj].Odwiedzone = false) and (SprawdzSciezke(ii-1,jj)) then
begin
ii := ii - 1;
end
else if (ii< odwiedzone =" false)"> 2) and (Plansza[ii,jj - 1].Odwiedzone = false) and SprawdzSciezke(ii,jj-1) then
begin
jj := jj - 1;
end
else if (jj < odwiedzone =" false)" koniec =" false" koniec =" True;">= 1) and (C <= 50) then begin; for kk := 1 to C do begin WczytajDane; if ( N >= 2) and (N <= 1000) then ZnajdzKoniec(kk); end; for kk := 1 to C do begin writeln(Odpowiedz[kk].LibK); for ss := 1 to Odpowiedz[kk].LibK do begin writeln(Odpowiedz[kk].Hist[ss].jj,' ',Odpowiedz[kk].Hist[ss].ii); end; end; end; end.
Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali.
Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne. To niech się podzieli z tym na forum LivePC.plhttp://www.livepc.pl/viewtopic.php?f=43&t=1064
Zadaniem 5 i zarazem ostatnim za jakie się zabrałem by je rozwiązać , jest zadanie pierwsze z 3 tury czyli Suma dzielników. A o to treść :
Cytuj:
Dana jest liczba naturalna n. Ile wynosi suma wszystkich różnych dzielników liczby n?
Wejście
W pierwszym wierszu wejścia znajdują się oddzielone pojedynczym odstępem dwie liczby naturalne C, M (1 ≤ C ≤ 20000, 1 ≤ M ≤ 1000000000). W kolejnych C wierszach wejścia znajdują się zestawy danych. Każdy z C zestawów danych składa się z jednej linii, która zawiera jedną liczbę naturalną n (1 ≤ n ≤ 1000000000).
Wyjście
Dla każdego zestawu danych, należy wyznaczyć sumę wszystkich różnych dzielników liczby n i wypisać w oddzielnej linii resztę z dzielenia tej sumy przez M (suma wszystkich różnych dzielników liczby n modulo M).
Przykład
Dla danych wejściowych:
4 100
3
4
5
100
poprawną odpowiedzią jest:
4
7
6
17
Wejście
W pierwszym wierszu wejścia znajdują się oddzielone pojedynczym odstępem dwie liczby naturalne C, M (1 ≤ C ≤ 20000, 1 ≤ M ≤ 1000000000). W kolejnych C wierszach wejścia znajdują się zestawy danych. Każdy z C zestawów danych składa się z jednej linii, która zawiera jedną liczbę naturalną n (1 ≤ n ≤ 1000000000).
Wyjście
Dla każdego zestawu danych, należy wyznaczyć sumę wszystkich różnych dzielników liczby n i wypisać w oddzielnej linii resztę z dzielenia tej sumy przez M (suma wszystkich różnych dzielników liczby n modulo M).
Przykład
Dla danych wejściowych:
4 100
3
4
5
100
poprawną odpowiedzią jest:
4
7
6
17
Zadanie wydaje się być totalnie banalnie, i słusznie. No ale co robi tak proste zadanie w 3 turze , ano jeżeli zadanie się wykonało w standardowy sposób jak odrazu przychodzi na myśl , czyli sprawdzeniu wszystkich liczb z zakresu od 1 do n czy są dzielnikami liczby , i sumowaniu ich po drodze, a następnie sprawdzić jaka jest reszta z dzielna tej sumy przez M. No ale taki program dla liczb w granicach miliona liczy około 13 do 15 sekund a max limit w zależności od zestawu danych gdzie jeden zestaw mógł zawierać 500 takich liczb , wynosił od 0.05 s do 2.00 s . Więc co teraz ?? A no należało albo znać , jeżeli się nie zna to zapoznać z jakimś trikiem. No i w poszukiwaniu jakiś skrótów , natrafiłem na takie założenia że, dzielników wystarczy szukać dla części całkowitej pierwiastka z danej liczby i brać do sumy zarówno ten dzielnik, jak i wynik dzielenia liczby przez niego (jeżeli dzielnik jest równy temu pierwiastkowi, to bierze się tylko jego). No więc zrobienie czegoś takiego to nic prostszego . Ale okazało się że to jeszcze za mało. Bo dostałem 5/10 pkt. w 4 miałem przekroczony limit wykonania i w jednym błędną odpowiedź.
Dla porównania daję wpierw rozwiązanie dłużnej liczące :
Kod:
program project1;
{$mode objfpc}{$H+}
var
NN,C,M,SumDzN,ii,kk:integer;
procedure ZnajdzDzielnikiIZsumuj;
var
Pie : integer;
begin
SumDzN:=0;
for ii:=1 to NN do
begin
if((NN mod ii)=0) then
SumDzN:=SumDzN + ii
end
end;
begin
readln(C,M);
for kk:=1 to C do
begin
readln(NN);
ZnajdzDzielnikiIZsumuj;
writeln(SumDzN mod M);
end;
end.
{$mode objfpc}{$H+}
var
NN,C,M,SumDzN,ii,kk:integer;
procedure ZnajdzDzielnikiIZsumuj;
var
Pie : integer;
begin
SumDzN:=0;
for ii:=1 to NN do
begin
if((NN mod ii)=0) then
SumDzN:=SumDzN + ii
end
end;
begin
readln(C,M);
for kk:=1 to C do
begin
readln(NN);
ZnajdzDzielnikiIZsumuj;
writeln(SumDzN mod M);
end;
end.
A teraz z wykorzystaniem opisanego triku :
Kod:
program project1;
{$mode objfpc}{$H+}
var
NN,C,M,SumDzN,ii,kk:integer;
procedure ZnajdzDzielnikiIZsumujOpt;
var
Pie : integer;
begin
SumDzN:=0;
Pie := TRUNC(sqrt(NN));
for ii:=1 to Pie do
begin
if((NN mod ii)=0) then
begin
if ii = sqrt(NN) then
SumDzN:=SumDzN + ii
else
SumDzN:=SumDzN + ii + TRUNC(NN/ii);
end
end
end;
begin
readln(C,M);
for kk:=1 to C do
begin
readln(NN);
ZnajdzDzielnikiIZsumujOpt;
writeln(SumDzN mod M);
end;
end.
{$mode objfpc}{$H+}
var
NN,C,M,SumDzN,ii,kk:integer;
procedure ZnajdzDzielnikiIZsumujOpt;
var
Pie : integer;
begin
SumDzN:=0;
Pie := TRUNC(sqrt(NN));
for ii:=1 to Pie do
begin
if((NN mod ii)=0) then
begin
if ii = sqrt(NN) then
SumDzN:=SumDzN + ii
else
SumDzN:=SumDzN + ii + TRUNC(NN/ii);
end
end
end;
begin
readln(C,M);
for kk:=1 to C do
begin
readln(NN);
ZnajdzDzielnikiIZsumujOpt;
writeln(SumDzN mod M);
end;
end.
Jak widać kod nie znacznie się zmienił za to czasy wykonywania spadły nawet 1000 krotnie dla dużych zestawów danych. Ale to i tak okazało się za mało.
Więc jeżeli ktoś zrobił to inaczej lub w innym języku niech się pochwali.
Bo moje rozwiązanie mimo że jest poprawne , na pewno nie jest optymalne.To niech się podzieli z tym na forum LivePC.plhttp://www.livepc.pl/viewtopic.php?f=43&t=1065
