| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
bfs,上限到199就可以了,因为对任一個合法的找钱序列,都可以改变顺序变成一個琐有部分和都小于200的序列#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
bool inRange(int n){
return n >= 0 && n <= 199;
}
int main() {
int N;
cin >> N;
for(int ii = 0; ii < N; ii++){
int zsgs[200];
for(int i = 1; i < 200; i++)zsgs[i] = -1;
zsgs[0] = 0;
queue<int> kydme;
kydme.push(0);
int me[6];
for(int i = 0; i < 6; i++) cin >> me[i];
int yjsclldgs = 0;
int zd = 0;
int zs = 0;
while(!kydme.empty()){
int top = kydme.front();
kydme.pop();
int cs = zsgs[top];
for(int i = 0; i < 6; i++){
int tar = top+me[i];
if(!inRange(tar) || zsgs[tar] != -1){
continue;
}
zsgs[tar] = cs+1;
if(tar <= 100 && tar > 0){
yjsclldgs++;
if(cs+1 > zd) zd = cs+1;
zs += (cs+1);
if(yjsclldgs == 100){
goto done;
}
}
kydme.push(tar);
}
for(int i = 0; i < 6; i++){
int tar = top-me[i];
if(!inRange(tar) || zsgs[tar] != -1){
continue;
}
zsgs[tar] = cs+1;
if(tar <= 100 && tar > 0){
yjsclldgs++;
if(cs+1 > zd) zd = cs+1;
zs += (cs+1);
if(yjsclldgs == 100){
goto done;
}
}
kydme.push(tar);
}
}
done:
double pj = zs / 100.0;
printf("%.2lf %d\n", pj, zd);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator