HDU 4546試合難易度
11993 ワード
試合の難易度
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 46 Accepted Submission(s): 6
Problem Description
最近、明ちゃんはACMのプログラミング問題を出して、HDOJで公開試合を行うことにしました.
仮に問題の数が全部でn道であると仮定すると、これらの問題の難易度は1000を超えない非負の整数に格付けされ、1試合に少なくとも1つの問題が必要であるが、この試合の難易度は、すべての問題の難易度の和であり、同時に、1試合はこの問題の順序とは関係なく、問題も繰り返さないと考えられる.
明らかに、次の情報が簡単に得られます.
試合は1つのテーマしか使わないと仮定し、n種類の案がある.
試合に2つのテーマを使うと仮定すると、(n-1)*n/2の案がある.
試合に3つのテーマを使うと仮定すると、(n-2)*(n-1)*n/6種類の案がある.
............
試合全体のn個のタイトルを使用すると仮定すると,このシナリオは1種のみである.
簡単な試算を経て、明ちゃんは総案数がほとんど天文数字であることを発見しました.
問題を簡単にするために、今明ちゃんはすべての案の中でm番目に小さい案を知りたいだけです.その試合の難易度はいくらですか.
Input
入力データの第1の挙動は、T組のテストデータがあることを示す整数T(1<=T<=20)である.
各グループのテストデータの第1行為の2つの整数n,m(0
Output
各テストデータのセットについて、1行の「Case#c:ans」(引用符を含まない)を出力し、ansは要求されるm番目の試合の難易度を表し、入力データはm番目の小さいスキームが存在することを保証し、具体的にはサンプルを参照してください.
Sample Input
2 5 6 1 1 1 1 1 5 25 1 2 3 4 5
Sample Output
Case #1: 2 Case #2: 11
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-初戦(1)
Recommend
liuyiding
私のやり方は、2つの秩序ある配列を絶えず結合し、増加した配列を維持することです.
まずa配列を小さいものから大きいものに並べ替える.
例えば、前のi-1個の数の組み合わせが秩序ある配列を生成する
b[now][1] 、 b[now][2]、b[now][3]、··········b[now][b[now][0]]
だからb[now][0]は配列の個数を格納する
そしてa[i]が加わる.a[i]を含む新しいシーケンスの生成:a[i]、a[i]+b[now][1] 、 a[i]+b[now][2]、a[i]+b[now][3]、··········a[i]+b[now][b[now][0]]
2つの秩序化された数列を結合すると,前のi個の数の組合せで生成された秩序化配列が得られる.
そしてどんどん押していきます.
この配列の大きさはmより大きくないで、mより大きい部分は必要ありません
また、配列の大きさがmより大きいと満タンになり、現在のa[i]が入っていない場合は、後ろのものも入らないことを説明し、直接breakする.
私のやり方の複雑さは比較的に大きいと感じます==555555
金山西山居が試合中にこの問題のFBを奪ったとは思わなかった...zzzzzzzzはこのような正解ではないようです.
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 46 Accepted Submission(s): 6
Problem Description
最近、明ちゃんはACMのプログラミング問題を出して、HDOJで公開試合を行うことにしました.
仮に問題の数が全部でn道であると仮定すると、これらの問題の難易度は1000を超えない非負の整数に格付けされ、1試合に少なくとも1つの問題が必要であるが、この試合の難易度は、すべての問題の難易度の和であり、同時に、1試合はこの問題の順序とは関係なく、問題も繰り返さないと考えられる.
明らかに、次の情報が簡単に得られます.
試合は1つのテーマしか使わないと仮定し、n種類の案がある.
試合に2つのテーマを使うと仮定すると、(n-1)*n/2の案がある.
試合に3つのテーマを使うと仮定すると、(n-2)*(n-1)*n/6種類の案がある.
............
試合全体のn個のタイトルを使用すると仮定すると,このシナリオは1種のみである.
簡単な試算を経て、明ちゃんは総案数がほとんど天文数字であることを発見しました.
問題を簡単にするために、今明ちゃんはすべての案の中でm番目に小さい案を知りたいだけです.その試合の難易度はいくらですか.
Input
入力データの第1の挙動は、T組のテストデータがあることを示す整数T(1<=T<=20)である.
各グループのテストデータの第1行為の2つの整数n,m(0
Output
各テストデータのセットについて、1行の「Case#c:ans」(引用符を含まない)を出力し、ansは要求されるm番目の試合の難易度を表し、入力データはm番目の小さいスキームが存在することを保証し、具体的にはサンプルを参照してください.
Sample Input
2 5 6 1 1 1 1 1 5 25 1 2 3 4 5
Sample Output
Case #1: 2 Case #2: 11
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-初戦(1)
Recommend
liuyiding
私のやり方は、2つの秩序ある配列を絶えず結合し、増加した配列を維持することです.
まずa配列を小さいものから大きいものに並べ替える.
例えば、前のi-1個の数の組み合わせが秩序ある配列を生成する
b[now][1] 、 b[now][2]、b[now][3]、··········b[now][b[now][0]]
だからb[now][0]は配列の個数を格納する
そしてa[i]が加わる.a[i]を含む新しいシーケンスの生成:a[i]、a[i]+b[now][1] 、 a[i]+b[now][2]、a[i]+b[now][3]、··········a[i]+b[now][b[now][0]]
2つの秩序化された数列を結合すると,前のi個の数の組合せで生成された秩序化配列が得られる.
そしてどんどん押していきます.
この配列の大きさはmより大きくないで、mより大きい部分は必要ありません
また、配列の大きさがmより大きいと満タンになり、現在のa[i]が入っていない場合は、後ろのものも入らないことを説明し、直接breakする.
私のやり方の複雑さは比較的に大きいと感じます==555555
金山西山居が試合中にこの問題のFBを奪ったとは思わなかった...zzzzzzzzはこのような正解ではないようです.
//============================================================================
// Name : B.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <math.h>
using namespace std;
const int MAXN=10010;
int a[MAXN];
int b[2][MAXN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m;
int iCase=0;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
iCase++;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
int now=0;
b[now][0]=1;
b[now][1]=a[0];
for(int i=1;i<n;i++)
{
int t1=1,t2=1;
bool ff=false;
b[now^1][0]=0;
while(t1<=b[now][0] && t2<=b[now][0] && b[now^1][0]<=m)
{
if(!ff && a[i]<=min(b[now][t1],b[now][t2]+a[i]))
{
b[now^1][++b[now^1][0]]=a[i];
ff=true;
continue;
}
if(b[now][t1]<b[now][t2]+a[i])
b[now^1][++b[now^1][0]]=b[now][t1++];
else
b[now^1][++b[now^1][0]]=b[now][t2++]+a[i];
}
while(t1<=b[now][0] && b[now^1][0]<=m)
{
if(!ff && a[i]<=b[now][t1])
{
b[now^1][++b[now^1][0]]=a[i];
ff=true;
continue;
}
b[now^1][++b[now^1][0]]=b[now][t1++];
}
while(t2<=b[now][0] && b[now^1][0]<=m)
{
if(!ff && a[i]<=b[now][t2]+a[i])
{
b[now^1][++b[now^1][0]]=a[i];
ff=true;
continue;
}
b[now^1][++b[now^1][0]]=b[now][t2++]+a[i];
}
if(!ff && b[now^1][0]<=m)
{
b[now^1][++b[now^1][0]]=a[i];
ff=true;
}
now^=1;
if(!ff)break;
}
printf("Case #%d: %d
",iCase,b[now][m]);
}
return 0;
}