akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;


int main(){

int N;
int A;
int i;
int max=1000000000;
cin >> N;
for(i=0;i<N;++i){
  cin >> A;
  int j=0;
  while(A%2 == 0){
    A /= 2;
    j++;
  }
  if(max > j){
    max = j;
  }
}
  cout << max;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int CalcCost(int *input_array, int n, int m);

int main(){
  int n;
  int sum=0;
  int *input_array;

  cin >> n;
  input_array = new int[n];

  for (size_t i = 0; i < n; i++){
    cin >> input_array[i];
    sum += input_array[i];
  }

  int m, ceil_m, floor_m;
  int cost, ceil_cost, floor_cost;
  if ((sum % n) == 0){
    m = int(sum / n);
    cost = CalcCost(input_array, n, m);
  } else {
    ceil_m = sum / n + 1;
    floor_m = sum / n;
    ceil_cost = CalcCost(input_array, n, ceil_m);
    floor_cost = CalcCost(input_array, n, floor_m);
    if (ceil_cost > floor_cost){
      cost = floor_cost;
    } else {
      cost = ceil_cost;
    }
  }

  cout << cost << endl;

  return 0;
}

int CalcCost(int *input_array, int n, int m){
  int cost=0;
  for (size_t i = 0; i < n; i++){
    cost += (m - input_array[i]) * (m - input_array[i]);
  }
  return cost;
}

Measured memory_bytes: 256
using System;
using System.Linq;
#if !DEBUG
    using System.IO;
#endif

public class Program {
    public static void Main() {
        #region SetAutoFlushIsFalse
#if !DEBUG
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
#endif
        #endregion
        var aArr = ReadLib.ReadAsULongArray();
        var a = aArr[0];
        var b = aArr[1];
        var x = aArr[2];

        var val = CalcVal(a, b, x);
        Console.WriteLine(val);
        #region Flush
#if !DEBUG
        Console.Out.Flush();
        sw.Close();
#endif
        #endregion

    }

    private static ulong CalcVal(ulong a, ulong b, ulong x) {
        if (x == 1) {
            return b - a + 1;
        }
        var firstN = (a / x) + (ulong)(a % x == 0 ? 0 : 1);
        var lastN = b / x;

        if (firstN > b) {
            return 0;
        }

        return lastN - firstN + 1;
    }
}

static class ReadLib {
    public static long ReadAsLong() {
        return long.Parse(Console.ReadLine());
    }

    public static int ReadAsInt() {
        return int.Parse(Console.ReadLine());
    }

    public static int[] ReadAsIntArray() {
        return Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    }

    public static long[] ReadAsLongArray() {
        return Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
    }

    public static ulong[] ReadAsULongArray() {
        return Console.ReadLine().Split(' ').Select(s => ulong.Parse(s)).ToArray();
    }

    public static string[] ReadAsStringArray() {
        return Console.ReadLine().Split(' ');
    }

    public static int[] ReadNTimesAsInt(int n) {
        return Enumerable.Range(1, n).Select(s => int.Parse(Console.ReadLine())).ToArray();
    }

    public static int[][] ReadNTimesAsIntArray(int n) {
        return Enumerable.Range(1, n).Select(s => ReadAsIntArray()).ToArray();
    }

}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 998244353;
const int maxn = 3030;



ll dp[maxn][maxn];
ll n, s;
ll a[maxn];

void add(ll& x, ll y) {
    x+=y;
    x%=mod;
}

	 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>s;

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

    dp[0][0]=1;

    for (int i=0; i<n; i++) {
	for (int j=0; j<=s; j++) {
	    add(dp[i+1][j], 2LL*dp[i][j]);
	    if (j+a[i]<=s) {
		add(dp[i+1][j+a[i]], dp[i][j]);
	    }
	}
    }


    cout<<dp[n][s]<<endl;  

    return 0;
}


Measured memory_bytes: 74684
#include <stdio.h>

int main(void) {
	int N, M, X;
	int A[128];
	int i;
	int tomatu = 0, sumipe = 0;
	if (scanf("%d%d%d", &N, &M, &X) != 3) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
		if (A[i] < X) tomatu++; else sumipe++;
	}
	printf("%d\n", tomatu <= sumipe ? tomatu : sumipe);
	return 0;
}


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

using namespace std;

int gcd(int a, int b) {
	for (; b; swap(a, b))
		a %= b;
	return a;
}

int main() {
	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	int g = gcd(n, m);
	for (int i = 0; i < g; i++) {
		if (s[n / g * i] != t[m / g * i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	cout << long(n) / g * m << endl;
	return 0;
}


Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dunk(n) cout << n << endl
#define all(v) v.begin(), v.end()


int main() {
    int n;
    cin>>n;
    map<string,int> mp;
    rep(i,n){
        string s;
        cin>>s;
        mp[s]++;
    }
    
    int mx=0;
    for(auto x:mp) mx=max(mx,x.second);
    for(auto x:mp){
        if(x.second!=mx) continue;
        dunk(x.first);
    }
    return 0;
}



Measured memory_bytes: 25216
"use strict";
main(require("fs").readFileSync("/dev/stdin", "UTF-8"));

function main(input) {
  input = input.split("\n");
  const num = parseInt(input.shift()); // マス数
  input = input[0].split(" ").map(m => parseInt(m)); // 各マスの高さ
  let max = 0;
  let count = 0;
  for (let i = 0; i < num; i++) {
    if (input[i] >= input[i + 1]) {
      count++;
    } else {
      if (max < count) max = count;
      count = 0;
    }
  }
  console.log(max);
}


Measured memory_bytes: 17804
#include <stdio.h>
int main(){
    int k,x,y,n,sum = 0;
    scanf("%d%d%d%d",&n,&k,&x,&y);
    for(int i=0;i<n;i++){
        if(i<k)sum += x;
        else sum += y;
    }
    printf("%d\n",sum);
}

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

int main()
{
    char s[102];
    int ara[30] = {0};
    //scanf("%s", s);
    cin >> s;
    for(int i = 0; s[i] != '\0'; i++)ara[s[i] - 'a']++;
    for(int i = 0; i <= 26; i++)
    {
        if(ara[i]%2 == 1)
        {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}


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

def gutyoku(head, tail):
    result = 0
    for i in range(tail, n + 1, 10):
        if int(str(i)[0]) == head:
            result += 1
    return result

result = 0
for i in range(1, 10):
    for j in range(1, 10):
        result += gutyoku(i, j) * gutyoku(j, i)
print(result)


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long ll;

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

  int count=s.size();

  int white = 0;
  rep(i,count){
    if(s.at(i)=='W')white++;
  }

  ll ans=0;
  ll move=0;
  
  rep(i,count){
    if(s.at(i)=='W'){
      ans += i-move;
      move++;
    }
  }
  
  cout << ans;
}

Measured memory_bytes: 3748
#include <stdio.h>

int main(){
    char s1[4],s2[4];
    int i,count=0;
	scanf("%s",s1);
    scanf("%s",s2);
    for(i=0;i<3;i++) if(s1[i] == s2[i]) count++;
    printf("%d\n",count);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1000000007;
const int INF = 1e9;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b;
	cin >> a >> b;
	printf("%s\n", a<=8&&b<=8?"Yay!":":(");
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,i,ans=0;
int main()
{
	scanf("%lld",&n);
	for(i=1;i*i<=n;i++)
	{
		if(n%i==0&&i<n/i-1)ans+=n/i-1; 
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  string flg="Yes";
  int N;
  string S;
  cin >> N >> S;
  if(N%2==1) flg="No";
  else {
    REP(i,(N+1)/2){
      if(S[i]!=S[i+(N+1)/2]){
        flg="No";
        break;
      }
    }
  }
  cout << flg << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <list>
#define maxn 100005
using namespace std;

list<char> s;

int main(int argc, char** argv)
{
	int q;
	char buf[maxn];
	scanf("%s%d", buf, &q);
	for(int i=0; buf[i]; i++) s.push_back(buf[i]);
	bool reversed = false;
	while(q--)
	{
		int op;
		scanf("%d", &op);
		if(op == 1) reversed = !reversed;
		else
		{
			int f; char c;
			scanf("%d %c", &f, &c);
			if(f == 1) // Add to front
				if(reversed) s.push_back(c); // Add to end
				else s.push_front(c); // Still add to front
			else // Add to end
				if(reversed) s.push_front(c); // Add to front
				else s.push_back(c); // Add to end
		}
	}
	if(reversed)
	{
		char* t = new char[s.size()];
		int cnt = 0;
		for(char c: s) t[cnt++] = c;
		for(int i=cnt-1; i>=0; i--) putchar(t[i]);
		delete[] t;
	}
	else for(char c: s) putchar(c);
	putchar('\n');
	return 0;
}

Measured memory_bytes: 9984
#![allow(unused)]
use std::io::{self, Read};

fn get_stdin() -> String {
    let mut buf = String::new();
    let mut stdin = io::stdin();
    stdin.read_to_string(&mut buf);
    return buf
}

fn to_nums(ss: &str) -> Vec<usize> {
    ss.split_whitespace()
        .map(|x| x.parse::<usize>().unwrap())
        .collect()
}

fn main() {
    let input = get_stdin();
    let lines = input.split('\n');
    for line in lines {
        let v = to_nums(line);
        let rect = Rectangle {
            height: v[0],
            width: v[1],
        };
        if rect.is_valid() {
            println!("{}", rect.draw());
        } else {
            break;
        }
    }
}

struct Rectangle {
    height: usize,
    width: usize,
}

impl Rectangle {
    fn draw(&self) -> String {
        let mut pic = "#".repeat(self.width);
        pic.push('\n');
        pic.repeat(self.height)
    }

    fn is_valid(&self) -> bool {
        self.height > 0 && self.width > 0
    }
}



Measured memory_bytes: 5036
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100000+10;
int a[maxn];
int i,j,k,l,t,n,m;
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
bool solve(){
	int i;
	fo(i,1,n)
		if (a[i]%2==1){
			/*if (a[i]==1){
				if (n%2==0) return 1;
				else return 0;
			}*/
			if (a[i]==1) return 0;
			a[i]--;
			break;
		}
	int d=a[1];
	fo(i,2,n) d=gcd(d,a[i]);
	fo(i,1,n) a[i]/=d;
	int t=0,l=0;
	fo(i,1,n)
		if (a[i]%2==0) t^=1;else l++;
	if (!t&&l==1) return solve()^1;
	else if (t) return 0;
	else return 1;
}
int main(){
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%d",&a[i]);
		k=a[i];
		if (k%2==0) t^=1;else l++;
	}
	if (!t&&l==1){
		if (solve()) printf("First\n");else printf("Second\n");
		return 0;
	}
	if (t) printf("First\n");else printf("Second\n");
}

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

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

    bool judge = false;
    int count_C = 0;
    int j = 0;

    for(int i = 2; i < S.size()-1; ++i){
        if(S[i] == 'C'){
            count_C++;
            j = i;
        }
    }



    for(int i = 1; i < S.size(); ++i){
        if (i != j){
            if(isupper(S[i])){
                judge = true;
            }
        }
    }

    if (S[0] != 'A'){
        cout << "WA" << endl;
    }
    else if (count_C != 1){
        cout << "WA" << endl;
    }
    else if (judge){
        cout << "WA" << endl;
    }
    else{
        cout << "AC" << endl;
    }
}

Measured memory_bytes: 256
n = int(input())
N = n
M = int(n**0.5) + 1
prime = [2]
primeflag = [False] + [False, True]*(M//2)

for i in range(3, M, 2):
    if primeflag[i] is False:
        primeflag[i] = True
        prime.append(i)
        for j in range(2*i, M, i):
            primeflag[j] = True

ans = []

for i in prime:
    while N % i == 0:
        ans.append(i)
        N //= i
else:
    if N != 1:
        ans.append(N)

print("{}:".format(n), ' '.join(map(str, ans)))


Measured memory_bytes: 5996
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(read())
N %= 10
hon = {2, 4, 5, 7, 9}
pon = {0, 1, 6, 8}
bon = {3}
if N in hon:
    print('hon')
elif N in pon:
    print('pon')
else:
    print('bon')

Measured memory_bytes: 9204
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

int main() {
  i64 A, B, T;
  std::cin >> A >> B >> T;
  std::cout << (T / A) * B << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;
 
#define int long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 	
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 9;

signed main() {
	IOS;
	ld p = 1.01;
	ld cur = 100;
	int c = 0;
	int x;	cin >> x;
	while(true){
		c++;
		cur = (cur*p);
		cur = (int)cur;
		if(cur >= x)
			break;
	}
	cout << c;
	return 0;
}

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

int main() {
    int N, W;
    cin>>N>>W;
    vector<pair<long, long>> I(N+1, {0, 0});
    vector<vector<long>> DP(W+1, vector<long>(N+1, 0));
    REP(i, 1, N+1){
        cin >> I[i].first >> I[i].second;
    }
    
    REP(i, 1, N+1){
        REP(w, 0, W+1){
            if(w -I[i].first >= 0) DP[w][i] = max(DP[w][i], DP[w - I[i].first][i-1] + I[i].second);
            DP[w][i] = max(DP[w][i], DP[w][i-1]);
        }
    }
    
    cout << DP[W][N] << endl;
}

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

int main(){
	int n,m;
	cin >> n >> m;
	vector<pair<ll, ll>> p(n);
	rep(i,n) cin >> p[i].first >> p[i].second;
	ll cnt=0;
	ll res=0;
	sort(p.begin(), p.end());
	rep(i,n){
		if(p[i].second+cnt <= m){
			cnt += p[i].second;
			res += p[i].first * p[i].second;
		}else{
			res += p[i].first * (m-cnt);
			break;
		}
	}
	cout << res << endl;
	return 0;
}




Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <deque>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<30;
const int EPS = 1e-8;

typedef pair<int, int> pii;

map<pii, double> mp;

double calc(int r1, int r2) {
  if (mp[pii(r1,r2)]) return mp[pii(r1,r2)];
  return mp[pii(r1,r2)] = sqrt((r1+r2)*(r1+r2) - (r1-r2)*(r1-r2));
}

int main() {
  string s;
  while(getline(cin, s)) {
    stringstream ss(s);
    double x;
    ss >> x;
    int r;
    vector<int> v;
    while(ss >> r) {
      v.push_back(r);
    }
    sort(ALL(v));
    int n = v.size();
    if (n == 0) {
      cout << "OK" << endl;
      continue;
    }
    deque<int> dq;
    REP(i,n/2) {
      if (i%2 == 0) {
        dq.push_front(v[i]);
        dq.push_back(v[n-i-1]);
      } else {
        dq.push_front(v[n-i-1]);
        dq.push_back(v[i]);
      }
    }
    if (n%2) {
      if (n==1)
        dq.push_back(v[0]);
      else if (dq[n-2] + calc(dq[0],v[n/2]) < dq[0] + calc(dq[n-2], v[n/2]))
        dq.push_front(v[n/2]);
      else
        dq.push_back(v[n/2]);
    }
    // FOR(it, dq) {
    //   cout << *it << " ";
    // }
    // cout << endl;

    double xx = dq[0] + dq[n-1];
    REP(i, n - 1) {
      xx += calc(dq[i], dq[i+1]);
    }
    if (xx <= x)
      cout << "OK";
    else
      cout << "NA";
    cout << endl;
  }
}

Measured memory_bytes: 0
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
ll a[N], b[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    sort(a, a + n);
    sort(b, b + n);
    ll f = n / 2;
    if (n % 2)
        cout << b[f] - a[f] + 1;
    else
        cout << b[f] + b[f - 1] - a[f] - a[f - 1] + 1;
}

Measured memory_bytes: 6648
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int[] d = new int[n];
        for(int i = 0; i < n; i++){
            d[i] = Integer.parseInt(sc.next());
        }
        
        if(d[0] != 0){
            System.out.println(0);
            return;
        }
        
        long[] d2 = new long[n];
        int max = 0;
        for(int i = 0; i < n; i++){
            d2[d[i]]++;
            if(d[i] > max) max = d[i];
        }
        
        if(d2[0] != 1){
            System.out.println(0);
            return;
        }
        
        final int MOD = 998244353;
        long ans = 1;
        for(int i = 2; i <= max; i++){
            long a = d2[i-1];
            for(int j = 1; j < d2[i]; j++){
                a *= d2[i-1];
                a %= MOD;
            }
            ans *= a;
            ans %= MOD;
        }
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 49000
#include <stdio.h>

int main()
{
    long long int input, sum=0;
    scanf("%lld", &input);
    for (int i=0;i<=input;i++)
    {
        if (i%3!=0 && i%5!=0)
        {
            sum=sum+i;
        }

    }
    printf("%lld", sum);

    return 0;
}

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

#define REP(i, a, b)  for(int i = a, _b = b; i < _b; ++i)
#define FOR(i, a, b)  for(int i = a, _b = b; i <= b; ++i)
#define FORD(i, a, b) for(int i = a, _b = b; i >= b; --i)

using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef long long llong;
const int MX = 55;

vector<int> adj[MX];
int V, E, cnt, ans;
vector<int> low, num;
bool skip[MX][MX];
vector<ii> edges;

void dfs (int u) {
	low[u] = num[u] = cnt++;
	for(int v: adj[u]) {
		if(skip[u][v]) continue;
		edges.push_back(ii(u, v));				
		skip[v][u] = true;
		if(num[v] == -1) {
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
		else {
			low[u] = min(low[u], num[v]);
		}
	}
}


int main() {
#ifdef Home
   freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
 	scanf("%d %d", &V, &E);
	num.assign(V+1, -1);
	low.assign(V+1, MX); 	
 	int u, v;
 	REP(i, 0, E) {
 		scanf("%d %d", &u, &v);
 		adj[u].push_back(v);
 		adj[v].push_back(u);
 	}
 	
 	FOR(v, 1, V) {
 		if(num[v] == -1) {
 			dfs(v);
 		}
 	}
 	for(auto e: edges) {
 		int u = e.first, v = e.second;
 		if(num[u] < low[v]) {
//	 		printf("%d -> %d\n", u, v); 		 		
 			ans++;
 		}
 			
 	}
 	printf("%d\n", ans);  
   return 0;
}

Measured memory_bytes: 256
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void solve() throws Exception {
		long l = scanInt();
		int n = scanInt();
		long x[] = new long[n], xsum[] = new long[n + 1];
		for (int i = 0; i < n; i++) {
			x[i] = scanInt();
			xsum[i + 1] = xsum[i] + x[i];
		}
		long ans = 0;
		for (int it = 0;; it++) {
			for (int i = 0; i < n; i++) {
				long cans = x[n - i - 1];
//				for (int j = n - i; j < min(n, 2 * n - 2 * i); j++) {
//					cans += (l - x[j]) * 2;
//				}
//				for (int j = max(0, n - 2 * i - 1); j < n - i - 1; j++) {
//					cans += x[j] * 2;
//				}
				if (min(n, 2 * n - 2 * i) > n - i) {
					cans += 2 * (l * (min(n, 2 * n - 2 * i) - (n - i)) - (xsum[min(n, 2 * n - 2 * i)] - xsum[n - i]));
				}
				if (n - i - 1 > max(0, n - 2 * i - 1)) {
					cans += 2 * (xsum[n - i - 1] - xsum[max(0, n - 2 * i - 1)]);
				}
				ans = max(ans, cans);
			}
			if (it == 0) {
				for (int i = 0, j = n - 1; i <= j; i++, j--) {
					long t = x[i];
					x[i] = l - x[j];
					x[j] = l - t;
				}
				for (int i = 0; i < n; i++) {
					xsum[i + 1] = xsum[i] + x[i];
				}
			} else {
				break;
			}
		}
		out.print(ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Measured memory_bytes: 44284
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<math.h>
#include<string>
using namespace std;

int main(int argc, char* argv[]){
  int n;
  cin >> n;
  vector<double> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  double ans = v[0];
  for(int i = 0; i < n-1; i++){
    ans = (ans + v[i+1])/2;
  }
  printf("%.7lf\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long int
#define ldouble long double
#define vin vector<int> 
#define rep(i,a,n) for(i=(a);i<(n);i++)
#define INF (int)1000000007

//setprecision()<<

using namespace std;

void fin(int i,int n,vin &a){
    rep(i,0,n){
        cin>>a.at(i);
    } 
} 

signed main() {
    int i;
    vector<string> S(7);
    S.at(0)="MON";
    S.at(1)="TUE";
    S.at(2)="WED";
    S.at(3)="THU";
    S.at(4)="FRI";
    S.at(5)="SAT";
    S.at(6)="SUN";
    string s;
    cin>>s;
    rep(i,0,7){
        if(s==S.at(i)){
            if(i==6){
                cout<<7<<endl;
                continue;
            }
            cout<<6-i<<endl;
        }

    }
return 0;
}

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

typedef struct {
	char word[64];
	int no;
	int length;
} DATA;

int main(void)
{
	DATA Dic[500];
	int DicIndex = 0;
	int MaxLengthID = 0;
	int MaxNoID = 0;
	char Input[1024];
	char wordBuf[64];
	char *rp;
	int i;
	
	fgets(Input, 1024, stdin);
	rp = Input;
	
	while (*rp != '\0'){
		char find = 0;
		
		if (*rp == ' '){
			rp++;
		}
		
		sscanf(rp, "%s", wordBuf);
		for (i = 0; i < DicIndex; i++){
			if (strcmp(wordBuf, Dic[i].word) == 0){
				Dic[i].no++;
				if (Dic[i].no > Dic[MaxNoID].no) MaxNoID = i;
				find = 1;
			}
		}
		
		if (find == 0) {
			strcpy(Dic[DicIndex].word, wordBuf);
			Dic[DicIndex].no = 1;
			Dic[DicIndex].length = strlen(wordBuf);
			if (Dic[DicIndex].length > Dic[MaxLengthID].length) MaxLengthID = DicIndex;
			DicIndex++;
		}
		rp += strlen(wordBuf);
	}
	
	printf("%s %s\n", Dic[MaxNoID].word, Dic[MaxLengthID].word);
	
	return (0);
}

Measured memory_bytes: 0
#include <cstdio>
using namespace std;

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

int main()
{
	int n,m,a,b,ab,ba,x1,x2,y1,y2,t[32][32];

	scanf("%d %d",&n,&m);
	REP(i,n)REP(j,n)
	{
		t[i][j]=(i==j?0:1<<20);
	}

	while(m--)
	{
		scanf("%d,%d,%d,%d",&a,&b,&ab,&ba);
		a--;b--;
		t[a][b]=ab;
		t[b][a]=ba;
	}
	scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);

	REP(k,n)REP(i,n)REP(j,n)
	{
		if(t[i][j]>t[i][k]+t[k][j]) t[i][j]=t[i][k]+t[k][j];
	}

	x1--;x2--;
	printf("%d\n",y1-y2-t[x1][x2]-t[x2][x1]);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

vector<bool> visited(105);
vector<vector<int>> edge(105);
bool dfs(int cur, int par) {
    // if a cycle doesn't exist, return true
    visited[cur] = true;
    bool ic = false;
    if (edge[cur].size() == 0) {
        return true;
    } else {
        for (int i = 0; i < edge[cur].size(); i++) {
            if (edge[cur][i] == par) {
                continue;
            }
            if (visited[edge[cur][i]]) {
                ic = true;
                break;
            } else {
                visited[edge[cur][i]] = true;
            }
            if (!dfs(edge[cur][i], cur)) {
                ic = true;
            }
        }
        if (ic) {
            return false;
        } else {
            return true;
        }
    }
}
signed main() {
    long long n, ans = 0;
    cin >> n;
    vector<long long> as(n);
    map<long long, long long> cnt;
    REP(i, n) { cin >> as[i]; }
    vector<long long> kakakakakakakakakaak(n);
    kakakakakakakakakaak[0] = as[0];
    cnt[kakakakakakakakakaak[0]]++;
    if (kakakakakakakakakaak[0] == 0){
        ans++;
    }
    cnt[0]++;
    for (long long i = 1; i < n; i++) {
        kakakakakakakakakaak[i] = kakakakakakakakakaak[i - 1] + as[i];
        cnt[kakakakakakakakakaak[i]]++;
        if (cnt[kakakakakakakakakaak[i]] > 1) {
            ans += cnt[kakakakakakakakakaak[i]] - 1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 15872
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	string s;
	scan(s);
	if((s[0]==s[1]&&s[2]==s[3]&&s[0]!=s[2])||(s[0]==s[2]&&s[1]==s[3]&&s[0]!=s[1])||(s[0]==s[3]&&s[1]==s[2]&&s[0]!=s[2])){
		prin("Yes");
	}
	else{
		prin("No");
	}
	return 0;
}


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

/* define const */

int a, b; /* finish defineing const */
int arr[1000];

int main()
{
    cin >> a >> b;
    // input

    int sub = b - a;

    for (int i = 1; i < 1000; i++)
    {
        arr[i] = arr[i - 1] + i;
        if (arr[i] - arr[i - 1] == sub)
        {
            cout << (arr[i - 1] - a) << endl;
            break;
        }
    }
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

ll N, K;
ll S[600];
ll A[600];

//約数列挙 O(n**1/2)
vector<ll> divisor(ll n){
    vector<ll> res;
    for(ll i = 1; i * i <= n; i++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n/i) res.push_back(n/i);
        }
    }
    return res;
}

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

    REP(i,N){
        ll a;
        cin >> a;
        A[i] = a;
    }

    //sort(A, A+N);

    S[0] = A[0];
    for(int i = 1; i < N; i++){
        S[i] = S[i-1] + A[i];
    }

    ll sum = S[N-1];

    auto div = divisor(sum);
    ll ans = 1;
    for(auto&& d : div){
        vector<ll> X(N);
        for(int i = 0; i < N; i++){
            X[i] = A[i] % d;
        }
        sort(X.begin(), X.end());

        vector<ll> low(N);
        vector<ll> high(N);
        low[0] = X[0];
        high[0] = d - X[0];
        for(int i = 1; i < N; i++){
            low[i] = X[i] + low[i-1];
            high[i] = d - X[i] + high[i-1];
        }

        for(int i = 1; i < N; i++){
            ll l, h;
            l = low[i-1];
            h = high[N-1] - high[i-1];

            if(abs(l - h) % d != 0) continue;

            ll k = max(l, h);
            if(k <= K) chmax(ans, d);
        }
    }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n,l;
	int ans=0;
	cin >>n>>l;
	vector<string> s(n);
	rep(i,n){
		cin>>s[i];
	}
	sort(all(s));
	rep(i,n){
		cout<<s[i];
	}
	cout<<endl;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N, T;
	int c, t;
	int ans = INF;
	cin >> N >> T;
	rep(i, 0, N)
	{
		cin >> c >> t;
		if (t <= T)
		{
			chmin(ans, c);
		}
	}

	if (ans == INF)
	{
		cout << "TLE" << endl;
	}
	else
	{
		cout << ans << endl;
	}

	return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

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

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

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;

template <typename T>
class RMQ {
	T query(int l, int r, int a, int b, int k){
		if( l <= a && b <= r ){
			return seg[k];
		}else if( l < b && a < r ){
			int m = (b+a)/2;
			T vl = query(l,r, a, m, k*2);
			T vr = query(l,r, m, b, k*2+1);
			return max(vl, vr);	// merge
		}
		return 0;	// default value
	}
public:
	vector<T> seg;	// セグメントツリー (親:k/2  子:k*2,k*2+1)
	int N;
	RMQ(int size){
		N = 1;
		while( N < size ) N<<=1;
		seg.assign(N*2, 0);		// default value
	}
	void update(int pos, T v){
		for(int k=N+pos; k>0; k/=2){
			seg[k] = v;
			v = max(seg[k], seg[k^1]);	// merge
		}
	}
	// [l,r)
	T get(int l, int r){
		return query(l, r, 0, N, 1);
	}
	T get(int pos){		// =get(pos, pos+1)
		return seg[N+pos];
	}
};


const ll MOD = 998244353;

int main(){
	ios_base::sync_with_stdio(false);
	ll N;
	vector<pll> v;
	map<ll,ll> zp;

	cin >> N;
	rep(i,N){
		ll X, D;
		cin >> X >> D;
		v.emplace_back(X, D);
	}
	v.emplace_back(INF, INF);
	sort(all(v));

	int cnt = 0;
	for(auto p: v) zp[p.X] = cnt++;

	RMQ<ll> seg(N+1);

	ll memo[200005] = {};
	memo[N] = 1;
	memo[N+1] = 1;
	rrep(i,N){
		ll x = v[i].X;
		ll nx = x + v[i].Y;
		auto it = lower_bound(all(v), pll(nx, 0));
		ll r = max<ll>(i, seg.get(i, zp[it->X]));
		seg.update(i, r);
		memo[i] = (memo[i+1] + memo[r+1]) % MOD;
	}

	// rep(i,N) cout << memo[i] << " "; cout << endl;

	cout << memo[0] << endl;

	return 0;
}

Measured memory_bytes: 22380
input = gets.to_i

digit = input.to_s.length

result = 0
if digit % 2 == 0
	while (digit - 2) >= 0
      result += (10 ** (digit - 1 ) - 10 ** (digit - 2))
      digit -= 2
    end
else
	result += (input - 10 ** (digit - 1))
    while (digit - 3) >= 0
      result += (10 ** (digit - 2 ) - 10 ** (digit - 3))
      digit -= 2
    end
  	result += 1
end
  
p result

Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define N 100010
class UnionFind{
  public:
  ll p[N],s[N];
  void init(){
    for(int i=0;i<N;i++)p[i]=i,s[i]=1;
  }
  ll par(ll x){
    ll y=x,z;
    while(x!=p[x])x=p[x];
    while(y!=x)z=p[y],p[y]=x,y=z;
    return x;
  }
  ll unite(ll a,ll b){
    a=par(a); b=par(b);
    if(a==b)return 0;
    ll res=s[a]*s[b];
    p[b]=a,s[a]+=s[b];
    return res;
  }
};UnionFind uf;
ll n,m,a[N],b[N],ans[N];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>a[i]>>b[i];
    uf.init();
    ll cur=n*(n-1)/2;
    for(int i=m-1;~i;i--){
      ans[i]=cur;
      cur-=uf.unite(a[i],b[i]);
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<endl;
    return 0;
}



Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define VMAX 50
#define EMAX 500
#define DMAX 20
#define TRUE 1
#define FALSE 0
#define NOTUSED 0
#define END -1
#define ROOT -1
using Graph=vector<vector<int>>;

int main(){
    // グラフを受け取る
    int n,m;
    cin>>n>>m;

    Graph G(n+1);
    G[0]={NOTUSED};
    REP(i,m){
        int a,b;
        cin>>a>>b;

        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 幅優先探索
    vector<int> d(n+1,-1);
    d[0]=NOTUSED;
    queue<int> que;
    vector<int> prev(n+1,-1);
    prev[0]=NOTUSED;
    prev[1]=NOTUSED;

    d[1]=0;
    que.push(1);

    while(!(que.empty())){
        int v=que.front();
        que.pop();

        for(int adj_v:G[v]){
            if(d[adj_v]!=-1){
                continue;
            }
            d[adj_v]=d[v]+1;
            prev[adj_v]=v;
            que.push(adj_v);
        }
    }

    // 出力
    cout<<"Yes"<<endl;
    for(int i=2; i<=n; i++){
        cout<<prev[i]<<endl;
    }
}

Measured memory_bytes: 10628
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<sstream>
#define ll long long
#define mes(x,y) memset(x,y,sizeof(x))
using namespace std;
int main(){
	string s;
	while(cin>>s){
		ll a=(s[0]-'0')*10+(s[1]-'0'),b=(s[2]-'0')*10+(s[3]-'0'),flag1=0,flag2=0;
		if(a>=1&&a<=12)flag1=1;
		if(b>=1&&b<=12)flag2=1;
		if(flag1==1&&flag2==1){
			cout<<"AMBIGUOUS"<<endl; 
		}
		if(flag1==1&&flag2==0){
			cout<<"MMYY"<<endl;
		}
		if(flag1==0&&flag2==1){
			cout<<"YYMM"<<endl;
		}
		if(flag1==0&&flag2==0){
			cout<<"NA"<<endl;
		}
	} 
} 


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int INF = 10000000;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
    ll n; cin >> n;
    ll ans = 0;
    vector<int> num(100010, 0);
    rep(i, n){
        ll a; cin >> a;
        ans += a;
        ++num[a];
    } 

    ll q; cin >> q;
    rep(i, q) {
        ll b, c; cin >> b >> c;
        ans += (c - b) * num[b];
        num[c] += num[b];
        num[b] = 0;
        cout << ans << endl;
    }

}

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


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

    string s;
    cin>>s;
    int a =0,b = 0;

    for(auto i: s){
        if(i == 'A') a++;
        else b++;
    }
    if(a==0 || b==0) cout<<"No\n";
    else cout<<"Yes\n";
}

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

#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

# define ll long long
# define ull unsigned ll

# define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int, int>
#define pll pair<ll, ll>

#define mod 1000000007
using namespace std;
typedef pair<int, int> pi;

//////////////////////////////////////////////////////////////
//const ll INF = 0xFFFFFFFFFFFFFFFL;
//clock_t time_p = clock();
//
//void abhigyan10() {
//    time_p = clock() - time_p;
//    cerr << "Time Taken : " << (float) (time_p) / CLOCKS_PER_SEC << "\n";
//}
//
//ll seed;
//mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
//
//inline ll rnd(ll l = 0, ll r = INF) {
//    return uniform_int_distribution<ll>(l, r)(rng);
//}
//
//#define clrbuf cin.ignore(numeric_limits<streamsize>::max(),'\n');
//#define preciset(x) cout<<setprecision(x)<<fixed;
//////////////////////////////////////////////////////////

ll pow(ll base, ll power) {
    ll result = 1;     // Initialize result

    base = base % mod; // Update base if it is more than or
    // equal to p

    if (base == 0)
        return 0; // In case base is divisible by p;

    while (power > 0) {
        // If power is odd, multiply base with result
        if (power & 1)
            result = (result * base) % mod;

        // power must be even now
        power = power >> 1; // power = power/2
        base = (base * base) % mod;
    }
    return result;
}

void forces() {
    int n, k;
    cin >> n >> k;

    map<ll, ll> myMap;
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        ++myMap[(x % k)];
    }

    for (auto x: myMap)
        cout << x.first << " " << x.second << '\n';


    cout << '\n';

}

void atCoder() {
    int n;
    cin >> n;
    ll ans = 0, i = 1000;
    while (true) {
        ans += i;
//        cout << i << " " << ans << "\n";
        if (ans >= n)
            break;
    }
    cout << ans - n << '\n';

}

int main() {
    fastio;

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    freopen("error.txt", "w", stderr);
#endif

    int test = 1;
//    cin >> test;

    while (test--) {
//        forces();
        atCoder();
    }

    return 0;
}



Measured memory_bytes: 3636
// Aizu Vol-2 0286: Computation of Salary
// 2017.8.20 bal4u@uu
// 2017.11.5 retry

#include <stdio.h>

#define MAX 10000
#define MAX2 500000

typedef struct { int n, nxt, end; } WAK;
typedef struct { int nxt, t, e; } LNK;

WAK wak[MAX+5];
LNK lnk[MAX2+5]; int used;
int b[MAX+5];

char buf[70002], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int N, M, L, i, j, k, ans;
	WAK *w;

	fgets(p=buf, 20, stdin), N = getint(), p++, M = getint();
	while (fgets(p=buf, 30, stdin) && *p != '0') {
		w = wak + getint(), p++, lnk[used].t = getint(), p++, lnk[used].e = getint();
		if (w->n == 0) w->nxt = used;
		else lnk[w->end].nxt = used;
		w->end = used++, w->n++;
	}
	fgets(p=buf, 10, stdin), L = getint();
	while (L--) {
		fgets(p=buf, 70000, stdin);
		for (i = 1; i <= M; i++) b[i] = getint(), p++;
		for (w = wak+1, i = 1; i <= N; i++, w++) {
			if (i > 1) putchar(' ');
			if (w->n == 0) { putchar('0'); continue; }
			for (ans = 0, k = w->nxt, j = w->n; j > 0; j--, k = lnk[k].nxt)
				ans += lnk[k].e * b[lnk[k].t];
			printf("%d", ans);
		}
		putchar('\n');
	}
	return 0;
}

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

int main()
{
  int x;
  cin >> x;
  int ans = 0;
  while (1)
  {
    int prime = 1;
    for (int i = 2; i * i < x; i++)
    {
      if (x % i == 0)
      {
        prime = 0;
      }
    }
    if (prime)
    {
      ans = x;
      break;
    }
    x++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;
const int mod = MOD7;

void ERROR(int num) { cout << "ERROR" << num << endl; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int X, N;
    cin >> X >> N;
    vector<int> P(N);
    rep(i,N) cin >> P[i];

    map<int,int> Map;
    rep(i,N){
    	Map[P[i]] = 2;
    }


    int ans=0;
    rep(i,101){
    	int num1 = X-i;
    	int num2 = X+i;
    	//cout << num1 << ":"<<Map[num1] << " "<< num2 << ":" <<  Map[num2] << endl;
    	if(Map[num1]==0){
    		ans = num1;
    		break;	
    	}
    	if(Map[num2]==0){
    		ans = num2;
    		break;	
    	}
    }

    cout << ans << endl;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long ;
int main(){
    int n;
    cin >> n;
    int ans=0;
    vector<int> a(n),b(n),c(n-1);
    rep(i,n) cin >>a[i];
    rep(i,n) cin >> b[i];
    rep(i,n-1) cin >> c[i];
    rep(i,n){
        int A = a[i];
        A--;
        ans += b[A];
        if(i>0){
            if(a[i]-a[i-1] == 1) ans+=c[a[i-1]-1];
        }
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 3608
n = int(input())
A = [*map(int, input().split())] + [0]
yen = 1000
kabu_yen = kabu_n = 0
for i in range(1,n+1):
    if A[i-1] < A[i]: # buy
        m = yen // A[i-1]
        cost = m * A[i-1]
        yen -= cost
        kabu_yen += cost
        kabu_n += m
    elif A[i-1] > A[i]: # sell
        yen += kabu_n * A[i-1]
        kabu_yen = kabu_n = 0
print(yen)


Measured memory_bytes: 9120
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int width, height;
char map[20][20];
int sx, sy;
bool used[20][20];

int dfs(int x, int y){
    used[y][x] = true;

    int res = 1;
    REP(i, 4){
        int nx = x + dx[i], ny = y + dy[i];
        if(0 <= nx && nx < width && 0 <= ny && ny < height &&
           !used[ny][nx] && map[ny][nx] == '.'){
            res += dfs(nx, ny);
        }
    }
    
    return res;
}

int main(){
    while(std::cin >> width >> height, width || height){
        REP(i, height){
            REP(j, width){
                std::cin >> map[i][j];
                if(map[i][j] == '@'){
                    sx = j; sy = i;
                    map[i][j] = '.';
                }
            }
        }

        REP(i, 20){
            REP(j, 20){
                used[i][j] = false;
            }
        }
        std::cout << dfs(sx, sy) << std::endl;
    }
}

Measured memory_bytes: 1168
#include "bits/stdc++.h"
using namespace std;

#define all(x) x.begin(), x.end()

long long com[70][70]; //67以上でオーバーフロー
void init(int n) {
        for (int i = 0; i <= n; i ++) {
                for (int j = 0; j <= i; j ++) {
                        if (j == 0 || j == i) com[i][j] = 1LL;
                        else com[i][j] = com[i - 1][j - 1] + com[i - 1][j];
                } 
        }
}
long long nCr(int n, int r) { return com[n][r]; }

int main() {
        int n;
        init(66);
        cin >> n;
        long long a, b;
        cin >> a >> b;
        vector<long long> v(n);
        for (int i = 0; i < n; i ++) cin >> v[i];
        sort(all(v));
        reverse(all(v));
        long long sum = 0;
        long long mi;
        for (int i = 0; i < a; i ++) { 
                sum += v[i];
                if (i == a - 1) mi = v[i];
        }
        cout << setprecision(10) << (double)sum / (double)a << endl;
        bool can_add = true;
        for (int i = 0; i < a; i ++) if (v[i] != mi) can_add = false;
        int cnt_A = 0, cnt_B = 0, cnt_all = 0;
        for (int i = 0; i < a; i ++) if (v[i] == mi) cnt_A ++;
        for (int i = 0; i < b; i ++) if (v[i] == mi) cnt_B ++;
        for (int i = 0; i < n; i ++) if (v[i] == mi) cnt_all ++;
        long long ans = 0;
        for (int i = cnt_A; i <= (can_add ? cnt_B : cnt_A); i ++) ans += nCr(cnt_all, i);
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repm(i, m, n) for (int i = (m); i < (int)(n); i++)
#define repr(i, n) for (int i = (n); i > 0; i--)
#define all(vec) vec.begin(), vec.end()
using namespace std;

int main(){
  int n;
  string s;
  cin >> s;
  
  string ans;
  if (s == "Sunny") cout << "Cloudy" << endl;
  if (s == "Cloudy") cout << "Rainy" << endl;
  if (s == "Rainy") cout << "Sunny" << endl;

  //cout << ans << endl;
}

Measured memory_bytes: 256