## 620 - Cellular Structure

Moderator: Board moderators

lu shukai
New poster
Posts: 7
Joined: Tue Aug 06, 2002 9:26 am

### 620 - Cellular Structure

program P620;
{\$APPTYPE CONSOLE}
uses
SysUtils;
var
i,n:integer;
arr:array[1..1000] of char;
len:integer;

function iso(i,j:integer):boolean;
begin
if i<=j then begin
iso:=false;
if (i=j) and (arr='A') then
iso:=true
else if (arr[len]='B')and(arr[len-1]='A')and iso(i,j-2) then
iso:=true
else if (arr[1]='B')and(arr[len]='A')and iso(i+1,j-1) then
iso:=true;
end;
end;

procedure slv;
begin
if len<>0 then begin
if (len=1) and (arr[1]='A') then
writeln('SIMPLE')
else if (arr[len]='B')and(arr[len-1]='A')and iso(1,len-2) then
writeln('FULLY-GROWN')
else if (arr[1]='B') and (arr[len]='A') and iso(2,len-1) then
writeln('MUTAGENIC')
else writeln('MUTANT')
end;
end;

begin
for i:= 1 to n do begin
len:=0;
while not eoln do begin
inc(len);
end;
slv;
end;
end.

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Your program couldn't even pass the sample input/output...

brainstorm
New poster
Posts: 1
Joined: Wed May 21, 2003 12:08 pm

### 620 WA

Cannot understand why WA, I've followed the rules of the problem and the test i/o is OK.

[cpp]
#include <iostream>
#include <vector>
#include <string>

using namespace std;

char ew[2000];
void examinar_celula (){

vector<char> cell;
char c;

cin.getline(ew,2000);
int i =0;
while (ew){
cell.push_back(ew);
i++;
}

string celltype;
bool b=false;
bool dp=false;
vector<char>::iterator iter;

if(cell.size()>1){
cell.pop_back();
}
/*
//Another way to archieve the same results commenting the for loop below

if (cell.size()==1){
dp=true;
celltype="SIMPLE";
}

if (*cell.begin()!='B' && *cell.end()=='B' && *(cell.end()-1)=='A'){
dp=true;
celltype="FULLY-GROWN";
}

if (*cell.begin()=='B' && *cell.end()=='A'){
dp=true;
celltype="MUTAGENIC";
}

*/

for (iter=cell.begin(); iter!=cell.end() ;iter++){

dp=false;

if (cell.size()==1 && *cell.begin()=='A'){
celltype="SIMPLE";
dp=true;
break;
}

if (*iter=='B'){
b=true;
}
if (!b && *cell.end()=='B'){
dp=true;
celltype="FULLY-GROWN";
}
if (*cell.begin()=='B'&& b && *cell.end()=='A' ){
dp=true;
celltype="MUTAGENIC";
}
if (!b && *cell.end()=='A'){
dp=true;
celltype="SIMPLE";
}

//if(dp==false){celltype="MUTANT";}
}

if (dp==false){celltype="MUTANT";}
cout << celltype << endl;
return;
}

int main (void) {

int i,n;
cin >> n;

cin.getline(ew,2000);
for (i=0;i<n;i++){
examinar_celula();
}
return 0;
}
[/cpp]

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
OK, maybe you can try these inputs:
10
A
AAB
BAAB
BAABA
BBBBBAABAABAAAA
BAABAAAB
BBAAAABABABABABABAB
BBBBBBBAABAABAAAAABAABA
BBAAABABAABAB
BBABAABABA
SIMPLE
FULLY-GROWN
MUTANT
MUTAGENIC
MUTAGENIC
MUTANT
FULLY-GROWN
MUTAGENIC
FULLY-GROWN
MUTANT
Good Luck!

angga888

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### 620

Since the OJ updated I don't what was going on my code.
Some already AC code being rejudged WA or TLE or even CJ(cannot be judged).

Here is my code of 620.
Don't know why WA.
If an organism were in two stages of growth at the same time the first option from the list above should be given as an answer.
and how should I understand this sentense mean?

is BAABA is MUTAGENIC?(in my code)

The code is deleted after I got AC of this Problem.
Last edited by Zhao Le on Tue Jan 20, 2004 1:59 pm, edited 1 time in total.
AC makes me feels good,
But WA makes me thinks hard.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Hint: You're forgetting to print MUTANT in some of the cases. Check your if-else blocks.

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China
Finally got AC.

but one thing I should make it clear.
MUTANT any other (in case of mutated organisms)
How should I understand this sentence?

if not case MUTAGENIC
then case MUTANT?

if my input is:
1
AA

what output should be?
MUTANT
AC makes me feels good,
But WA makes me thinks hard.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
If it the current cellular structure does not fit into one of the three profiles, then it is listed as MUTANT.

AA is mutant 'cause it's definitely not SIMPLE (only A), and also can't be either FULLY GROWN or MUTAGENIC (which require an odd number of cells anyway.)

Not sure if that makes it any clearer.

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China
AC makes me feels good,
But WA makes me thinks hard.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 620 - getting TLE..

The proportion of TLE for this problem seems to be very low..
..so it infers that either I completely misunderstood the problem or there is a big dent in my code. ----- btw I am getting TLE.

My approach :
[c]
bool valid(int l, int u) {
if( l>=u && str=='A')
return true;
if( u-l > 1 ) {
if( valid(l, u-2) && str=='B' && str[u-1]=='A')
return true;
if( valid(l+1, u-1) && str[l]=='B' && str=='A')
return true;
}
return false;
}
[/c]

I check o like this..
.. is it ok( well it's not otherwise it would have been AC)..

Some hints would be appreciated.

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
1. if the length is even, it is a MUTANT.
2. if the length is 1 and it is not 'A', it is a MUTANT.
3. if the length is 1 and it is 'A', it is a SIMPLE.
4. go through the string of cells from the end, also keep track of your position from the start of the string. loop until you found a MUTANT (those do not fulfill the condition or the start position equals to the end position). // i believe this is what you implemented inside your "valid" function, although it seems that your function is more complicated than it needs to be (ex. evaluating un-necessary stuff and not terminating once you found an error (keep on backtracking)).

ex. - if end == 'B' then end - 1 should be 'A' , if true end -- else MUTANT
- else if end == 'A' then start should be 'B', if true start ++ else MUTANT
5. once the loops end, all you need to do is to check the following conditions:
- if start is not end - 1 , it is a MUTANT
- if the last character of the cell is a 'B', it is a FULLY-GROWN.
- else it is a MUTAGENIC.

hope this helps.
Last edited by wirjawan on Tue Oct 26, 2004 11:10 am, edited 1 time in total.
..

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### thanx

I found my mistake...
.. I made a very stupid mistake

[c]
if( valid(l, u-2) && str=='B' && str[u-1]=='A')
return true;
if( valid(l+1, u-1) && str[l]=='B' && str=='A')
return true;
[/c]

I place the call of the valid function at the end and it got AC in 0 seconds.

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
ah.. good to hear =)
..

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

### 620 - Cellular Structure - Grammar?

Can anybody explain me the grammar here. It is not clear at all to me.
Thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You are given four structures.

Code: Select all

``````1.   A. It is simple stage.
2. OAB. It Is fully-grown stage.
3. BOA. It is mutagenic stage.
4. Not same as 1, 2 or 3.``````
Now you can replace 'O' by any stages(1, 2 or 3). Suppose you are given 'AAB'. The first 'A' represents O from simple stage. So, the total structure matches with the 2nd structure.

Suppose you are given 'BAABA'. You can divide it like 'B', 'AAB', 'A'. Which is a mutagenic stage.

more details...

Code: Select all

``````AAB
A = O
A AB
O AB , fully-grown stage

BAABA
AAB = OAB , fully-grown stage
B AAB A
B  O  A , mutagenic stage.
``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage