結果
| 問題 | No.1992 Tendon Walk |
| ユーザー |
 高森藍子
|
| 提出日時 | 2023-01-17 21:15:19 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 15,215 bytes |
| コンパイル時間 | 1,889 ms |
| コンパイル使用メモリ | 182,880 KB |
| 実行使用メモリ | 4,380 KB |
| 最終ジャッジ日時 | 2023-08-30 23:57:36 |
| 合計ジャッジ時間 | 2,721 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 2 ms
4,380 KB |
| testcase_03 | AC | 1 ms
4,376 KB |
| testcase_04 | AC | 2 ms
4,376 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 1 ms
4,376 KB |
| testcase_08 | AC | 2 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ALL(a) (a).begin(),(a.end())
#define brep(i,n) for(int i=n-1;i>=0;i--)
#define rep(hhh,n) for(int i=hhh;i<n;i++)
#define jrep(hhh,n) for(int j=hhh;j<n;j++)
#define krep(hhh,n) for(int k=hhh;k<n;k++)
#define lrep(hhh,n) for(int l=hhh;l<n;l++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define out(n) cout << n <<endl;
#define sot(A) sort(A.begin(),A.end())
#define rsot(A) sort(A.rbegin(),A.rend())
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vc vector<char>
#define vs vector<string>
#define vpi vector<pair<int,int>>
#define vvc vector<vector<char>>
#define vvi vector<vector<int>>
#define vvd vector<vector<double>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
//#define vli vector<long int>
//#define vlpi vector<pair<long int,long int>>
//#define vvli vector<vector<long int>>
#define vvpi vector<vector<pair<int,int>>>
#define dout(x,y) cout<<x<<" "<<y<<endl;
#define tout(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;
#define Pi pair<int,int>
#define TPi tuple<int,int,int>
#define TPd tuple<double,int,int>
int MOD1=1000000000+7;
int MOD2=998244353;
int BIG=10000000000000000;
class BIT {
public:
//データの長さ
int n;
//データの格納先
vector<int> a;
//コンストラクタ
BIT(int n):n(n),a(n+1,0){}
//a[i]にxを加算する
void add(int i,int x){
i++;
if(i==0) return;
for(int k=i;k<=n;k+=(k & -k)){
a[k]+=x;
}
}
//a[i]+a[i+1]+…+a[j]を求める
int sum(int i,int j){
return sum_sub(j)-sum_sub(i-1);
}
//a[0]+a[1]+…+a[i]を求める
int sum_sub(int i){
i++;
int s=0;
if(i==0) return s;
for(int k=i;k>0;k-=(k & -k)){
s+=a[k];
}
return s;
}
//a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要)
int lower_bound(int x){
if(x<=0){
//xが0以下の場合は該当するものなし→0を返す
return 0;
}else{
int i=0;int r=1;
//最大としてありうる区間の長さを取得する
//n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
while(r<n) r=r<<1;
//区間の長さは調べるごとに半分になる
for(int len=r;len>0;len=len>>1) {
//その区間を採用する場合
if(i+len<n && a[i+len]<x){
x-=a[i+len];
i+=len;
}
}
return i;
}
}
};
class CR{
public:
vi fac;
vi finv;
vi inv;
CR(int N):fac(N+1),finv(N+1),inv(N+1){
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i <= N; i++){
fac[i] = fac[i - 1] * i % MOD2;
inv[i] = MOD2 - inv[MOD2%i] * (MOD2 / i) % MOD2;
finv[i] = finv[i - 1] * inv[i] % MOD2;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD2) % MOD2;
}
};
struct UnionFind {
vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2
UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
for(int i = 0; i < N; i++) par[i] = i;
}
int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y) { // xとyの木を併合
int rx = root(x); //xの根をrx
int ry = root(y); //yの根をry
if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
}
bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};
void conf(vi A){
rep(0,A.size()){
cout << A[i] <<" ";
}
cout<<endl;
}
void conf(vvi A){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<A[i][j]<<" ";
}
cout<<endl;
}
}
void conf(vvpi A){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<"("<<A[i][j].first<<" "<<A[i][j].second<<")"<<" ";
}
cout<<endl;
}
}
void conf(vpi A){
rep(0,A.size()){
cout <<'('<< A[i].first <<" "<<A[i].second<<')'<<" ";
}
cout<<endl;
}
int max(int a,int b){
if(a>b)return a;
else return b;
}
int min(int a,int b){
if(a>b)return b;
else return a;
}
vector<int> enumdiv(int n) {
vector<int> S;
for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
sort(S.begin(), S.end());
return S;
}//与えられた１つの数の約数をvectorで昇順で返す（重複なし）,計算量√N
int modpow(int x,int n,int mod){
int res=1;
while(n>0){
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}//高速べき乗(modの値を返す)、計算量log(N)
int ppow(int x,int n){
int res=1;
while(n>0){
if(n&1)res=res*x;
x=x*x;
n>>=1;
}
return res;
}//高速べき乗、計算量log(N)
int modinv(int a, int m) {
int b = m, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}//拡張EuClidの互除法、a,mが互いに素ならOK、log(a);
vi smallest_prime_factors(int n) {
vi spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (int i = 2; i * i <= n; i++) {
if (spf[i] == i) {
for (int j = i * i; j <= n; j += i) {
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
vi soinsu(int N){
vi T;
int n=N;
int k=2;
while(k*k<=n){
if(N%k==0){
N=N/k;
T.push_back(k);
}
else{
k++;
}
}
if(N!=1)T.push_back(N);
if(T.size()==0){
T.push_back(n);
}
return T;
}//素因数分解した結果をviで返す(sort済み)
int legendre(int N,int k){
int ans=0;
while(N>=k){
ans+=N/k;
k*=k;
}
return ans;
}//N!がkで何回割ることが出来るか
vb Eratosthenes(int N){
vb IsPrime(N+1,true);
IsPrime[0] = false; // 0は素数ではない
IsPrime[1] = false; // 1は素数ではない
for(int i=2; i*i<=N; ++i) // 0からsqrt(max)まで調べる
if(IsPrime[i]) // iが素数ならば
for(int j=2; i*j<=N; ++j) // (max以下の)iの倍数は
IsPrime[i*j] = false;
return IsPrime;
}//Nまでの数が素数か素数でないかを返す、計算量nloglogn
vi dikstra(int s,int V,vector<vector<pair<int,int>>> &G){
vi d(V,2000000000);
priority_queue<Pi,vector<Pi>,greater<Pi>> que;
d[s]=0;
que.push(Pi(0,s));
while(!que.empty()){
Pi p=que.top();que.pop();
int v=p.second;
if(d[v]<p.first)continue;
rep(0,G[v].size()){
int a=G[v][i].second;
int b=G[v][i].first;
if(d[a]>d[v]+b){
d[a]=d[v]+b;
que.push(Pi(d[a],a));
}
}
}
return d;
}//始点は0start
/*int clk=1;
void clkdfs(vvi &A,vpi &B,int v){
if(seen[v])return ;
seen[v] = true; // v を訪問済にする
B[v].first=clk;
clk++;
// v から行ける各頂点 next_v について
for (int next_v:A[v]) {
if (seen[next_v-1]) continue; // next_v が探索済だったらスルー
clkdfs(A,B,next_v-1); // 再帰的に探索
}
B[v].second=clk;
clk++;
}*/
/*int W,H;
void dfs(vvi &A,int h,int w){
//if(A[h][w]==0)return;
A[h][w] =0; // v を訪問済にする
vi dh={-1,-1,-1,0,0,1,1,1};
vi dw={-1,0,1,-1,1,-1,0,1};
rep(0,8){
if(h+dh[i]>=0&&h+dh[i]<=H-1&&w+dw[i]>=0&&w+dw[i]<=W-1&&A[h+dh[i]][w+dw[i]]==1){
//dout(h+dh[i],w+dw[i]);
dfs(A,h+dh[i],w+dw[i]); // 再帰的に探索
}
}
}*/
int lgcd(int A, int B){
int a,b,C;
while (A!=0 && B!=0){
if (A>B){
a=A/B;
A=A-B*a;
}else{
b=B/A;
B=B-A*b;
}
}
C=max(A,B);
return C;
}
void YN(bool A){
if(A){
out("Yes");
}else{
out("No");
}
}
double max(double a,double b){
if(a>b){
return a;
}else{
return b;
}
}
double min(double a,double b){
if(a>b){
return b;
}else{
return a;
}
}
/*int H,W;
void dfs(vs &G,int h,int w,vvi &seen){
vi dh={1,0,-1,0};
vi dw={0,1,0,-1};
rep(0,4){
if(h+dh[i]>=0&&h+dh[i]<=H-1&&w+dw[i]>=0&&w+dw[i]<=W-1&&G[h+dh[i]][w+dw[i]]=='.'&&seen[h+dh[i]][w+dw[i]]==1000000000){
seen[h+dh[i]][w+dw[i]]=seen[h][w]+1;
dfs(G,h+dh[i],w+dw[i],seen); // 再帰的に探索
}
}
//A[h][w]=1;
}*/
/*void dfs(int a,vvi &G,vb &seen,int &ans){
if(ans>=1000000)return;
ans++;
if(seen[a]==true)return ;
seen[a]=true;
for (auto next_v : G[a]) {
if (seen[next_v]) continue;
dfs(next_v,G,seen,ans);
}
seen[a]=false;
}*/
/*int INF=10000000000000000;
Pi rec(int bit, int v,int V,vvpi &dist,vvpi &dp)
{
// すでに探索済みだったらリターン
if (dp[bit][v].first != -1) return dp[bit][v];
// 初期値
if (bit == 1) {
dp[bit][v].first= 0;
dp[bit][v].second=1;
return dp[bit][v];
}
// 答えを格納する変数
int res = INF;
// bit の v を除いたもの
int prev_bit = bit & (~(1<<v));
int p=0;
// v の手前のノードとして u を全探索
for (int u = 0; u < V; ++u) {
if (!(prev_bit & (1<<u))) continue; // u が prev_bit になかったらダメ
// 再帰的に探索
if (res > rec(prev_bit, u,V,dist,dp).first + dist[u][v].first&&rec(prev_bit,u,V,dist,dp).first+dist[u][v].first<=dist[u][v].second) {
res = rec(prev_bit, u,V,dist,dp).first + dist[u][v].first;
}
}
for (int u = 0; u < V; ++u){
if (!(prev_bit & (1<<u))) continue;
if(res!=INF&&res == rec(prev_bit, u,V,dist,dp).first + dist[u][v].first&&rec(prev_bit,u,V,dist,dp).first+dist[u][v].first<=dist[u][v].second){
p+=rec(prev_bit, u,V,dist,dp).second;
}
}
dp[bit][v].first = res;
dp[bit][v].second=p;
return dp[bit][v]; // メモしながらリターン
}*/
/*bool dfs(string a,map<string,string> &G,map<string,bool> &seen,string X){
if(seen[a])return true;
seen[a]=true;
bool ans=true;
if(G.find(a)!=G.end()){
string s=G[a];
if(s==X){
ans=false;
}
ans=dfs(s,G,seen,X);
}
return ans;
}*/
/*int H,W;
void dfs(int x,int y,vvi &dp,vs &S){
vi dx={1,0};
vi dy={0,1};
rep(0,2){
if(y+dy[i]>=0&&y+dy[i]<=H-1&&x+dx[i]>=0&&x+dx[i]<=W-1&&S[y+dy[i]][x+dx[i]]=='.'){
dp[y+dy[i]][x+dx[i]]=(dp[y+dy[i]][x+dx[i]]+dp[y][x])%MOD1;
}
}
}*/
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) での最小の要素を取得。O(log(n))
find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
*/
/*template <typename T>
struct RMQ {
const T e = numeric_limits<T>::max();
function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1, x2); };
int n;
vector<T> dat;
RMQ(int n_) : n(), dat(n_ * 4, e) {
int x = 1;
while (n_ > x) {
x *= 2;
}
n = x;
}
void set(int i, T x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
}
void update(int i, T x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2; // parent
dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) {
return e;
} else if (a <= l && r <= b) {
return dat[k];
} else {
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return fx(vl, vr);
}
}
int find_rightest(int a, int b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
int find_leftest(int a, int b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
int find_rightest_sub(int a, int b, T x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
return a - 1;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn
return vr;
} else { // 左の部分木を見て値をreturn
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
int find_leftest_sub(int a, int b, T x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
return b;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // 左の部分木を見て b 以外ならreturn
return vl;
} else { // 右の部分木を見て値をreturn
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
};*/
signed main(){
int X;cin>>X;
int a=0;
int ans=0;
vi dx={2,2,-1,-1,2,-1,-1};
bool flag=false;
rep(0,100){
jrep(0,7){
a+=dx[j];
ans+=abs(dx[j]);
if(a==X){
flag=true;
break;
}
}
if(flag)break;
}
out(ans);
}