暑期培训第一周组队赛

DNA Sorting

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 9 Accepted Submission(s) : 3

Problem Description

One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.

Input

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output

Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.

Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

////大意是以上面提到的方式排序，安排好序的字符串输出
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct stu
{
	char s[100];
	int cnt;
}arr[100];

int cmp(struct stu a,struct stu b)
{
	//if(a.t==b.t) return 0;
	return a.cnt<b.cnt;//升序 
}
int main()
{
	int m,n;
	int i,j,k,l;
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		scanf("%d%d",&m,&n);
		getchar();		
		for(i=0;i<100;++i)
		{
			arr[i].cnt=0;
		}
		
		for(i=0;i<n;++i)
		{
			scanf("%s",arr[i].s);
		}
		for(i=0;i<n;i++)//题目中提到的方式 把得数存到一个数组里 
		{
			for(k=0;k<m;k++)
			{
				for(j=k;j<m;j++)
				{
					if(arr[i].s[k]>arr[i].s[j])
						arr[i].cnt++;
				}
			}
		}
		sort(arr,arr+n,cmp);
		for(i=0;i<n;++i)
		{
			printf("%s
",arr[i].s);
		}
		
	}
	return 0;
}

Change the ball

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 26 Accepted Submission(s) : 2

Problem Description

Garfield has three piles of balls, each pile has unique color of following: yellow, blue, and red. Now we also know Garfield has Y yellow balls, B blue balls, and R red balls. But Garfield just wants to change all the balls to one color. When he puts two balls of different color togather, the balls then change their colors automatically into the rest color. For instance, when Garfield puts a red one and a yellow one togather, the two balls immediately owns blue color, the same to other situations. But the rule doesn’t work when the two balls have the same color.
Garfield is not able to estimate the minimal steps to achieve the aim. Can you tell him?

Input

For each line, there are three intergers Y, B, R(1<=Y,B,R<=1000),indicate the number refered above.

Output

For each case, tell Garfield the minimal steps to complete the assignment. If not, output the symbol “):”.

Sample Input

1 2 3
1 2 2

Sample Output

):
2

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	int a[3];
	while(scanf("%d%d%d",&a[0],&a[1],&a[2])!=EOF)
	{
		sort(a,a+3);
		int step=0;		
		if((a[1]-a[0])%3==0)
			step=a[1];
		else if((a[2]-a[1])%3==0)
			step=a[2];
		else if((a[2]-a[0])%3==0)
			step=a[2];
		else {
			printf("):
");continue;
		}
		printf("%d
",step);
	}
return 0;
}

ZOJ问题

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 44 Accepted Submission(s) : 4

Problem Description

对给定的字符串(仅仅包括'z','o','j'三种字符),推断他能否AC。

是否AC的规则例如以下：
1. zoj能AC。
2. 若字符串形式为xzojx，则也能AC，当中x能够是N个'o' 或者为空。
3. 若azbjc 能AC，则azbojac也能AC，当中a,b,c为N个'o'或者为空；

Input

输入包括多组測试用例。每行有一个仅仅包括'z','o','j'三种字符的字符串，字符串长度小于等于1000；

Output

对于给定的字符串。假设能AC则请输出字符串“Accepted”，否则请输出“Wrong Answer”。

Sample Input

zoj
ozojo
ozoojoo
oozoojoooo
zooj
ozojo
oooozojo
zojoooo

Sample Output

Accepted
Accepted
Accepted
Accepted
Accepted
Accepted
Wrong Answer
Wrong Answer

//ZOJ问题
//1. zoj能AC。
//2. 若字符串形式为xzojx，则也能AC，当中x能够是N个'o' 或者为空；
//3. 若azbjc 能AC。则azbojac也能AC。当中a,b,c为N个'o'或者为空；
//若azbjc 能AC，则azbojac也能AC
//这里中间加了一个o。右边加了a个o，找到了一个规律。就是：
//a*b==c即Aceeptd，a表示z之前o的个数，  
//b表示zj之间o的个数。c表示j之后o个数   
#include<stdio.h>
#include<string.h>
int main()
{
	int a,b,c,i;//a表示z之前o的个数，
	//b表示zj之间o的个数，c表示j之后o个数 
	char s[1010];
	while(gets(s))
	{
		//a=b=c=0;
		int len=strlen(s);
		
		for(i=0;i<len;i++)
		{
			if(s[i]=='z')//找到z，它前面的都是o 
			   a=i;
			if(s[i]=='j')
			   b=i-a-1;//找到j，算出中间的o 
		}
		c=len-a-b-2;
		
		if(a==0)
		{
			if(b>0&&c==0)
			{
				printf("Accepted
");
			}
			else printf("Wrong Answer
");  
		
		}
		else
		{
			if(a*b==c&&b>0) //b>0一定要加，可能会出现oozj 
			printf("Accepted
");
			else printf("Wrong Answer
");  
		}
		//printf("%d %d %d

",a,b,c);
	}
	return 0;
}
 /*

N！Again

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 24 Accepted Submission(s) : 10

Problem Description

WhereIsHeroFrom:             Zty, what are you doing ?
Zty:                                     I want to calculate N!......
WhereIsHeroFrom:             So easy! How big N is ?
Zty:                                    1 <=N <=1000000000000000000000000000000000000000000000…
WhereIsHeroFrom:             Oh! You must be crazy! Are you Fa Shao?
Zty:                                     No. I haven's finished my saying. I just said I want to calculate N! mod 2009

Hint : 0! = 1, N! = N*(N-1)!

Input

Each line will contain one integer N(0 <= N<=10^9). Process to end of file.

Output

For each case, output N! mod 2009

Sample Input

4 
5

Sample Output

24
120

//2009=7*7*41,41以后的数对2009求余都是0，离散中讲过mod k。mod就是求余的意思 
#include<stdio.h>
int main()
{
	int i,n;
	while(~scanf("%d",&n))
	{
		int s=1;
		if(n>=41) printf("0
");
		else
		{
			for(i=2;i<=n;++i)
			{
				s=(s*i)%2009;
			}
			printf("%d
",s);
		}
		
	}
	return 0;
}

1sting

Time Limit : 5000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 36 Accepted Submission(s) : 10

Problem Description

You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get.

Input

The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.

Output

The output contain n lines, each line output the number of result you can get .

Sample Input

Sample Output

1
2
8

//做完fibonacci和大菲波数就能懂了 

#include<stdio.h>
#include<string.h>
char s[210];
int num[210][1010];
int len;
int main()
{
    int n;
    int i,j;
    memset(num,0,sizeof(num));
    num[1][0]=1;
    num[2][0]=2;
    //int k,l;
    //l=0;
    for(i=3;i<210;i++)
    {
        //k=0;
        for(j=0;j<1000;j++)
        {
            //l=k+num[i-1][j]+num[i-2][j];
            //num[i][j]=l%10;
            //k=l/10;
            num[i][j]+=num[i-1][j]+num[i-2][j];//'+='把我坑慘了 
            if(num[i][j]>=10)
            {
            	num[i][j]-=10;
            	num[i][j+1]+=1;
            }
        }           
    }
    scanf("%d",&n);
    getchar();
    while(n--)
    {    
        scanf("%s",s);
        len=strlen(s);     
		for(i=1000-1;i>0&&num[len][i]==0;--i)//清零 
		;
		  
        for(;i>=0;i--)
           printf("%d",num[len][i]);
        printf("
");
    }
    return 0;
}

Word Amalgamation

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 5 Accepted Submission(s) : 3

Problem Description

In millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program that can unscramble words.

Input

The input contains four parts: 1) a dictionary, which consists of at least one and at most 100 words, one per line; 2) a line containing XXXXXX, which signals the end of the dictionary; 3) one or more scrambled 'words' that you must unscramble, each on a line by itself; and 4) another line containing XXXXXX, which signals the end of the file. All words, including both dictionary words and scrambled words, consist only of lowercase English letters and will be at least one and at most six characters long. (Note that the sentinel XXXXXX contains uppercase X's.) The dictionary is not necessarily in sorted order, but each word in the dictionary is unique.

Output

For each scrambled word in the input, output an alphabetical list of all dictionary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no dictionary words can be formed), output the line "NOT A VALID WORD" instead. In either case, output a line containing six asterisks to signal the end of the list.

Sample Input

tarp
given
score
refund
only
trap
work
earn
course
pepper
part
XXXXXX
resco
nfudre
aptr
sett
oresuc
XXXXXX

Sample Output

score
******
refund
******
part
tarp
trap
******
NOT A VALID WORD
******
course
******

 

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
    char s[10];
    char st[10];//已经排好序的字符串 
   
};
node arr[103];
int cmp(node a,node b)
{
	return strcmp(a.s,b.s)<=0;
}
int main()
{
    char s[10];
    int i,n=0;
    while(scanf("%s",s),strcmp(s,"XXXXXX")!=0)
    {
        strcpy(arr[n].s,s);//这里用得特别好，这样就能够把原来的字符串和如今的字符串分别存入 
        sort(s,s+strlen(s));
        strcpy(arr[n].st,s);
        n++;
    }
    sort(arr,arr+n,cmp);//依照字典顺序将字符串排序 
    bool flag;
    while(scanf("%s",s),strcmp(s,"XXXXXX")!=0)
    {
        sort(s,s+strlen(s));
        flag=0;
        for(i=0;i<n;i++)//全部的都比較一下 
        {
        	if(strcmp(arr[i].st,s)==0)//排序完后比較两都排好序的字符串 
			{
				flag=1;printf("%s
",arr[i].s); 
			}  
        }  
        if(!flag)
        	printf("NOT A VALID WORD
");
        printf("******
");//每次找完一个都要输出这个 
    }
    return 0;
}

kiki's game

Time Limit : 5000/1000ms (Java/Other) Memory Limit : 40000/10000K (Java/Other)

Total Submission(s) : 24 Accepted Submission(s) : 15

Problem Description

Recently kiki has nothing to do. While she is bored, an idea appears in his mind, she just playes the checkerboard game.The size of the chesserboard is n*m.First of all, a coin is placed in the top right corner(1,m). Each time one people can move the coin into the left, the underneath or the left-underneath blank space.The person who can't make a move will lose the game. kiki plays it with ZZ.The game always starts with kiki. If both play perfectly, who will win the game?

Input

Input contains multiple test cases. Each line contains two integer n, m (0<n,m<=2000). the="" input="" is="" terminated="" when="" n="0" and="" m="0." <="" div="">

Output

If kiki wins the game printf "Wonderful!", else "What a pity!".

Sample Input

Sample Output

What a pity!
Wonderful!
Wonderful!

#include<stdio.h>
int main()
{
	int m,n;
	while(scanf("%d%d",&m,&n),m+n)
	{
		if(m%2==0||n%2==0) printf("Wonderful!
");
		else printf("What a pity!
");
	}
	return 0;
}

/*
我们把Win的地方标记成W，Lose的地方标记成L
W	W	W	W	W	W	W	W
L	W	L	W	L	W	L	W
W	W	W	W	W	W	W	W
L	W	L	W	L	W	L	W
W	W	W	W	W	W	W	W
L	W	L	W	L	W	L	W

我们能够找到规律，当m%2==0||n%2==0，就Win了
*/

叠筐

Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 52 Accepted Submission(s) : 11

Problem Description

须要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。

这个工作如今要让计算机来完毕。得看你的了。

Input

输入是一个个的三元组，各自是，外筐尺寸n（n为满足0<n<80的奇整数）。中心花色字符，外筐花色字符。后二者都为ascii可见字符；< div="">

Output

输出叠在一起的筐图案，中心花色与外筐花色字符从内层起交错相叠，多筐相叠时，最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行间隔。

Sample Input

11 B A
5 @ W

Sample Output

 AAAAAAAAA 
ABBBBBBBBBA
ABAAAAAAABA
ABABBBBBABA
ABABAAABABA
ABABABABABA
ABABAAABABA
ABABBBBBABA
ABAAAAAAABA
ABBBBBBBBBA
 AAAAAAAAA 

 @@@ 
@WWW@
@W@W@
@WWW@
 @@@

#include<stdio.h>
char map[100][100];
int main()
{
    int n,i,j,mark;
    char a,b,t,flag=0;
    while(~scanf("%d %c %c",&n,&a,&b))
    {
        if(flag) putchar('
');
        flag=1;
        if((n-1)%4)//推断哪个在最外面，这个是找规律 
        {
            t=a;
            a=b;
            b=t;
        }
        t=a,mark=1;//t和mark的初始化 
        for(i=0;i<=n/2;i++)
        {
            t=a;
            mark=1;
            for(j=0;j<n;j++)
            {
                if(n!=1&&i==0&&(j==0||j==n-1))//注意n==1的时候
                {
                    putchar(' ');
                    map[i][j]=' ';
                    continue;
				}
                map[i][j]=t;
                putchar(t);
                if(i>j||j>=(n-1)-i)//这也是找规律，什么时候要变 
                {
                    if(mark)//轮流变化
                    {
                        t=b;
                        mark=0;
                    }
                    else
                    {
                        t=a;
                        mark=1;
                    }
                }
            }
            putchar('
');
        }
        for(i=n/2-1;i>=0;i--)
        {
            for(j=0;j<n;j++)
            {
                printf("%c",map[i][j]);
            }
            putchar('
');
        }
    }
    return 0;
}

I Love You Too

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 11 Accepted Submission(s) : 5

Problem Description

This is a true story. A man showed his love to a girl,but the girl didn't replied clearly ,just gave him a Morse Code:
****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/ He was so anxious that he asked for help in the Internet and after one day a girl named "Pianyi angel" found the secret of this code. She translate this code as this five steps:
1.First translate the morse code to a number string:4194418141634192622374
2.Second she cut two number as one group 41 94 41 81 41 63 41 92 62 23 74,according to standard Mobile phone can get this alphabet:GZGTGOGXNCS

3.Third she change this alphabet according to the keyboard:QWERTYUIOPASDFGHJKLZXCVBNM = ABCDEFGHIJKLMNOPQRSTUVWXYZ
So ,we can get OTOEOIOUYVL
4.Fourth, divide this alphabet to two parts: OTOEOI and OUYVL, compose again.we will get OOTUOYEVOLI
5.Finally,reverse this alphabet the answer will appear : I LOVE YOU TOO

I guess you might worship Pianyi angel as me,so let's Orz her.
Now,the task is translate the number strings.

Input

A number string each line(length <= 1000). I ensure all input are legal.

Output

An upper alphabet string.

Sample Input

4194418141634192622374
41944181416341926223

Sample Output

ILOVEYOUTOO
VOYEUOOTIO

#include<stdio.h>
#include<string.h>
int i,len,j;
char s1[1010],s2[1010];
char s[11][5]={"_","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
char str[]={"QWERTYUIOPASDFGHJKLZXCVBNM"};
char s3[1010],s4[1010];
char res[1010];
int main()
{	
	while(gets(s1))
	{
		len=strlen(s1);
		for(i=0,j=0;i<len;i+=2)//数字转换为字母 
		{
			s2[j++]=s[s1[i]-'0'-1][s1[i+1]-'0'-1];
		}
		int k;
		for(i=0;i<j;++i)//依照题目给的方式进行字符变化 
		{
			for(k=0;k<26;++k)
				if(str[k]==s2[i])
				{
					s1[i]='A'+k;break;
				}
		}
		len=len/2+1;
		for(i=0;i<len/2;++i)//把一个字符串分成两 
		{
			s3[i]=s1[i];
		}
		s3[i]='';
		int t=i;
		for(j=0;i<len-1;++i)
		{
			s4[j++]=s1[i];
		}
		s4[j]='';
		int l1=strlen(s3),l2=strlen(s4);
		
		int flag=1;
		i=0,j=0;
		char ch;
		while(s4[i]!='')//轮流存到res数组里 
		{			
			if(!flag)
			{
				flag=1;
				ch=s4[i];
				++i;
				//if(s4[i]=='') continue;
			}
			else
			{
				flag=0;
				ch=s3[i];
				
			}
			
			res[j++]=ch;
		}
		if(l1!=l2) res[j++]=s3[i];
		/*
		k=0;
		for(i=0;i<j;++i,k+=2)
		{
			res[k]=s3[i];
			res[k+1]=s4[i];			
		}
		for(;i<t;++i)
		{
			res[k]=s3[i];
			++k;
		}
		*/
		for(i=j-1;i>=0;--i)
		{
			printf("%c",res[i]);
		}
		puts("");
	}
	return 0;
}

数塔

Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 15 Accepted Submission(s) : 11

Problem Description

在讲述DP算法的时候。一个经典的样例就是数塔问题，它是这样描写叙述的：

有例如以下所看到的的数塔。要求从顶层走究竟层，若每一步仅仅能走到相邻的结点。则经过的结点的数字之和最大是多少？

已经告诉你了。这是个DP的题目，你能AC吗?

Input

输入数据首先包含一个整数C,表示測试实例的个数，每一个測试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度。接下来用N行数字表示数塔，当中第i行有个i个整数。且全部的整数均在区间[0,99]内。

Output

对于每一个測试实例，输出可能得到的最大和，每一个实例的输出占一行。

Sample Input

Sample Output

#include<stdio.h>
#define Max(a,b) (a)>(b)?(a):(b)

int a[100][110];
int main()
{
	
	int i,j;
	int t,n,m;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		
		for(i=1;i<=n;++i)//把数存入 
		{
			for(j=1;j<=i;++j)
			scanf("%d",&a[i][j]);			
		}
		for(i=n;i>1;--i)//从下往上加 
		{
			for(j=i;j>1;--j)
			{
				a[i-1][j-1]+=Max(a[i][j],a[i][j-1]);//把以下两个的较大的一个和上面那个数相加 
			}
		}
		printf("%d
",a[1][1]);//一直加到第一个，输出答案 
	}
	return 0;
}