akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef vector<double> Vec;
typedef vector<Vec> Mat;
typedef pair<ll,ll> P;
typedef pair<double,ll> Pd;
typedef priority_queue<P,vector<P>,greater<P>> P_queue;
typedef priority_queue<Pd,vector<Pd>,greater<Pd>> Pd_queue;

const ll MOD=998244353;
const ll mod=1000000007;
const ll INF=1e15;
const double DEL=1e-6;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

#define REP(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define SORT(a) sort(ALL(a))
#define U_ERASE(V) V.erase(unique(ALL(V)), V.end());
#define ADD(a,b) a=(a+b)%mod
ll N;
ll ans=0;
vec d;
const ll MAXN=1000010;
bool arrived[MAXN];

void Solve(ll i){
    if(arrived[d[i]]) return;
    if(i==N-1) ans++;
    else if(d[i]!=d[i+1]) ans++;
   // cout<<"arrived"<<endl;
    for(ll j=1; j*d[i]<MAXN; j++) arrived[d[i]*j]=true;
    return;
}
int main(){
    ll N,K; cin>>N>>K;
    vec d(N);
    rep(i,N) cin>>d[i];
    sort(ALL(d));
    ll ans=0;
    rep(i,K) ans+=d[i];
    cout<<ans<<endl;

}

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

int main()
{
    int n;
    cin >> n;
    ll xsum = 0;
    rep(i, n)
    {
        ll a;
        cin >> a;
        xsum = xsum ^ a;
    }
    if (xsum == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
    
  string s, t; cin >> s >> t;
  if (s == t.substr(0, s.size())) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


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

using namespace std;

int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin>>str;
    if(str[0]=='A'&&str[1]=='R'&&str[2]=='C')
    cout<<"ABC"<<endl;
    else
    cout<<"ARC"<<endl;

    return 0;
}


Measured memory_bytes: 3648
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
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; }
int INF=1e10;
int MOD=1e9+7;
signed main(){
 int a;
  cin>>a;
  int b=a%10;
  if(b==3)
    cout<<"bon";
  else if(b==0||b==1||b==6||b==8)
    cout<<"pon";
  else
    cout<<"hon";
}

Measured memory_bytes: 3652
#include<stdio.h>
#include<string.h>
int main(){
        int t[200],h[200];
        int n,m;
        int i,j;
        int temp;
        int sum=999,a,b;
        int sumt,sumh;
        while(1){
                memset(t,0,sizeof(t));
                memset(h,0,sizeof(h));
                scanf("%d %d",&n,&m);
                if(n==0&&m==0)break;
                sumt=0;
                for(i=0;i<n;i++){
                        scanf("%d",&t[i]);
                        sumt+=t[i];
                }
                sumh=0;
                for(i=0;i<m;i++){
                        scanf("%d",&h[i]);
                        sumh+=h[i];
                }
                for(i=0;i<n-1;i++){
                        for(j=i+1;j<n;j++){
                                if(t[i]>t[j]){
                                        temp=t[i];
                                        t[i]=t[j];
                                        t[j]=temp;
                                }
                        }
                }
                for(i=0;i<m-1;i++){
                        for(j=i+1;j<m;j++){
                                if(h[i]>h[j]){
                                        temp=h[i];
                                        h[i]=h[j];
                                        h[j]=temp;
                                }
                        }
                }
sum=999;
                for(i=0;i<n;i++){
                        for(j=0;j<m;j++){
//                              printf("*%d %d\n",t[i],h[j]);
                                if(sumt-t[i]+h[j]==sumh+t[i]-h[j]){
                                        if(sum>t[i]+h[j]){
                                                sum=t[i]+h[j];
                                                a=t[i];
                                                b=h[j];
                                        }
                                }
                        }
                }
                if(sum==999){
                        printf("-1\n");
                }else{
                        printf("%d %d\n",a,b);
                }
        }
        return 0;
}

Measured memory_bytes: 612
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(graph, edges, now, ret):
    edges[now] = True
    if all(edges): ret += 1

    for next in graph[now]:
        if edges[next]: continue
        ret = dfs(graph, edges, next, ret)
    edges[now] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ret = 0
    edges = [False] * N
    edges[0] = True
    ret = dfs(g, edges, 0, ret)
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define Data_Nerd ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define files freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
using namespace std;
typedef long long ll;

const int N = 1e5;

int arr[N], memo[N], n, k;

int dp() {
	for(int i = 2; i < n; ++i)
		memo[i] = 1e9;
	memo[1] = abs(arr[0] - arr[1]);
	for(int i = 2; i < n; ++i)
		for(int j = i - 1; j >= max(0, i - k); --j)
			memo[i] = min(memo[i], abs(arr[i] - arr[j]) + memo[j]);
	return memo[n - 1];
}

int main() {
    Data_Nerd

	scanf("%d%d", &n, &k);

    for(int i = 0; i < n; ++i)
    	scanf("%d", arr + i);

    cout << dp();

    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

vector<vector<int>> dp;

int main(void) {
    int N, K;
    cin >> N >> K;

    int R, S, P;
    cin >> R >> S >> P;
    map<char, int> win;
    win['r'] = P;
    win['s'] = R;
    win['p'] = S;

    string T;
    cin >> T;
    int tlen = (int) T.size();
    T = " " + T;

    dp.resize(tlen + 1, vector<int>(3, 0));
    for (int i = 1; i <= tlen; i++) {
        if (i <= K) {
            if (T[i] == 'r') {
                dp[i][0] = win['r'];
            } else if (T[i] == 's') {
                dp[i][1] = win['s'];
            } else {
                dp[i][2] = win['p'];
            }
        } else {
            int prev_max = max(max(dp[i - K][0], dp[i - K][1]), dp[i - K][2]);
            dp[i][0] = prev_max;
            dp[i][1] = prev_max;
            dp[i][2] = prev_max;

            if (T[i] == 'r') {
                dp[i][0] = max(dp[i - K][1], dp[i - K][2]) + win['r'];
            } else if (T[i] == 's') {
                dp[i][1] = max(dp[i - K][0], dp[i - K][2]) + win['s'];
            } else {
                dp[i][2] = max(dp[i - K][0], dp[i - K][1]) + win['p'];
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < K; i++) {
        ans += max(max(dp[tlen - i][0], dp[tlen - i][1]), dp[tlen - i][2]);
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int n;
double v[51];

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}
	sort(v, v + n);
	double ans = v[0];
	for (int i = 1; i < n; ++i)
	{
		ans = (ans + v[i]) / 2;
	}
	cout << ans << endl;
}

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

struct PotentializedUnionFind{
    vector<int> par,rank,diff_weight;

    //はじめに全てが根であるとしておく
    PotentializedUnionFind(int N):par(N),rank(N,0),diff_weight(N,0){iota(par.begin(),par.end(),0);}

    int root(int x){//根に当たるまで再帰で探す
        if(par[x] == x) return x;
        else{
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = root(par[x]);
        }
    }

    bool unite(int x, int y,int w){//根が同じでなかったらつなげる
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if(x == y) return false;
        if(rank[x] < rank[y]){
            diff_weight[x] -= w;
            par[x] = y;
        }
        else{
            diff_weight[y] += w;
            par[y] = x;
            if(rank[x] == rank[y]) ++rank[x];
        }
        return true;
    }

    bool same(int x,int y){//つながっているかどうか判定
        return root(x) == root(y);
    }

    int weight(int x){
        root(x);
        return diff_weight[x];
    }

    int diff(int x,int y){
        return weight(y) - weight(x);
    }
};

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

    int N,M,L,R,D;
    cin >> N >> M;
    PotentializedUnionFind PUF(N);
    for(int i = 0;i < M;++i){
        cin >> L >> R >> D;
        --L,--R;
        if(PUF.same(L,R)){
            int diff = PUF.diff(L,R);
            if(diff != D){
                cout << "No" << endl;
                return 0;
            }
        }
        else{
            PUF.unite(L,R,D);
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <random>
using namespace std;
typedef long long ll;
const ll inf = 1001001001001001;

int D;
int v=27;
vector<int> c(v,0);
vector<vector<int>> s;
vector<int> t;
vector<int> last(v,0);

void init(){
    cin >> D;
    s.resize(D+1);
    t.resize(D+1);
    for(int i=0;i<D+1;i++){
        s[i].resize(v);
    }

    for(int i=1;i<27;i++){
        cin >> c.at(i);
    }
    for(int i=1;i<D+1;i++){
        for(int j=1;j<27;j++){
            cin >> s.at(i).at(j);
        }
    }
/*
    for(int i=1;i<D+1;i++){
        cin >> t.at(i);
    }
*/

}

void init_last(){
  for(int i=0;i<v;i++){
    last.at(i) = 0;
  }
}

void calc(){
    init_last();
  	ll sum=0;
  	for(int d=1;d<D+1;d++){
      	//day d: i
      	ll best_of_day=-inf;
      	for(int i=1;i<27;i++){
          	ll sum_of_day=0;
          	vector<int> tmp_last = last;
          	sum_of_day += s.at(d).at(i);
          	tmp_last.at(i) = 0;
          	for(int j=1;j<27;j++){
              	sum_of_day -= c.at(j) * (d - tmp_last.at(j));
            }
          
          	if(sum_of_day > best_of_day){
              	best_of_day = sum_of_day;
              	last = tmp_last;
              	t.at(d) = i;
            }
        }      
    }
}

int main(){
    init();
  	calc();
  	for(int i=1;i<D+1;i++){
      cout << t.at(i) << endl;
    }
  	return(0);
}

Measured memory_bytes: 3700
#include <iostream>
#include <string>

using namespace std;

int main () {
  string s;
  cin >> s;

  int ans = s[0] - '1';
  ans += 9 * ((int) s.size() - 1);

  int dans = 0;
  for (char c : s) {
    dans += c - '0';
  }
  
  cout << max(ans, dans) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;

int main()
{
    // 整数の入力
    ll N,M;
    cin >> N>>M;
    if (N == M){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n = int(input())

ans=[0]*(n+100000)

import math
for x in range(1,int(math.sqrt(n+1)+1)):
    if x**2 > n:
        break
    for y in range(1,int(math.sqrt(n+1)+1)):
        if x**2 +y**2 + x*y> n:
            break
        for z in range(1,int(math.sqrt(n+1)+1)):
            calc = x**2+y**2+z**2+x*y+y*z+z*x
            ans[calc]+=1

for i in range(1,n+1):
    print(ans[i])

Measured memory_bytes: 70040
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll h,w;cin >> h >>w;
    vector<vector<char>> g(h,vector<char>(w));
    rep(i,h)rep(j,w)cin >> g[i][j];
    ll ans=0;
    vvl seen(h,vl(w,0));
    ll cnt=0;
    queue<pl> que;
    rep(i,h)rep(j,w){
        if(g[i][j]=='#'){
            seen[i][j]=1;
            que.push({i,j});
            cnt++;
        }
    }
    while(1){
        if(cnt==h*w)break;
        ans++;
        queue<pl> nque;
        while(!que.empty()){
            pl v=que.front();
            que.pop();
            rep(i,4){
                ll ny=v.fi+dy[i],nx=v.se+dx[i];
                if(ny<0||nx<0||ny>=h||nx>=w)continue;
                if(seen[ny][nx]==0&&g[ny][nx]=='.'){
                    g[ny][nx]='#';
                    seen[ny][nx]=1;nque.push({ny,nx});
                    cnt++;
                }
            }
        }
        que=nque;
    }
    cout <<ans <<endl;
}

Measured memory_bytes: 25524
package main

import (
  "fmt"
  "math"
)

func main() {
  var x, a, b int
  fmt.Scanf("%d %d %d", &x, &a, &b)
  
  da := math.Abs(float64(x - a))
  db := math.Abs(float64(x - b))

  ans := "A"
  if db < da {
    ans ="B"
  }
  fmt.Printf("%s\n", ans)
}

Measured memory_bytes: 1836
#include<stdio.h>
int main()
{
  long int i,N;
  char S[10*10*10*10*10];	// おいしさ
  long int sum = 1;	// おいしさのサム値
  // 数を取得
  scanf("%d",&N);
  
  // 文字列を取得
  scanf("%s", S);
  
  for(i=1;i<N;i++)
  {
    if(S[i]==S[i-1])
    {
//      printf("一緒:%d,%c\n", i,S[i]);
    }
    else
    {
      sum++;
//      printf("違う:%d,%c\n", i,S[i]);
    }
  }
 
  printf("%d",sum);
 
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>
using namespace std;

int pow(int x,int y){
    int ret=1;
    while(y>0){
        ret*=x;
        y--;
    }
    return ret;
}

int index(string str){
    int ret=0,i;
    int len=str.length();
    for(i=0;i<len;i++){
        if(str[i]=='A')ret+=pow(4,i);
        if(str[i]=='C')ret+=pow(4,i)*2;
        if(str[i]=='G')ret+=pow(4,i)*3;
        if(str[i]=='T')ret+=pow(4,i)*4;
    }
    ret--;
    return ret;
}

int main(void){
    bool* dic=(bool*)malloc(sizeof(bool)*16777216);
    memset(dic,0,sizeof(dic));
    int n,i;
    string str;
    char order[7];
    
    cin>>n;
    
    for(i=0;i<n;i++){
        cin>>order>>str;
        if(order[0]=='i'){
            dic[index(str)]=1;
        }
        else{
            if(dic[index(str)]){
                cout<<"yes"<<endl;
            }
            else{
                cout<<"no"<<endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 4516
#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <numeric> // accumulate(begin,end,初期値)

typedef long long ll;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<x<<endl;
#define rep(i,n) for(ll i = 0;i < n;++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SUM(vec) accumulate(all(vec),0);

const ll INF = 1e9+7;

// 各桁の和
template<typename T>
T digit(T num){
  T sum = 0;
  while(num){
    sum += num % 10;
    num /= 10;
  }
  return sum;
}

int main(){
  ll N,M;
  cin>>N>>M;
  vector<int> dp(N+100,0);dp[0] = 1;
  vector<bool> isOk(N+1,true);
  rep(i,M){
    int a;
    cin>>a;
    isOk[a] = false;
  }

  
  rep(i,N){
    for(int j = i + 1;j <= min(N,i+2);++j){
      if(isOk[j]){
        dp[j] += dp[i];
        dp[j] %= INF;
      }
    }
  }

  print(dp[N])
  return 0;
}


Measured memory_bytes: 640
<?php
    // get inputs from stdin
    $input = intval(fgets(STDIN));
    // when value is 1
    if($input === 1) {
        echo 1;

    }
    // when value is odd 
    else if($input % 2 === 1) {
        echo ((intval($input/2) + 1)/$input);
    }

    // when value is even
    else {
        echo 0.5;
    }

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

using namespace std;
typedef long long ll;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  int n;
  while (cin >> n, n) {
    vector<string> s(n);
    vector<int> d(n, 0);
    for (int i = 0; i < n; i++) {
      cin >> s[i];
      while (d[i] < s[i].size() && s[i][d[i]] == '.') d[i]++;
    }

    for (int i = 0; i < n; i++) {
      int last = i;
      for (int j = i + 1; j < n && d[j] > d[i]; j++) {
        if (d[j] == d[i] + 1) last = j;
      }
      for (int j = i + 1; j <= last; j++) {
        if (d[j] == d[i] + 1) s[j][d[i]] = '+';
        else s[j][d[i]] = '|';
      }
    }

    for (int i = 0; i < n; i++) {
      replace(s[i].begin(), s[i].end(), '.', ' ');
      cout << s[i] << endl;
    }
  }

  return 0;
}


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

int n;
string choice = "abcdefghij";

int generate(string Argstr, int decided, int endlim, int now_letter) {
  string temp = Argstr;
  if (decided + 1 == endlim) {
    for (size_t i = 0; i < now_letter + 1; i++) {
      temp.at(decided) = choice.at(i);
      cout << temp << endl;
    }
  }else{
    for (size_t i = 0; i < now_letter; i++) {
      temp.at(decided) = choice.at(i);
      generate(temp, decided + 1, endlim, now_letter);
    }
    if (decided != 0) {
      temp.at(decided) = choice.at(now_letter);
      generate(temp, decided + 1, endlim, now_letter + 1);
    }
  }
  return 0;
}

int main() {
  cin >> n;
  string str(n,'a');
  if (n == 1) {
    cout << "a" << endl;
  }else{
    generate(str, 0, n, 1);
  }
  return 0;
}


Measured memory_bytes: 1536
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        while(true){
            int H = sc.nextInt();
            int W = sc.nextInt();
            if(H == 0 && W == 0) break;

            for(int j=0; j<H; j++){
                for(int i=0; i<W; i++){
                     if((i*j==0) || i==W-1 || j==H-1) System.out.print("#");
                     else System.out.print(".");
                }
                System.out.println("");
            }
            System.out.println("");
        }
    }
}


Measured memory_bytes: 34644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main()
{
	ll a, b, ans = 1;
	scanf("%lld %lld", &a, &b);
	
	ll fpb = __gcd(a, b);
	ll temp = fpb;
	
	for(ll i = 2; i * i <= fpb and temp > 1; i++){
		if(temp % i == 0) ans++;
		while(temp % i == 0) temp /= i;
	}
	if(temp > 1) ans++;
	printf("%lld\n", ans);
}

Measured memory_bytes: 3796
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;


int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

string s1,s2;
cin>>s1;
cin>>s2;
int n=0;
for(int i = 0;i<s1.size();i++){
    if(s1[i]!=s2[i]){
        n++;
    }
}
cout<<n;



return 0;

}


Measured memory_bytes: 3800
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  bool four = false;
  string S;
  for(int i=0; i<N; i++){
    cin >> S;
    if(S == "Y"){
      four = true;
    }
  }
  if(four) {
    cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
}

Measured memory_bytes: 256
H,W = map(int,input().split())
H_cnt = 0
maze = ["" for _ in range(W)]
maze_ok = [True]*W
for _ in range(H):
  m = input()
  if m != "."*W:
    for i in range(W):
      maze[i] += m[i]
  else:
    H_cnt += 1
for i in range(W):
  if maze[i]=="."*(H-H_cnt):
    maze_ok[i]=False

ans = ["" for _ in range(H-H_cnt)]
for i in range(H-H_cnt):
  for j in range(W):
    if maze_ok[j]:
      ans[i] += maze[j][i]

for a in ans:
  print(a)
                 
    
    
    
    
    
  
    




Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>

int main(void)
{
	int coin[301], coin_next[301];
	int i, j, k;
	int paid;
	int a;
	
	memset(coin, 0, sizeof(coin));
	coin[0] = 1;

	for (i = 1; i <= 17; i++){					// 種別
		memset(coin_next, 0, sizeof(coin_next));
		for (j = 0; j <= 300 / (i * i); j++){	// 枚数
			for (k = 0; k <= 300; k++){
				if (coin[k] != 0){
					if (k + (i * i) * j <= 300){
						coin_next[k + (i * i) * j] += coin[k];
					}
				}
			}
		}
		memcpy(coin, coin_next, sizeof(coin));

	}

	while (1){
		scanf("%d", &paid);
		if (paid == 0){
			break;
		}

		printf("%d\n", coin[paid]);
	}
	return (0);
}

Measured memory_bytes: 600
class Solver(object):
    def __init__(self):
        self.s = input()
        self.k = int(input())
        self.compressed = self.to_compressed_format(self.s)

    def solve(self):
        if (self.compressed[0][0] == 1) and (self.k <= self.compressed[0][1]):
            print(1)
            return
        else:
            for i in self.s:
                if int(i) != 1:
                    print(i)
                    return
            print(1)
            return

    def wrong_solve(self):
        print(self.compressed)
        counter = 0
        for (n, count) in self.compressed:
            print(n, count)
            counter += self.length_after(n, count)
            print("chk")
            if counter >= self.k:
                return n

    @staticmethod
    def length_after(n, count):
        return count * (n ** (5 * (10 ** 15)))

    @staticmethod
    def to_compressed_format(s):
        res = []
        counter = 1
        prev = int(s[0])
        for c in s[1:]:
            n = int(c)
            if n == prev:
                counter += 1
            else:
                res.append((prev, counter))
                prev = int(n)
                counter = 1
        res.append((prev, counter))
        return res


if __name__ == "__main__":
    s = Solver()
    s.solve()

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

using namespace std;

typedef long long ll;

#define FOR(a, b, i) for(int i=a; i<b; i++)
#define RFOR(a, b, i) for(int i=a; i>=b; i--)
#define PB push_back
#define MP make_pair
#define MOD 1e9+7
#define newline cout<<"\n"


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int w, h, x, y; cin>>w>>h>>x>>y;

    double area = (double)w*(double)h;
    area /=2;

    cout<<area<<" ";

    if(x*2==w && y*2==h) cout<<1<<endl;
    else cout<<0<<endl; 




    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iterator>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= 9; i++) {
		if (i * 111 >= N) {
			cout << i * 111;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

string s;

int main(){
	getline(cin,s);
	while(getline(cin,s)){
		int a=s.find("Hoshino");
		while(a!=string::npos){
			s=s.substr(0,a)+"Hoshina"+s.substr(a+7);
			a=s.find("Hoshino");
		}
		cout<<s<<endl;
	}
}

Measured memory_bytes: 0
#--Strings with the Same Length

N = int(input())
S, T = map(str, input().split())

s_str = list(S)
t_str = list(T)

ans = " "
connect = [0] * N

for num in range(N):
  connect[num] = s_str[num] + t_str[num]
  ans = ans + connect[num]

print(ans)


Measured memory_bytes: 3060
S = input()

INF = float("inf")

l = ""

def bsr(a, v, lo = 0, hi = None):
	if hi == None:
		hi = len(a) - 1
	if hi < lo:
		return lo
	mi = (lo + hi) // 2
	if v < a[mi]:
		hi = mi - 1
	else:
		lo = mi + 1
	return bsr(a, v, lo, hi)

sep = []
for i, s in enumerate(S):
	if l == "R" and s == "L":
		sep.append(i)
	l = s
sep = [-INF] + sep + [INF]

count = [0] * (len(S) + 1)

for i, s in enumerate(S):
	p = bsr(sep, i)
	if s == "L":
		p -= 1
	p = sep[p]
	if abs(p - i) % 2 == 0:
		count[p] += 1
	else:
		count[p - 1] += 1

print(*count[:-1], sep=" ")


Measured memory_bytes: 8276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
  int X, Y, Z, K;
  cin >> X >> Y >> Z;
  cin >> K;
  ll A[X];
  ll B[Y];
  ll C[Z];
  for(int i = 0; i<X; i++) cin >> A[i];
  for(int i = 0; i<Y; i++) cin >> B[i];
  for(int i = 0; i<Z; i++) cin >> C[i]; sort(C, C+Z, greater<>());
  
  vector<ll> vec;
  for(int i=0; i<X; i++){
    for(int j=0; j<Y; j++){
      vec.push_back(A[i]+B[j]);
    }
  }
  sort(vec.begin(), vec.end(), greater<>());
  
  int minNum = min(K, X*Y);  
  priority_queue<ll> que;
  for(int i=0; i<minNum; i++){
    for(int j=0; j<Z; j++){
      que.push(vec[i]+C[j]);
    }
  }
  for(int i=0; i<K; i++){
    auto tmp = que.top(); que.pop();
    cout << tmp << endl;
  }
  return 0;
}

Measured memory_bytes: 43236
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define print(x) cout<<x<<endl;
typedef long long ll;


bool graph[8][8];

int dfs(int v,int N,bool visited[8]){
	bool all_visited = true;

	rep(i, 0, N) {
		if (visited[i] == false)
			all_visited = false;
	}
	if (all_visited) return 1;

	int ret = 0;
	rep(i, 0, N) {
		if (graph[v][i] == false)continue;
		if (visited[i]) continue;

		visited[i] = true;
		ret += dfs(i, N, visited);
		visited[i] = false;
	}

	return ret;
}

int main() {
	int N, M;
	int A, B;
	cin >> N >> M;
	rep(i, 0, M) {
		cin >> A >> B;
		graph[A - 1][B - 1] = graph[B - 1][A - 1] = true;
	}

	bool visited[8];
	rep(i, 0, N) {
		visited[i] = false;
	}
	visited[0] = true;
	print(dfs(0, N, visited));
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
 
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		int count=0;
		for(int i=0;i<s.length()-1;i++){
			if(s.charAt(i)!=s.charAt(i+1))count++;
		}
		System.out.println(count);
		sc.close();
	}
 
}


Measured memory_bytes: 26496
import java.util.*;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
 
 
public class Main{
	public static void main (String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map<Integer, Integer> m = new HashMap<>();
		for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            m.putIfAbsent(a, 0);
            m.put(a, m.get(a) + 1);
        }
		int ans = 0;
        for (int a : m.keySet()) {
            if (m.get(a) > a) {
                ans += m.get(a) - a;
            } else if (m.get(a) < a) {
                ans += m.get(a);
            }
        }
        System.out.println(ans);
	}
}

Measured memory_bytes: 63420
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
#define sign(a) ((a>0)-(a<0))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define LL long long
#define INF (LL)(1LL<<60)
#define all(a) a.begin(), a.end()
#define gr greater<LL>()

using namespace std;

void solve(long long N, long long A, long long B){
    cout << min(A*N, B) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(N, A, B);
    return 0;
}


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

int f(int n){
	int a = 0;
	while(0 < n){
		a += n%10;
		n /= 10;
	}
	return a;
}

int main(){
	int n;
	cin >> n;
	int num = f(n);
	if(n%num == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

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

int main() {
    long long N;
    cin >> N;
    long long ans=0;
    vector <long long> v(N+1, 0);
    for (long long i=1; i<=N; i++) {
        long long t = N/i;
        ans += t*(i+i*t)/2;
        for (long long j=1; j<N/i; j++) v[i*j]++;
    }
    cout << ans;
}

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

struct Problem {
  int num;
  int bonus;
  int score;
};

int main() {
  cout << setprecision(15);
  int d, g;
  cin >> d >> g;
  vector<Problem> p(d);
  for (int i = 0; i < d; ++i) {
    cin >> p[i].num;
    cin >> p[i].bonus;
    p[i].score = 100 * (i+1);
  }
  int ans = 10000; 
  int loop_max = pow(2, d);
  for (int i = 0; i < loop_max; ++i) {
    int total_score = 0;
    int total_num = 0;
    for (int j = 0, mask = 1; j < d; ++j, mask <<= 1) {
      if (i & mask) {
        total_score += p[j].score * p[j].num + p[j].bonus; 
        total_num += p[j].num; 
      }
    }
    if (total_score < g) {
      for (int j = d-1, mask = 1 << (d-1); j>=0; --j, mask>>=1) {
        if ((i & mask) == 0) {
          int num = min((g - total_score + p[j].score - 1)/p[j].score, p[j].num - 1);
          total_score += p[j].score * num;
          total_num += num;
        }
        if (total_score >= g) break;
      }
    }
    if (total_score >= g) ans = min(total_num, ans); 
  }     
  cout << ans << endl;
  return 0;
}


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

int main(){

    int N,X;
    int input;
    cin >> N >> X;
    cin >> input;
    vector<int> v;
    vector<int> steps;
    steps.push_back(0);
    v.push_back(input);
    int D_last = 0;
    int L_last = v[0];
    for(int i=1;i<N;i++){
        cin >> input;
        v.push_back(input);
    }

    for(int i=0;i<N;i++){
        steps.push_back(D_last+L_last);
        D_last = D_last+L_last;
        L_last = v[i+1];
    }

    int result = 0;
    for(int i=0;i<steps.size();i++){
        if(steps[i] <= X){
            result++;
        }
    }

    cout << result;

}


Measured memory_bytes: 256
#define ONLINE_JUDGE
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
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<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;


void solve();

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

void solve(){
    ll n,k;cin>>n>>k;
    vl cnt(n);
    rep(i,k){
        ll d;cin>>d;
        rep(j,d){
            ll a;cin>>a;--a;
            ++cnt[a];
        }
    }

    ll ans=0;
    rep(i,n)if(!cnt[i])++ans;
    cout<<ans<<endl;
}


Measured memory_bytes: 3664
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC155
{
    class C
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            //string[] S = new string[N];
            Dictionary<string, int> dic = new Dictionary<string, int>();
            for (int i = 0; i < N; i++)
            {
                string S = Console.ReadLine();
                if (!dic.ContainsKey(S)) { dic.Add(S, 1); }
                else dic[S]++;
            }

            int max = 0;
            foreach (var item in dic)
            {
                if (max < item.Value) max = item.Value;
            }

            List<string> list = new List<string>();
            foreach (var item in dic)
            {
                if (item.Value == max) list.Add(item.Key);
            }

            var array = list.ToArray();

            Array.Sort(array, StringComparer.OrdinalIgnoreCase);

            //Console.WriteLine("---");
            foreach (var item in array)
            {
                Console.WriteLine(item);
            }
        }
    }
}

Measured memory_bytes: 42204
h,w=map(int,input().split())
s=[input() for _ in range(h)]
ans=[]
for i in range(h):
    t=''
    for j in range(w):
        if s[i][j]=='#':
            t+='#'
        else:
            cnt=0
            if i>0:
                if s[i-1][j]=='#':
                    cnt+=1
            if i<h-1:
                if s[i+1][j]=='#':
                    cnt+=1
            if j>0:
                if s[i][j-1]=='#':
                    cnt+=1
            if j<w-1:
                if s[i][j+1]=='#':
                    cnt+=1
            if i>0 and j>0:
                if s[i-1][j-1]=='#':
                    cnt+=1
            if i<h-1 and j>0:
                if s[i+1][j-1]=='#':
                    cnt+=1
            if i>0 and j<w-1:
                if s[i-1][j+1]=='#':
                    cnt+=1
            if i<h-1 and j<w-1:
                if s[i+1][j+1]=='#':
                    cnt+=1
            t+=str(cnt)
    ans.append(t)
for a in ans:
    print(a)


Measured memory_bytes: 3064
import numpy as np

h, w = map(int, input().split())
s = [input() for _ in range(h)]

t = np.zeros((h, w), dtype=np.int32)
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            t[i][j] = 1

l = np.zeros((h, w), dtype=np.int32)
r = np.zeros((h, w), dtype=np.int32)
u = np.zeros((h, w), dtype=np.int32)
d = np.zeros((h, w), dtype=np.int32)

for i in range(w):
    if i == 0:
        l[:, i] = t[:, i]
    else:
        l[:, i] = (l[:, i-1] + 1) * t[:, i]

for i in range(w-1, -1, -1):
    if i == w-1:
        r[:, i] = t[:, i]
    else:
        r[:, i] = (r[:, i+1] + 1) * t[:, i]

for i in range(h):
    if i == 0:
        u[i] = t[i]
    else:
        u[i] = (u[i-1] + 1) * t[i]

for i in range(h-1, -1, -1):
    if i == h-1:
        d[i] = t[i]
    else:
        d[i] = (d[i+1] + 1) * t[i]

lrud = l+r+u+d-3
print(np.max(lrud))

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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = --end(s); i != begin(s); --i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T, class ... Args> constexpr void mins(T& a, Args... args) { a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr void maxs(T& a, Args... args) { a = max<T>({ a,args... }); }

int n;
int num[15];
void solve() {
    cin >> n;

    ++num[0];
    rep(i, n) { int d; cin >> d; ++num[d]; }

    int ans = -1;
    rep(i, 13) if (num[i] > 2) ans = iinf;
    if (num[0] > 1 || num[12] > 1) ans = iinf;
    auto dis = [](int n) {return min(abs(n), 24 - abs(n)); };
    rep(s, 1 << 11) {
        int res = iinf;
        rep(i, 13) loop(j, i + 1, 13) {
            int l = i, r = j;
            if (num[i] == 0 || num[j] == 0) continue;
            if (i > 0 && i<12 && s >> (i - 1) & 1) l = 24 - l;
            if (j > 0 && j<12 && s >> (j - 1) & 1) r = 24 - r;

            mins(res, dis(l - r));

            if (num[i] == 2) {
                mins(res, dis(24 - l - r), dis(24 - l - l));
                if (num[j] == 2) mins(res, dis(24 - l - (24 - r)));
            }
            if (num[j] == 2) mins(res, dis(24 - r - r), dis(l - (24 - r)));
        }

        maxs(ans, res);
    }

    if (ans == iinf) cout << 0 << endn;
    else cout << ans << endn;

}

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

    solve();

    cout << flush;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n;
	while(cin>>n and n!=0)
	{
		int cnt=0;
		for(int i=0;i<n/4;i++)
		{
			int a;
			cin >> a;
			cnt+=a;
		}
		cout << cnt << endl;
	}
}



Measured memory_bytes: 2988
N = int(input())

def f(n):
    L = [1]
    c = 1
    while 6**c <= n:
        L.append(6**c)
        c += 1
    c = 1
    while 9**c <= n:
        L.append(9**c)
        c += 1
    return L

dp = [0 for i in range(N+1)]
dp[1] = 1

for i in range(N):
    L = f(i+1)
    temp = dp[i+1-L[0]]
    for j in range(len(L)):
        if temp > dp[i+1-L[j]]:
            temp = dp[i+1-L[j]]
    dp[i+1] = temp+1
    
print(dp[N])

Measured memory_bytes: 3864
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+5;

int main()
{
    int n,k;
    cin >> n >> k;
    
    int h[n];
    for(int i=0;i<n;++i)
    {
        cin >> h[i];
    }
    vector<int> dp(n,INF);
    dp[0]=0;
    for(int i=0;i<n;++i)
    {
        for(int j=i+1;j<i+k+1 && j<n;++j)
        {
            dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]));
        }
    }
    cout << dp[n-1] << endl;
    
    return 0;
}


Measured memory_bytes: 4044
'use strict'

function Main(input) {
  const inputList = input.split('');
  let count = 0;

  for (let i=0; i<inputList.length; i++) {
    if (inputList[i] === '1') count++
  }
  console.log(count)
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 10952
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	int n=in();
	vector<int> a(n),pre;
	trav(i,a)i=in();
	partial_sum(all(a),back_inserter(pre));
	
	int ans=1e18,cur,mv;
	
	for(int sign=0;sign<2;sign++)
	{
		cur=0,mv=0;
		for(int i=0;i<n;i++)
		{
			int x=pre[i]+cur;
			if(i%2==sign and x>=0)
			{
				cur-=(x+1);
				mv+=(x+1);
			}
			else if(i%2!=sign and x<=0)
			{
				cur+=(1-x);
				mv+=(1-x);
			}
			
		}
		ans=min(ans,mv);
	}
	cout<<ans;
	
}

Measured memory_bytes: 5080
#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int main(){
	double a, b, c;
	double PI = acos(-1);
	cin >> a >> b >> c;
	//cout << sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))<<endl;
	printf("%.8f\n", sin(c * PI / 180)*a*b / 2);
	printf("%.8f\n", a + b + sqrt((sin(c * PI / 180)*a)*(sin(c * PI / 180)*a) + (b - cos(c * PI / 180)*a)*(b - cos(c * PI / 180)*a)));
	printf("%.8f\n", sin(c * PI / 180)*b);
}


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

#define N 100005

int n, m;

class edge
{
	private:
		int fr, to;
		
	public:	
		edge(void) {};
		edge(int u, int v)
		{
			fr = min(u, v);
			to = max(u, v);
		}
		
		int u(void)
		{
			return fr;
		}
		
		int v(void)
		{
			return to;
		}
		
		int another(int one)
		{
			return one == fr ? to : fr;
		}
		
		friend bool operator < (const edge &a, const edge &b)
		{
			return a.fr != b.fr ? a.fr < b.fr : a.to < b.to;
		}
}E[N];

vector<int> to[N];

vector<edge> answer;

int dfn[N], low[N], tim;

void tarjan(int u, int f)
{
	dfn[u] = low[u] = ++tim;
	
	for (auto i : to[u])
		if (i != f)
		{
			edge e = E[i];
			int v = e.another(u);
			
			if (!dfn[v])
			{
				tarjan(v, i);
				low[u] = min(low[u], low[v]);
			}
			else
				low[u] = min(low[u], dfn[v]);
		}
		
	if (u && dfn[u] <= low[u])
		answer.push_back(E[f]);
}

signed main(void) 
{
	cin >> n >> m;
	
	for (int u, v; m--; )
	{
		cin >> u >> v;
		E[m] = edge(u, v);
		to[u].push_back(m);
		to[v].push_back(m);
	}
	
	tarjan(0, -1);
	
	sort(begin(answer), end(answer));
	
	for (auto e : answer)
		cout << e.u() << " " << e.v() << endl;
}

Measured memory_bytes: 7236
# -*- coding: utf-8 -*-
"""
Created on Mon Aug  6 16:07:14 2018

@author: Yuki
"""


# 入力
D, G = map(int, input().split())
P = []
C = []
for i in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)

# 全部解いた場合の点数
MAX_POINT_LIST = []
for i in range(D):
    MAX_POINT_LIST.append(P[i] * 100 * (i + 1) + C[i])

# 全部解く問題のパターン最大2**10を全探索する。
res_list = []
flag = [False for i in range(D)]
for i in range(2**D):
    tmp_point = 0
    tmp_count = 0
    tmp_bin = bin(i)[2:].zfill(D)
    for ii in range(D):
        flag[ii] = False
        if tmp_bin[ii] == '1':
            flag[ii] = True
            tmp_point += MAX_POINT_LIST[ii]
            tmp_count += P[ii]
    if tmp_point >= G:
        res_list.append(tmp_count)
    else:
        for ii in range(D):
            if flag[ii] == False:
                # flag[ii]　この点数の問題を全解きしてない場合使える
                if tmp_point + (P[ii] - 1) * 100 *(ii + 1) >= G:
                    comp_cnt = (G - tmp_point - 1) // (100 * (ii + 1)) + 1
                    res_list.append(comp_cnt + tmp_count)
    # 今回のMAX_POINTだけでは足りない場合
    # MAX_POINTに選ばれていない点数のやつから足していく
                
print(min(res_list))


Measured memory_bytes: 3064
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>
using namespace std;

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 100005
#define LOG_MAX 20
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define in(x) scanf("%d", &x)
#define inl(x) scanf("%lld", &x)
#define in2(x, y) scanf("%d %d", &x, &y)
#define inl2(x, y) scanf("%lld %lld", &x, &y)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define finish(x) {cout<<x<<'\n'; return;}
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const char en = '\n';

void solve() {
	int n, k;
	in2(n, k);
	int a[n];
	for(int i=0;i<n;i++) in(a[i]);
	sort(a, a+n);
	
	int sum = 0;
	for(int i=0;i<k;i++)sum+=a[i];
	cout<<sum<<en;
}

int main() {
	int t = 1;
	
	//~cin>>t;
	while(t--) {
		solve();
	}
    return 0;
}


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

typedef long long ll;
const ll MOD = 1000000007;

#define fr first
#define sc second

ll modpow(ll x,ll k){
	if(k == 0)return 1;
	ll ret = modpow(x,k/2);
	ret *= ret; ret %= MOD;
	if(k%2 == 1){
		ret *= x; ret %= MOD;
	}
	return ret;
}

int main(){
	ll n;
	cin >> n;
	
	ll ret = 0;
	map<ll,ll> dp[2];
	dp[0][0] = 1;
	for(int s = 60 ; s >= 0 ; s --){
		ll z = (1LL<<(s+1))-2;
		dp[1].clear();
		for(auto p: dp[0]){
			dp[1][p.fr] += p.sc;
			dp[1][p.fr+(1LL<<s)] += p.sc;
			dp[1][p.fr+(1LL<<(s+1))] += p.sc;
		}
		dp[0].clear();
		for(auto p: dp[1]){
			if(p.fr > n)continue;
			else if(p.fr+z > n)dp[0].insert(p);
			else ret += p.sc*modpow(3,s);
		}
		ret %= MOD;
		/*cout << "s=" << s << endl;
		cout << "ret=" << ret << endl;
		for(auto p: dp[0]){
			cout << p.fr << " " << p.sc << endl;
		}*/
	}
	cout << ret << endl;
}



Measured memory_bytes: 256