akhauriyash/Code-Regression huggingface dataset:
#if 0
かかった時間：約1時間半
最初はわかりませんが、aojで他の人のソースコードを参考して、
先生のヒント「2点を通る円だけを考えれば十分である」がわかりました。
簡単に作成し、でも何度もwrong answerでした。
困っている時に、先生のヒントの「例外ケースにも注意」を思い出しました。
そして点が一つしかない場合にプログラムが何も処理していないと発見しました。
初条件を変えればacceptedを得ました。
#endif
#include <iostream>
#include <complex>
#include <cmath>
#define EPS 1e-9
using namespace std;
typedef complex<double> xy_t;
int n;
xy_t points[301];
int count_in(xy_t center)
{
  int ans=0;
  for(int i=0;i<n;i++)
  {
    if (abs(center-points[i])<1.0+EPS)
      ans++;
  }
  return ans;
}

xy_t ppdcl(xy_t a)
{
  return xy_t(a.imag(),-a.real());
}
xy_t delta_v(xy_t C1,xy_t C2)
{
  xy_t half=(C1-C2)*0.5;
  double l=abs(half);
  return ppdcl(half)*sqrt(1-l*l)*(1.0/l);
}

int main()
{
  while(1)
  {
    cin>>n;
    if (n==0) break;
    double x,y;
    for(int i=0;i<n;i++)
    {
      cin>>x>>y;
      points[i]=xy_t(x,y);
    }
    int maxn=1;
    for(int i=0;i<n;i++)
    {
      for(int j=i;j<n;j++)
      {
        if(abs(points[i]-points[j])<2.0+EPS)
        {
          xy_t mid_p=(points[i]+points[j])*0.5;
          maxn=max(maxn,count_in(mid_p+delta_v(points[i],points[j])));
          maxn=max(maxn,count_in(mid_p-delta_v(points[i],points[j])));
        }
      }
    }
    cout<<maxn<<endl;
  }

}



Measured memory_bytes: 3148
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class B
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		var A = new int[3, 3];
		for(int i = 0; i < 3; i++)
		{
			for(int j = 0; j < 3; j++)
				A[i, j] = GetInt();
		}

		int N = GetInt();
		var flag = new bool[3, 3];
		for(int i = 0; i < N; i++)
		{
			int b = GetInt();
			for(int j = 0; j < 3; j++)
			{
				for(int k = 0; k < 3; k++)
				{
					if(b == A[j, k])
						flag[j, k] = true;
				}
			}
		}

		for(int i = 0; i < 3; i++)
		{
			bool ok = true;
			for(int j = 0; j < 3; j++)
			{
				if(!flag[i, j])
				{
					ok = false;
					break;
				}
			}
			if(ok)
			{
				WriteLine("Yes");
				return;
			}
		}

		for(int i = 0; i < 3; i++)
		{
			bool ok = true;
			for(int j = 0; j < 3; j++)
			{
				if(!flag[j, i])
				{
					ok = false;
					break;
				}
			}
			if(ok)
			{
				WriteLine("Yes");
				return;
			}
		}

		if(flag[0, 0] && flag[1, 1] && flag[2, 2])
		{
			WriteLine("Yes");
			return;
		}

		if(flag[0, 2] && flag[1, 1] && flag[2, 0])
		{
			WriteLine("Yes");
			return;
		}

		WriteLine("No");
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => Enumerable.Range(0, (int)N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(long N) => Enumerable.Range(0, (int)N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDouble()).ToArray();
	public static decimal[] GetDecimals(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDecimal()).ToArray();
	public static string[] GetStrings(long N) => Enumerable.Range(0, (int)N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 13140
def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A


if __name__ == '__main__':
    N=int(input())
    A = InputToInt()
    A.sort()
    su = 0
    for i in range(1, N):
        su += A[-i]*(0.5**i)
    su += A[0]*(0.5**(N-1))
    print(su)


Measured memory_bytes: 3060
package main

import "fmt"

func main() {
	var n, m, l int
	fmt.Scan(&n, &m, &l)
	A := make([][]int, n)
	B := make([][]int, m)
	for i := range A {
		A[i] = make([]int, m)
		for j := range A[i] {
			fmt.Scan(&A[i][j])
		}
	}
	for i := range B {
		B[i] = make([]int, l)
		for j := range B[i] {
			fmt.Scan(&B[i][j])
		}
	}
	C := make([][]int, n)
	for i := range C {
		C[i] = make([]int, l)
	}
	for j := 0; j < l; j++ {
		for i := 0; i < n; i++ {
			// C[i][j]が固定された
			// Aのi行目とBのj列目を掛け算して(要素数は同じでm)でC[i][j]にいれる
			for k := 0; k < m; k++ {
				C[i][j] += A[i][k] * B[k][j]
			}
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < l; j++ {
			if j > 0 {
				fmt.Print(" ")
			}
			fmt.Print(C[i][j])
		}
		fmt.Println()
	}
}



Measured memory_bytes: 2588
#include <bits/stdc++.h>
     
#define pll pair <long long,long long>
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define vll vector <ll>
#define NFS ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define M 1000000007   
using namespace std;

void solve()
{
	int r;
	cin>>r;
	cout<<setprecision(12);
	cout<<(2*22*r)/(double)7<<endl;
}
 
int main()
{
    NFS
 	int t=1;
 	//cin>>t;
 	while(t--)
 	{
 		solve();
 	}
    return 0;
}

Measured memory_bytes: 3800
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
k = sum(B)-sum(A)


if k < 0:
    print('No')
else:
    cnt_a = 0
    cnt_b = 0
    for a, b in zip(A, B):
        if a < b:
            x, y = divmod((b-a), 2)
            cnt_a += x+y
            cnt_b += y
        elif b < a:
            cnt_b += a-b
    if max(cnt_a, cnt_b) <= k:
        print('Yes')
    else:
        print('No')


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

int main(){
    int n;
    int64_t a[100000], sum = 0;
    int64_t sr[100002], sl[100002];
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> a[i];
        sum += a[i];
    }
    sr[n] = sr[n+1] = 0;
    for(int i=n-1;i>=0;--i){
        sr[i] = sr[i+2] + a[i];
    }
    sl[0] = a[0];
    sl[1] = a[1];
    for(int i=2;i<n;++i){
        sl[i] = sl[i-2] + a[i];
    }
    for(int i=0;i<n;++i){
        int64_t x = sum - 2*sr[i+1];
        if(i>=2) x -= 2*sl[i-2];
        cout << x << " \n"[i==n-1];
    }
    
    return 0;
}

Measured memory_bytes: 3712
#include <iostream>

using namespace std;

int main()
{
    int a[3];
    int sum=0;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<3;i++)
        for(int y=0;y<i;y++)
        if(a[i]==a[y])
        sum++;
    if(sum==3)
        sum--;
    cout<<(3-sum);

    return 0;
}


Measured memory_bytes: 3576
#include <stdio.h>

int main(void)
{
	int x, i, j, n;
	int cards[4][13] = { 0 };
	char c;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		
		scanf("%s %d", &c, &x);

		switch (c) {
		case 'S':cards[0][x - 1] = 1; break;
		case 'H':cards[1][x - 1] = 1; break;
		case 'C':cards[2][x - 1] = 1; break;
		case 'D':cards[3][x - 1] = 1; break;
		default:break;
		}

	}

	for (i = 0; i < 4; i++) {
		for (j = 0; j < 13; j++) {
			if (cards[i][j]==0) {
				switch(i){
				case 0:printf("S %d\n", j + 1); break;
				case 1:printf("H %d\n", j + 1); break;
				case 2:printf("C %d\n", j + 1); break;
				case 3:printf("D %d\n", j + 1); break;
				default:break;
				}
			}
		}
	}

	return 0;

}

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

#define MAX 10000

using namespace std;

#define inf    0x3f3f3f3f
#define ll long long
#define all(a) (a).begin(),(a).end()
#define INF (int)1e15
#define MOD 1000000007
#define access(i) a[i/3][i%3]

 int main(){

 string s; cin>>s;



  int n = s.length();

  char ani = s[n-1];

  if(ani == 's')
  {
       for(int i=0;i<n;i++)
            cout<<s[i];

       cout<<"es"<<endl;
  }
  else {
     for(int i=0;i<n;i++)
            cout<<s[i];

         cout<<"s"<<endl;
  }


 return 0;
 }


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if(s.indexOf("9") != -1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
bool is(string s){
    string t=s;
    reverse(t.begin(),t.end());
    return s==t;
}
int main(){
    string s;
    cin>>s;
    int n=s.size();
    if(is(s)){
        if(is(s.substr(0,(n-1)/2))){
            if(is(s.substr((n+3)/2-1))){
                O("Yes");
            }else O("No");
        }else O("No");
    }else O("No");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int N, M;
  cin >> N >> M;
  bool bl = (N == M);
  if (bl) puts("Yes");
  else puts("No");
  return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
 
using namespace std;
 
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
 
int H, W;
int N, M;
 
int L, T;
int R, B;
 
int ans;
 
char F[65][65];
char c[65][65];
 
void get_rect() {
   
  L = 65, T = 65;
  R = 0, B = 0;
   
  rep(i, 65) rep(j, 65) {
    if(c[i][j] == '#') {
      T = min(T, i);
      L = min(L, j);
      B = max(B, i);
      R = max(R, j);
    }
  }
   
}
 
void solve() {
 
  char G[65][65];
  int ans_tmp;
   
  rep(k, N-B+T) rep(l, M-R+L) { // oku hidari ue
     
    rep(i, N) rep(j, M) { G[i][j] = F[i][j]; }
     
     
    REP(i, T, B+1) REP(j, L, R+1) { // c no hidari ue
       
      int pos_i = i-T, pos_j = j-L; // small rect oku basyo
       
      if(G[k+pos_i][l+pos_j] == '#' && c[i][j] == '#') { goto Next; }
       
      if(c[i][j] == '#') {
    G[k+pos_i][l+pos_j] = '#';
      }
       
    }
     
     
    ans_tmp = 0;
     
    rep(i, N) {
      bool ok = 1;
      rep(j, M) {
    if(G[i][j] == '.') { ok = 0; }
      }
      ans_tmp += ok;
       
    }
      ans = max(ans, ans_tmp);
  Next:;
  }
   
   
}
 
int main() {
   
  int Tc; cin >> Tc;
  rep(_, Tc) {
     
    scanf("%d%d",&H, &W);
    rep(i, 65) rep(j, 65) c[i][j] = '.';
    rep(i, H) rep(j, W) cin >> c[i][j];
    scanf("%d%d",&N, &M);
    rep(i, N) rep(j, M) cin >> F[i][j];
     
    ans = -1;
    rep(t, 4) {
      char tmp[65][65];
       
      rep(i, 65) rep(j, 65)
    tmp[j][65-1-i] = c[i][j];
      rep(i, 65) rep(j, 65) {
    c[i][j] = tmp[i][j];
      }
      get_rect();
      solve();
    }
     
    cout << ans << endl;
  }
   
  return 0;
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxN = 2e6 + 1;
const lli mod = 1e9 + 7;
lli fat[maxN];
lli x, y;

lli modPow(lli x, lli y)
{
  lli ans = 1;
  while (y)
  {
    if (y & 1LL) ans = ans * x % mod;
    x = x * x % mod, y >>= 1LL;
  }
  return ans;
}

lli inv(lli num)
{
  return modPow(num, mod - 2);
}

lli choose(lli n, lli k)
{
  return fat[n] * inv(fat[k] * fat[n - k] % mod) % mod;
}

int main()
{
  fat[0] = 1;
  for (int i = 1; i < maxN; i ++)
    fat[i] = i * fat[i - 1] % mod;

  while (scanf("%lld %lld", &x, &y) != EOF)
  {
    if ((x + y) % 3 != 0) printf("0\n");
    else
    {
      lli line = (x + y) / 3;
      if (x - line < 0 || y - line < 0) printf("0\n");
      else printf("%lld\n", choose(line, x - line));
    }
  }
  return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <unordered_map> //???????????\??¢??°

using namespace std;

//???????????°??????TEST????????????????????¬???????????????????????????????????¢????????????
//#define TEST //*******************************************************************************************************************************************

//?????????????????¨??§?????\????????????????????????????????°?????????????¨???????????????????dout???????????????????????§???????????¬??????????????????????????????????????????
#ifdef TEST
    #define dout cout
#else
    stringstream dummy; //???????????°??????dout?????????????????????????????????
    #define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummy?????????????????????????????????????????¨?????¢?????¢???????????????
    //???????????¨??????????????????goodbit?????????????????????????????¨???????????´????????????????????????????????¨?????°?????????????????§???????????????????????????????????? http://d.hatena.ne.jp/linden/20060427/p1
#endif


#define disp(A) dout << #A << " = " << (A) << endl
#define disP(A) dout << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)

#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl


//http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2529878#1

vector<int> a;

bool canMakeNumber(int startIndex, int key) {
    
//    dout << "canMakeNumber?(" << startIndex << ", " << key << ")\n";
    
    if( a[startIndex]==key ) {
//        dout << "OK\n";
        return true;
    }
    else if( startIndex == a.size()-1 ) {
//        dout << "NG\n";
        return false;
    }
    else if( key - a[startIndex] < 0 ) {
        return canMakeNumber(startIndex + 1, key);
    }
    else {
        return canMakeNumber(startIndex + 1, key) || canMakeNumber( startIndex + 1,  key-a[startIndex] );
    }
    
}

int main(void) {

    int N, numOfQuery;
    cin >> N;

    int x;
    rep(i,0,N) { cin >> x; a.push_back(x);}

//    dispAll(a,N);
//    sort(a, a+N);
//    dispAll(a,N);

    cin >> numOfQuery;

    int q[numOfQuery];
    rep(i,0,numOfQuery) cin >> q[i];

//    dispAll(q,numOfQuery);



//    numOfQuery = 1;
    rep(i,0,numOfQuery) {

//        dout << "========\n";
//        disp(key);

        cout << (canMakeNumber(0, q[i]) ? "yes" : "no" ) << endl;
    }


    return 0;
}

Measured memory_bytes: 3152
#include <string>
#include <iostream>
#include <vector>
#include <cassert>
#include <random>
#include <algorithm>
#include <deque>
#include <cstring>
#include <time.h>
#include <cstdio>
#include <tuple>
#include <utility>

std::vector<std::vector<std::pair<int,int>>> g;
std::vector<int> d;

void dfs(int cur,int par,int dist) {
  d[cur]=dist;
  for (auto e:g[cur]) {
    if (e.first==par) continue;
    dfs(e.first,cur,(e.second+dist)%2);
  }
}

int main() {
  int n;
  std::cin >> n;
  g.resize(n);
  d.resize(n);
  for (int i=0;i<n-1;++i) {
    int u,v,w;
    std::cin>>u>>v>>w;
    --u;--v;
    w%=2;
    g[u].push_back({v,w});
    g[v].push_back({u,w});
  }
  dfs(0,-1,0);
  for (int i=0;i<n;++i) {
    printf("%d\n",d[i]);
  }
}


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

using namespace std;

int main()
{
    int n,l;
    cin >> n >> l;

    int check=0;
    if(l<0 && l+n-1<0){
        check=l+n-1;
    }
    else if(l<0){
        check=0;
    }
    else if(l>=0){
        check=l;
    }

    int ans=0;
    for(int i=0;i<n;i++){
        if(check!=l) ans+=l;
        l++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, x = read_line(int, int)

m = []
for i in range(n):
    mm, = read_line(int)
    m.append(mm)

count = len(m)
x -= sum(m)

count += x // min(m)

print(count)


Measured memory_bytes: 38384
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;
long long int lcm(long long int x, long long int y)
		{
			if(x==0)
				return y;
			if(y==0)
				return x;
			long long int r=0, a, b;
			a = (x > y) ? x : y; // a is greater number
			b = (x < y) ? x : y; // b is smaller number
			r = b;
			while(a % b != 0)
			{
				r = a % b;
				a = b;
				b = r;
			}
			return (x*y)/r;
}

int main()
{
   
    long long int a,b,c;
    cin>>a>>b;
    c=lcm(a,b);
    cout<<c;
    return 0;
}


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

using namespace std;
using Graph = vector<vector<int>>;

int main() {
  int k;
  string s;
  cin>>k>>s;
  int n=s.size();
  if(n<=k){
    cout<<s<<endl;
  }
  else{
    for(int i=0;i<k;i++){
      cout<<s.at(i);
    }
    cout<<"..."<<endl;
  }
  
}

Measured memory_bytes: 3560
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		long mod=1000000007;
		long xsum=0;
		long ysum=0;
		for(long i = 0; i<n; i++){
			xsum+=(sc.nextLong())*(2*i-n+1);
			xsum%=mod;
		}
		for(long i = 0; i<m; i++){
			ysum+=(sc.nextLong())*(2*i-m+1);
			ysum%=mod;
		}
		System.out.println((xsum*ysum)%mod);
	}
}


Measured memory_bytes: 67316
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9 + 7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}

int main(){
    ll n,m; cin >> n >> m;
    vl s(n),t(m);
    rep(i,n) cin >> s[i];
    rep(j,m) cin >> t[j];
    vvl dp(n+1,vl(m+1,0));
    rep(i,n+1) dp[i][0] = 1;
    rep(j,m+1) dp[0][j] = 1;
    rep(i,n){
        rep(j,m){
            if(s[i]==t[j]) dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j];
            else dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]-dp[i][j];
            if(dp[i+1][j+1]<0) dp[i+1][j+1] += mod;
            dp[i+1][j+1] %= mod;
        }
    }
    /*rep(i,n+1){
        rep(j,m+1) cout << dp[i][j] << " ";
        cout << endl;
    }*/
    cout << dp[n][m] << endl;
}

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

#define ll long long

ll pow(ll base, ll exp, ll mod) {
    if(exp == 0) return 1;
    if(exp % 2 == 1) return (base * pow(base, exp - 1, mod)) % mod;
    ll tmp = pow(base, exp / 2, mod);
    return (tmp * tmp) % mod;
}

int main() {
    std::ios::sync_with_stdio(false);
    using namespace std;
    const ll mod = 2019;
    string S;
    cin >> S;
    reverse(S.begin(), S.end());
    ll result = 0;
    map<ll, ll> B;
    B[0] = 1;
    ll c = 0;
    for(int i = 0; i < S.size(); i++)
        if(S[i] != '0') {
            c = (c + (S[i] - '0') * pow(10, i, mod)) % mod;
            //cout << c << "\n";
            result += B[c];
            B[c] += 1;
        }

    /*
    cout << "\n";
    cout << "\n";
    cout << "\n";
    for(auto it : B) {
        cout << it.first << " " << it.second << "\n";
    }
    */

    cout << result << "\n";

    return 0;
}


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

int main() {
  int n;
  int cnt=1;
  cin >> n;
  vector<int> v(n);
  for(int i=0;i<n;i++){
    cin >> v.at(i);
  }
  
  sort(v.begin(),v.end());
  
  int min=v.at(0);
  for(int i=1;i<n;i++){
    if(min ==v.at(i))
      continue;
    else{
      min=v.at(i);
      cnt++;
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int count = 0;


			if (n==0){
				break;
			}
			String[] step =new String[n];
			for (int i = 0; i < n; i++){
				step[i] = sc.next();
			}
			n = n%2 ==0 ? n : n-1;//????????????????\???°????????£??????????????????????????????????????????
			// if n is 5, commands are compared 1st with 2nd and 3rd with 4th.
			for (int i =0; i < n;i = i+ 2){
				if(step[i].charAt(0)!=step[i+1].charAt(0)){
					count ++;
				}
			}
			System.out.println(count);

		}
	}


}

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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;
}


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  ll N; cin >> N;
  // ll N, K; cin >> N >> K;
  // ll x, y, z; cin >> x >> y >> z;
  // ll a, b, c; cin >> a >> b >> c;
  // string s; cin >> s;
  vector<ll> a(N); rep(i, N) cin >> a[i];
  sort(a.begin(), a.end());
  ll ans = 0;

  for(int i = 0; i < N; i ++) {
    for(int j = i + 1; j < N; j++) {
      for(int k = j + 1; k < N; k++) {
	if(a[i]+a[j] >a[k] && a[i] != a[j] && a[j] != a[k] && a[k] != a[i]) {
	  ans++;
	  //	  cerr << a[i] << " " << a[j] << " " << a[k] << endl;
	}
      }
    }
  }

  

  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

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

    if (K % 2 != 0) {
        ll num = N / K;
        print(num*num*num);
    } else {
        ll num = N / K;
        ll ans = 0;
        ans += num * num * num;
        num = N / (K/2) - N / K;
        ans += num * num * num;
        print(ans);
    }
}

signed main() {
    solve();
}


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

int m[1000];
int main(){
  int N, X;
  cin >> N >> X;
  int mini = INT_MAX;
  int ans = N;
  for(int i = 0; i < N; i++){
    cin >> m[i];
    X = X - m[i];
    mini = min(mini, m[i]);
  }
  ans = ans + floor(X / mini);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdint>
#include <algorithm>
#include <iostream>

int main()
{
    int64_t h;

    std::cin >> h;

    int64_t cur_h = h, cur_n = 1;
    int64_t num = 0;

    while ( cur_h > 0 ) {
        if ( cur_h > 1 ) {
            cur_h >>= 1;
            num += cur_n;
            cur_n <<= 1;
        } else {
            cur_h = 0;
            num += cur_n;
        }
    }

    std::cout << num << std::endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		long[][] A = new long[N][N];
		long ans = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				A[i][j] = sc.nextLong();
				ans += A[i][j];
			}
		}

		boolean[][] connected = new boolean[N][N];
		for(int i=0; i<N; i++) {
			Arrays.fill(connected[i], true);
		}
		for(int i=0; i<N; i++) {
			connected[i][i] = false;
		}

		for(int k=0; k<N; k++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					//別の経由地を通ったほうが距離が短くなる場合
					if(A[i][j] > A[i][k] + A[k][j]) {
						System.out.println(-1);
						return;
					}
					//別の経由地を通っても最短距離になる場合
					else if(connected[i][j] && i != k && j != k && A[i][j] == A[i][k] + A[k][j]) {
						ans -= A[i][j];
						connected[i][j] = false;
					}
				}
			}
		}

		//無向グラフなので2で割る
		ans /= 2;

		System.out.println(ans);

	}

}


Measured memory_bytes: 50572
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;

int main(){
    int N;
    cin >> N;
    ll a[N], sum[2];
    fill(sum, sum+2, 0);
    vector<int> ids[2];
    rep(i, N){
        cin >> a[i];
        if(a[i] > 0){
            ids[i%2].pb(i+1), sum[i%2] += a[i]; 
        }
    }
    //負の要素しか存在しない場合
    if(ids[0].empty() && ids[1].empty()){
        int id = -1;
        ll ans = -INF;
        rep(i, N){
            if(a[i] > ans) ans = a[i], id = i;
        }
        cout << ans << endl;
        ids[0].pb(id+1);
    }
    else{
        if(sum[0] >= sum[1]) cout << sum[0] << endl;
        else{
            cout << sum[1] << endl;
            swap(ids[0], ids[1]);
        }
    }
    vector<int> res;
    int n = ids[0].size();
    rep3(i, N, ids[0][n-1]+1) res.pb(i);
    rep3(i, n-2, 0){
        int l = ids[0][i], r = ids[0][i+1];
        rep3(i, (l+r)/2, l+1) res.pb(i);
    }
    rep2(i, 1, ids[0][0]-1) res.pb(1);
    cout << res.size() << endl;
    for(auto &e: res) cout << e << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400005;
int size[N],ne[N],tot,fi[N],zz[N],x,y,n,cnt,d[N];
void jb(int x,int y){
	ne[++tot]=fi[x];
	fi[x]=tot;
	zz[tot]=y;
}
void dfs(int x,int y){
	size[x]=1;int cnt=0;
	for (int i=fi[x];i;i=ne[i])if (zz[i]!=y){
		dfs(zz[i],x);
		size[x]+=size[zz[i]];
		cnt+=size[zz[i]]&1;
	}
	if (cnt>=2){
		puts("First");
		exit(0);
	}
}
signed main(){
	scanf("%lld",&n);
	if (n&1){
		puts("First");
		return 0;
	}
	for (int i=1;i<n;i++){
		scanf("%lld%lld",&x,&y);
		jb(x,y);jb(y,x);
		d[x]++;d[y]++;
	}
	int cnt=0;
	for (int i=1;i<=n;i++)
		if (d[i]>1){
			dfs(i,0);
			break;
		}
	puts("Second");
}

Measured memory_bytes: 13312
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<ctime>
#include<complex>
#include<list>
using namespace std;

const int INF=100005;
long long ans;
int n,m,k;
int a[INF],used[INF],Use[INF];
vector<int> nei[INF];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q[INF],qq;

void dfs(int x,int p,int c){
	used[x]=1;
	q[c].push(make_pair(a[x],x));
	for(int i=0;i<nei[x].size();i++) if(nei[x][i]!=p) dfs(nei[x][i],x,c);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",a+i);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	for(int i=0;i<n;i++) if(!used[i]) dfs(i,-1,k++);
	if(k==1){
		cout<<0<<endl;
		return 0;
	}
	for(int i=0;i<k;i++){
		ans+=q[i].top().first;
		Use[q[i].top().second]=1;
		q[i].pop();
	}
	for(int i=0;i<n;i++) if(!Use[i]) qq.push(make_pair(a[i],i));
	for(int i=0;i<k-2;i++){
		if(!qq.size()){
			cout<<"Impossible"<<endl;
			return 0;
		}
		ans+=qq.top().first;
		qq.pop();
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 12408
a,b,c,d,e,f = map(int, input().split())
w = []
s = []

# 入れられるwaterの量ベクトル
ws = 0
while ws*a*100 <= f:
  water = ws * a
  while water*100 <= f:
    if water not in w and water != 0:
      w.append(water)
    water += b
  ws += 1

# 入れられるsugarの最大量ベクトル
ans = [1,0]
for wb in range(len(w)):
  sc = 0
  sd = 0
  ss = 0
  while sc/w[wb] <= e and sc + w[wb]*100 <= f:
    suger = sc * c
    while suger/w[wb] <= e and suger + w[wb]*100 <= f:
      if ss < suger:
        ss = suger
      suger += d
    sc += 1
  
  if ss/w[wb] >= ans[1]/ans[0]:
    ans = [w[wb] , ss]
print(' '.join(map(str,[ans[0]*100+ans[1],ans[1]])))

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

int main() {
	int N;
	cin >> N;
	int t[N+1], x[N+1], y[N+1];
	t[0] = x[0] = y[0] = 0;
	for (int i = 0; i < N; i++) {
		cin >> t[i+1] >> x[i+1] >> y[i+1];
	}

	bool flag = true;
	for (int i = 0; i < N; i++) {
		int time = t[i+1] - t[i];
		int dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i]);
		if (time < dist || dist % 2 != time % 2) {
			flag = false;
		}
	}

	if (flag) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 1408
s = int(input())
a = [s]

for i in range(0,1000000):
  if a[i]%2 ==0:
    a.append(a[i]/2)
  else:
    a.append(3*a[i] +1)
  if a[i] in a[:i]:
    print(i+1)
    exit()

Measured memory_bytes: 38512
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3
0 0 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0

output:
1
1
0
"""

import sys

EPS = 1e-9


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def check_ccw(p0, p1, p2):
    # flag = float('inf')
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        # print('COUNTER_CLOCKWISE')
        flag = 1
    elif cross(a, b) < -1 * EPS:
        # print('CLOCKWISE')
        flag = -1
    elif dot(a, b) < -1 * EPS:
        # print('ONLINE_BACK')
        flag = 2
    elif abs(a) < abs(b):
        # print('ONLINE_FRONT')
        flag = -2
    else:
        # print('ON_SEGMENT')
        flag = 0
    return flag


def check_intersection(_lines):
    for line in _lines:
        line = tuple(map(int, line))
        p0, p1, p2, p3 = (x + y * 1j for x, y in zip(line[::2], line[1::2]))
        flag = (check_ccw(p0, p1, p2) * check_ccw(p0, p1, p3) <= 0) and \
               (check_ccw(p2, p3, p0) * check_ccw(p2, p3, p1) <= 0)

        if flag:
            print('1')
        else:
            print('0')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    l_num = int(_input[0])
    lines = map(lambda x: x.split(), _input[1:])

    check_intersection(lines)

Measured memory_bytes: 7980
package main

import (
	"fmt"
	"strconv"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var s string
	fmt.Scan(&s)

	ans1 := 0
	for i, a := range s {
		j, _ := strconv.Atoi(string(a))
		if i%2 != j {
			ans1++
		}
	}
	ans2 := 0
	for i, a := range s {
		j, _ := strconv.Atoi(string(a))
		if (i+1)%2 != j {
			ans2++
		}
	}

	fmt.Println(min(ans1, ans2))
}


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

const ll MOD = 1e9+7;

int main() {

    int N, K;
    cin >> N >> K;

    vl A, B;
    ll tmp;
    rep(i, N) {
        cin >> tmp;
        if (tmp >= 0) A.push_back(tmp);
        else B.push_back(-tmp);
    }

    int a = A.size();
    int b = B.size();

    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());

    if (b == 0 && A[0] == 0) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;

    if (a == 0 && K%2 == 1) {
        rep(i, K) {
            ans = (ans * B[b-1-i]) % MOD;
        }
        ans = (MOD - ans);
        cout << ans << endl;
        return 0;
    }

    if (K == N) {
        rep(i, a) {
            ans = (ans * A[i]) % MOD;
        }
        rep(i, b) {
            ans = (ans * B[i]) % MOD;
        }
        if (b%2 == 1) {
            ans = MOD - ans;
        }
        cout << ans << endl;
        return 0;
    }


    int itr_a = 0;
    int itr_b = 0;

    int cnt = 0;
    while(cnt < K) {
        if (K - cnt == 1) {
            ans = (ans * A[itr_a]) % MOD;
            cnt++;
            break;
        }
        if (itr_a + 1 < a && itr_b + 1 < b) {
            if (A[itr_a]*A[itr_a+1] > B[itr_b]*B[itr_b+1]) {
                ans = (ans * A[itr_a]) % MOD;
                ans = (ans * A[itr_a+1]) % MOD;
                itr_a += 2;
            }
            else {
                ans = (ans * B[itr_b]) % MOD;
                ans = (ans * B[itr_b+1]) % MOD;
                itr_b += 2;
            }
        }
        else if (itr_a + 1 < a) {
            ans = (ans * A[itr_a]) % MOD;
            ans = (ans * A[itr_a+1]) % MOD;
            itr_a += 2;
        }
        else {
            ans = (ans * B[itr_b]) % MOD;
            ans = (ans * B[itr_b+1]) % MOD;
            itr_b += 2;
        }
        cnt += 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5468
#include <bits/stdc++.h>
#define INF pow(10, 9) + 7
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define chmax(x, y) x = max(x, y)
#define print(x) cout << x << "\n"
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;

void solve(){
	
	ll N, pop_count;
	string X;
	cin >> N >> X;
	vl ans(N, 1);
	vl A(N);
	
	ll cnt = 0;
	
	ll M0 = 0;
	ll M1 = 0;
	ll temp0 = 1;
	ll temp1 = 1;
	
	rep(i, N)  cnt += X[i] == '1';
	
	rep(i, N){
		if(X[N - 1 - i] == '1'){
			if(cnt != 1)  M0 = (M0 + temp0) % (cnt - 1);
			M1 = (M1 + temp1) % (cnt + 1);
		}
		if(cnt != 1)  temp0 = (temp0 * 2) % (cnt - 1);
		temp1 = (temp1 * 2) % (cnt + 1);
	}
	
	temp0 = 1;
	temp1 = 1;

	rep(i, N){
		
		if(X[N - 1 - i] == '0')  A[N - 1 - i] = (M1 + temp1) % (cnt + 1);

		else{
			if(cnt == 1){
				A[i] = 0;
				ans[N - 1 - i] -= 1;
			}
			else{
				A[N - 1 - i] = (M0 - temp0) % (cnt - 1);
				A[N - 1 - i] = (A[N - 1 - i] + (cnt - 1)) % (cnt - 1);
			}
				
		}
		
		if(cnt != 1)  temp0 = (temp0 * 2) % (cnt - 1);
		temp1 = (temp1 * 2) % (cnt + 1);
		
	}

	rep(i, N){
		
		while(A[i]){
			
			pop_count = __builtin_popcount(A[i]);
			A[i] %= pop_count;
			ans[i] += 1;
			
		}
		
	}
	
	rep(i, N)  print(ans[i]);

}	

int main(){
    
    fastio;
	solve();
    
	return 0;
	
}


Measured memory_bytes: 6788
import itertools


N, M, Q = map(int, input().split())

a = [None] * Q
b = [None] * Q
c = [None] * Q
d = [None] * Q

for i in range(Q):
    num = list(map(int, input().split()))
    a[i], b[i], c[i], d[i] = num[0] - 1, num[1] - 1, num[2], num[3]

A = [i for i in range(1, M + 1)]

max_v = 0
for v in itertools.combinations_with_replacement(A, N):
    tmp_sum = 0
    for i in range(Q):
        if v[b[i]] - v[a[i]] == c[i]:
            tmp_sum += d[i]
    max_v = max(max_v, tmp_sum)

print(max_v)


Measured memory_bytes: 68128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        void solve(InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int A = in.nextInt();
            int B = in.nextInt();
            out.println(Math.min(N*A, B));
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int size) {
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        long[] nextLongArray(int size) {
            long[] arr = new long[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fsp(x) fixed << setprecision(x)
#define xout cerr
const ll inf = LLONG_MAX;
const long double pi = acosl(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

//#include <vector>
//#include <cmath>
std::vector<long long> div(long long n) {
	std::vector<long long> v(1, 1);
	if (n == 1) return v;
	for (long long i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) v.push_back(i);
	}
	if (sqrt(n) == (long long)sqrt(n)) {
		for (long long i = v.size() - 2; i >= 0; i--) v.push_back(n / v[i]);
	}
	else {
		for (long long i = v.size() - 1; i >= 0; i--) v.push_back(n / v[i]);
	}
	return v;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//const ll p = 1e9 + 7;
	//const ll p = 998244353;

	ll n;
	cin >> n;
	vector<ll> a(n);
	for (ll i = 0; i < n; i++) cin >> a[i];

	ll ans = 0, sum = 0;
	for (ll i = 0; i < n; i++) {
		if (sum >= 0) {
			if (sum + a[i] >= 0) {
				ans += sum + a[i] + 1;
				sum = -1;
			}
			else sum += a[i];
		}
		else {
			if (sum + a[i] <= 0) {
				ans += - sum - a[i] + 1;
				sum = 1;
			}
			else sum += a[i];
		}
	}

	ll ans2 = 0; sum = 0;
	for (ll i = 0; i < n; i++) {
		if (sum > 0) {
			if (sum + a[i] >= 0) {
				ans2 += sum + a[i] + 1;
				sum = -1;
			}
			else sum += a[i];
		}
		else {
			if (sum + a[i] <= 0) {
				ans2 += - sum - a[i] + 1;
				sum = 1;
			}
			else sum += a[i];
		}
	}

	cout << min(ans, ans2) << endl;
}


Measured memory_bytes: 3976
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int n,m;
	cin>>n>>m;
	vint cnt(m);
	map<int,int> ma;
	rep(i,n){
		int x;
		cin>>x;
		cnt[x%m]++;
		ma[x]++;
	}
	vint cnt2(m);
	for(auto x: ma){
		cnt2[x.fi%m] += x.se/2;
	}
	ll ans = 0;
	ans += cnt[0]/2;
	rep(i,1,m){
		int j = m-i;
		if(i>j) break;
		if(i==j){
			ans += cnt[i]/2;
		}
		else{
			int t = min(cnt[i], cnt[j]);
			ans += t;
			if(cnt[i]-t>1){
				ans += min(cnt2[i], (cnt[i]-t)/2);
			}
			if(cnt[j]-t>1){
				ans += min(cnt2[j], (cnt[j]-t)/2);
			}
		}
	}
	cout<<ans<<endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) int((a).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

#define _deb(x) cout<<x;
void _print() {cerr << "]\n";} template <typename T, typename... V>void _print(T t, V... v) {_deb(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
template <class T, class U> void print_m(const map<T,U> &m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}
template<class T, class U>void debp(const pair<T, U> &pr, bool end_line=1){cout<<"{"<<pr.first<<" "<<pr.second<<"}"; cout<<(end_line ? "\n" : ", ");}
template <class T> void print_vp(const T &vp, int sep_line=0){if(vp.empty()){cout<<"Empty"<<endl; return;}if(!sep_line) cout<<"{ ";for(auto x: vp) debp(x,sep_line);if(!sep_line) cout<<"}\n";cout<<endl;}
template <typename T>void print(const T &v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<sz(v); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<endl;}
template <typename T>void print_vv(const T &vv){if(sz(vv)==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<sz(*vv.begin()); j++)cout<<setw(w)<<j<<" ";cout<<endl;int i = 0;for(auto &v: vv){cout<<i++<<" {";for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<"},\n";}cout<<endl;}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int k; string s;
    while(cin>>k>>s){
        int n = s.size();
        if(n<=k){
            cout<<s<<endl;
        }else{
            cout<<s.substr(0,k)<<"..."<<endl;
        }
    }
    return 0;
}

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

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N) cin >> a.at(i);
    ll ans = -1;
    auto left = a.begin();
    ll c = 1;
    ll cnt = 0;
    while(left != a.end()){
        auto result = find(left,a.end(),c);
        if(result != a.end()){
            cnt++;
            c++;
            left = result + 1;
        }/*else if(a.at(result-a.begin())==c){
            cnt++;
            break;
        }*/
        else{
            break;
        }
    }
    if(cnt != 0) ans = N - cnt;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    long long int n,k;
    cin>>n>>k;
    vector<long long int> A(n);
    REP(i,n){
        cin>>A[i];
    }
    long long int result=0;
    REP(i,n){
        REP(j,n){
            if(A[i]>A[j]){
                if(i<j){
                    result=(result+(k*(k+1)/2))%mod;
                }else{
                    result=(result+(k*(k-1)/2))%mod;
                }
            }
        }
    }
    cout<<result<<endl;
    return 0;
}


Measured memory_bytes: 888
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define PI 3.14159265358979323846264338327950288
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)
typedef long long ll;
using namespace std;

// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //

int main(void) {

	int N; cin >> N;
	priority_queue<
		double,
		vector<double>,
		greater<double>		
	> queue;

	rep(i, N) {
		int x;
		cin >> x;
		queue.push(x);
	}

	double ans;
	while (true) {
		if (queue.size() == 1) {
			ans = queue.top();
			break;
		}
		double x = queue.top(); queue.pop();
		double y = queue.top(); queue.pop();
		queue.push((x + y) / 2);
	}

	cout << setprecision(7) << ans << endl;
	return 0;
}


Measured memory_bytes: 3812