2014-04-11

SRM 616 Div1 500 ColorfulCoins

12:53 |

最大60種類のコインの額面が与えられる。コインには種類ごとに異なる色が塗ってある。額面は見た目では分からない。
ATMがあって数値をいれると対応する額のコインが最小枚数でじゃらじゃら出てくる。
全種類のコインの色を特定するのに最低何回ATMから引き出せばいいか求めよ。
1≦額面≦10^18, 額面は単調増加で与えられて最初は1, どの２つの額面も割り切れる

複雑だ....
(いろいろ考察)
1 10 100 1000 だったら、4321円引き出せば1が1枚, 10が2枚, 100が3枚, 1000が4枚もらえるので1回で特定できる。
1 2 4 8 だと、8は何枚でも出せるけど 1 2 4 は 1枚までしかもらえないので困る。

1回の引き出しで出せるコインの枚数は額面/直前の額面-1 まで
特定できるとはどういうことか？
あるコインについて、1〜N回目に取る枚数をN要素ベクトルだと思うと、要素が1個でも異なるなら識別できる。
(i回目にvec[i]枚出てきたような色は vec が異なれば一意に定まる)
出せるコインの枚数が K なら取り方は (K+1)^N 通りある。
が、全部0の場合そもそも何色か分からないので、特定に役立つ組み合わせは (K+1)^N-1通り。(書いて実行するまで気付かなかった)

基本的には、出せるコインの枚数が K であるようなコインの種類数が (K+1)^N-1 以下なら識別できそう。
出せるコインの枚数が K 枚未満のやつは？→ (K+1)^N 通りの中に必ず含まれるので、その分余裕を減らさないといけない。
というわけで、すべての K について
「出せるコインの枚数が K 以下であるようなコインの種類数 ≦ (K+1)^N-1」
なら N 回で全種類識別可能。
1枚ずつ取っていけば最悪でも60回で全部識別できるので N in [1, 60] を全部試す。

方針を思いついたのが終了13分前
全部 0 の場合を -1 するのに気づいてサンプル通って提出したのが終了2分前
ぎりぎりセーフ

例: 1  2  4  12  24 の場合

額   1回で何枚までとれるか
 1   1
 2   1
 4   2
12   1
24   ∞

額  最大  1,2 回目に何枚とるか(例)
 1    1    1,0
 2    1    0,1
12   1    1,1 // ここまで (1+1)^2-1 == 3 種類以下ならOK
 4    2    2,0 // ここまで (2+1)^2-1 == 8 種類以下ならOK
24   ∞   3,0 // ここまで (大きな値+1)^2-1 種類以下ならOK

accepted

(実際には 60<2^6なので最大でも6回で識別できるようです)

ll po(ll a, ll b) {
	ll v=1;
	REP(i, b) {
		v*=a;
		if(v>10000) return 10000; // 1, 2, 3, たくさん　の精神
	}
	return v;
}

class ColorfulCoins {
	public:
	int minQueries(vector<long long> V) {
		int N=V.size();
		map<ll, ll> hi;
		RANGE(i, 1, N) {
			ll v = V[i]/V[i-1];
			hi[v]++;
		}
		hi[1LL<<60]++;
		cout<<hi<<endl;
		RANGE(n, 1, N+1) {
			ll used=0;
			int ok=1;
			FOR(e, hi) {
				ll cap = po(e->first, n) - 1 - used;
//				cout<<"C "<<cap<<" "<<e->first<<" "<<e->second<<endl;
				if(cap < e->second) {ok=0;break;}
				used += e->second;
			}
			if(ok) return n;
		}
		return -1;
	}
};

kojingharangの日記

2014-04-11

SRM 616 Div1 500 ColorfulCoins