結果

問題 No.308 素数は通れません
ユーザー sugim48
提出日時 2015-12-01 00:46:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,692 bytes
コンパイル時間 1,218 ms
コンパイル使用メモリ 90,264 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 05:35:45
合計ジャッジ時間 33,041 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37 WA * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int dy[4] = {0, -1, 0, 1};
int dx[4] = {-1, 0, 1, 0};

void dfs(int y, int x, vector<vector<int> >& a, vector<int>& mi) {
	int H = a.size(), W = a[0].size();
	for (int k = 0; k < 4; k++) {
		int _y = y + dy[k], _x = x + dx[k];
		if (_y >= 0 && _y < H && _x >= 0 && _x < W && a[_y][_x]) {
			mi[a[_y][_x]] = min(mi[a[_y][_x]], W);
			a[_y][_x] = 0;
			dfs(_y, _x, a, mi);
		}
	}
}

int main() {
	vector<bool> p(10000, true);
	p[1] = false;
	for (int i = 2; i < 10000; i++)
		if (p[i])
			for (int j = i * 2; j < 10000; j += i)
				p[j] = false;
	vector<int> mi(10000, INT_MAX);
	for (int W = 1; W <= 1000; W++) {
		vector<vector<int> > a(10000 / W + 1, vector<int>(W));
		for (int i = 1; i < 10000; i++)
			if (!p[i])
				a[(i - 1) / W][(i - 1) % W] = i;
		dfs(0, 0, a, mi);
	}
	string s; cin >> s;
	int n = s.length();
	if (n <= 3) {
		stringstream ss(s);
		int x; ss >> x;
		cout << mi[x] << endl;
		return 0;
	}
	int x = 0;
	for (int i = 0; i < s.length(); i++)
		x = (x * 10 + s[i] - '0') % 14;
	if (x != 1) cout << 14 << endl;
}
0