akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll a[100000];
int main(void){
    ll n;
    cin>>n;
    ll i=0;
    while(true){
        a[i]=i*i;
        if(i*i>=1000000000){
            break;
        }
        i++;
    }
    for(int j=0;j<=i;j++){
        if(a[j]<=n){
            
        }else{
            cout<<a[j-1]<<endl;
            return 0;
        }
    }
    
}


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

int main() {
  long n,m,aaa=99999999,ans=0;
  cin >> n >> m;
  vector<vector<long>> ab(m,vector<long>(2));
  for(long i=0;i<m;i++) cin >> ab[i][0] >> ab[i][1];
  sort(ab.begin(),ab.end());
  for(long i=m-1;i>=0;i--) if(ab[i][1]<=aaa) ans++,aaa=ab[i][0];
  cout << ans << endl;
}

Measured memory_bytes: 5760
n,m = map(int,input().split())
hlist = list(map(int,input().split()))
ten = []
append = ten.append
for i in range(n):
    append(1)
#print(ten)
for i in range(m):
    a,b = map(int,input().split())
    if hlist[a-1] > hlist[b-1]:
        ten[b-1] = 0
    elif hlist[b-1] > hlist[a-1]:
        ten[a-1] = 0
    elif hlist[b-1] == hlist[a-1]:
        ten[a-1] = 0
        ten[b-1] = 0


print(sum(ten))  

Measured memory_bytes: 20052
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

// Educational DP/DPまとめコンテスト A-Frog1
// dp[i] := 足場iへ到達する最小コスト 

int INF = 1e9+7;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  vector<int> h(N, 0);
  REP(i, N){
    cin >> h[i];
  }
  vector<int> dp(N+5, INF); // 多めにとる
  dp[0] = 0;
  REP(i, N){
    chmin(dp[i+2], dp[i]+abs(h[i]-h[i+2]));
    chmin(dp[i+1], dp[i]+abs(h[i]-h[i+1]));
  }
  cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
MOD=10**9+7
N, M = map(int, input().split())

FCT = [1]
for i in range(1, M+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    # {the num of case B when A=range(1,N+1)} x {permutation of A}
    # use inclusion-exclusion principle against former
    ans = 0
    for i in range(N+1):
        cp = (cmb(N, i) * pmu(M-i, N-i))%MOD
        ans = (ans + (1 if i%2==0 else -1) * cp) % MOD
    return (ans * pmu(M, N)) % MOD

if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 118560
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        int[] memo = new int[999999];
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 2;
        for (int i = 3; i < 999999; i++) {
            memo[i] = -1;
        }
        BufferedReader r =new BufferedReader(new InputStreamReader(System.in));
        do {
            String str = r.readLine();
            if (null == str) break;
            int num = Integer.parseInt(str);
            if (memo[num-1] < 0) {
                int count = 2;
                boolean isPrime = false;
                for (int i = 3; i <= num; i += 2) {
                    for (int j = 2; j * j <= i; j++) {
                        if (i % j == 0) {
                            isPrime = false;
                            break;
                        }
                        isPrime = true;
                    }
                    if (isPrime) count++;
                    memo[i-1] = count;
                }
                System.out.println(count);
            } else {
                System.out.println(memo[num-1]);
            }
        } while(true);
    }
}

Measured memory_bytes: 29360
# Sports Festival
from collections import Counter
N, M = map(int, input().split())
data = [list(map(int, input().split())) for i in range(N)]
ans = N
for i in range(M):
    K = []
    for j in range(N):
        K.append(data[j][0])
    index, weight = Counter(K).most_common()[0]
    ans = min(ans, weight)
    for k in range(N):
        data[k].remove(index)
print(ans)

Measured memory_bytes: 4596
Imports System.Collections.Generic

Public Class Program
  Shared Sub Main()
    Dim n As Integer = Cin.Int()
    Dim dic As Dictionary(Of String, Integer) = New Dictionary(Of String, Integer)()
    Dim m As Integer = 0
    For i As Integer = 0 To n - 1
      Dim s As String = Cin.Str()
      If dic.Containskey(s) Then
        dic(s) += 1
      Else
        dic.Add(s, 1)
      End If
      m = Math.Max(m, dic(s))
    Next
    
    Dim ans As List(Of String) = New List(Of String)()
    For Each x As KeyValuePair(Of String, Integer) In dic
      If m = x.Value Then ans.Add(x.Key)
    Next
    ans.Sort(StringComparer.OrdinalIgnoreCase)
    Console.WriteLine(String.Join(vbLf, ans))
  End Sub
End Class

Public Class Cin
  Public Shared Function Str() As String
    Return Console.ReadLine().Trim()
  End Function
  Public Shared Function Int() As Integer
    Return Integer.Parse(Str())
  End Function
  Public Shared Function Lng() As Long
    Return Long.Parse(Str())
  End Function
  Public Shared Function Dbl() As Double
    Return Double.Parse(Str())
  End Function
  Public Shared Function StrArr(Optional separator As String = " ") As String()
    Return Str().Split(separator)
  End Function
  Public Shared Function IntArr(Optional separator As String = " ") As Integer()
    Return Array.ConvertAll(Of String, Integer)(StrArr(separator), AddressOf Integer.Parse)
  End Function
  Public Shared Function LngArr(Optional separator As String = " ") As Long()
    Return Array.ConvertAll(Of String, Long)(StrArr(separator), AddressOf Long.Parse)
  End Function
  Public Shared Function DblArr(Optional separator As String = " ") As Double()
    Return Array.ConvertAll(Of String, Double)(StrArr(separator), AddressOf Double.Parse)
  End Function
End Class

Measured memory_bytes: 47732
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>

using namespace std;

typedef long long ll;

const ll N = 1e5 + 10;

ll n;
ll h[N];
ll q, b, c, res;


int main() {
	cin >> n;
	for (ll i = 1; i <= n; i++) {
		ll t;
		cin >> t;
		res += t;
		h[t]++;
	}

	cin >> q;
	while (q--) {
		cin >> b >> c;

		if (h[b] == 0) {
			;
		}
		else {
			res += h[b] * (c - b);
			h[c] += h[b];
			h[b] = 0;
		}

		cout << res << endl;
	}

	return 0;
}

Measured memory_bytes: 4416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<ll, ll>P;
#define PI 3.14159265359
#define MOD 1000000007
const int MAX = 510000;
ll gcd(ll a, ll b){
    if (a % b == 0)
    {  return(b);}
    else{return(gcd(b, a % b));}
}
ll lcm(ll a, ll b)
{return a * b / gcd(a, b);}

int main(){
  int N;cin>>N;
  ll dp[N];
  rep(i,N){cin >>dp[i];}
  ll gcoto[N];//gcoto[i]は、dp[0]からdp[i]までのgcd
  ll gcnfrom[N];
  gcoto[0]=dp[0];
  rep(i,N-1){
  	gcoto[i+1]=gcd(gcoto[i],dp[i+1]);
  }
  gcnfrom[N-1]=dp[N-1];
  for(int i=N-2;i>=0;i--){
  	gcnfrom[i]=gcd(gcnfrom[i+1],dp[i]);
  }
  ll maxgc=gcnfrom[1];
  for(int i=0;i<N-1;i++){
  	maxgc=max(maxgc,gcd(gcoto[i-1],gcnfrom[i+1]));
  }
  maxgc=max(maxgc,gcoto[N-2]);
  cout<<maxgc;
  
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

using namespace std;

template <typename T>
std::map<T, int> Factorize(T x) {
  std::map<T, int> m;
  for (T i = 2; i * i <= x;) {
    if (x % i == 0) {
      m[i]++;
      x /= i;
    } else {
      ++i;
    }
  }
  if (x > 1) m[x]++;
  return m;
}

int main() {
  in(ll, n, k);
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll sum = accumulate(all(a), 0LL);
  map<ll, int> fs = Factorize(sum);
  vector<pair<ll, int>> v(all(fs));

  auto check = [&](ll g) {
    vector<ll> mods(n);
    rep(i, n) mods[i] = a[i] % g;
    sort(all(mods));
    vector<ll> upper(n + 1);
    for (int i = n - 1; i >= 0; --i) {
      upper[i] = upper[i + 1] + g - mods[i];
    }
    vector<ll> lower(n + 1);
    rep(i, n) {
      lower[i + 1] = lower[i] + mods[i];
    }
    rep(i, n) {
      ll l = lower[i + 1], u = upper[i + 1];
      dbg(g, l, u);
      if (l > k) continue;
      if (l == u) {
        return true;
      }
    }
    return false;
  };

  function<ll(int, ll)> dfs = [&](int depth, ll g)->ll {
    if (depth == v.size()) {
      if (check(g)) {
        return g;
      }
      return 0LL;
    }
    ll ret = 0;
    rep(i, v[depth].second + 1) {
      ret = max(ret, dfs(depth + 1, g));
      g *= v[depth].first;
    }
    return ret;
  };

  out(dfs(0, 1));
}


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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	long long n, k; cin >> n >> k;
	n %= k;
	long long min = n;
	while (abs(n - k) < min)
	{
		n = abs(n - k);
		min = std::min(min, n);
	}
	cout << min;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

ll r[100010];
ll d[100010];
vector<vector<ll> > v;
ll flag;

ll f(ll p){
  d[p] = 1;
  if(v[p].sz==1)return r[p];
  ll total = 0;
  ll mx = 0;
  rep(i,0,v[p].sz){
    if(d[v[p][i]]==1)continue;
    ll ret = f(v[p][i]);
    total += ret;
    mx = max(mx,ret);
  }
  mx = total-mx;
  if(total<r[p])flag = 0;
  ll t = r[p]*2-total;
  ll u = min(mx,total/2);
  if(t<0)flag = 0;
  if(u<(total-t)/2){
    flag = 0;
  }
  return t;
}

int main(){
  flag = 1;
  ll n;
  cin>>n;
  rep(i,0,n){
    ll a;
    cin>>a;
    r[i] = a;
  }
  vector<vector<ll> > v_(n,vector<ll>());
  v = v_;
  rep(i,0,n-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    v[a].pb(b);
    v[b].pb(a);
  }
  if(n==2){
    if(r[0]==r[1]){
      cout << "YES" << endl;
      return 0;
    }
    else{
      cout << "NO" << endl;
      return 0;
    }
  }
  int index = -1;
  rep(i,0,n){
    if(v[i].sz>=2)index = i;
  }
  clr(d,0);
  ll ret = f(index);
  if(ret!=0)flag = 0;
  if(flag==1){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
  return 0;
}
 

Measured memory_bytes: 13952
#include <stdio.h>

int main(void)
{
  long long x, y, n, tmp;
  scanf("%lld %lld", &x, &y);

  if(x > y){
    tmp = x;
    x = y;
    y = tmp;
  }

  n = x%y;
  while(n != 0){
    x = y;
    y = n;
    n = x%y;
  }

  printf("%lld\n", y);

  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)

using namespace std;

llint n;

string s;
void dfs(llint p, llint x)
{
	if(p > n){
		cout << s<< endl;
		return;
	}
	for(llint i = 0; i <= x+1; i++){
		s += i+'a';
		dfs(p+1, max(x, i));
		s.erase(s.end()-1);
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	dfs(1, -1);
	
	return 0;
}

Measured memory_bytes: 1536
n = int(input())
a = [int(i) for i in input().split()]
color = [0] * 8
any = 0
for i in a:
    if 1 <= i <= 399:
        color[0] = 1
    elif 400 <= i <= 799:
        color[1] = 1
    elif 800 <= i <= 1199:
        color[2] = 1
    elif 1200 <= i <= 1599:
        color[3] = 1
    elif 1600 <= i <= 1999:
        color[4] = 1
    elif 2000 <= i <= 2399:
        color[5] = 1
    elif 2400 <= i <= 2799:
        color[6] = 1
    elif 2800 <= i <= 3199:
        color[7] = 1
    else:
        any += 1
m = max(sum(color), 1)
M = sum(color) + any
print(m, M)


Measured memory_bytes: 9056
def main():
    S = input()
    K = int(input())
    ans = ['' for _ in range(len(S))]
    for i in range(len(S)):
        d = ord(S[i]) - ord('a')
        shift = (26 - d) % 26
        if K - shift >= 0:
            ans[i] = 'a'
            K -= shift
        else:
            ans[i] = S[i]
    if K > 0:
        K %= 26
        d = (K + ord(ans[-1]) - ord('a')) % 26
        ans[-1] = chr(d + ord('a'))
    print(''.join(ans))


if __name__ == '__main__':
    main()

Measured memory_bytes: 10128
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

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


Measured memory_bytes: 3644
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n::Int,w::Int=parseMap(split(readline()))
    dp::Vector{Vector{Int}}=[[0 for j in 0:100010] for i in 1:110]
    data::Vector{Vector{Int}}=[parseMap(split(readline())) for i in 1:n]
    for i in 1:n
        for j in 0:w
            wi::Int,vi::Int=data[i]
            if j-wi>=0
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1-wi]+vi)
            end
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
        end
    end
    println(dp[n+1][w+1])
end
main()

Measured memory_bytes: 268520
package main

import "fmt"

func main() {

	var (
		n  int
		q  int
		ss string
		s  []string
		t  string
		d  string
	)

	fmt.Scan(&n, &q)
	fmt.Scan(&ss)

	for _, c := range ss {
		s = append(s, string([]rune{c}))
	}

	td := make([][]string, q)
	for i := 0; i < q; i++ {
		fmt.Scan(&t, &d)
		td[i] = []string{t, d}
	}

	leftIndex := solveLeft(-1, n, n, q, s, td)
	rightIndex := solveRight(-1, n, n, q, s, td)

	fmt.Print(rightIndex - leftIndex - 1)

}

func solveLeft(l int, r int, n int, q int, s []string, td [][]string) int {
	mid := int((r + l) / 2)
	if r-l <= 1 {
		return l
	}
	index := mid
	for i := 0; i < q; i++ {
		if td[i][0] == s[index] {
			if td[i][1] == "L" {
				index--
				if index == -1 {
					return solveLeft(mid, r, n, q, s, td)
				}
			} else {
				index++
				if index == n {
					return solveLeft(l, mid, n, q, s, td)
				}
			}
		}
	}
	return solveLeft(l, mid, n, q, s, td)
}

func solveRight(l int, r int, n int, q int, s []string, td [][]string) int {
	mid := int((r + l) / 2)
	if r-l <= 1 {
		return r
	}
	index := mid
	for i := 0; i < q; i++ {
		if td[i][0] == s[index] {
			if td[i][1] == "R" {
				index++
				if index == n {
					return solveRight(l, mid, n, q, s, td)
				}
			} else {
				index--
				if index == -1 {
					return solveRight(mid, r, n, q, s, td)
				}
			}
		}
	}
	return solveRight(mid, r, n, q, s, td)
}


Measured memory_bytes: 23808
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  int num = 1;
  for(int i=0;i<N;i++){
    num = min(num*2,num+K);
  }

  cout << num << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

typedef pair<ll, ll> P;
#define fs first
#define sc second

int main(){
    int N;
    cin >> N;
    int a[N];
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }

    sort(a, a + N);

    bool check = true;
    for(int i = 0; i < N - 1; i++){
        if(a[i] == a[i + 1]){
            check = false;
        }
    }

    if(check){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        String s = scanner.next();
        int l = s.length();
        for (int i = 1; i < l; i++) {
            if (s.charAt(i - 1) == s.charAt(i)) {
                System.out.println("Second");
                return;
            }
        }
        if (s.charAt(l - 1) == s.charAt(0)) {
            System.out.println(l % 2 == 0 ? "First" : "Second");
        } else {
            System.out.println(l % 2 == 0 ? "Second" : "First");
        }
    }
}

Measured memory_bytes: 26068
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n = int(input())

    now = 0
    for _ in range(n):
        a,b = get_nums_l()
        if a == b:
            now += 1
            if now >= 3:
                print("Yes")
                return
        else:
            now = 0
    print("No")

main()

Measured memory_bytes: 67620
#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>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;



int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    rep(i,n) cin >> a[i+1];
    vector<int> ans(n+1);
    for (int i = n; i >= 1; i--) {
        int cnt = 0;
        for (int j = i; j <= n; j += i) {
            cnt += ans[j];
        }
        ans[i] = a[i]^(cnt%2);
    }
    int b = 0;
    for (int i = 1; i <= n; i++) {
        if (ans[i]) b++;
    }
    cout << b << endl;
    for (int i = 1; i <= n; i++) {
        if (ans[i]) cout << i << endl;
    }
    return 0;
}

Measured memory_bytes: 4796
n = int(input())
x = [[int(i) for i in input().split()] for i in range(n)]

import math

l = 0
for j in range(n):
    for k in range(j + 1, n):
        l += ((x[j][0] - x[k][0]) ** 2 + (x[j][1] - x[k][1]) ** 2) ** 0.5

a = 2 * math.factorial(n - 1) / math.factorial(n)

print(l * a)

Measured memory_bytes: 3188
n = int(input())
d = {}
for _ in range(n):
    h = input()[0]
    if h in 'MARCH':
        d[h] = d.get(h, 0) + 1
a = list(d.values())
r = 0
for i in range(len(a)):
    for j in range(i+1, len(a)):
        for k in range(j+1, len(a)):
            r += a[i]*a[j]*a[k]
print(r)

Measured memory_bytes: 3060
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
using comp = complex<double>;

const ll MOD = 1000000007LL;
const double PI = 3.14159265358979323846;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

// functions and classes

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

	ll N;
	cin >> N;

	double sqrtN = sqrt(N);

	ll res = 0;
	for (ll i = sqrtN + 2LL; i >= 1LL; --i)
	{
		if (i * i > N)
			continue;
		if (N % i != 0)
			continue;
		res = i + N / i - 2LL;
		break;
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>

using namespace std;

void solve1() {
	int x, y;
	cin >> x >> y;

	int A[] = { 1,3,5,7,8,10,12 };
	int B[] = { 4,6,9,11 };
	if (x == 2 || y == 2) {
		cout << "No" << endl;
		return;
	}
	bool _x = false, _y= false;
	for (int i = 0; i < 8; i++)
	{
		if (A[i] == x)
			_x = true;
		if (A[i] == y)
			_y = true;
	}
	if ((_x == true &&_y == true) || (_x == false && _y == false)) {
		cout << "Yes" << endl;
		return;
	}
	else {
		cout << "No" << endl;
		return;
	}

}

int main() {
	solve1();
	return 0;
}

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

int64_t ryuka(int x){
  if(x == 0){
    return 2;
  }
  else if(x == 1){
    return 1;
  }else{
    vector<int64_t> L (10000);
    L.at(0) = 2;
    L.at(1) = 1;
    for(int i = 2; i <= x; i++){
      L.at(i) = L.at(i - 2) + L.at(i - 1);
    }
    return L.at(x);
  }
}

int main() {
  int N;
  cin >> N;
  cout << ryuka(N) << endl;
}

Measured memory_bytes: 3632
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         HashSet<String> set = new HashSet<String>();
         for(int i=0; i < N; i++)
            set.add(infile.readLine());
         System.out.println(set.size());
      }
   }

Measured memory_bytes: 67088
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#pragma warning( disable:4996 )
#define min(a, b) ((a) < (b) ? (a) : (b))
int N;
int h[100002];
int dp[100002];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &h[i]);
	}
	if (N == 2) {
		printf("%d\n", abs(h[N] - h[N - 1]));
	}
	else {
		dp[N] = 0;
		dp[N - 1] = abs(h[N] - h[N - 1]);
		//dp[N - 2] = abs(h[N] - h[N - 2]);
		dp[N - 2] = min(abs(h[N] - h[N - 2]), dp[N - 1] + abs(h[N - 2] - h[N - 1]));
		for (int i = N - 3; i >= 1; i--) {
			dp[i] = min(dp[i + 1] + abs(h[i] - h[i + 1]), dp[i + 2] + abs(h[i] - h[i + 2]));
		}
		printf("%d\n", dp[1]);
	}
	
	return 0;
}

Measured memory_bytes: 896
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
#print(S)
dpyoko = [[1]*(W) for i in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            dpyoko[i][j] = 0
        else:
            if j != 0:
                dpyoko[i][j] += dpyoko[i][j-1]
dptate = [[1]*(W) for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            dptate[i][j] = 0
        else:
            if i != 0:
                dptate[i][j] += dptate[i-1][j]
for j in range(W-1,-1,-1):
    for i in range(H):
        if dpyoko[i][j] == 0:
            continue
        if j == W-1:
            continue
        dpyoko[i][j] = max(dpyoko[i][j],dpyoko[i][j+1])
for i in range(H-1,-1,-1):
    for j in range(W):
        if dptate[i][j] == 0:
            continue
        if i == H-1:
            continue
        dptate[i][j] = max(dptate[i][j],dptate[i+1][j])
dp = [[0]*(W) for i in range(H)]
res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        dp[i][j] = dptate[i][j]+dpyoko[i][j]-1 
        if res < dp[i][j]:
            res = dp[i][j]
print(res)       


Measured memory_bytes: 278280
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{

  int n;
  int h[100005];
  int dp[100005];
  cin >> n;

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

  dp[0] = 0;
  dp[1] = abs(h[1] - h[0]);

  for(int i=2; i<n; i++) dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
 
  cout << dp[n-1] << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>

using namespace std;

int main()
{
    int s,w;
    cin >> s >> w;
    
    if (w >= s){
        cout << "unsafe" << endl;
    }
    else {
        cout << "safe" << endl;
    }
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
using namespace std;
int main(void){
    string s;
    cin >> s;
    
    if(s == "Sunny"){
        cout << "Cloudy" << endl;
    }
    if(s == "Cloudy"){
        cout << "Rainy" << endl;
    }
    if(s == "Rainy"){
        cout << "Sunny" << endl;
    }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

struct lesson {
	int from;
	int to;
	int hap;
};

int main() {
	int N,M,L;cin>>N>>M>>L;
	vector<vector<vector<lesson>>>les(5,vector<vector<lesson>>(N));
	for (int i = 0; i < M; ++i) {
		int d,a,k,t;cin>>d>>a>>k>>t;
		a--;
		les[d][a].push_back(lesson{ a,a + k,t });
	}
	vector<int>sums(L+1,-1e9);
	sums[0]=0;
	for (int day = 0; day < 5; ++day) {
		vector<vector<int>>dp(N+1,vector<int>(L+1,-1e9));
		dp[0][0]=0;
		for (int start = 0; start < N; ++start) {
			for (int take = 0; take <= L; ++take) {
				if (take != L) {

					for (auto le : les[day][start]) {
						const int goal = le.to;
						dp[goal][take+1]=max(dp[goal][take+1],dp[start][take]+le.hap);
					}
				}
				dp[start+1][take]=max(dp[start+1][take],dp[start][take]);
			}
		}
		vector<int>nextsums(L+1,-1e9);
		for (int i = 0; i <= L; ++i) {
			for (int j = 0; j <= L; ++j) {
				if (i + j <= L) {
					nextsums[i+j]=max(nextsums[i+j],sums[i]+dp[N][j]);
				}
			}
		}
		sums=nextsums;
	}
	int ans=*max_element(sums.begin(),sums.end());
	cout<<ans<<endl;
	return 0;
}

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

long long int small(long long int a, long long int b) {
	if (a < b)return a;
	else return b;
}

long long int big(long long int a, long long int b) {
	if (a < b)return b;
	else return a;
}

int main(void) {
	
	long long int num,a,dig,min = 100;
	scanf("%lld", &num);

	for (int i = 1; i <= (long long int)sqrt(num) + 1; i++) {
		if (num % i == 0) {
			dig = 0;
			a = big(num / i, i);
			while (a >= 1) a /= 10,dig++;
			min = small(min, dig);
		}		
	}
	printf("%lld\n", min);

}

Measured memory_bytes: 128
import sys
import copy


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    ls = [0] * 50
    for v in a:
        s = bin(v)[2:]
        for i in range(len(s)):
            if s[-i-1] == "1":
                ls[i] += 1
    ans = ["0"] * 50
    for i in range(len(ls)):
        if ls[-i-1] <= n // 2:
            ans[i] = "1"
            t = copy.deepcopy(ans)
            if k < int("".join(t), 2):
                ans[i] = "0"
    t = 0
    for v in a:
        t += int("".join(ans), 2) ^ v
    print(t)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 58352
s2 = input()
t = input()

lst = []
for i in range(len(s2)-len(t)+1):
    moji = ''
    if s2[i] == t[0] or s2[i] == '?':
        moji = s2[:i]+t[0]

        flg = 0
        for j in range(1,len(t)):
            if s2[i+j] == t[j] or s2[i+j] == '?':
                moji += t[j]
            else:
                flg = 1
                break
        if flg == 0:
            lst.append(moji+s2[i+len(t):])

if not lst:
    print('UNRESTORABLE')
else:
    print(min(lst).replace('?','a'))



Measured memory_bytes: 9008
def examB():
    N = I()
    X = [0]*N; Y = [0]*N
    for i in range(N):
        X[i],Y[i] = LI()
    pq = defaultdict(int)
    for i in range(N):
        for j in range(i+1,N):
            curx = X[j]-X[i]
            cury = Y[j]-Y[i]
            pq[curx,cury] +=1
            pq[-curx, -cury] += 1
    if N>1:
        ans = N - max(pq.values())
    else:
        ans = 1
    print(ans)

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()


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

using namespace std;

typedef long long ll;

const int MAXN = 2031;

struct Point
{
    int x, y;
};

double dist(Point a, Point b)
{
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)* (a.y - b.y));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<Point> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].x >> a[i].y;
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    double sum = 0;
    int cnt = 0;
    do {
//        cerr << 1;
        for (int i = 0; i < n - 1; i++)
        {
            sum += dist(a[p[i]], a[p[i + 1]]);
        }
        cnt++;
    } while (next_permutation(p.begin(), p.end()));

    cout << fixed << setprecision(10) << sum / cnt;
    return 0;
}


Measured memory_bytes: 256
input()
arr = [int(num) for num in input().strip().split(' ')]
q = int(input())

queries = []

for i in range(q):
    query = [ int(num) for num in input().strip().split(' ')]
    queries.append(query)

nums = dict()
summ = 0

for number in arr:
    summ += number
    if number not in nums:
        nums[number] =  1
    else:
        nums[number] += 1

for query in queries:
    curr, new = query
    if curr not in nums: 
        print(summ)
        continue
    count = nums[curr]
    diff = (new-curr)*count
    summ += diff
    del nums[curr]
    if new not in nums:
        nums[new] = count
    else:
        nums[new] += count
    print(summ)

Measured memory_bytes: 35664
#include <algorithm>
//#include <bits/stdc++.h>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
#define INF 1LL << 40;
#define MOD 1000000007;
#define ll long long
#define all(x) x.begin(), x.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)
#define prique priority_queue
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<ll> vl;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
template <class T> inline void chmax(T &a, T b) { a < b ? a = b : a; };
template <class T> inline void chmin(T &a, T b) { a > b ? a = b : a; };
struct edge {
    int to, cost;
};

int main() {
    int n;
    string s;
    cin >> n >> s;
    int l = 0, r = 0, ans = 0, cnt;
    while(r < n) {
        cnt = 0;
        if(s.substr(r).find(s.substr(l, r - l)) != string::npos) {
            ans = max(ans, r - l);
            r++;
        } else {
            l++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;
///////////////////////////
#define INF 1000000009
#define MAX_V 1000000
typedef pair<ll, ll> p;
typedef vector<ll> V;
struct edge{ll to, cost;};
multimap<V, ll> mp;
std::vector<std::vector<edge> > G(MAX_V);
std::vector<ll> pre(MAX_V,-1);
priority_queue<p, std::vector<p>, greater<p> > que; //class, inner, compair
std::vector<ll> d(MAX_V+1, INF);
void dijkstra(int start){
  d[start]=0;
  que.push(p(0, start));
  while(!que.empty()){
    p p_now=que.top(); que.pop();
    ll v = p_now.second;
    if(d[v]<p_now.first) continue;
    for(int i=0;i<G[v].size();i++){
      edge e = G[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        pre[e.to] = v;
        que.push(p(d[e.to], e.to));
      }
    }
  }
}
/////////////////////////////////////////////
int main(int argc, char const *argv[]) {
  ll N, M, a, b, c;
  std::cin >> N >> M;
  ll n = 1;
  for(int i=1;i<=N;i++,n++) mp.emplace(V{i, -1}, n);
  for(int i=0;i<M;i++){
    std::cin >> a >> b >> c;
    if(mp.find(V{a, c})==mp.end()) {
      mp.emplace(V{a, c}, n);
      G[n].push_back(edge{a, 0});
      G[a].push_back(edge{n, 1});
      n++;
    }
    if(mp.find(V{b, c})==mp.end()) {
      mp.emplace(V{b, c}, n);
      G[n].push_back(edge{b, 0});
      G[b].push_back(edge{n, 1});
      n++;
    }
    ll k = (*mp.lower_bound(V{a, c})).second;
    ll t = (*mp.lower_bound(V{b, c})).second;
    G[k].push_back(edge{t, 0});
    G[t].push_back(edge{k, 0});
  }
  dijkstra(1);
  //for(int i=1;i<=n;i++) std::cout << d[i] << '\n';
  std::cout << (d[N]==INF?-1:d[N]) << '\n';
  return 0;
}


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

int main() {
  int d, g;
  cin >> d >> g;
  vector<int> p(d), c(d);
  rep(i,d) cin >> p.at(i) >> c.at(i);
  
  int ans = 1e9;
  rep(bit,1<<d) {
    int sum = 0, num = 0, rest = 0;
    rep(i,d) {
      if (bit & (1 << i)) {
        sum += 100 * (i+1) * p.at(i) + c.at(i);
        num += p.at(i);
      }
      else rest = i;
    }
  
    if (sum < g) {
      int tmp = 100 * (rest+1);
      int need;
      if ((g-sum) % tmp == 0) need = (g-sum) / tmp;
      else need = ((g-sum) / tmp) + 1;
      if (need >= p.at(rest)) continue;
      num += need;
    }
    
    ans = min(ans, num);
  }
  
  cout << ans << endl;
}

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

int main(){
  int n, s;
  cin >> n >> s;
  vector<vector<ll>> dp(n, vector<ll> (3005));  
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  dp[0][0] = 2; dp[0][a[0]] = 1;
  rep(i, n-1){
    rep(j, s+1){
      dp[i+1][j] = dp[i][j]*2 % mod;
      if( j >= a[i+1] ) dp[i+1][j] = (dp[i+1][j] + dp[i][j-a[i+1]]) % mod;
      }
    }
  ll ans = dp[n-1][s];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 74016
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <limits>
#include <time.h>
#include <cstdint>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define rRep(i,a,b) for(ll i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main(){
  ll N,ans=0;
  cin >> N;
  auto V=divisor(N);
  rep(i,V.size()){
    ll K=(N-V[i])/V[i];
    if(K>V[i]){
      ans+=K;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3608
#include <stdio.h>

void toarray(int a,int *b){
  int i;
  for(i=0;i<3;i++){
    b[i]=a%10;
    a=a/10;
  }
  b[3]=a;
  return;
}

void mysort(int *a){
  int b,i,j;
  for(i=0;i<3;i++){
    for(j=i;j<4;j++){
      if(a[i]>a[j]){b=a[i];a[i]=a[j];a[j]=b;}
    }
  }
  return;
}

int main(){
  int c,i,m[4],n;
  while(scanf("%d\n",&n),n!=0){
    c=0;
    if(n%1111>0){
      while(n!=6174){
        toarray(n,&m[0]);
        mysort(&m[0]);
        n=(m[3]-m[0])*1000+(m[2]-m[1])*100+(m[1]-m[2])*10+(m[0]-m[3]);
        c++;
      }
      printf("%d\n",c);
    } else {
      printf("NA\n");
    }
  }
  return 0;
}

Measured memory_bytes: 612
a, b, c = list(map(int, input().split()))
k = int(input())
ans = 0

if (a>=b):
    while (a>=b):
        b = b*2
        ans+=1
if (b>=c):
    while (b>=c):
        c = c*2
        ans+=1 

if ans <=k:
    print("Yes")
else:
    print("No")
    

Measured memory_bytes: 9176
#include <stdio.h>

int main(void){
    int i,j,k;

    int data[7] = {0};
    int dife[7] = {0};
    for(i = 0;i < 7;i++){
        scanf("%d %d",&data[i],&dife[i]);
        printf("%d\n",data[i] - dife[i]);
    }
    return 0;
}

Measured memory_bytes: 600
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _2
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            long n = long.Parse(str);
            double k = Math.Sqrt(n);
            for (long i = (long)k+1; i >=1; i--)
            {
                if(n%i==0)
                {
                    Console.WriteLine(i+n/i-2);
                    break;
                }
            }
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	int n;
	long long a[100010];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long sum = 0, ans = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (i % 2 == 0) {
			if (sum <= 0) {
				ans += abs(sum) + 1;
				sum = 1;
			}
		}
		else {
			if (sum >= 0) {
				ans += abs(sum) + 1;
				sum = -1;
			}
		}
	}
	sum = 0;
	long long ans1 = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (i % 2 == 0) {
			if (sum >= 0) {
				ans1 += abs(sum) + 1;
				sum = -1;
			}
		}
		else {
			if (sum <= 0) {
				ans1 += abs(sum) + 1;
				sum = 1;
			}
		}
	}
	if (ans > ans1) {
		cout << ans1 << endl;
	}
	else {
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1024
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

typedef long long ll ;
typedef double db;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define for0(i,n)          for(int i=0;i<n;i++)
#define for1(i,n)          for(int i=1;i<=n;i++)
#define forab(a,b)       for(int i=a;i<=b;i++)
//#define gcd(a, b)     __gcd(a, b)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)     cout<<"Case "<<z<<": "<<x<<"\n"
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

int main()
{
	ll i,j,x,flag=0;
	cin>>x;
	for(i=-200 ; i<=200 ; i++){
		for(j=-200; j<=200 ; j++){
			if(pow(i,5) - pow(j,5) == x){
				cout<<i<<" "<<j<<nw;
				flag=1;
				break;
				}
			}
		if(flag) break;
		}
	return 0;
}

Measured memory_bytes: 4056
#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 at(x,i) get<i>(x);
#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(){
    CST(7);
    double h,w,x;cin >> w >> h >>x;
    x/=w;
    if(h*w/2<x){
        double y=h*w-x;
        y=y*2/w;
        cout << atan(y/w)/3.1415926535*(double)180 <<endl;
    }
    else{
        double y=2*x/h;
        cout << atan(h/y)/3.1415926535*(double)180 <<endl;
    }
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int dp[40000];
int a[1000+1],b[1000+1]; 
int main(){
	fastio;
	int n,h;
	cin>>h>>n;
	rb(i,1,n){
		cin>>a[i]>>b[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[h]=0;
	int res=INF;
	rb(i,1,n){
		rl(j,h,0){
			dp[max(j-a[i],0)]=min(dp[max(j-a[i],0)],dp[j]+b[i]);
		}
		res=min(res,dp[0]);
	}cout<<res;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl
#define printD(a) cout << setprecision(15) << (a) << endl
using namespace std;
int max_int = 2147483647;
int prime = 10e9+7;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<auto>& a,int n);
double PI = 3.14159265358979;
int n;




signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int m,x;
    cin >> n >> m >> x;
    vec(c,n);
    twovec(a,n,m);
    REP(i,n){
        cin >> c[i];
        REP(j,m){
            cin >> a[i][j];
        }
    }
    int ans = max_int;
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                S.push_back(i);
            }
        }
        if(S.size() == 0) continue;
        vec(w,m);
        REP(i,S.size()){
            REP(j,m){
                w[j] += a[S[i]][j];
            }
        }
        bool is = true;
        REP(i,m){
            if(w[i] < x) is = false;
        }
        if(is){
            int tmp = 0;
            REP(i,S.size()){
                tmp += c[S[i]];
            }
            ans = min(ans,tmp);
        }
    }
    if(ans == max_int) {print(-1);}
    else{
        print(ans);
    }

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}

//key以上の初めてのitr
int nibul(auto a,auto b){return lower_bound(All(a),b) - a.begin();}
//key以下の最後のitr
int nibuu(auto a,auto b){return upper_bound(All(a),b) - a.begin()-1;}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}


Measured memory_bytes: 3604