Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 08.11.2003, 19:15   #16
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by Boyov
A chto sobstvenno effectivno ???



Vot original'naya zadacha
http://neerc.ifmo.ru/past/2002/problems/folding.htm

Tam ob ogranicheniyax vaabshe ne skazano, (eto otnositsya i ko vsem ostal'nim zadacham 2002 goda) ,navernoe nado polagat' chto ix net .
The input file contains a single line of characters from 'A' to 'Z' with at least 1 and at most 100 characters.

a eto - ne ogranichenie? )))))))
sobstwenno gorosja otsjuda i nado nachinat' ))
ty mozhesh sebe pozwolit' neodnokratno proskanirowat' fajl, kazhdyj raz szhimaja ocherednuju porciju dannyh



real'no - u tebja
k alfawitu A-Z dobawljajutsja simwoly а,б,в,ф,г,е... и т.д., kotorye fakticheski predstawljajut iz sebja -
а === 10(AY)
б === 2(EPRST)

i tak dalee i na kazhdom prohode tebe nuzhno szhimat' stroku sostojashuju iz
A-Zа-я
Reply With Quote
Old 09.11.2003, 11:55   #17
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by nm
The input file contains a single line of characters from 'A' to 'Z' with at least 1 and at most 100 characters.

a eto - ne ogranichenie? )))))))
sobstwenno gorosja otsjuda i nado nachinat' ))
ty mozhesh sebe pozwolit' neodnokratno proskanirowat' fajl, kazhdyj raz szhimaja ocherednuju porciju dannyh



real'no - u tebja
k alfawitu A-Z dobawljajutsja simwoly а,б,в,ф,г,е... и т.д., kotorye fakticheski predstawljajut iz sebja -
а === 10(AY)
б === 2(EPRST)

i tak dalee i na kazhdom prohode tebe nuzhno szhimat' stroku sostojashuju iz
A-Zа-я
Thanks
Reply With Quote
Old 10.11.2003, 17:42   #18
Школьник
 
Join Date: 04 2002
Location: Vanadzor
Posts: 227
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default solution

PHP Code:
SOLUTION for "Folding" problem for NEERC'2002 }
{ (C) Roman Elizarov, 2002 }

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 65520,0,655360}
program FOLDING_SOLUTION;

const
  MAX_N = 100;

type
  TArray = array[1..MAX_N, 1..MAX_N] of integer;
  PArray = ^TArray;

var
  s: string;
  n, i, j, k, l, lr, x, p, q, ofs: integer;
  a, op: PArray;
  min, bestop, tmp: integer;
  c: char;
  ok: boolean;

procedure recwrite(i, j: integer);
var
  bestop, l, x: integer;
begin
  bestop := op^[i, j];
  if bestop = 0 then begin
    for l := i to j do
      write(s[l]);
  end else if bestop > 0 then begin
    recwrite(i, bestop);
    recwrite(bestop + 1, j);
  end else begin
    l := -bestop;
    x := (j - i + 1) div l;
    write(x, '
(');
    recwrite(i, i + l - 1);
    write('
)');
  end;
end;

begin
  { Allocate memory }
  new(a);
  new(op);
  { Open input/output }
  assign(input, '
folding.in'); reset(input);
  assign(output, '
folding.out'); rewrite(output);
  { Read }
  readln(s);
  n := length(s);
  { Solve }
  for i := 1 to n do begin
    a^[i, i] := 1;
    op^[i, i] := 0;
  end;
  for l := 2 to n do { lenght of subsequences to optimize }
    for i := 1 to n - l + 1 do begin { from s[i] }
      j := i + l - 1; { to s[j] }
      min := l;
      bestop := 0;
      { Try concatenation }
      for k := i to j - 1 do begin
        tmp := a^[i, k] + a^[k + 1, j];
        if tmp < min then begin
          min := tmp;
          bestop := k;
        end;
      end;
      { Try repeating }
      for lr := 1 to l div 2 do { length of repeating seq }
        if l mod lr = 0 then begin
          x := l div lr; { repeat count }
          ok := true;
          for p := 1 to lr do begin
            ofs := i + p - 1;
            c := s[ofs];
            for q := 2 to x do begin
              inc(ofs, lr);
              if s[ofs] <> c then begin
                ok := false;
                break;
              end;
            end;
            if not ok then
              break;
          end;
          if ok then begin
            tmp := 3 + a^[i, i + lr - 1];
            if x >= 10 then
              inc(tmp);
            if x >= 100 then
              inc(tmp);
            if tmp < min then begin
              min := tmp;
              bestop := -lr;
            end;
          end;
        end;
      { assign result }
      a^[i, j] := min;
      op^[i, j] := bestop;
    end;
  { Write }
  recwrite(1, n);
  writeln;
end. 

im mot pascal chka, teseq dzez mot ashxatum a?
Reply With Quote
Old 10.11.2003, 17:44   #19
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default Re: solution

.........skipped


fu polnyj perebor
plz uvelichte limit do 1000 simwolow i posmotrim kak ono budet rabotat'
Reply With Quote
Old 10.11.2003, 18:24   #20
Школьник
 
Join Date: 04 2002
Location: Vanadzor
Posts: 227
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

verjapes es im algoritmov areci!!!


http://www.gushar.com/folding.php?NE...NEERCYESYESYES


Reply With Quote
Old 10.11.2003, 18:55   #21
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by strax.
verjapes es im algoritmov areci!!! :)


http://www.gushar.com/folding.php?NE...NEERCYESYESYES


;)
imho neprawil'no rabotaet :) na wot takoj stroke :)

wot tebe raz stroka
NEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABBNEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABB

i rezul'tat -
2(2(NEER8(CYLKA)NEER5(CYLKA))BB)

dobavim s konca k uzhe sushestwujushemu BB - ABBABBABBABBA i tak mnogo raz -wobshem wot zdes' rezul'tirujushaja stroka


NEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABBNEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBA

poluchaetsja wot chto :)
2(NEER8(CYLKA)NEER5(CYLKA))BB2(NEER8(CYLKA)NEER5(CYLKA))30(BBA)

chto garantirowanno neprawilono :)
dolzhno pouchitsja

2(2(NEER8(CYLKA)NEER5(CYLKA))BB)A29(BBA)


za praiwll'nost' chisla 29 -ne ruchajus'

wsjacheskih bug-ow :))))
Reply With Quote
Old 12.11.2003, 10:54   #22
Школьник
 
Join Date: 04 2002
Location: Vanadzor
Posts: 227
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

nm
ha , &isht es asum, sxal ka mech@, bayc im grac principov chem karogh uxxel.

chnayac vor im graci aravelutyun@ nranum a vor input text-i chapi vra limit chka drac.
Reply With Quote
Old 12.11.2003, 18:40   #23
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by strax.
nm
ha , &isht es asum, sxal ka mech@, bayc im grac principov chem karogh uxxel.

chnayac vor im graci aravelutyun@ nranum a vor input text-i chapi vra limit chka drac.

moje delo - skazat' :)
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 09:56.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.