akhauriyash/Code-Regression huggingface dataset:
import math

EPS = 1e-10

def equals(a, b):
    return abs(a - b) < EPS


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)

    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)

    def __mul__(self, a):
        return Point(self.x * a, self.y * a)

    def __rmul__(self, a):
        return self * a

    def __truediv__(self, a):
        return Point(self.x / a, self.y / a)

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def __lt__(self, p):
        if self.x != p.x:
            return self. x < p.x
        else:
            return self.y < p.y

    def __eq__(self, p):
        return equals(self.x, p.x) and equals(self.y, p.y)


class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2


def dot(a, b):
    return a.x * b.x + a.y * b.y


def cross(a, b):
    return a.x * b.y - a.y * b.x


def getCrossPoint(s1, s2):
    base = s2.p2 - s2.p1
    d1 = abs(cross(base, s1.p1 - s2.p1))
    d2 = abs(cross(base, s1.p2 - s2.p1))
    t = d1 / (d1 + d2)
    return s1.p1 + (s1.p2 - s1.p1) * t


if __name__ == '__main__':
    q = int(input())
    ans = []
    for i in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = [int(v) for v in input().split()]
        s1 = Segment(Point(x0, y0), Point(x1, y1))
        s2 = Segment(Point(x2, y2), Point(x3, y3))
        ans.append(getCrossPoint(s1, s2))

    for v in ans:
        print('{0:.10f} {1:.10f}'.format(v.x, v.y))


Measured memory_bytes: 6024
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K, i, dist = 0;
    cin >> N >> K;
    vector<int> address(N);
    for (i = 0; i < N; i++) {
        cin >> address.at(i);
        if (address.at(i) < (K -address.at(i))) {
            dist += address.at(i) * 2;
        } else {
            dist += (K -address.at(i)) * 2;
        }
    }
    
    cout << dist << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(0);
    
    int n;
  	int ans = 0;
    cin >> n;
    vector<int> a(n+1);
    vector<int> dp(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[a[i]] = dp[a[i] - 1] + 1;
      	ans = max(ans, dp[a[i]]);
    }
    cout << n-ans << '\n';
    
    return 0;
}

Measured memory_bytes: 1792
from collections import Counter
from heapq import heapify, heappush, heappop

def solve():
    N = int(input())
    Ss = list(map(int, input().split()))

    cnt = Counter(Ss)

    PQ = [-N]
    for key in sorted(cnt.keys(), reverse=True):
        num = cnt[key]
        if len(PQ) < num:
            return False
        depths = []
        for _ in range(num):
            depths.append(-heappop(PQ))
        for depth in depths:
            for d in range(depth):
                heappush(PQ, -d)

    return True

if solve():
    print('Yes')
else:
    print('No')



Measured memory_bytes: 36420
#include <bits/stdc++.h>
using namespace std;

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getBit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void Main() {
  vector<int> f(1000001);
  for (int i = 1; i <= 1000000; i++)
  for (int j = 1; i * j <= 1000000; j++) {
    f[i * j]++;
  }
  int n; cin >> n;
  int ans = 0;
  for (int i = 1; i < n; i++) {
    ans += f[n - i];
  }
  cout << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  cerr << "i love ------- <3 \n";
#endif
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  // cin >> T;
  while (T--) Main();
}


Measured memory_bytes: 11048
// header {{{
#include <bits/stdc++.h>
using namespace std;

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    string s;cin >> s;
    string t = "CODEFESTIVAL2016";
    int ans = 0;
    int n = s.size();
    for(int i=0;i<n;i++){
        if(t[i] != s[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main(){
	char a;
	cin >> a;
	if('a'<=a&&a<='z'){
		cout << 'a' << endl;
	}else{
		cout << 'A' << endl;
	}
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
int main() {
	long int a, b, x;
	cin >> a >> b >> x;
 
	long int a1 = a / x;
	long int b1 = b / x;
 
	if ((a%x) == 0) {
		a1 = a1 - 1;
	}
	cout << b1 - a1 << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
//qsort用 降順ソート
int comp(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}
int main(void)
{
    int N;
    int i;
    int ret = 0;
    scanf("%d",&N);
    if(N==1){
        printf("1\n");
        return 0;
    }
    // N以下の2の累乗を求める
    for(i=0;i<8;i++){
        if(pow(2,i)<=N){
            ret = pow(2,i);
        }else{
            break;
        }
    }
    printf("%d\n",ret);
    return 0;
}


Measured memory_bytes: 2532
#include <bits/stdc++.h>
#define kika "kika"
#define tam 100000
#define ll long long
#define ii pair <int, int>
#define dl pair <ll, ll>
#define vi vector <int>
#define vl vector <ll>
#define vii vector <ii>
#define graph vector <vi>

using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll k, x;
	cin >> k >> x;
	if (500 * k >= x) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

bool path1[200000], path2[200000];

int main()
{
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    rep(i, M) {
        int A, B;
        cin >> A >> B;
        A--, B--;
        if (A > B) swap(A, B);
        if (A == 0) path1[B] = true;
        if (B == N-1) path2[A] = true;
    }

    rep(i, N) {
        if (path1[i] && path2[i]) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned LL
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector< PII >
#define VVI vector< VI >
#define PB push_back
#define F first
#define S second
const int INF=1e9;
const int MOD=1e9+7;
string s;
int main(){
    cin>>s;
    int l=0;
    int r=s.size()-1;
    int ans=0;
    while(l<r){
        if(s[l]=='x'&&s[r]!='x')ans++,l++;
        else if(s[l]!='x'&&s[r]=='x')ans++,r--;
        else if(s[l]!=s[r]){
            ans=-1;
            break;
        }
        else{
            l++;
            r--;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 512
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

	int n;
  cin >> n;
  vector<ll> a(n+1);

  a[0] = 0;
  for(int i=1;i<=n;i++) {
    cin >> a[i];
    a[i] += a[i-1];
  }

  ll ans = LLONG_MAX;
  for(int i=1;i<n;i++) {
    ll diff = abs((a[n] - a[i]) - a[i]);
    if(ans > diff) {
      ans = diff;
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge
{
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f)
        : from(u), to(v), cap(c), flow(f) {}
};

const int maxn = 505;
struct Dinic
{
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    long long d[maxn];
    int cur[maxn];
    void init(int n)
    {
        this->n = n;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int cap)
    {
        edges.emplace_back(from, to, cap, 0);
        edges.emplace_back(to, from, 0, 0);
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool BFS()
    {
        memset(vis, 0, sizeof(vis));
        memset(d, 0, sizeof(d));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = 0; i < G[x].size(); i++)
            {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    long long DFS(int x, long long a)
    {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++)
        {
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min<long long>(a, e.cap - e.flow))) > 0)
            {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
    long long Maxflow(int s, int t)
    {
        this->s = s, this->t = t;
        long long flow = 0;
        while (BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
} solver;

int main()
{
    int n;
    scanf("%d", &n);
    solver.init(n + 2);
    int s = 0, t = n + 1;
    long long sum = 0;
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        if (x < 0) solver.AddEdge(s, i, -x);
        if (x > 0) solver.AddEdge(i, t, x), sum += x;
        for (int j = i + i; j <= n; j += i) solver.AddEdge(i, j, INF);
    }
    printf("%lld\n", sum - solver.Maxflow(s, t));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int pcnt(int x) {
  return __builtin_popcount(x);
}
int f(int x) {
  if (x == 0) return 0;
  return f(x%pcnt(x))+1;
}

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> x(n);
  rep(i,n) x[i] = s[i]-'0';
  int pc = 0;
  rep(i,n) pc += x[i];
  vector<int> ans(n);
  rep(b,2) {
    int npc = pc;
    if (b == 0) npc++; else npc--;
    if (npc <= 0) continue;
    int r0 = 0;
    rep(i,n) {
      r0 = (r0*2)%npc;
      r0 += x[i];
    }
    int k = 1;
    for (int i = n-1; i >= 0; --i) {
      if (x[i] == b) {
        int r = r0;
        if (b == 0) r = (r+k)%npc;
        else r = (r-k+npc)%npc;
        ans[i] = f(r)+1;
      }
      k = (k*2)%npc;
    }
  }

  rep(i,n) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 5152
#include <bits/stdc++.h>
using namespace std;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define VIN(x) for(auto&youso_: (x) )cin>>youso_
#define VOUT(x, delim) for(auto&youso_: (x) )cout<<youso_<<delim;cout<<endl

#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) i64 __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    CIN(K);
    i64 N = 50;

    i64 ncycle = K / N + (K % N > 0);
    i64 k = ncycle * N;
    vector<i64> A(N, N - 1 + ncycle);
    REP(i, k - K) {
        i64 decl = i % N;
        REP(i, N) {
            if (decl == i) A[i] -= N;
            else A[i]++;
        }
    }

    COUT(N);
    VOUT(A, " ");

    return 0;
}


Measured memory_bytes: 3632
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	ans := 0
	for i := 0; i < n; i++ {
		var l, r int
		fmt.Scan(&l, &r)
		ans += (r - l) + 1
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<vector<int>> vect(n,vector<int>(3,0));
    for(int i=0 ; i<n ; i++){
        cin>>vect[i][0]>>vect[i][1]>>vect[i][2];
    }
    vector<vector<int>> dp(n,vector<int>(3,0));
    dp[0][0]=vect[0][0];
    dp[0][1]=vect[0][1];
    dp[0][2]=vect[0][2];
    
    for(int i=1 ; i<n ; i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+vect[i][0];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+vect[i][1];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+vect[i][2];
        
    }
    cout<<max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2])<<endl;
    return 0;
}

Measured memory_bytes: 11136
#include <stdio.h>

#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left, int mid, int right) {
  int i, j, k;
  int n1 = mid -left;
  int n2 = right - mid;
  for(i=0;i<n1;i++) L[i] = A[left + i];
  for(i=0;i<n2;i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  i=0, j=0;
  for(k=left; k<right; k++) {
    cnt++;
    if(L[i]<=R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[],int n,int left,int right) {
  int mid;
  if(left+1 < right) {
    mid = (left+right) / 2;   
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);   
  }
}

int main(void) {
  int A[MAX], n, i;
  cnt = 0;

  scanf("%d",&n);          //n格納
  for(i=0;i<n;i++) scanf("%d",&A[i]);    //n個の整数A[i]に格納

  mergeSort(A, n, 0, n); //mergeSort 　A→A[] n→n 0→left n→right
  for(i=0;i<n;i++) {
    if(i) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n%d\n",cnt);

  return 0;
}


Measured memory_bytes: 5628
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000003;
vector<long long> fact;
long long modpow(long long n, int k) {
	long long r = 1;
	while (k > 0) {
		if (k&1) (r *= n) %= mod;
		(n *= n) %= mod;
		k >>= 1;
	}
	return r;
}
long long modinv(int n) {
	return modpow(n, mod-2);
}
void solve() {
	long long X, D, N;
	cin >> X >> D >> N;
	if (D == 0) {
		cout << modpow(X, N) << endl;
	} else if (N >= mod) {
		cout << 0 << endl;
	} else {
		long long s = X * modinv(D) % mod;
		long long t = (X+(N-1)*D) * modinv(D) % mod;
		if (0 < s && s <= t) {
			cout << fact[t] * modinv(fact[s-1]) % mod * modpow(D, N) % mod << endl;
		} else {
			cout << 0 << endl;
		}
	}
}
int main() {
	fact = vector<long long>(mod);
	fact[0] = 1;
	for (unsigned i = 1; i < fact.size(); ++ i) fact[i] = fact[i-1] * i % mod;

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; ++ i) {
		solve();
	}
}


Measured memory_bytes: 8704
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

int main(void)
{
  int n; cin >> n;
  string s;
  string res = "Three";
  REP(i, n) {
    cin >> s;
    if(s == "Y") {
      res = "Four";
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
f=lambda:map(int,input().split())
h,w,n=f()
c=[0]*10
c[0]=(h-2)*(w-2)
d={}
while n:
 n-=1;x,y=f()
 for i in range(9):
  a=(x+i%3,y+i//3)
  if h>=x+i%3>2<y+i//3<=w:d[a]=d.get(a,0)+1;c[d[a]-1]-=1;c[d[a]]+=1
print(*c)

Measured memory_bytes: 166560
#include <iostream>

using namespace std;


int main(){
  int a,b,c;
  int f=0;

  cin >>a>>b>>c;
  for(int i=a; i<=b; i++){
    if( (c%i) ==0) {
      f++;
    }
  }
  cout <<f<<endl;
  return 0;
}



Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
    /*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
ll ncd(ll n,ll d){
    ll x = 1,y=1;
    for(int i=0;i<d;i++){
        x = x*(n-i)%mod;
        y = y*(i+1)%mod;
    }
    return x*modpow(y,mod-2,mod)%mod;
}
int main() {    
    srand(time(NULL));
    for(int j=0;j<14;j++){
    for(int i=0;i<26;i++){
        cout<<i+1<<endl;
    }
    }
    for(int i=0;i<1;i++){

          cout<<rand()%26+1<<endl;  
    }
}
    



Measured memory_bytes: 3560
#include<stdio.h>
#define PI 3.14159265358979323846
double getArea(double);
double getPerimeter(double);
int main(void)
{
  double r;
  scanf("%lf",&r);
  printf("%f %f\n",getArea(r),getPerimeter(r));
  return 0;
}
double getArea(double r)
{
  return r*r*PI;
}
double getPerimeter(double r)
{
  return 2*r*PI;
}


Measured memory_bytes: 2064
import java.util.*;

public class Main  {

	

	static double[][] dp;
	static double[]arr;
	static int n;
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
	     n=sc.nextInt();
	    arr=new double[n];
	    for(int i=0;i<n;i++)
	    {
	    	arr[i]=sc.nextDouble();
	    	
	    }
	    dp=new double[n][n+1];
	    dp[0][0]=1-arr[0];
	    dp[0][1]=arr[0];
	    for(int i=1;i<n;i++)
	    {
	    	for(int j=0;j<=n;j++)
	    	{
	    		dp[i][j]=(1-arr[i])*dp[i-1][j];
	    		if(j>0)
	    		{
	    			dp[i][j]+=arr[i]*dp[i-1][j-1];
	    		}
	    		
	    	}
	    }
	    double ans=0;
	    for(int i=n/2+1;i<=n;i++)
	    {
	    	ans+=dp[n-1][i];
	    	
	    }
	    System.out.println(ans);
	}
	
	
	
}


Measured memory_bytes: 118208
#include <bits/stdc++.h>

using namespace std;

std::vector<pair<unsigned long long, unsigned long long>> prime_factors(unsigned long long number)
{
    std::vector<pair<unsigned long long,unsigned long long>> result;
    unsigned long long root = static_cast<unsigned long long>(std::sqrt(number));
    int count = 0;
    int leng = 0;
    int flag = 0;
    while (number % 2 == 0) {
        if(count == 0) {
            result.push_back(pair<unsigned long long, unsigned long long>(2,0));
            count += 1;
            flag = 1;
        }
        result[leng].second += 1;
        number = number / 2;
    }
    if (flag == 1) {
        leng++;
        flag = 0;
    }

    for (unsigned int i = 3; i <= root; i+=2) {
        count = 0;
        while (number % i == 0) {
            if(count == 0) {
                result.push_back(pair<unsigned long long, unsigned long long>(i,0));
                count += 1;
                flag = 1;
            }
            result[leng].second += 1;
            number = number /i;
        }
        if (flag == 1) {
            leng++;
            flag = 0;
        }
    }

    if(number > 2) {
        result.push_back(pair<unsigned long long, unsigned long long>(number,1));
    }

    return result;
}

int main(void)
{
    unsigned long long N;
    cin >> N;
    if(N == 1) {
         cout << 0 << endl;
         return 0;
    }
    int result = 0;
    vector<pair<unsigned long long,unsigned long long>> l = prime_factors(N);

    /*
    for(int i = 0;i < (int)l.size();i++) {
        cout << l[i].first << " " << l[i].second << endl;
    }
    */
    
    for(int i = 0;i <(int)l.size();i++) {
        for(unsigned long long dif = 1;; dif++){
            //cout << dif << " " << l[i] << endl;
            if(l[i].second >= dif) {
                l[i].second = l[i].second - dif;
                result++;
            }
            else {
                break;
            }

        }
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 3732
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
vector<ll> node[10005];
ll dist[10005]={0};
bool used[10005];
ll inayos[10005]={0};
int main(){
    ll n;
    cin>>n;
    for(int i=1;i<n;i++){
      ll a,b;
      cin>>a>>b;
      node[a].push_back(b);
      node[b].push_back(a);
    }
    queue<ll> que;
    for(int i=1;i<10005;i++) used[i]=false;
    used[1]=true;
    que.push(1);
    ll num=1;
    while(!que.empty()){
      ll pos=que.front();
      que.pop();
      dist[pos]=num;
      num++;
      for(int i=0;i<node[pos].size();i++){
        ll to=node[pos][i];
        if(!used[to]){
          used[to]=true;
          que.push(to);
        }
      }
    }
    vector<P> vec;
    for(int i=1;i<=n;i++) vec.push_back(P(dist[i],i));
    sort(vec.begin(),vec.end());
    ll ans=0,mx=0;
    vector<ll> yoc;
    for(int i=1;i<=n;i++){
      ll c;
      cin>>c;
      yoc.push_back(c);
      ans+=c;
      mx=max(mx,c);
    }
    ans-=mx;
    cout<<ans<<endl;
    sort(yoc.begin(),yoc.end(),greater<ll>());
    for(int i=0;i<n;i++){
      //cout<<vec[i].first<<" "<<vec[i].second<<" "<<yoc[i]<<endl;
      inayos[vec[i].second]=yoc[i];
    }
    for(int i=1;i<=n;i++) cout<<inayos[i]<<(i==n?"\n":" ");
}


Measured memory_bytes: 1532
import numpy as np

a = list(map(int, input().split()))
def task(b):
    return abs(b[1] - b[0]) + abs(b[2] - b[1])
a = np.array(a)
p = np.array([[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]) - 1
Min = np.inf
for i in range(6):
    Min = min(Min, task(a[p[i,:]]))
print(Min)


Measured memory_bytes: 12504
import time

n,p = map(int,input().split())

if n >= 40 or p == 1:
    print("1")
elif n == 1:
    print(p)
else:
    s = 0
    fact = {}
    start = time.time()
    check = False
    while s == 0:
        for i in range(2,p+1):
            now = time.time()
            if now > start+1.9:
                s = 1
                check = True
                break
            if p%i == 0:
                p = p//i
                if p == 1:
                    s = 1
                if i not in fact:
                    fact[i] = 1
                else:
                    fact[i] += 1
                break
    ans = 1
    for i in fact:
        if fact[i] >= n:
            ans = ans*i**(fact[i]//n)
    print(ans)

Measured memory_bytes: 3184
def CountMine(x, y):
    count = 0
    for k in range(3):
        for l in range(3):
            if S[x-1+k][y-1+l] == '#':
                count += 1
    return count
    
    

H, W = list(map(int, input().split()))
S = [[0]*(W+2)] + [[0] + list(input()) + [0] for _ in range(H)] + [[0]*(W+2)]

for i in range(H):
    for j in range(W):
        if S[i+1][j+1] == '.':
            print(CountMine(i+1, j+1), end="")
        else:
            print('#', end="")
    print('\n')


Measured memory_bytes: 3444
N = int(input())
for l in range(N):
    A = [int(i) for i in input().split()]
    B = 0
    C = 0
    ans = "YES"
    for i in range(10):
        if A[i] > B:
            B = A[i]
        elif A[i] > C:
            C = A[i]
        else:
            ans = "NO"
    print(ans)



Measured memory_bytes: 5600
class UF():
  def __init__(self, N):
    self.par = [-1]*N

  def find(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]

  def union(self, x,y):
    p1,p2 = self.find(x),self.find(y)
    if p1 == p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

  def same(self, x,y):
    return self.find(x) == self.find(y)

N = int(input())
coordinates = []
for i in range(N):
  x,y = list(map(int, input().split()))
  coordinates.append((i,x,y))

edges = []

sort_x = sorted(coordinates, key=lambda x: x[1])
for i in range(N-1):
  u,v = sort_x[i][0], sort_x[i+1][0]
  edges.append([u,v,abs(sort_x[i][1] - sort_x[i+1][1])])

sort_y = sorted(coordinates, key=lambda x: x[2])
for i in range(N-1):  
  u,v = sort_y[i][0], sort_y[i+1][0]
  edges.append([u,v,abs(sort_y[i][2] - sort_y[i+1][2] )])

edges.sort(key=lambda x: x[2])
uf = UF(N)
res = 0
for u,v,c in edges:
  if not uf.same(u,v):
    uf.union(u,v)
    res += c

print(res)


Measured memory_bytes: 141948
import math
def sosu(x):
    if x == 2:
        return 1
    elif x < 2 or x % 2 == 0:
        return 0
    i = 3
    while i <= math.sqrt(x):
        if x % i == 0:
            return 0
        i += 2
    return 1
    
n = int(input())
m = 0
for i in range(n):
    a = int(input())
    b = sosu(a)
    m += b 
print(m)


Measured memory_bytes: 5676
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

vector<pair<int,int>> g[100100];
ll d[100100];

bool dfs(int v) {
  for (auto e: g[v]) {
    int w, c;
    tie(w, c) = e;
    if (d[w] == ll(1e18)) {
      d[w] = d[v] + c;
      if (!dfs(w)) return false;
    }
    else {
      if (d[w] != d[v] + c) return false;
    }
  }
  return true;
}

void solve(ll N, ll M, vector<ll> L, vector<ll> R, vector<ll> D) {
  REP(i,M) {
    int s = L[i] - 1, t = R[i] - 1, d = D[i];
    g[s].emplace_back(t, d);
    g[t].emplace_back(s, -d);
  }
  REP(i,N) d[i] = ll(1e18);
  bool ok = true;
  REP(i,N) {
    if (d[i] != ll(1e18)) continue;
    // cout << i << endl;
    d[i] = 0;
    if (!dfs(i)) ok = false;
  }
  // REP(i,N) cout << d[i] << endl;
  cout << ok << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll M;
	ll N;
	scanf("%lld", &N);
	scanf("%lld", &M);
	vector<ll> L(M-1+1);
	vector<ll> R(M-1+1);
	vector<ll> D(M-1+1);
	for (int i = 0 ; i <= M-1 ; i++) {
	  scanf("%lld", &L[i]);
	  scanf("%lld", &R[i]);
	  scanf("%lld", &D[i]);
	}
	solve(N, M, L, R, D);
	return 0;
}


Measured memory_bytes: 21760
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    int nodd = 0;
    int a;
    rep (i, n)
    {
        cin >> a;
        if (a & 1) ++nodd;
    }

    cout  << (nodd > 0 ? "first\n" : "second\n");
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int max(int a, int b) {
	if (a < b) {
		return b;
	}
	else {
		return a;
	}
}
int main() {
	string S;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
	
		if (S[i] == 'A' || S[i] == 'G' || S[i] == 'C' || S[i] == 'T') {
			S[i] ='A';
		}
		else {
			S[i] ='N';
		}
	}
	

	int ma = 1; 
	int a = 0, cpy = 0;
	for (int i = 0; i < S.size(); i++) {
		for (int j = 1; j <= S.size()-i; j++) {
			string sub = S.substr(i, j);
			
			for (int k = 0; k < sub.size(); k++) {
				if (sub[k] == 'A') {
					ma = ma * 1;
				}
				else {
					ma = ma * 0;
				}

			}
			if (ma == 1) {
				a = sub.size();
			}
			cpy = max(a, cpy);
		} ma = 1;
   }
	cout << cpy;
	system("pause");
	return 0;
}



Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX_V = 100005;

vector<int> G[MAX_V];
vector<int> color(MAX_V);

// 辺に属性がある場合
/*
struct edge {int to,cost;};
vector<edge> G[MAX_V];
*/

// 2部グラフの場合: b*w - m 2部グラフでない場合: n(n-1)/2 - m
bool dfs(int v, int c){
    color[v] = c;
    rep(i, G[v].size()){
        if(color[G[v][i]] == c) return false;
        if(color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
    }
    return true;
}

int main(){
    ll N, M;
    cin >> N >> M;
    rep(i, M){
        int s, t;
        cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
        // 無向グラフの場合
        G[t].push_back(s);
    }

    // グラフの操作
    ll B = 0, W = 0;
    if(dfs(0, 1)){
        rep(i, N){
            if(color[i] == 1){
                B++;
            }
            else if(color[i] == -1){
                W++;
            }
        }
        cout << B*W - M << endl;
    }
    else {
        cout << ((N * (N-1)) / 2) - M << endl;
    }
}

Measured memory_bytes: 9444
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
  int s;
  cin >> s;
  vector<int> v;
  vector<int> d(1000000, 0);
  for (int i = 0; ; i++) {
    if (i == 0) {
      v.push_back(s);
      d.at(s)++;
      continue;
    }
    if (v.at(i - 1) % 2 == 0) {
      v.push_back(v.at(i - 1) / 2);
      d.at(v.at(i - 1) / 2)++;
    } else {
      v.push_back(3 * (v.at(i - 1)) + 1);
      d.at(3 * (v.at(i - 1)) + 1)++;
    }

    for (int j = 0; j < d.size(); j++) {
      if (d.at(j) == 2) {
        cout << i + 1 << endl;
        return 0;
      }
    }

  }

}

Measured memory_bytes: 4096
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
    int flag=0;
    while(1)
    {
	int sum,price,coin[4]={0},exchange[4]={0},value[4]={10,50,100,500};
	cin >> price;
	if (price == 0)
	    break;
	if (flag == 0)
	{
	    flag = 1;
	} else {
	    cout << endl;
	}
	sum = 0;
	for(int i=0; i<4; i++)
	{
	    cin >> coin[i];
	    sum += coin[i]*value[i];
	}
	sum -= price;
	for (int i=3; i>=0; i--)
	{
	    while(value[i] <= sum)
	    {
		sum -= value[i];
		exchange[i]++;
	    }
	}
	for (int i=0; i<4; i++)
	{
	    while(coin[i] > 0 && exchange[i] > 0)
	    {
		coin[i]--;
		exchange[i]--;
	    }
	    if (coin[i] > 0)
	    {
		cout << value[i] << " " << coin[i] << endl;
	    }
	}
    }
}

Measured memory_bytes: 864
#include<stdio.h>
int main(void){
    int i=0;
    int count[36]={};
    char C;
    while(scanf("%c",&C)==1){
        if('A'<=C && C<='Z'){
            count[C-65]++;
        }
        else if('a'<=C && C<='z'){
            count[C-97]++;
        }
    }

    for(i=97;i<123;i++){
        printf("%c : %d\n",i,count[i-97]);
    }
    return 0;
}


Measured memory_bytes: 2048
import itertools

a,b,m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
P = [list(map(int,input().split())) for i in range(m)]
y = []
#普通に足算する
aa = min(A)
bb = min(B)
xx =aa+bb

#割引券使う
for i in range(m):
  y.append(A[P[i][0]-1] + B[P[i][1]-1] - P[i][2])
#min出す
yy = min(y)

print(min(xx,yy))

Measured memory_bytes: 42536
#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    set<char> st;
    for (int i = 0; i < s.length(); i++) {
        st.insert(s.at(i));
    }

    if (st.size() == s.length()) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <deque>
using namespace std;
using ll = long long;
using itn = int;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;

int main() {

    int n;
    cin >> n;

    vector<int> k(n);
    for (int i = 0; i < n; i++) {
        cin >> k[i];
    }

    sort(k.begin(), k.end());

    cout << k[n/2] - k[(n/2) -1] << endl;
    return 0;
    
    

}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<=(n);++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const double Pi = acos(-1);
const ll mod=1e9+7;

int main(){
    int a,b;
    cin >>a>>b;
    cout << a*b <<endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int a, b;
  cin >> a >> b;
  for (int i = 0; i < max(a, b); i ++) cout << min(a, b);
  cout << endl;
}


Measured memory_bytes: 256
//Leo
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=1e9+1e8;
int n,maxx,mini,ans,k,a[1000000];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) if(a[i]>maxx) maxx=a[i],k=i;
	mini=inf;
	for(int i=1;i<=n;i++) if(abs(maxx/2-a[i])<mini && k != i) ans=a[i],mini=abs(maxx/2-a[i]);
	printf("%d %d\n",maxx,ans);
	return 0;
}

Measured memory_bytes: 640
def getDis(k, abc, n):
    r = [[] for i in range(n)]
    for a, b, c in abc:
        r[a-1] += [(b-1, c)]
        r[b-1] += [(a-1, c)]
    dis = [-1] * n
    stack = [k]
    dis[k] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in r[label]:
            if dis[i] == -1:
                dis[i] = dis[label] + c
                stack.append(i)
    return dis


N = int(input())
abc = [[int(i) for i in input().split()] for i in range(N-1)]
Q, K = map(int, input().split())
xy = [[int(i) for i in input().split()] for i in range(Q)]
d = getDis(K-1, abc, N)
for i in range(Q):
    print(d[xy[i][0] - 1] + d[xy[i][1] - 1])


Measured memory_bytes: 78136
import math 

K  = int(input())
total  = 0

for s in range(1,K+1):
    for t in range(1,K+1):
        alpha = math.gcd(s,t)
        if alpha == 1:
            total += K
            continue
        for u in range(1,K+1):
            # print(s,t,u,math.gcd(alpha,u))
            total +=math.gcd(alpha,u)

print(total)


Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;
  int n=s.size();
  string t="";
  
  for(int i=0;i<n;i++){
    if(s[i]=='B'){
      if(t.size()>0) t.pop_back();
    }
    else t+=s[i];
  }
  
  cout << t << endl;
}

Measured memory_bytes: 3628
S = [ _ for _ in input()]
ACGT = ["A", "C", "G", "T"]
ans = 0
for i, data in enumerate(S):
    if data not in ACGT:
        continue
    if i >= len(S):
        break

    cnt = 1
    for j in range(i + 1, len(S)):
        if S[j] not in ACGT:
            ans = max(ans, cnt)
            break

        cnt += 1

    ans = max(ans, cnt)

print(ans)


Measured memory_bytes: 3060
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

import collections
pq=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    while len(pq) > 0 and pq[0][0] < x:
        totalDamage -= pq[0][1]
        pq.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    pq.append((x+2*d,dam))

print(ans)

Measured memory_bytes: 85824
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using LL = long long;

int dp[1234567];

int main(){
    for(int i=10;i<=1000000;++i){
        int d=0;
        int val=i;
        while(val>0){
            val/=10;
            d++;
        }
        int ten=1;
        int maxval=0;
        for(int e=0;e<d-1;++e){
            ten*=10;
            int lo=i%ten;
            int hi=(i-lo)/ten;
            //dp[i]=max(dp[i],dp[lo*hi]+1);
            maxval=max(maxval,lo*hi);
            //assert(lo*hi<i);
            //cout<<dp[i]<<endl;
        }
        dp[i]=dp[maxval]+1;
    }
    int Q;
    cin>>Q;
    for(int i=0;i<Q;++i){
        int r;
        cin>>r;
        cout<<dp[r]<<endl;
    }
    return 0;
}



Measured memory_bytes: 7020
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> dp(n+2);
  vector<int> broken(n);
  rep(i,m){
    int a;
    cin >> a;
    broken[a] = 1;
  }
  dp[n] = 1;
  for(int i=n-1;i>=0;i--){
    if(broken[i]==1){
      dp[i] = 0;
      continue;
    }
    dp[i] = (dp[i+1] + dp[i+2])%1000000007;
  }
  
  cout << dp[0] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned short int us;

#define forn(i, n) for (int i = 0; i < int(n); ++i)

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(15);

    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; ++i)
        cin >> h[i];

    vector<int> a(n);

    for (int i = 1; i < n; ++i)
    {
        a[i] = a[i - 1] + abs(h[i - 1] - h[i]);

        for (int j = max(0, i - k); j < i - 1; ++j)
            a[i] = min(a[i], a[j] + abs(h[j] - h[i]));
    }

    cout << a[n - 1];
}























Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>

#if defined SUBLIME
#  define ISTREAM ss
#else
#  define ISTREAM cin
#endif


using namespace std;
int main()
{
	#if defined SUBLIME
		string str = "12300 99";
		stringstream ss;
		ss << str;
	#endif
	int a, b;
	double c;
	ISTREAM >> a >> b;
	c = (double) (a % b) / b;
	cout << a / b << " " << a % b << " " << fixed << setprecision(8) << (double) a / b << endl;
}

Measured memory_bytes: 3212
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)


int main(){
    vector<int> v;
    while(1){
        char x;
        cin >> x;
        if(cin.eof()){
            break;
        }
        v.push_back(x);
    }
    rep(i, v.size()){
        cout << 'x';
    }
    cout << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#else
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
 public:
  int c[22], d[22];
  int a[22][22];
  void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n; ++i) {
      cin >> c[i];
      for (int j = 0; j < m; ++j) cin >> a[i][j];
    }
    int ans = MOD;
    for (int i = 0; i < (1 << n); ++i) {
      memset(d, 0, sizeof d);
      int sum = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          sum += c[j];
          for (int ii = 0; ii < m; ++ii) d[ii] += a[j][ii];
        }
      }
      bool ok = 1;
      for (int j = 0; j < m; ++j) {
        if (d[j] < x) ok = 0;
      }
      if (ok) {
        ans = min(ans, sum);
      }
    }
    if (ans == MOD)
      cout << -1 << '\n';
    else
      cout << ans << '\n';
  }
} NSPACE;
int main() {
  FPEN;
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  NSPACE.solve();
}

Measured memory_bytes: 3652
#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int n, m, sum=1;
	
	cin >> n >> m;
	
	for(int i=0; i<n; i++){
		if(i == 0) sum *= m;
		else{
			sum *= m - 1; 
		} 
	}
	
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static long[] ReadLongArray()
    {
        return ReadLine().Split().Select(x => long.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
        var tmp = ReadLongArray();
        long n = tmp[0], m = tmp[1], d = tmp[2];
        double ans = (n-d) * (m-1) * 2.0 / (n * n);
        if (d == 0) ans /= 2.0;
        WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;

//  Utility method to convert integer into string
string toString(int n)
{
    string str;
    stringstream ss;
    ss << n;
    ss >> str;
    return str;
}

// Method to convert n to base negBase
string toNegativeBase(int n, int negBase)
{
    //  If n is zero then in any base it will be 0 only
    if (n == 0)
        return "0";

    string converted = "";
    while (n != 0)
    {
        // Get remainder by negative base, it can be
        // negative also
        int remainder = n % negBase;
        n /= negBase;

        // if remainder is negative, add abs(base) to
        // it and add 1 to n
        if (remainder < 0)
        {
            remainder += (-negBase);
            n += 1;
        }

        // convert remainder to string add into the result
        converted = toString(remainder) + converted;
    }

    return converted;
}

//  Driver code to test above methods
int main()
{
    int n ;
    cin>>n;
    int negBase = -2;

    cout << toNegativeBase(n, negBase);

    return 0;
} 

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
	int n;
	int count = 0;
	char in, log = 0;
	scanf("%d", &n);
	scanf("%*c");
	for(int i = 0; i < n; i++){
		scanf("%c", &in);
		if(in != log){
			log = in;
			count++;
		}
	}
	printf("%d\n", count);
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

bool ans[100][100];
int n;
int a[100], b[100];
int in[100], out[100];

struct edge {
	int to, cap, rev;
	edge(int a, int b, int c) { to = a, cap = b, rev = c; }
};

vector<vector<edge>> G;
bool used[200];

void add_edge(int from, int to, int cap) {
	G[from].push_back(edge(to, cap, G[to].size()));
	G[to].push_back(edge(from, 0, G[from].size() - 1));
}

int dfs(int v, int t, int f) {
	if (v == t) {
		return f;
	}
	used[v] = true;
	for (int i = 0; i < G[v].size(); i++) {
		edge &e = G[v][i];
		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int getflow(int s, int t) {
	int flow = 0;
	while (1) {
		for (int i = 0; i < 200; i++)used[i] = false;
		int f = dfs(s, t, 1000000000);
		if (f == 0)return flow;
		flow += f;
	}
}

int main() {
	cin >> n;
	int sum = 0, s1 = 0, s2 = 0;
	int sum2 = 0;
	for (int i = 0; i < n + 1; i++) {
		cin >> a[i];
		sum += a[i] * i;
		s1 += a[i];
	}
	sum2 = sum;
	for (int i = 0; i < n + 1; i++) {
		cin >> b[i];
		sum -= b[i] * i;
		s2 += b[i];
	}
	if (sum != 0 || s1 != n || s2 != n) {
		cout << "NO" << endl;
		return 0;
	}
	int Sum = 0;
	for (int i = 0; i < n + 1; i++) {
		for (int j = 0; j < a[i]; j++) {
			in[Sum] = i;
			Sum++;
		}
	}
	Sum = 0;
	for (int i = 0; i < n + 1; i++) {
		for (int j = 0; j < b[i]; j++) {
			out[Sum] = i;
			Sum++;
		}
	}

	//building edge
	G.resize(1 + n + n + 1);
	for (int i = 0; i < n; i++) {
		add_edge(0, i + 1, out[i]);
	}
	for (int i = 0; i < n; i++) {
		add_edge(i + n + 1, 2 * n + 1, in[i]);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			add_edge(i + 1, j + n + 1, 1);
		}
	}

	int ret = getflow(0, 2 * n + 1);
	if (ret != sum2) {
		cout << "NO" << endl;
		return 0;
	}
	cout << "YES" << endl;

	//フローから経路を復元していく

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < G[i + 1].size(); j++) {
			if (G[i + 1][j].cap == 0) {
				ans[i][G[i + 1][j].to - n - 1] = true;
			}
		}
	}

	//出力
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << ans[i][j];
			if (j != n - 1)cout << " ";
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    map<ll, int> mp;
    ll s = 0;
    ll ans = 0;
    int n;
    cin >> n;
    mp[0] = 1;
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        s += t;
        if (mp.count(s)) {
            ans += mp[s];
        }
        ++mp[s];
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 12800