939 - Genes

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

Moderator: Board moderators

Post Reply
User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

939 - Genes

Post by uDebug » Fri May 16, 2014 1:14 pm

Here's some input / output I found useful during testing / debugging.

Input:

Code: Select all

17
Zara Elizabeth
Cooper dominant
Trong-Phe non-existent
Maya Aaraadhanaa
Albert Robert
Elizabeth Maya 
Suzanne Albert
John Alberta
Cooper Elizabeth
Suzanne Alberta
Elizabeth Robert
Suzanne dominant
John recessive
John Albert
Albert Maya
Trong-Phe Aaraadhanaa
Zara dominant
AC Output:

Code: Select all

Aaraadhanaa recessive
Albert dominant
Alberta dominant
Cooper dominant
Elizabeth dominant
John recessive
Maya dominant
Robert dominant
Suzanne dominant
Trong-Phe non-existent
Zara dominant
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 939 - Genes

Post by dibery » Wed Jan 28, 2015 4:16 pm

Got WA, passed the cases above.

Please help, thanks.

Here's my code:

Code: Select all

#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#define child gene[i]
using namespace std;

int main()
{
	int people, next[3][3] = { { 0, 2, 0 }, { 2, 1, 1 }, { 0, 1, 2 } }; // Gene to next generation
	string type[] = { "non-existent", "dominant", "recessive" };

	while( cin >> people )
	{
		map<string,int> family;
		map<string,string> one;
		set<string> all;
		string gene[ people ], name[ people ];

		for( int i = 0; i < people; ++i )
		{
			cin >> name[ i ] >> gene[ i ];
			if( find( type, type+3, gene[ i ] ) == type+3 )
				all.insert( gene[ i ] );
			else
				family[ name[ i ] ] = find( type, type+3, gene[ i ] ) - type;
		}

		while( !all.empty() )
			for( int i = 0; i < people; ++i )
				if( find( type, type+3, child ) == type+3 && all.find( name[ i ] ) == all.end() )
					if( family.find( child ) == family.end() )
						family[ child ] = family[ name[ i ] ], one[ child ] = name[ i ];
					else if( one[ child ] != name[ i ] )
						family[ child ] = next[ family[ child ] ][ family[ name[ i ] ] ], all.erase( child );

		for( map<string,int>::iterator i = family.begin(); i != family.end(); ++i )
			cout << i->first << ' ' << type[ i->second ] << endl;
	}
}
Life shouldn't be null.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 939 - Genes

Post by brianfry713 » Thu Jan 29, 2015 1:59 am

Try only reading N once.
Check input and AC output for thousands of problems on uDebug!

hala33
New poster
Posts: 1
Joined: Thu Jul 21, 2016 12:44 pm

Re: 939 - Genes

Post by hala33 » Thu Jul 21, 2016 12:49 pm

I have passed the test cases you put and u debug test cases but still wrong answer dont know why? any help please?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Genes {
static TreeMap<String, String> result;static TreeMap<String, String> condition;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
result=new TreeMap<String,String>();
int n=Integer.parseInt(bf.readLine());
condition =new TreeMap<String,String>();
HashMap<String, parent> children= new HashMap<String,parent>();
for (int i = 0; i < n; i++) {
StringTokenizer st=new StringTokenizer(bf.readLine());
String first=st.nextToken();
String second=st.nextToken();
if(second.equals("non-existent") ||
second.equals("recessive") || second.equals("dominant")){
condition.put(first, second);
}
else{
if(children.containsKey(second)){
parent p=children.get(second);
p.m=first;
children.put(second, p);
extraCalc(second,p.f,p.m);
}
else{
parent p=new parent();
p.f=first;
children.put(second, p);
}
}
}
for(Map.Entry<String,parent> entry : children.entrySet()) {
if(!result.containsKey(entry.getKey())){
extraCalc(entry.getKey(),entry.getValue().f,entry.getValue().m);
}

}
for(Map.Entry<String,String> entry : condition.entrySet()) {
result.put(entry.getKey(), entry.getValue());
}
for(Map.Entry<String,String> entry : result.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getValue());
}
}
public static void extraCalc(String ch,String f,String m){
String first=condition.get(f);
String second=condition.get(m);
if(first==null)
first=result.get(f);
if(second==null)
second=result.get(m);
if(first==null || second==null){
return;
}
// boolean has_gene = false;
// if (!first.equals("non-existent") && !second.equals("non-existent")) {
// has_gene = true;
// } else if (first.equals("dominant") || second.equals("dominant")) {
// has_gene = true;
// }
//
// if (has_gene) {
// if (first.equals("dominant") && second.equals("dominant")) {
// result.put(ch,"dominant");
// } else if (first.equals("dominant") && second.equals("recessive")) {
// result.put(ch,"dominant");
// } else if (first.equals("recessive") && second.equals("dominant")) {
// result.put(ch,"dominant");
// } else {
// result.put(ch,"recessive");
// }
// } else {
// result.put(ch,"non-existent");
// }
//System.out.println(entry.getKey()+" "+first+" "+second);
if(first.equals("recessive") && second.equals("recessive")) {
result.put(ch, "recessive");
}
else if (first.equals("dominant")){
if(second.equals("dominant") || second.equals("recessive"))
result.put(ch, "dominant");
else
result.put(ch, "recessive");
}
else if(second.equals("dominant")){
if(first.equals("recessive"))
result.put(ch, "dominant");
else
result.put(ch, "recessive");
}
else if(first.equals("recessive") && second.equals("recessive")){
result.put(ch, "recessive");
}
else
result.put(ch, "non-existent");

}
}

class parent{
String f,m;
public parent(){

}
public parent(String ff,String mm){
f=ff;
m=mm;
}
}

Post Reply

Return to “Volume 9 (900-999)”