Rezultati

Up. imeNalogaJezikRezultatČas oddaje
scoreoutofboundsexception-2019 Revolver C++ 100/100OK 09. maj '19 @ 18:54

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 14/14 3,254 MiB 0,000 s OK
#2 [več] 14/14 3,160 MiB 0,000 s OK
#3 [več] 14/14 3,164 MiB 0,000 s OK
#4 [več] 14/14 3,164 MiB 0,000 s OK
#5 [več] 14/14 3,164 MiB 0,000 s OK
#6 [več] 15/15 3,254 MiB 0,000 s OK
#7 [več] 15/15 3,254 MiB 0,000 s OK

Ocenjevani program (rev.cpp):
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

double dp[30];
double prob[30];
int pre[30];

double calcdp(int p){
	if(p == 0) return 1;
	if(dp[p] != -1) return dp[p];
	
	dp[p] = 0;
	for (int i = 0; i < p && p - i - 1 >= 0; i++){
		if (dp[p] < prob[i] * calcdp(p - i - 1)){
			dp[p] = prob[i] * calcdp(p - i - 1);
			pre[p] = i + 1;
		}
		//dp[p] = max(dp[p], prob[i] * calcdp(p - i - 1));
	}
	
	return dp[p];
}

bool printSol(int p){
	if (p == 0) return false;
	else {
		if (printSol(p - pre[p])) cout<<"ROLL"<<endl;
		for (int i = 0; i < pre[p] - 1; i++){
			cout<<"FIRE"<<endl;
		}
		//cout<<pre[p]<<endl;
	}
	return true;
}

int main(){
	int T;
	cin>>T;
	
	int n, p;
	string s;
	for (int t = 0; t < T; t++){
		cin>>n>>p;
		cin>>s;
		
		int pos[n], nextpos[n];
		for (int i = 0; i < n; i++){
			pos[i] = 1;
			nextpos[i] = 0;
		}
		
		int free = 0, all = 0;
		for (int i = 0; i < p; i++){
			free = 0; all = 0;
			
			//for (int j = 0; j < n; j++) cout<<pos[j]<<" ";
			//cout<<endl;
			
			for (int j = 0; j < n; j++){
				if (pos[j] == 0) continue;
		
				if (s[j] != '*'){
					free++;
					if (j != n - 1) nextpos[j+1] = 1;
					else nextpos[0] = 1;
				}
				all++;
			}
			
			for (int j = 0; j < n; j++){
				pos[j] = nextpos[j];
				nextpos[j] = 0;
			}
			
			prob[i] = ((double)free) / ((double)all);
		}
		for (int i = 1; i < p; i++){
			prob[i] *= prob[i -1];
		}
		
		
		//for (int i = 0; i < p; i++) cout<<prob[i]<<endl;
		//cout<<endl;
		
		for (int i = 0; i < p + 5; i++) dp[i] = -1;
		//for (int i = 0; i <= p; i++) cout<<calcdp(i)<<endl;
		printf("%.10lf\n", calcdp(p));
		printSol(p);
	}
	
	
}