620 - Cellular Structure

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

620 - Cellular Structure

Post by lu shukai » Sun Sep 08, 2002 2:21 pm

// 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.

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Fri Oct 11, 2002 5:58 pm

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

Post by brainstorm » Wed May 21, 2003 12:34 pm

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]

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Thu Jun 19, 2003 7:44 pm

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! :D

angga888 :lol:

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

620

Post by Zhao Le » Sun Jan 18, 2004 9:09 am

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.
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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon Jan 19, 2004 7:51 pm

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

Post by Zhao Le » Tue Jan 20, 2004 12:10 pm

Finally got AC. :lol:

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

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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed Jan 21, 2004 3:17 am

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

Post by Zhao Le » Thu Jan 22, 2004 4:22 pm

Thanks for your reply.
AC makes me feels good,
But WA makes me thinks hard.

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

620 - getting TLE..

Post by sohel » Mon Oct 25, 2004 4:04 pm

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

Post by wirjawan » Tue Oct 26, 2004 10:55 am

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.
..

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

thanx

Post by sohel » Tue Oct 26, 2004 11:06 am

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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by wirjawan » Tue Oct 26, 2004 11:12 am

ah.. good to hear =)
..

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

620 - Cellular Structure - Grammar?

Post by mamun » Sun Nov 27, 2005 2:27 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Dec 26, 2005 1:14 am

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

Post Reply

Return to “Volume 6 (600-699)”