620 - Cellular Structure

[lu shukai]

// I always get wa please help
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
readln(n);
for i:= 1 to n do begin
len:=0;
while not eoln do begin
inc(len);
read(arr[len]);
end;
slv;
readln;
end;
end.

[cytse]

Your program couldn't even pass the sample input/output...

[brainstorm]

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]

OK, maybe you can try these inputs:

10
A
AAB
BAAB
BAABA
BBBBBAABAABAAAA
BAABAAAB
BBAAAABABABABABABAB
BBBBBBBAABAABAAAAABAABA
BBAAABABAABAB
BBABAABABA

And the answers:

SIMPLE
FULLY-GROWN
MUTANT
MUTAGENIC
MUTAGENIC
MUTANT
FULLY-GROWN
MUTAGENIC
FULLY-GROWN
MUTANT

Good Luck!

angga888

[Zhao Le]

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.
Thanks in advance.

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.

[UFP2161]

Hint: You're forgetting to print MUTANT in some of the cases. Check your if-else blocks.

[Zhao Le]

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

[UFP2161]

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]

Thanks for your reply.

[sohel]

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]

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.

[sohel]

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.

Nevertheless, thanks for your reply.

[wirjawan]

ah.. good to hear =)

[mamun]

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

[Jan]

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.