Takze zadanie:
Ve vstupním textovém souboru sparse.in je posloupnost čtvercových matic celých čísel. Všechny matice mají rozměr 1000000x1000000.
Každá matice je určena takto: První řádek ve vstupním souboru pro danou matici začíná znakem '#', za kterým následuje pořadové číslo matice. Pak následuje blíže neurčený počet řádků, které obsahují všechny nenulové prvky matice. Každý z těchto řádků začíná mezerou (nebo tabelátorem), a pak následují tři celá čísla (řádek, sloupec, hodnota) oddelená mezerami. Každý z těchto řádků tedy reprezentuje jeden nenulový prvek matice. Zadání každé matice končí řádkem, který začíná znakem '#'. Poté může následovat další matice. Vstupní posloupnost matic je ukončena řádkem, který začíná znakem '@'.
Úkolem je vypočítat součet zadaných matic a výsledek zapsat do výstupního textového souboru sparse.out. Pokud je však nějaká matice obsažena ve vstupních datech vícekrát, do výsledného součtu se započítá pouze jednou!
Formát výstupního textového souboru bude podobný jako formát vstupních dat. Výstupní soubor bude obsahovat tolik řádků, kolik bude nenulových prvků výsledného součtu matic. Na každém řádku budou tři celá čísla (řádek, sloupec, hodnota) oddělená mezerami analogicky jako ve vstupním souboru.
[/color]
Prvky jednotlivých matic nemusí být ani ve vstupním, ani ve výstupním souboru nijak uspořádány.
Následující příklad obsahuje deset matic ve vstupním souboru, ale do výsledného součtu se započítá pouze osm z nich, protože matice s pořadovým číslem #1 a #3 jsou totožné (tudíž se do součtu započítá pouze jedna z nich), podobně také matice #5 a #9. Matice #8 obsahuje samé nuly.
Příklad vstupu:
#1
1 1 1
2 2 2
1000000 1000000 1000000
1 100 100
2 100 100
3 100 99
#
#2
1 1 1
2 2 2
1000000 1000000 1000000
1 100 100
2 100 100
3 100 100
#
#3
1 1 1
2 2 2
1000000 1000000 1000000
1 100 100
2 100 100
3 100 99
#
#4
100 100 1
#
#5
100 100 2
#
#6
100 100 3
#
#7
100 100 4
#
#8
#
#9
100 100 2
#
#10
100 100 5
#
@
Správný výstup:
1 1 2
1 100 200
2 2 4
2 100 200
3 100 199
100 100 15
1000000 1000000 2000000
MOJ PROGRAM:
Kód: Vybrať všetko
program ridke_matice;
type spoj=^seznam;
seznam=record
radek:longint;
sloupec:longint;
hod:longint;
dalsi:spoj;
dolu:spoj;
end;
var start:spoj;
prvni:spoj;
ins,kam:text;
slovo, tslovo:string;
x,y,value,i:longint;
code: integer;
procedure PrevedNaTriCisla (s: string; var x,y,value :longint);
var i,code:integer;
temp:string;
begin
i:=0;
x:=-1; y:=-1;
temp:='';
repeat
i:=i+1;
if((temp <> '') and (s[i] = ' ')) then
begin
if(x=-1) then
val(temp, x, code);
if(y=-1) then
val(temp, y, code);
temp:='';
end
else
if(s[i] <> ' ') then
temp:=temp + s[i];
until (i=Length(s));
val(temp, value, code);
end;
procedure pripoj (dalsiradek:boolean;var zacatekmatice:spoj;x,y,value:longint);
{dalsiradek mi urci ci ma pripojit krabicku na dalsi riadok alebo pokr v matici na zacatek matice}
var kam,last,zacatekradku:spoj;
begin
last:=nil; zacatekradku:=nil;kam:=nil;
if (zacatekmatice <> nil) then
begin
zacatekradku:=zacatekmatice;
{zac.rad je ukazatel na zacatek posledniho radku}
while (zacatekradku^.dolu <>nil) do zacatekradku:=zacatekradku^.dolu;
last:=zacatekradku;
{last je ukazatel na posledny prvok posledneho radku}
while (last^.dalsi<>nil) do last:=last^.dalsi;
end
else
last:=nil;
new (kam);
kam^.radek:=x;
kam^.sloupec:=y;
kam^.hod:=value;
kam^.dalsi:=nil;
kam^.dolu:=nil;
if (last <>nil) then
begin
if (dalsiradek) then
zacatekradku^.dolu:=kam {pridam ako novy riadok}
else
last^.dalsi:=kam; {pridam na konec}
end;
if (zacatekmatice=nil) then zacatekmatice:=kam;
if (start=nil) then start:=kam;
{start nastavim na prvy prvok prvej matice}
end;
procedure secti (var zaciatok:spoj);
var i,j,k:longint;
prvok:spoj;
last,zac,pom,pocet,index:spoj;
begin
prvok:=zaciatok;
zac:=zaciatok^.dolu;
pom:=zaciatok^.dolu;
index:=zaciatok^.dolu;
pocet:=zaciatok;
i:=0;
while pocet<>nil do begin
inc (i);
pocet:=pocet^.dolu;
end;
last:=zaciatok;
for j:=1 to (i-1) do last:=last^.dolu;
repeat
while prvok<>nil do begin
while zac<>nil do begin
while (prvok^.radek<>pom^.radek) and
(prvok^.sloupec<>pom^.sloupec) and
(pom<>nil) do
pom:= pom^.dalsi;
if pom=nil {dosli sme sa na konec} then
begin
zac:=zac^.dolu;
pom:=zac;
end
else begin
prvok^.hod:=(prvok^.hod)+(pom^.hod);
pom^.radek:=-1;
pom^.sloupec:=-1;
zac:=zac^.dolu;
pom:=zac;
end;
end;
prvok:=prvok^.dalsi;
zac:=index;
end;
prvok:=index;
index:=index^.dolu;
zac:=index;
until prvok=last;
end;
procedure spojenie (var zaciatok:spoj);
var i,j:integer;
pom,zac,ukaz:spoj;
begin
zac:=zaciatok;
pom:=zac;
ukaz:=zac^.dolu;
while (ukaz<>nil) do
begin
while (pom<>nil) do pom:=pom^.dalsi;
pom:=ukaz;
zac^.dolu:=nil;
zac:=ukaz;
ukaz:=ukaz^.dolu;
end;
end;
procedure porovnaj (var zaciatok:spoj);
var pom1,pom2,chod,zac1,zac2,ukaz1,ukaz2:spoj;
i,j,k:integer;
begin
pom1:=zaciatok;
pom2:=zaciatok^.dolu;
zac1:=pom1;
zac2:=pom2;
chod:=pom2;
ukaz1:=pom1;
ukaz2:=pom2;
while ukaz1<>nil do begin
while ukaz2<>nil do begin
i:=0;
j:=0;
pom1:=ukaz1;
pom2:=ukaz2;
while pom1^.dalsi<>nil do
begin
pom1:= pom1^.dalsi;
{zistim zda jsou velikosti } inc(i);
{matic rovnake tj.i=j} end;
while pom2^.dalsi<>nil do
begin
pom2:=pom2^.dalsi;
inc (j);
end;
if i=j then {potrebujem porovnat prvky}
begin{je tu moznost ze sa budu rovnat}
k:=0;
zac1:=ukaz1;
zac2:=ukaz2;
chod:=ukaz2;
while (zac1^.radek=zac2^.radek) and
(zac1^.sloupec=zac2^.sloupec) and
(zac1^.hod=zac2^.hod) do
inc (k); {pocitaj kolko hodnot sa rovna}
if k=i then {oni sa rovnaju}
begin
while chod<>nil do
begin
chod^.hod:=0;
chod:=chod^.dalsi;
end;
end;
ukaz2:=ukaz2^.dolu;
end;
ukaz1:=ukaz1^.dolu;
ukaz2:=ukaz1^.dolu;
end;
end;
end;
procedure vypis (var zaciatok:spoj);
var chod:spoj;
begin
chod:=zaciatok;
while (chod<>nil) do begin
if (chod^.radek<>-1) then
begin
writeln (kam,chod^.radek,' ',chod^.sloupec,' ',chod^.hod);
chod:=chod^.dalsi;
end
else
chod:=chod^.dalsi;
end;
end;
begin
start := nil;
prvni := nil;
assign (ins,'sparse.in');
assign (kam,'sparse.out');
reset (ins);
rewrite (kam);
repeat
readln(ins, slovo);
if (slovo[1]='#') then
begin
i:=0;
repeat
readln(ins, tslovo);
if(tslovo<>'#') then
begin
i:= i + 1;
prevednatricisla (tslovo,x,y,value);
if(i=1) then
Pripoj (true, prvni, x, y, value) {novy radek}
else
Pripoj (false, prvni, x, y, value); {pridej na konec}
end;
until (tslovo='#');
end;
until (slovo='@');
close(ins);
prvni:=start;
porovnaj (start);
secti (start);
spojenie (start);
Vypis (start);
close (kam);
end.keby to niekomu pomohlo:
Záznam o vyhodnocení
Compiling... OK
Test 1... <init> <run> RE:Runtime error 201: Range check error
Test 2... <init> <run> RE:Runtime error 201: Range check error
Test 3... <init> <run> RE:Runtime error 201: Range check error
