Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ctrl-alt-defeat-2019 Revolver C++ 100/100OK 09. maj '19 @ 19:17

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 14/14 3,512 MiB 0,000 s OK
#2 [več] 14/14 3,508 MiB 0,010 s OK
#3 [več] 14/14 3,512 MiB 0,004 s OK
#4 [več] 14/14 3,477 MiB 0,009 s OK
#5 [več] 14/14 3,473 MiB 0,009 s OK
#6 [več] 15/15 3,473 MiB 0,015 s OK
#7 [več] 15/15 3,508 MiB 0,022 s OK

Ocenjevani program (Revolver.cpp):
#include <bits/stdc++.h>

using namespace std;

const double inf=1e20;

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,p;
		scanf("%d%d",&n,&p);
		char s[1000];
		scanf("%s",s);
		int next[n];
		for(int o=0;o<n;o++)
		{
			int cnt=0;
			for(int i=o;;i=(i+1)%n)
			{
				if(s[i]=='*') break;
				cnt++;
			}
			next[o]=cnt;
		}
		int val[23];//n
		for(int i=0;i<23;i++) val[i]=0;
		for(int o=0;o<n;o++)
		{
			for(int i=next[o];i>=0;i--) val[i]++;
		}
		double arr[23];//nx/ny
		arr[22]=-inf;
		for(int i=0;i<22;i++)
		{
			if(val[i+1]==0||val[i]==0) arr[i]=-inf;
			else arr[i]=log((double)val[i+1]/val[i]);
		}
		double dp[p][23];
		int from[p];
		dp[0][0]=arr[0];
		for(int o=1;o<23;o++) dp[0][o]=-inf;
		for(int o=1;o<p;o++)
		{
			for(int i=1;i<23;i++)
			{
				dp[o][i]=dp[o-1][i-1]+arr[i];
			}
			dp[o][0]=-inf;
			for(int i=0;i<23;i++)
			{
				if(dp[o-1][i]>dp[o][0])
				{
					dp[o][0]=dp[o-1][i];
					from[o]=i;
				}
			}
			dp[o][0]+=arr[0];
		}
		double best=-inf;
		int id;
		for(int i=0;i<23;i++)
		{
			if(dp[p-1][i]>best)
			{
				best=dp[p-1][i];
				id=i;
			}
		}
		printf("%.11f\n",exp(best));
		int now=id;
		vector<bool> v;
		for(int i=p-1;i>0;i--)
		{
			if(now>0)
			{
				v.push_back(0);
				now--;
			}
			else
			{
				v.push_back(1);
				now=from[i];
			}
		}
		for(int i=p-2;i>=0;i--)
		{
			if(v[i]==0) printf("FIRE\n");
			else printf("ROLL\n");
		}
	}
}