Na wstępie.....

Witam wszystkich odwiedzających.

Do moich hobby należy testowanie oprogramowania a przede wszystkim , śledzenie rozwoju alternatywnych systemów operacyjnych. Z tego faktu będzie wynikała tematyka moich wypocin. Również będę chciał w tym miejscu zaprezentować swoje osiągnięcia, jak i porażki.

sobota, 20 grudnia 2008

Motorola ROKR Z6

Od dziś jestem , póki co :) , szczęśliwym posiadaczem Motoroli ROKR Z6. Pierwsze wrażenia, są jak najbardziej pozytywne , po prostu telefonik daje radę :). Jak to coś wygląda ... ?? A tak ...:

Image


Parametry które posiada ten telefon nie mogły być gorsze od posiadanego już Sony Ericssona K750i i pochodne. Czyli takie standardy jak:

* Aparat 2 MB piksele - jakoś zdjęć znacznie lepsza niż w K750i
* Lampa "błyskowa" - znacznie jaśniej świeci.
* Obsługa kart pamięci - w przypadku motoroli to micro-SD , SE wiadomo MSproduo. Oba teoretycznie obsługują do 2 GB , ale w praktyce da się więcej wycisnąć :).
* Odtwarzacz muzyki - ale to nie jest byle co jak w "soniaczu", tylko porządny Player kompatybilny z Windows Media Player 10,11 , obsługujący pliki zakodowane w : DRM, MP3, AAC, AAC+, AAC+, AMR NB, WAV, XMF.
* Odtwarzać Video - naturalnie lepszy niż w soniaczu (MPEG 4 3GPP, h.263)
* USB 2.0 pozwala na bardzo szybką wymianę muzyki – przykładowo przesłanie 500 piosenek zajmuje ok. 15 minut.
* Bluetooth Stereo v2.0 profil A2DP

Ale to są pierdoły , które w zasadzie każdy telefon musi posiadać, lecz oczywiście faktem jest że, jedni mają lepiej to zaimplementowane inni gorzej. Więc co go wyróżnia od zwykłych teflonów :

* Procesor: ARM 11- Zegar procesora: 500 MHz !! i 64 MB RAM !! To już jak na telefon jest sporo. Niedawno instalowałem Xp na kopie z procesorem o taktowaniu 466 Mhz i 64 MB pamięci operacyjnej. Oczywiście po sporym odpluskwianiu systemu, działała do dzisiaj w miarę przyzwoicie, do Worda i przeglądania News starcza w zupełności, nawet pasjans nie tnie :).

* A teraz najlepsze : System operacyjny zainstalowany na nim to Linux!! 8) , mój następny telefon miał mieć Linux na pokładanie , i tak się stało :)

Image


A jak wygląda cena , hmmm no fakt nabyłem go po cenie znacznie niższej niż cena rynkowa i to prawie 70% taniej. Trafiłem na dobrą promocję w moim ulubionym Hiper Markecie :P . Więc jak by nie było patrzeć jego okazyjna cena , jak najbardziej skłaniała do zakupu :).

Dodam że telefon jest telefonem typowo muzycznym, więc w zestawie dostajemy wypasione słuchawki oraz 1 GB kartę pamięci :).

Więcej parametrów technicznych :

dane podstawowe:
System 850 900 1800 1900
Waga (g) 105
Szerokość (mm) 45
Wysokość (mm) 105
Grubość (mm) 16
Maksymalny czas rozmów (min) 420 (7 h)
Maksymalny czas czuwania (h) 400 (16.7 dni)
Pojemność 780

wyświetlacz:
Kolorowy
Liczba kolorów 256 tys.
Rozdzielczość ekranu 240 x 320 px
Liczba ekranów 1

wiadomości:
Słownik T9
MMS
Klient pocztowy email

pamięć:
Pamięć wbudowana (MB) 64
Karta pamięci

pozostałe:
Gry
CSD
GPRS
EDGE
Odtwarzanie mp3

komunikacja:
Bluetooth
Przeglądarka WAP
Klient pocztowy email
Przeglądarka HTML,XHTML

kamera:
Wbudowany aparat cyfrowy
Lampa błyskowa (flash)
Maks. rozdzielczość zdjęcia 1600x1200 px
Nagrywanie filmów

oprogramowanie:
Java
Kalendarz
Zegarek
Budzik
Kalkulator
Dyktafon

funkcje głosowe:
Wybieranie głosowe
System głośnomówiący
Odtwarzanie mp3
Dyktafon

Oficjalna strona telefonu :
http://www.motorola.com/consumers/v/ite ... ocaleId=33

Coś po Polsku:
http://manager.money.pl/hitech/telefony ... ,1810.html

niedziela, 14 grudnia 2008

III Internetowe Mistrzostwa Polski w Programowaniu

Jako że III Internetowe Mistrzostwa Polski w Programowaniu dobiegają końca postanowiłem się pochwalić tym co udało mi się zrobić. Jest tego niewiele i różnej jakości wykonania. Ale to na co mi czas pozwalał to zrobiłem. Pierwsze zadanie to : Wejście Mikołaja. A o to treść:

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


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. 8) 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 :

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


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.


Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali. 8) 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



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
.


Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali. 8) 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.).

Image

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.).

Image
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.


Jeżeli ktoś zrobił inaczej lub w innym języku niech się pochwali. 8) 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ść :

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


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.


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.


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. 8) 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