Sankt-Peterburgskie Olimpiady po Informatike

Zadachi mezhdunarodnoj olimpiady 1990 goda

Pervyj tur: Igra 15
Vtoroj tur: Kartinnaja galereja

Zadacha "Igra 15"

Zadana tablica razmerom 4x4, v kazhdoj kletke kotoroj, krome dvuh, soderzhitsja odno iz chisel ot 1 do 14 (vse chisla raznye). Ostavshiesja dve kletki - pustye. (Primer - tablica 1.)

Tablica 1       Tablica 2
7 3 5 14
  4 9 13
1   2 10
11 8 12 6
1 2 3 4
5 6 7 8
9 10 11 12
13 14    

Pravila peremeschenija. Chislo iz ljuboj kletki mozhet byt' peremescheno po gorizontali ili po vertikali v ljubuju nezanjatuju sosednjuju kletku. Kletka, v kotoroj ranee razmeschalos' chislo, stanovitsja pustoj.

Cel'. Neobhodimo s pomosch'ju ukazannogo pravila vypolnit' po shagam preobrazovanie proizvol'noj ishodnoj tablicy v konechnuju tablicu 2.

Zadanie. Napisat' programmu, kotoraja:

  1. osuschestvljaet vvod s klaviatury ishodnoj tablicy i vyvod ee na jekran (pustye kletki mogut byt' zakodirovany nuljami);
  2. vypolnjaet preobrazovanie vvedennoj tablicy v tablicu 2;
  3. na kazhdom shage vyvodit na jekran sleva variant tablicy do jetogo hoda, sprava - variant tablicy posle hoda i ukazyvaet nomer hoda (1,2,3 i t. d.) tak, chto v konce raboty programmy budet pokazano polnoe chislo sdelannyh hodov;
  4. minimiziruet chislo hodov, neobhodimyh dlja reshenija zadachi.

Zadacha "Kartinnaja galereja"

V kartinnoj galeree kazhdyj storozh rabotaet v techenie nekotorogo nepreryvnogo otrezka vremeni. Raspisaniem storozha nazyvaetsja mnozhestvo par [T1(i), T2(i)] - momentov nachala i konca dezhurstva i-go storozha iz intervala [0; EndTime].

Dlja zadannogo raspisanija strazhi trebuetsja:

a) proverit', v ljuboj li moment vremeni v galeree nahoditsja ne menee dvuh storozhej. Esli uslovie a) ne vypolnjaetsja, to:

b) perechislit' vse intervaly vremeni s nedostatochnoj ohranoj (menee dvuh storozhej);

v) dobavit' naimen'shee chislo storozhej s zadannoj, odinakovoj dlja vseh dlitel'nost'ju dezhurstva, chtoby poluchit' pravil'noe raspisanie (udovletvorjajuschee usloviju a));

g) proverit', mozhno li obojtis' bez dobavlenija novyh storozhej, esli razreshaetsja sdvigat' vremja dezhurstva kazhdogo storozha s sohraneniem vremeni ego dezhurstva;

d) pri polozhitel'nom otvete na punkt g) sostavit' raspisanie s naimen'shim chislom sdvigov.

Vhodnye dannye (vse momenty vremeni zadajutsja v celyh minutah):

Vyhodnye dannye:

  1. otvet na punkt a) v forme da/net;
  2. pri otvete "net" na punkt a) - spisok par (k,l) - nachal i koncov vseh maloohranjaemyh intervalov s ukazaniem chisla storozhej v kazhdom (0 ili 1);
  3. chislo dopolnitel'nyh storozhej i momenty nachala i okonchanija dezhurstva kazhdogo dopolnitel'nogo storozha;
  4. otvet na punkt g) v forme da/net; esli "da", to nomera storozhej, smena kotoryh sdvigaetsja, i znachenija sdvigov;
  5. otvet na punkt d) - naimen'shee chislo storozhej, smena kotoryh sdvigaetsja, ih nomera i znachenija sdvigov.

Primechanie. Programma dolzhna dopuskat' nezavisimoe testirovanie punktov v), g), d).

Используются технологии uCoz