結果

問題 No.2146 2 Pows
コンテスト
ユーザー 👑 ygussany
提出日時 2022-12-02 23:23:19
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,330 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 31,232 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2024-10-10 01:53:37
合計ジャッジ時間 5,213 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int bit[22] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152};

void chmin(long long* a, long long b)
{
	if (*a > b) *a = b;
}

int main()
{
	int N;
	long long A, B, C;
	scanf("%d %lld %lld %lld", &N, &A, &B, &C);
	
	int i, ii, j, k, x, y, yy, z, rem[200001] = {};
	const long long sup = 1LL << 60;
	long long ans[200001], tmp;
	for (i = 1, tmp = 1, rem[1] = 1; 1; i++) {
		tmp = tmp * 2 % N;
		if (rem[tmp] != 0) break;
		rem[tmp] = i + 1;
	}
	for (i = 2, ans[1] = A + B; i <= N; i++) {
		ans[i] = sup;
		if (rem[i] != 0) ans[i] = A + B + C * (rem[i] - 1);
		for (ii = i; ii <= i * 10; ii += N) {
			for (z = 0; bit[z] <= ii; z++) {
				if (ii % bit[z] == 0) {
					chmin(&(ans[i]), A * (ii / bit[z]) + B + C * z);
					continue;
				}
				for (y = 2; y <= z + 1; y++) {
					for (k = z, j = ii, x = 0, yy = 0; yy < y - 1 && j > 0; k--) {
						if (j / bit[k] > 0) {
							yy++;
							x += j / bit[k];
							j %= bit[k];
						}
					}
					if (yy == y - 1 && j > 0) {
						for (; j % bit[k] != 0; k--);
						x += j / bit[k];
						chmin(&(ans[i]), A * x + B * y + C * z);
					} else break;
				}
			}
		}
	}
	
	printf("%lld\n", ans[N]);
	for (i = 1; i < N; i++) printf("%lld\n", ans[i]);
	fflush(stdout);
	return 0;
}
0