Pascalis

Gal galit padėti su trečiu uždaviniu? Pats sugalvojau būdą kaip galima rasti salų skaičių, bet jis nėra labai racionalus.

DruskininkaiUzd2008.doc

Aš (turbūt) daryčiau taip:

 

Eini nuo kairio viršutinio krašto į dešinę (priėjęs eilutės galą leidiesi stulpeliu žemyn) ir tikrini kiekvieną langelį.

- Jei jis juodas - eini į kitą ciklą, kuriame su tarkim BFS suskaičiuoji visus tą salą sudarančius langelius ir pažymi juos kaip baltus.

- - Salų skaičių padidini vienetu.

- - Patikrini ar rasta sala neviršijo prieš tai buvusio maksimalaus dydžio. Jei viršijo - pasižymi šios salos dydį kaip maksimalų.

- Jei baltas - einu toliau. B-)

 

Dydis tik 100x100x10=100.000, tad turėtų laisvai visus testus įveikti per mažiau nei sekundę. :D

O ta apačioj sala, kur tokie 2 prisijungę, tai atskira ar vis dėl to reiktų priskaityt prie tos pačios didesnės?

 

(čia šeip, jei ir man tokį tektų spręst kada..)

Aš (turbūt) daryčiau taip:

 

Eini nuo kairio viršutinio krašto į dešinę (priėjęs eilutės galą leidiesi stulpeliu žemyn) ir tikrini kiekvieną langelį.

- Jei jis juodas - eini į kitą ciklą, kuriame su tarkim BFS suskaičiuoji visus tą salą sudarančius langelius ir pažymi juos kaip baltus.

- - Salų skaičių padidini vienetu.

- - Patikrini ar rasta sala neviršijo prieš tai buvusio maksimalaus dydžio. Jei viršijo - pasižymi šios salos dydį kaip maksimalų.

- Jei baltas - einu toliau. :D

 

Dydis tik 100x100x10=100.000, tad turėtų laisvai visus testus įveikti per mažiau nei sekundę. B-)

Būtų gerai jei aš mokėčiau tą grafų teoriją :D

O ta apačioj sala, kur tokie 2 prisijungę, tai atskira ar vis dėl to reiktų priskaityt prie tos pačios didesnės?

Priskaityt prie didesnės. Bent jau pavyzdyje priskaityta. Kaip ir visos kitos įstrižai besijungiančių langelių grupės. :D

 

Būtų gerai jei aš mokėčiau tą grafų teoriją B-)

Na paieškas į gylį ir į plotį reiktų išmokti, norint geriau pasirodyti Kazicko konkurse. :D

Sveiki chebra, nekursiu naujos temos. Yra uždavinių B-)

 

1. Parašykite sakinių seką natūraliojo skaičiaus n pirmajam skaitmeniu rasti.

2. Parašykite sakinių seką kuri patikrina ar natūraliojo skaičiaus n skaitmenys sudaro geometrinę progresiją.

 

Čia būtinai reikia su while ciklu. Iš karto ačiū.

1. Parašykite sakinių seką natūraliojo skaičiaus n pirmajam skaitmeniu rasti.

program prog1;
var x: longint;
begin
readln(x);
while x > 9 do x := x div 10;
writeln(x);
Readln;
end.

 

program prog2;
var x, dal: longint;
k: real;
begin
readln(x);
if (x div 100) = 0 then writeln ('Taip') // Vienaþenklis arba dviþenklis
	else
		begin
			dal := x div 10 mod 10;
			if (dal <> 0) then
				begin
					k := (x mod 10) / dal;
					while (x > 9) and ((x mod 10) = k*(x div 10 mod 10)) do
						x := x div 10;
					if x < 10 then writeln ('Taip')
						else writeln ('Ne');
				end
			else
				writeln('Ne');	  // Jei antras skaitmuo nulis, tai ne
		end;
readln;
end.

Na paieškas į gylį ir į plotį reiktų išmokti, norint geriau pasirodyti Kazicko konkurse. :D

Na nelabai jau spėsiu, penktadienį varau į Druskininkus. Beto Kazicko konkurse spręsti visus uždavinius pakanka mokyklinių žinių (tikėkimės man pakaks) B-)

 

Bėja o koki ten prizai, nes žinau, kad pernai tu kažkuriam konkurse buvai prizininkas :D

Na nelabai jau spėsiu, penktadienį varau į Druskininkus. Beto Kazicko konkurse spręsti visus uždavinius pakanka mokyklinių žinių (tikėkimės man pakaks) :D

Na dėl mokyklinių žinių, tai turbūt priklauso nuo mokyklos, nes mes mokykloje tai dar net failų skaitymo/rašymo nesimokom, tad be tokių žinių tikrai nelabai ką ten išspręstume. B-)

Bėja o koki ten prizai, nes žinau, kad pernai tu kažkuriam konkurse buvai prizininkas :D

Aha, pernai Aukštaitijos regione antrą vietą užėmiau. Prizas lyg ir piniginis buvo, berods 2 ar 3 šimtai litų, tiksliai nepamenu.

O pačiame jau finaliniame etape tai nedalyvavau pernai, nes buvau išvykęs į Baltijos šalių informatikos olimpiadą. :D

Dzūkijos regione šiandien užėmiau antrą vietą :) Dar nelabai suprantu kas atsitiko. Kai Blonskis diplomą teikė net dėkui pasakyti nesugebėjau :D

Dzūkijos regione šiandien užėmiau antrą vietą :D Dar nelabai suprantu kas atsitiko. Kai Blonskis diplomą teikė net dėkui pasakyti nesugebėjau :D

Šaunuolis! Sveikinu. :)

 

Beje, norėdamas šiek tiek pasiruošti ir aš Kazicko konkursui (Aukštaitija, kitą penktadienį, gal kas dalyvausit? :D), parašiau tą programą, kur klausei, tai įdedu, jei kas norės pasinagrinėti: :D

program u3;
type t_map = array[0..101] of array [0..101] of boolean;
var prad: text;
   map: t_map;
   n, i, j, x, y, nr: integer;
   ch: char;
   salu: integer;
   max_saloje: integer;
   kiek_saloje: integer;


procedure ieskom(x,y: integer; var sk: integer);
var i, j: integer;
begin
   sk := sk+1;
   map[x,y] := false;
   for i := -1 to 1 do
       for j := -1 to 1 do
           if(map[x+i,y+j]) then ieskom(x+i,y+j,sk);
end;

begin
   assign(prad, 'U3.txt');
   reset(prad);
   readln(prad, n);

   for nr := 1 to n do
   begin
   { --- Pradinių duomenų skaitymas --- }
       salu := 0;
       max_saloje := 0;
       readln(prad, x, y);
       for i := 1 to x do
           begin
               for j := 1 to y do
                   begin
                       read(prad, ch);
                       if (ch = '1') then map[i,j] := true
                                     else map[i,j] := false;
                   end;
               readln(prad);
           end;
   { --- Lauko rėminimas --- }
       for i := 0 to x+1 do
           begin
               map[i,0] := false;
               map[i,y+1] := false;
           end;
       for j := 0 to y+1 do
           begin
               map[0,j] := false;
               map[x+1,j] := false;
           end;

   { --- Salų skaičiavimas --- }
       for i := 1 to x do
           for j := 1 to y do
               if (map[i,j]) then
                   begin
                       salu := salu+1;
                       kiek_saloje := 0;
                       ieskom(i,j,kiek_saloje);
                       if (kiek_saloje > max_saloje) then max_saloje := kiek_saloje;
                   end;
       writeln(salu, ' ', max_saloje);
   end;
   close(prad);
   Readln;
end.

Negaliu garantuoti, kad tai pats optimaliausias būdas, bet kažko stebuklingai greitesnio nesugalvoju.

Aišku keletas kosmetinių pataisymų šioje programoje tikrai galimi. :)

Beje, norėdamas šiek tiek pasiruošti ir aš Kazicko konkursui (Aukštaitija, kitą penktadienį, gal kas dalyvausit? :)), parašiau tą programą, kur klausei, tai įdedu, jei kas norės pasinagrinėti: :D

 

O gal dalyvauji ir kituose olimpiadose? Nes aš savo rajone antrą vietą užėmiau ir patekau toliau į Šiaulių aps. programuotojų olimpiadą.

Redagavo Sausio 24, 2009 Darexs

Beje, norėdamas šiek tiek pasiruošti ir aš Kazicko konkursui (Aukštaitija, kitą penktadienį, gal kas dalyvausit? :)), parašiau tą programą, kur klausei, tai įdedu, jei kas norės pasinagrinėti: :D

Dėkui, aš pats pasirašiau be rekursijos, bet būtinai pažiūrėsiu ir tavo būdą.

 

 

O gal dalyvauji ir kituose olimpiadose? Nes aš savo rajone antrą vietą užėmiau ir patekau toliau į Šiaulių aps. programuotojų olimpiadą.

 

Kažką painioji (o gal aš), bet po rajoninės būna Respublikinės pirma dalis, kur sprendimus siunti į serverį Vilniuje ir tada geriausių darbų autorius kviečia į finalą. Beje gal žinot kada vyks ta olimpiada, nes http://ims.mii.lt/olimp kažkodėl neveikia.

Beje gal žinot kada vyks ta olimpiada, nes http://ims.mii.lt/olimp kažkodėl neveikia.

Kiek pamenu, vasario 7 d. :)

Kiek pamenu, vasario 7 d. :)

 

Gerai pameni, vasario 7d. vyks antras etapas.