* Uždavinukai Codeforces ir pnš.
* Savo užduotys
BENDRAI
Šiuo laikotarpiu mažai programavau, dar mažiau - gilinausi ar skaičiau literatūros/tutorialų. Dalyvavau Codeforces platformos renginiuose. Rudens pradžioj poroj OpenCup'o kontestų. Tebesprendžiu viską Perl kalba. Rezultatai vidutiniški, nesama lygio pakylėjimo. Netgi pablogėjimas lyginant šių metų su praeitų metų Codeforces reitingu. Vieną dieną ėmiau ir suprogramavau "žodžių kryžiuoklį" - skirtą kryžiažodžiams sudaryt.
UŽDAVINUKAI
Codeforces patikdavo eilutiniai uždaviniai. Ir patiko vienas dvimačio masyvo uždavinys: Stačiakampėje matricoje (iki 50x50) taškai tai - vanduo, grotelės - žemyno dalis. Reikia užpilti tiek ežerų, kad liktų tik K, ir sunaudoti kuo mažiau žemių.
Sprendžiau nuoseklia paieška ir bfs'u. Nuoseklia paieška randu tašką (vandens telkinio dalį), ir sukuriu masyvą šiam vandens telkiniui, į masyvą push'inu keturių gretimų langelių koordinates. Ir tęsiu su šio masyvo elementais tą patį. Jeigu koordinatė išeina iš stačiakampio ribų - reiškia susiliejimą su vandenynu = ne ežeras. Vėl nuoseklia paieška ieškau taško. Visus surastus ežerus surikiuoju pagal plotą, ir užpilu mažiausius.
Rinktinės reguliariosios išraiškos iš įvairių Codeforces uždavinių:
Uždavinyje, kur visus masyvo elementus
reikėjo suporuot į vienodas sumas:
0 while s/\b(\d+)((?: \d+)*) ((??{ $each - $1 }))\b/ (push @pairs, "$1 $3"), $2 /e;
Uždavinys - ar tai veidrodinis palindromas? (sprendimas rekursinis):
$F = 1; $F &&= f( <> ); print ! $F ? "NIE" : "TAK"; sub f { my ($A) = shift; $A =~ s/\B.*\B// &&$&&& ( $F &&= f($&) ); $F &&= $A =~ /bd|db|pq|qp|^([ovwxAHIMOT-Y])\1?$/; }
Uždavinys apie masyvo kairiųjų elementų naikinimą, priklausomai nuo c: s/.*(\b\d+) (\d+\b)(??{ $2 - $1 <= $c })//;
(nepraėjo: TLE#55; o su non-greedy '.*?' -
gavosi Perl bug'as (Can't COERCE unknown...),
pranešiau, bet yra žinomas)
Uždavinys - vietoje klaustukų įrašyti raides taip (jei įmanoma),
kad eilutėje būtų 26-ių raidžių nuoseklus substringas,
turintis savyje visas abėcėlės raides.
$c = $_ = <>; while( /(?=(.{26}))/g ){ next if ($L = $1) =~ /(\w).*\1/; $L =~ s/\?/$_/ for grep $L !~ /$_/, 'A'..'Z'; substr $c, pos, 26, $L; $c =~ y/?/X/; $f = 1; last; } print $f ? $c : -1
Uždavinys. Ar tų pačių metų iš eilės einančių dviejų mėnesių
pirmosios dienos gali būti duotomis dvejomis
savaitės dienomis (nekeliamuosiuose metuose)?
($f, $s) = map s/..\K.*//sr, <>;
print qw(NO YES)[ ("motuwethfrsasu" x 2) =~ /$f((..){2,3})?(?<=$s)/ && 1 ]
OpenCup'e GP_of_SPb patiko uždavinys apie laikmatį. Yra juosta, sujungta ratu, ant kurios kas 12 langelių nupaišytos padalos. Viso 12 x 60 = 720 padalų = 60 minučių. Ties kas penkta padala yra nupaišytas minučių skaičius: ..., 5, 0, 55, 50, ..., 10, 5, 0, 55, ... . Stebėtojas gauna tik laikmačio langelio vaizdą, kuris yra 60 x 12 matmenų (tik užapvalinti kampai užtemdyti). Tikslus laikas yra ties langelio viduriu. Iš langelio vaizdo reikia pasakyti tikslų laiką (laikmačio tikslumu, t.y. 5 sek).
Pvz. įėjimo duomenys:
-------X..........XX..........XX..........XX.........-------
----..XX..........XX..........XX..........XX..........XX----
-..........................................................-
X..................................................XXXXXXX..
XX.................................................XX.......
XX.................................................XXXXXX...
XX......................................................XX..
XX......................................................XX..
XX.................................................XX...XX..
-...................................................XXXXX..-
----....................................................----
-------..............................................-------
(paveikslėlyje matosi 10-uko fragmentas ir pilnas penketukas)
Atsakymas: 07:05 (t.y. 7 min, 5 s)
Programos pagrindinis fragmentas:
#!/usr/bin/perl
use warnings;
use strict;
my $i;
my @A;
while(<DATA>){
chomp;
/\d/ ? $i = $& : push @{ $A[$i] }, $_;
}
chomp( @_ = <> );
my $regex = join ".{721}", map { s/\./\\./gr =~ y/-/./r } @_[0..9];
my @L;
push @L, ('.' x 5 . ( 'X' x 2 . '.' x 10 ) x 64 . 'X' x 2 . '.' x 5) x 2;
push @L, '.' x length $L[0];
for my $i ( 'a26', 0, 'a48', (map { (split //, $_ * 5), 'a44' } reverse 2 .. 11), 'a4', 5, 'a52', 0, 'a26' ){
for my $j (0 .. 6){
$L[$j + 3] .= $i =~ /a(\d+)/ ? '.' x $1 : $A[$i][$j]
}
}
my $L = join "\n", @L;
$L =~ s/$regex.*//s or print "NOOOOO!\n";
my $sec5 = (720 - length $L) % 720;
printf "%02d:%02d\n", (int $sec5 / 12), 5 * ($sec5 % 12);
__DATA__
0
.XXXXX..
XX..XXX.
XX.XXXX.
XXXX.XX.
XXX..XX.
XXX..XX.
.XXXXX..
........
<...>
(http://ideone.com/4MDCaC)
SAVO UŽDUOTYS
Sudariau žodžių kryžiuoklį. Jis veikia lėtai, nes atlieką daug perrinkimo. Veikimo laikas berods didėja ^2.5, didėjant kryžiuojamų žodžių skaičiui.
Normaliai veikia su iki ~20 žodžių.
Įsimena žodžius. Tada ilgiausią deda horizontaliai. Vėliau perrenka visus kitus žodžius, bandydamas sukryžiuoti, gaunant kuo daugiau susikirtimų, ir kuo mažesnį naują kryžiažodžio plotą (apimantįjį stačiakampį).
Pvz. išvestis:
V V
* V * V
H * * * * * * * * * V *
* * * H * * * * * * * * *
* H * * * * * * * * * * * * * *
* * * H * * * * * * *
* H * * * * * * * * * * * * *
* H * * * * * * * *
* * *
H * * * * * * * * *
H * * * * * *
[lietuvos upė]
[saugos prietaisas]
[gėlė]
[riešutas]
[spalva]
[naminis žinduolis]
[mėnuo]
[rusijos miestas]
[transporto priemonė]
[savaitės diena]
[vasaros šventė]
[medis]
[plėšri žuvis]
