列表

详情

NC17492. Rock-Paper-Scissors Tournament

描述

You have found an ancient record about a rock-paper-scissors tournament. There are N = 2n players in the tournament and the tournament is played in a single-elimination format. The players are numbered from 1 to N inclusive. There are at most 32 players in the tournament.

The tournament consists of n - 1 rounds. In the first round, player 2i - 1 will play against player 2i for all 1 ≤ i ≤ 2n - 1. The loser of each round is eliminated. The process repeats with the winner of the game between players 2i - 1 and 2i relabelled as player i until only one participant remain. That participant is the winner of the tournament.

In ancient times, the people are not very clever. You know from your history textbook that there are 3 types of people : one who always plays Rock, one who always plays Scissors, and one who always plays Paper. We denote them by R, S, P respectively for convenience.

In the record, it is stated that participant i is of type si. Unfortunately, some records are not clear and thus you can't determine which type some participants are. Thus, you replace their type with a question mark instead.

Therefore, the record looks like a string of N characters, s = s1s2...sN, where si denotes the type of participant i, or is equal to '?' (without quotes) if the type is unknown.

After that, you calculated the number of ways A, B, C the question marks can be replaced with one of the characters R, S or P so that the winner of the tournament is of type R, S, P respectively. (Note that paper beats rock, rock beats scissors and scissors beats paper)

The next day, you realized that the paper containing the string s is gone. However, you still remember the values of A, B, C. Can you find a string s with length ≤ 32 such that the number of ways to fill in the question marks with one of the letters R, S or P so that a player of type R, S and P wins the tournament is A, B, C respectively?

输入描述

The first line of input contains a single integer T (1 ≤ T ≤ 50).

The next T lines contain three space-separated integers each, A, B, C (1 ≤ A, B, C ≤ 332).

输出描述

For each testcase, output a single line consisting of a string s that satisfies the conditions. The length of s must be a power of 2 between 1 and 32 inclusive. Each character of s should be either 'R', 'S', 'P' or '?' (without quotes). If there are multiple solutions, you may output any of them. If no such string satisfying the conditions exist, output a single line consisting of the word "Impossible" (without quotes, case-sensitive) instead.

示例1

输入: 

3
1 2 6
3 5 7
1 1 1

输出: 

RR?P?PRP
Impossible
?

说明:

For the first testcase, the only way for a R-type guy to win the tournament is when the question marks are filled in this way : {RRSPSPRP}

After the first round, the remaining participants are {RSSP}.

After the second round, the remaining participants are {RS}.

After the last round, the remaining participant is {R}, as desired.

There are 2 and 6 ways to fill in the question marks for a S-type and P-type player to win respectively.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 1288ms, 内存消耗: 41756K, 提交时间: 2018-08-14 00:22:21 

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef __int128 int128;
int T;
struct node
{
	LL x,y,z;
	char s[17];
};
char s[1100];
vector<node> f[2],sp;
set<pair<int,pair<int,int> > > tt;
map<pair<int,pair<int,int> >,string> S,SS;
string change(char s[])
{
	int n=strlen(s);
	string res="";
	for (int i=0;i<n;i++)
		res=res+s[i];
	return res;
}
int p;
void init()
{
	node tmp;
	tmp.x=1,tmp.y=tmp.z=0,tmp.s[0]='R',tmp.s[1]=0,f[0].push_back(tmp);
	tmp.y=1,tmp.x=tmp.z=0,tmp.s[0]='S',tmp.s[1]=0,f[0].push_back(tmp);
	tmp.z=1,tmp.x=tmp.y=0,tmp.s[0]='P',tmp.s[1]=0,f[0].push_back(tmp);
	tmp.x=tmp.y=tmp.z=1,tmp.s[0]='?',tmp.s[1]=0,f[0].push_back(tmp);
	S[make_pair(1,make_pair(0,0))]="R";
	S[make_pair(0,make_pair(1,0))]="S";
	S[make_pair(0,make_pair(0,1))]="P";
	S[make_pair(1,make_pair(1,1))]="?";
	for (int i=0;i<4;i++)
	{
		f[p^1].clear();
		tt.clear();
		for (int j=0;j<f[p].size();j++)
			for (int k=0;k<f[p].size();k++)
			{
				LL ax=f[p][j].x,ay=f[p][j].y,az=f[p][j].z;
				LL bx=f[p][k].x,by=f[p][k].y,bz=f[p][k].z;
				LL dx=ax*bx+ax*by+bx*ay;
				LL dy=ay*by+ay*bz+az*by;
				LL dz=az*bz+az*bx+bz*ax;
				if (!tt.count(make_pair(dx,make_pair(dy,dz))))
				{
					tt.insert(make_pair(dx,make_pair(dy,dz)));
					int len=strlen(f[p][j].s);
					node tmp;
					tmp.x=dx,tmp.y=dy,tmp.z=dz;
					for (int i=0;i<len;i++)
						tmp.s[i]=f[p][j].s[i],tmp.s[i+len]=f[p][k].s[i];
					tmp.s[len+len]=0;
					f[p^1].push_back(tmp);
					S[make_pair(dx,make_pair(dy,dz))]=change(tmp.s);
					if (i==3) SS[make_pair(dx,make_pair(dy,dz))]=change(tmp.s);
				}
			}
		p^=1;
	}
	for (int i=0;i<f[p].size();i++)
		if (f[p][i].x==0||f[p][i].y==0||f[p][i].z==0) sp.push_back(f[p][i]);
	for (int i=0;i<sp.size();i++)
		for (int j=i+1;j<sp.size();j++)
		{
			LL ax=sp[i].x,ay=sp[i].y,az=sp[i].z;
			LL bx=sp[j].x,by=sp[j].y,bz=sp[j].z;
			LL dx=ax*bx+ax*by+bx*ay;
			LL dy=ay*by+ay*bz+az*by;
			LL dz=az*bz+az*bx+bz*ax;
			S[make_pair(dx,make_pair(dy,dz))]=change(sp[i].s)+change(sp[j].s);
		}
}
LL a,b,c;
//  (x+y)   x     0   = a
//        (y+z)   y   = b
//    z         (z+x) = c	
void work()
{
	int128 aa=a,bb=b,cc=c;
	int inf=1;
	for (int i=1;i<=16;i++)
		inf*=3;
	for (int i=0;i<f[p].size();i++)
	{
		int128 x=f[p][i].x,y=f[p][i].y,z=f[p][i].z;
		if (x==0||y==0||z==0) continue;
		int128 d=(x+y)*(y+z)*(z+x)+x*y*z;
		int128 ax=aa*(y+z)*(z+x)+x*y*cc-x*bb*(z+x);
		int128 ay=bb*(x+y)*(z+x)+y*z*aa-y*cc*(x+y);
		int128 az=cc*(x+y)*(y+z)+x*z*bb-z*aa*(y+z);
		if (ax%d||ay%d||az%d) continue;
		ax/=d,ay/=d,az/=d;
		if (ax<0||ay<0||az<0||ax>inf||ay>inf||az>inf) continue;
		if (SS.count(make_pair(int(ax),make_pair(int(ay),int(az)))))
		{
			cout<<change(f[p][i].s)<<SS[make_pair(int(ax),make_pair(int(ay),int(az)))]<<endl;
			return;
		}
	}
	cout<<"Impossible"<<endl;
}
		
int main()
{
	init();
	scanf("%d",&T);
	while (T--)
	{
		scanf("%lld %lld %lld",&a,&b,&c);
		if (S.count(make_pair(a,make_pair(b,c))))
		{
			cout<<S[make_pair(a,make_pair(b,c))]<<endl;
			continue;
		}
		work();
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 136ms, 内存消耗: 4584K, 提交时间: 2018-08-10 11:44:20 

#include <bits/stdc++.h>
#define N 100010
#define inf 43046721 
using namespace std;

struct info{
	int r,s,p;
	const bool operator <(const info t) const{
		if (r!=t.r) return r<t.r;
		if (s!=t.s) return s<t.s;
		return p!=t.p;
	}
};

map<vector<long long>,string> mp[5];
int tes;
long long a,b,c;

void work()
{
	if (a<=inf&&b<=inf&&c<=inf)
		for (int i=0;i<5;i++) if (mp[i].count(vector<long long>{a,b,c})){
			cout<<mp[i][vector<long long>{a,b,c}]<<endl;
			return;
		}
	
	__int128 r,s,p,r0,s0,p0,R,S,P,d;
	for (map<vector<long long>,string>::iterator i=mp[4].begin();i!=mp[4].end();i++){
		r=(i->first)[0];s=(i->first)[1];p=(i->first)[2];
		r0=a;s0=b;p0=c;
		d=r*s*p+(r+s)*(r+p)*(s+p);
		R=r0*(s+p)*(r+p)+s0*(-r)*(r+p)+p0*r*s;
		S=r0*s*p+s0*(p+r)*(s+r)+p0*(-s)*(s+r);
		P=r0*(-p)*(p+s)+s0*p*r+p0*(r+s)*(p+s);
        if (R<0||S<0||P<0) continue;
		if (R%d||S%d||P%d) continue;
		R/=d;S/=d;P/=d; 
        if (R>inf||S>inf||P>inf) continue;
		if (mp[4].count(vector<long long>{(long long)R,(long long)S,(long long)P})){
			cout<<i->second<<mp[4][vector<long long>{(long long)R,(long long)S,(long long)P}]<<endl;
			return;
		}
	}
	puts("Impossible");
}

void init()
{
	int i;
	map<vector<long long>,string>::iterator j,k;
	vector<long long> l,r;
	for (i=0;i<5;i++) mp[i].clear();
	mp[0][vector<long long>{1,1,1}]="?";
	mp[0][vector<long long>{1,0,0}]="R";
	mp[0][vector<long long>{0,1,0}]="S";
	mp[0][vector<long long>{0,0,1}]="P";
	for (i=0;i<4;i++)
		for (j=mp[i].begin();j!=mp[i].end();j++)
			for (k=mp[i].begin();k!=mp[i].end();k++){
				l=j->first;
				r=k->first;
				mp[i+1][vector<long long>{l[0]*r[0]+l[0]*r[1]+l[1]*r[0],l[1]*r[1]+l[1]*r[2]+l[2]*r[1],l[2]*r[2]+l[2]*r[0]+l[0]*r[2]}]=j->second+k->second;
			}
}

int main()
{
	init();
	scanf("%d",&tes);
	while (tes--){
		scanf("%lld%lld%lld",&a,&b,&c);
		work();
	}
}

上一题

© 2025 nowcoder.com