akhauriyash/Code-Regression huggingface dataset:
# abc109_c


def mcd(x, y):
    if x > y:
        big = x
        small = y
    else:
        big = y
        small = x
    while True:
        rest = big % small
        if rest == 0:
            return small
        else:
            big = small
            small = rest


def solve(seq):
    satisfy = []  # find distances to satisfy
    for i in range(len(seq) - 1):
        satisfy.append(abs(seq[i] - seq[i + 1]))
    # print(satisfy)

    if len(satisfy) == 1:
        return satisfy[0]

    mcds = []
    for i in range(len(satisfy) - 1):
        mcds.append(mcd(satisfy[i], satisfy[i + 1]))
    # print(sol)

    return min(mcds)


if __name__ == "__main__":
    firstline_input = list(map(int, input("").split(" ")))
    seq = list(map(int, input("").split(" ")))
    seq.insert(0, firstline_input[1])
    print(solve(seq))


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

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

  string s;
  cin >> s;
  int ans = 0;
  int anstmp = 0;
  for(int i=0;i<s.length();i++) {
    if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
      anstmp++;
      ans = max(ans, anstmp);
    } else {
      anstmp = 0;
    }
  }

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


Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var n = cin.ReadLong;
            var m = cin.ReadLong;
            if (n < m / 2)
                WriteLine(n + (m - 2 * n) / 4);
            else
                WriteLine(Min(n, m / 2));
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}


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

using namespace std;


int main()
{
    long long sum1 = 0;

    int n;
    cin >> n;

    vector<long long> v(n);

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

    long long sum2 = 0;
    long long minn = 3e14;

    for (int i = 0 ; i < n ; i++){
        sum2+= v[i];

        long long dif = abs(sum2 - (sum1-sum2));
        minn = min(minn, dif);
    }

    cout << minn <<endl;

    return 0;
}


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

int main () {
  int n, m, ans = 0;
  cin >> n >> m;
  
  if (n != 0 || n != 1) {
    ans += n*(n-1)/2;
  }
  if (m != 0 || m != 1) {
    ans += m*(m-1)/2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3608
a,b,c,d=map(int,input().split())
if a<=c:
  if b<=c:
    print(0)
  else:
    if b<=d:
      print(b-c)
    else:
      print(d-c)
else:
  if d<=a:
    print(0)
  else:
    if d<=b:
      print(d-a)
    else:
      print(b-a)

Measured memory_bytes: 38384
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> t(N);
    for (int i=0; i<N; i++) cin >> t[i];

    int ans = 0;

    for (int i=1; i<N; i++) ans += t[i]-t[i-1] < T ? t[i]-t[i-1] : T;
    ans += T;

    cout << ans << endl;

    return 0;
}

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


using namespace std;

int main()
{
int a[5],b[5],Y=0,min=124,memo;
int i;
cin>>a[0];
cin>>a[1];
cin>>a[2];
cin>>a[3];
cin>>a[4];

for(i=0;i<5;i++){
	b[i] = a[i]%10;
	if((b[i]<min)&&(b[i]!=0)){
		min=b[i];
		memo = i;
	}
}
double hako;
for(i=0;i<5;i++){
	if(i!=memo){
		hako = a[i]*0.1;
		hako = (int)(hako + 0.9);
		
		hako = 10*hako;
		
		Y = Y+(int)(hako);
	}
}
Y = Y + a[memo];
cout<<Y<<endl;

}	

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

int stoi(string str) {
	int ret;
	ret = int(str[1])-48;
 	return ret;
}

int main() {
	int n, min, flg;
	string tmp;
	cin >> n;
	string *org = new string[n];
	string *a = new string[n];
	
	for (int i = 0; i < n; i++)
		cin >> org[i];
	for (int i = 0; i < n; i++)
		a[i] = org[i];
	for (int i = 0; i < n -1; i++)
		for(int j = n - 1; j > i; j--)
			if (stoi(a[j]) < stoi(a[j - 1])) {
				tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
			}
	flg = 1;
	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++)
			for (int k = 0; k < n - 1; k++)
				for (int l = k + 1; l < n; l++)
					if ((stoi(org[i]) == stoi(org[j])) && (org[i] == a[l]) && (org[j] == a[k]))
						flg *= 0;

	for (int i = 0; i < n - 1; i++)
		cout << a[i] << ' ';
		cout << a[n - 1] << endl;
	if (flg)
		cout << "Stable" << endl;
	else
		cout << "Not stable" << endl;
	for (int i = 0; i < n; i++)
		a[i] = org[i];
	for (int i = 0; i < n -1; i++) {
		min = i;
		for (int j = i + 1; j < n ; j++) {
			if (stoi(a[j]) < stoi(a[min]))
				min = j;
		}
		if (min != i) {
			tmp = a[i];
			a[i] = a[min];
			a[min] = tmp;
		}
	}
	flg = 1;
	for (int i = 0; i < n -1; i++)
		for (int j = i + 1; j < n ; j++)
			for (int k = 0; k < n - 1; k++)
				for (int l = k + 1; l < n; l++)
					if ((stoi(org[i]) == stoi(org[j])) && (org[i] == a[l]) && (org[j] == a[k]))
						flg *= 0;
	for (int i = 0; i < n - 1; i++)
		cout << (a[i]) << ' ';
		cout << (a[n - 1]) << endl;
	if (flg)
		cout << "Stable" << endl;
	else
		cout << "Not stable" << endl;
	return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(void)
{
  vector<int> a(6);
  for(int &x: a) cin >> x;
  REP(i, 5) {
    int count = 0;
    for(int x: a) if(x==i) ++count;
    if(count == 3) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 256
object Main extends App {
  
  val sc = new java.util.Scanner(System.in)
  val prices = Map(
    0.25d -> sc.nextLong(),
    0.5d -> sc.nextLong(),
    1d -> sc.nextLong(),
    2d -> sc.nextLong()
  )
  val n = sc.nextLong()
  val cosp = prices.map{ case (s, p) => (s, (p / s).toLong)}.toList.sortBy(_._2).map(_._1)
  val ans = cosp.foldLeft((n, 0L))((rc, key) => {
    key match {
      case 2.0d if rc._1 >= 2 => ((rc._1 % key).toLong, rc._2 + ((rc._1 / key).toLong * prices(key)).toLong)
      case 2.0d if rc._1 < 2 => rc
      case _ => (0L, rc._2 + (rc._1 / key).toLong * prices(key))
    }
  })
  println(ans._2)
}


Measured memory_bytes: 55488
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
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 (a>b) { a=b; return true; } return false; }

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<pair<int, int>> cb(m);
    rep(i,m){
        int b, c;
        cin >> b >> c;
        cb[i] = make_pair(c, b);
    }

    sort(all(a));
    sort(rall(cb));

    int start = 0;
    int sum = 0;
    rep(i,m){
        if (sum > n) break;
        int c = cb[i].first;
        int b = cb[i].second;
        int cnt = 0;
        for(int j = start; j < n; j++){
            if (a[j] >= c || cnt == b) break;
            a[j] = c;
            start = j + 1;
            cnt++;
            sum++;
        }
    }

    ll ans = 0;
    rep(i,n){
        ans += a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 4236
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<math.h>
#include<utility>
#include<climits>
#include <algorithm> 
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>


using namespace std; 


int main(){
    int n,k;
    cin>>n>>k;
    vector<int> ar(n,0);
    for(int i=0;i<n;i++)
        cin>>ar[i];
    vector<int> dp(k+1,0);

    for(int i=0;i<=k;i++){
        for(int j=0;j<n;j++){
            if(ar[j]<=i && !dp[i-ar[j]])
                dp[i]=1;
        }
    }
    if(dp[k])
        cout<<"First"<<endl;
    else
        cout<<"Second"<<endl;

}





Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

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

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
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 ll INF = 1LL <<60;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始


int main(){
  string s[3];
  int n[3];
  int cnt[3];
  for(int i = 0; i < 3; i++){
    cin>>s[i];
    n[i] = s[i].length();
    cnt[i] = 0;
  }
  int tmp = 0;
  while(1){
    int tmp2 = s[tmp][cnt[tmp]] - 'a';
    cnt[tmp]++;
    if(cnt[tmp]==n[tmp]+1) {break;}
    tmp = tmp2;
  }
  cout<<(char)(tmp+'A')<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define maxvex 200001
int cnt[maxvex];
using namespace std;
int main()
{
	int n;
	int m;
	int i;
	int num=0;
	cin >> n;
	for (i = 0; i < n - 1;i++)
	{
		cin >> m;
		cnt[m]++;
	}
	for (i = 0; i < n; i++)
	{
		cout << cnt[i + 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 4412
import sys
input=sys.stdin.readline

N=int(input())
L=[[] for _ in range(N)]
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        x-=1
        L[i].append((x,y))
ans=0
for i in range(2**N):
    H=[]
    for j in range(N):
        if (i>>j)&1 ==1:
            H.append(j)
    S=[-1]*N
    for j in H:
        for x,y in L[j]:
            if S[x]==-1 or S[x]==y:S[x]=y
            else:break
        else:continue
        break
    else:
        for k,x in enumerate(S):
            if (x==0 and k in H)or (x==1 and k not in H):break
        else:
            ans=max(ans,len(H))
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
 
int d[5] = { 0, 1, 0, -1, 0 };
int dist[100][100][4][11];
 
int main() {
    int n, m, a;
    cin >> n >> m >> a;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    int si, sj, gi, gj;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (s[i][j] == 'S') {
                si = i;
                sj = j;
            }
            if (s[i][j] == 'G') {
                gi = i;
                gj = j;
            }
            for (int k = 0; k < 4; ++k)
                for (int l = 0; l <= a; ++l)
                    dist[i][j][k][l] = 80;
        }
    }
    deque<int> qi, qj, qd, qm;
    dist[si][sj][1][0] = 0;
    qi.push_back(si);
    qj.push_back(sj);
    qd.push_back(1);
    qm.push_back(0);
    while (!qi.empty()) {
        int pi = qi.front();
        int pj = qj.front();
        int pd = qd.front();
        int pm = qm.front();
        qi.pop_front();
        qj.pop_front();
        qd.pop_front();
        qm.pop_front();
        if (pi == si && pj == sj && pd == 3) continue;
        int dis = dist[pi][pj][pd][pm];
        {
            int ti = pi + d[pd], tj = pj + d[pd + 1];
            if (ti >= 0 && ti < n && tj >= 0 && tj < m && s[ti][tj] != '#' && dist[ti][tj][pd][pm] > dis) {
                dist[ti][tj][pd][pm] = dis;
                qi.push_front(ti);
                qj.push_front(tj);
                qd.push_front(pd);
                qm.push_front(pm);
            }
        }
        if (pi == si && pj == sj || pi == gi && pj == gj) continue;
 
        {
            int td = pd ^ 1;
            int ti = pi + d[td], tj = pj + d[td + 1];
            if (ti >= 0 && ti < n && tj >= 0 && tj < m && s[ti][tj] != '#' && pm < a && dist[ti][tj][td][pm + 1] > dis) {
                dist[ti][tj][td][pm + 1] = dis;
                qi.push_front(ti);
                qj.push_front(tj);
                qd.push_front(td);
                qm.push_front(pm + 1);
            }
        }
        {
            int td = pd ^ 3;
            int ti = pi + d[td], tj = pj + d[td + 1];
            if (ti >= 0 && ti < n && tj >= 0 && tj < m && s[ti][tj] != '#' && dis < a && dist[ti][tj][td][pm] > dis + 1) {
                dist[ti][tj][td][pm] = dis + 1;
                qi.push_front(ti);
                qj.push_front(tj);
                qd.push_front(td);
                qm.push_front(pm);
            }
        }
    }
    int ans = 50;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j <= a; ++j)
            ans = min(ans, dist[gi][gj][i][j] + j);

    cout << (ans < 50 ? ans : -1) << "\n";
    return 0;
}

Measured memory_bytes: 4824
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << ((a < b & b < c) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  vector<int>mochi(N);
  
  for(int i = 0;i < N;i++) {
    cin >> mochi.at(i);
  }
  
  sort(mochi.begin(),mochi.end());
  reverse(mochi.begin(),mochi.end());
  
  int dan = 1;
  
  for(int i = 0;i < N-1;i++) {
    
    if(mochi.at(i+1) < mochi.at(i)) {
      dan++;
    }
    
    else if(mochi.at(i+1) == mochi.at(i)) {
      continue; }
  }
  
  cout << dan << endl;
}
      

Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int Q;
	cin >> Q;

	priority_queue<int> lh;
	priority_queue<int, vector<int>, greater<int>> uh;

	int lh_cnt = 0, uh_cnt = 0;
	lint lh_sum = 0, uh_sum = 0;
	lint B = 0;

	for (int i = 0; i < Q; i++) {

		int q;
		cin >> q;

		if (q == 1) {

			int a, b;
			cin >> a >> b;

			B += b;

			if (lh.empty() || lh.top() > a) {

				if (lh_cnt == uh_cnt) {
					
					lh.emplace(a);
					lh_sum += a;

					lh_cnt++;

				}
				else { 

					assert(lh_cnt > uh_cnt);

					lh.emplace(a);
					lh_sum += a;

					int tmp = lh.top();
					lh.pop();
					uh.emplace(tmp);
					lh_sum -= tmp;
					uh_sum += tmp;

					uh_cnt++;

				}

			}

			else {
			
				if (lh_cnt == uh_cnt) {

					uh.emplace(a);
					uh_sum += a;

					int tmp = uh.top();
					uh.pop();
					lh.emplace(tmp);
					uh_sum -= tmp;
					lh_sum += tmp;

					lh_cnt++;

				}
				else {

					assert(lh_cnt > uh_cnt);

					uh.emplace(a);
					uh_sum += a;

					uh_cnt++;

				}

			}


		}
		else {
			cout << lh.top() << " " << uh_sum - lh_sum + B + (lh_cnt != uh_cnt) * lh.top() << "\n";
		}

	}

	return 0;
}

Measured memory_bytes: 3452
#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d",&a)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%ld\n",a)
#define pll(a) printf("%lld\n",a) 
#define sc(a) scanf("%c",&a)a
#define pc(a) printf("%c",a)
#define ll long long
#define mod 1000000007

#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF INT_MAX
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define VI vector<int>
#define VL vector<ll>
#define PI pair<int,int>
#define PL pair<ll,ll>
long double PIE=acos(-1);
//////////////////////////////////////////////////////////////
const ll N=1e5+5;
ll Ans=1;
bool done[1000009];
vector < ll > primes;

void FindPrime(ll N)
{
    done[1] = 1;
    for(int i=2;i<=N;i++)
	{
        if(done[i]) continue;
        for(int j=i*2;j<=N;j+=i)
		{
            done[j] = 1;
        }
        primes.push_back(i);
    }
}

ll solve(ll Num)
{
    for(int i=0;i<primes.size();i++)
	{
    	int p=primes[i];
        if(p*p*p > Num) break;
        ll Count = 1;
        while(Num%p == 0)
		{
            Num /= p,Count++;
        }
        Ans *= Count;
    }
    ll sq = (ll)sqrt(Num);
    if(!done[Num]) 
	Ans *= 2;
    else if(sq*sq == Num && !done[sq]) 
	Ans *= 3;
    else if(Num != 1) 
	Ans *= 4;
    return Ans;
}


ll fact[N], invfact[N];



ll pow(ll a, ll b, ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

ll modinv(ll k)
{
	return pow(k, mod-2, mod);
}


ll nCr(ll x, ll y)
{
	if(y>x)
		return 0;
	ll num=fact[x];
	num*=invfact[y];
	num%=mod;
	num*=invfact[x-y];
	num%=mod;
	return num;
}

void initinv()
{
	fact[0]=1;
	fr(i,1,N)
	{
		fact[i]=(i*fact[i-1])%mod;
	}
	invfact[N]=modinv(fact[N]);
	for(int i=N-1;i>=1;i--)
	{
		invfact[i]=((i+1)*invfact[i+1])%mod;
	}
}
///////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
ll dp[1005][1005];
char mat[1005][1005];
int main()
{
	int h,w;
	cin>>h>>w;
	fr(i,1,h)
	{
		fr(j,1,w)
		{
			cin>>mat[i][j];
		}
	}
	for(int i=1;i<=w;i++)
	{
		if(mat[1][i]=='.')
		dp[1][i]=1;
		else
		break;
	}
	for(int i=1;i<=h;i++)
	{
		if(mat[i][1]=='.')
		dp[i][1]=1;
		else
		break;
	}
	for(int i=2;i<=h;i++)
	{
		for(int j=2;j<=w;j++)
		{
			if(mat[i][j]=='.')
			{
				dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
			}
		}
	}
	cout<<dp[h][w];
    return 0;
}





Measured memory_bytes: 12300
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;

int main(void){
 int N,M,a;
 map<int,int> B; 
 long long int ans=0;

 cin>>N>>M;
 vector<long long int>A(N+1,0);
 for(int i=1; i<N+1;i++){
  cin>>a;
  A[i]=(A[i-1]+a)%M;
 }
 for(int i=0; i<N+1; i++){
  ans+=B[A[i]];
  B[A[i]]++;
 }
 std::cout<<ans<<std::endl;
}


Measured memory_bytes: 3968
from bisect import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
D = [0]*N
E = [0]*(N+1)
for i, b in enumerate(B) :
    D[i] = N - bisect(C, b)
for i, d in enumerate(D[::-1]) :
    E[N-i-1] = E[N-i] + d
c = 0
for a in A:
    c += E[bisect(B, a)]
print(c)

Measured memory_bytes: 24720
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline void setin(string s) {
	freopen(s.c_str(), "r", stdin);
}

inline void setout(string s) {
	freopen(s.c_str(), "w", stdout);
}

template <typename T> inline T range(T l, T r) {
	return uniform_int_distribution <T>(l, r)(rng);
}

template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

struct pt {
	int x, y, r;
};

const ld inf = 2e18;
const ld eps = 1e-15;
const int mod = 1e9 + 7;
const int N = 1e3 + 15;
int n, m;
pt a[N];

inline ll sq(int x) {
	return 1ll * x * x;
}

ld d[N], g[N][N];

inline void add_edge(int u, int v) {
	ld dist = sqrt(sq(a[u].x - a[v].x) + sq(a[u].y - a[v].y));
	dist = max((ld)0, dist - a[u].r - a[v].r);
	g[u][v] = dist;
	// cout << u << ' ' << v << ' ' << g[u][v] << endl;
}

bool used[N];

inline bool ls(ld a, ld b) {
	return a - b > eps;
}

main() {
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	// setin("input.txt");
	cin >> a[1].x >> a[1].y >> a[2].x >> a[2].y;
	a[1].r = a[2].r = 0;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i+2].x >> a[i+2].y >> a[i+2].r;
	n += 2;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			add_edge(i, j);
	fill(d, d + N, inf);
	d[1] = 0;
	while(1) {
		int v = -1;
		for(int i = 1; i <= n; ++i)
			if(!used[i] && (v == -1 || d[i] < d[v]))
				v = i;
		if(v == -1)
			break;
		used[v] = true;
		for(int to = 1; to <= n; ++to)
			if(ls(d[to], d[v] + g[v][to]))
				d[to] = d[v] + g[v][to];
	}
	// for(int i = 1; i <= n; ++i)
	// 	cout << d[i] << ' ';
	// cout << endl;
	// assert(used[2]);
	cout.precision(30);
	cout << d[2] << endl;
	return 0;
}

Measured memory_bytes: 16256
#define _USE_MATH_DEFINES 
#include<iomanip> 
#include<cmath>  
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
typedef long long ll;
#define repi(i,a,b) for(ll i = (ll)(a) ; i < (ll)(b) ; i++)
#define repd(i,a,b) for(ll i = (ll)(a) ; i > (ll)(b) ; i--)
#define rd(x) cin >> x
#define wr(x)  cout << x
#define wrln(x) cout << x << endl
#define wl() cout << endl
const ll MAX_10p5 = 100010;
const ll MAX_10p9 = 1000000010;
const ll MAX_10p18 = 1000000000000000010;
const ll MOD = 1000000007;
const ll m4x[4] = { 1,0,-1,0 };
const ll m4y[4] = { 0,1,0,-1 };
const ll m8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const ll m8y[8] = { 0,1,1,1,0,-1,-1,-1 };
const ll m9x[9] = { 1,1,0,-1,-1,-1,0,1,0 };
const ll m9y[9] = { 0,1,1,1,0,-1,-1,-1,0 };

struct edge {
	ll from, to, cost;
	bool operator<(const edge& right) const {
		return cost < right.cost;
	}
};
struct point {
	ll x, y;
	bool operator<(const point& right) const {
		return x == right.x ? y < right.y : x < right.x;
	}
};

///////////////////////////////////////////////////////////////////////////////////////

int main() {
	while (1) {
		ll N, M, ans = 0;
		cin >> N >> M;
		ll hsum[1550], wsum[1550];
		hsum[0] = wsum[0] = 0;
		unordered_map<ll, ll> um;
		if (N == 0 && M == 0) break;
		repi(i, 0, N) {
			ll h;
			rd(h);
			hsum[i + 1] = h + hsum[i];
		}

		repi(i, 0, M) {
			ll w;
			rd(w);
			wsum[i + 1] = w + wsum[i];
		}

		repi(i, 0, N) {
			repi(j, i + 1, N + 1) {
				ll d = hsum[j] - hsum[i];
				if (um.find(d) == um.end()) um[d] = 1;
				else um[d]++;
			}
		}

		repi(i, 0, M) {
			repi(j, i + 1, M + 1) {
				ll d = wsum[j] - wsum[i];
				if (um.find(d) != um.end()) {
					ans += um[d];
				}
			}
		}
		wrln(ans);
	}
	return 0;
}



Measured memory_bytes: 16832
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N;
  cin>>N;
  
  vector<int> L(N);
  for(int i=0;i<N;i++){
    cin>>L[i];
  }
  
  int 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(L[i]!=L[j]&&L[j]!=L[k]&&L[k]!=L[i]){
          if(L[i]+L[j]>L[k]&&L[j]+L[k]>L[i]&&L[k]+L[i]>L[j]){
            ans++;
          }
        }
      }
    }
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 3640
#include <iostream>

void solve() {
    int s, w;
    std::cin >> s >> w;
    std::cout << (s <= w ? "unsafe" : "safe") << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3664
#include<iostream>
#include<stdio.h>
int main(){
	int i;
	char s[20];
	scanf("%s",s);
	for(i=0;s[i]!='\0';i++);
	if(i>0) i--;
	for(;i>=0;i--) std::cout << s[i];
	std::cout<<std::endl;

	
    return 0;
}

Measured memory_bytes: 1144
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int N;
    cin >> N;
    vector<int> V(N), C(N);
    for(int i=0; i<N; i++){
        cin >> V[i];
    }
    for(int i=0; i<N; i++){
        cin >> C[i];
    }
    int ans=0;
    for(int i=0, p; i<N; i++){
        p = V[i] - C[i];
        if(p > 0) ans += p;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
io = STDIN
d,G=io.gets.split.map(&:to_i)
ar=d.times.map do |i|
  q,c = io.gets.split.map(&:to_i)
  [100*(i+1),q,100*(i+1)*q+c] #点数、問題数、合計
end
$ans=1000
def dfs(questions,highest,amt,num)
  if amt>=G
    $ans=[$ans,num].min
  else
    if questions==[]
      x,q,tot=highest
      if G-amt<=x*(q-1)
        $ans=[$ans,num+((G-amt).to_f/x).ceil].min
      end
      return
    end
    x,q,tot=questions[0]
    dfs(questions[1..-1],highest,amt+tot,num+q)
    dfs(questions[1..-1],questions[0],amt,num)
  end
end
dfs(ar,[],0,0)
p $ans


Measured memory_bytes: 3836
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

#define rep(i,x,y) for (int i=x;i<=y;i++)
#define dep(i,y,x) for (int i=y;i>=x;i--)
#define sz(x) (int)(x.size())

using namespace std;

typedef long long LL; 
typedef unsigned long long uLL;

const int maxn=2000+7;

int n,k;
LL a[maxn],cur[maxn],K,x,ans;

int main()
{
 scanf("%d%lld",&n,&K);
 rep(i,1,n) scanf("%lld",&a[i]);

 ans=0;
 rep(i,1,n) ans+=a[i],cur[i]=a[i];

 rep(i,1,n)
 {
  rep(j,1,n)
  {
   k=j-i;
   if (k<=0) k+=n;
   cur[j]=min(cur[j],a[k]);
  }

  x=i*K;
  rep(j,1,n) x+=cur[j];

  // printf("%lld\n",x);
  ans=min(ans,x);
 }
 
 printf("%lld\n",ans);

 // system("pause");
 return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		String s = sc.next(), t = sc.next();
		int a = sc.nextInt(), b = sc.nextInt();
		String u = sc.next();
		if(u.equals(s))a--;
		else b--;

		pw.print(a+" "+b);
		pw.close();
	}

	static class FastScanner {
		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

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

	    public String nextLine() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                return reader.readLine();
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }

	        return tokenizer.nextToken("\n");
	    }

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

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

	    public double nextDouble() {
	         return Double.parseDouble(next());
	     }

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }
	}

}

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

typedef long long ll;
const ll MOD = 1e9+7;
const int N = 1e5;

ll dmod(ll x){
	if(x < 0){
		return MOD - ((-x) % MOD);
	}
	return x%MOD;
}

ll fe(ll x, ll p){
	if(p==0) return 1ll;
	if(p==1) return x;
	ll ret = fe(x,p/2);
	ret = dmod(ret*ret);
	if(p&1) ret = dmod(ret*x);
	return ret;
}

int n,k;
ll li[N+5];
ll fakto[N+5];

ll nCr(ll n, ll r){
	ll inv = fe(dmod(fakto[r] * fakto[n-r]),MOD-2);
	return dmod(fakto[n] * inv);
}

int main(){
	fakto[0] = 1ll;
	for(int i=1;i<=N;i++){
//		cout << fakto[i-1] << endl;
		fakto[i] = dmod(fakto[i-1] * (ll)(i));
	}
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&li[i]);
	sort(li+1,li+n+1);
	ll ans = 0ll;
	for(int i=1;i<=n-k+1;i++){ //minimum
		ans = dmod(ans - dmod(nCr(n-i,k-1) * li[i]) + MOD);
	}
	for(int i=n;i>=k;i--){
		ans = dmod(ans + dmod(nCr(i-1,k-1) * li[i]));
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <bitset>
#include <cassert>

using namespace std;

int a[100009];
const int INF = 2000000000;

int main() {
    int n, t;
    cin >> n >> t;
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    int cur_min = INF;
    int max_d = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] - cur_min > max_d) {
            max_d = a[i] - cur_min;
        }
        cur_min = min(cur_min, a[i]);
    }
    int cnt = 0;
    cur_min = INF;
    for (int i = 0; i < n; ++i) {
        if (a[i] - cur_min == max_d) {
            ++cnt;
        }
        cur_min = min(cur_min, a[i]);
    }
    cout << cnt << endl;
}

Measured memory_bytes: 640
(function(input) {
    var p = input.split('\n');
    var n = Number(p.shift());
    var x = p.shift().split(' ', n).map(Number);
    var y = p.shift().split(' ', n).map(Number);
    console.log(distance(x, y, 1));
    console.log(distance(x, y, 2));
    console.log(distance(x, y, 3));
    console.log(distance(x, y, Infinity));
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

function distance(x, y, p) {
    if (p === Infinity) {
        var m = 0;
        for (var i = 0; i < x.length; i++) {
            var d = Math.abs(x[i] - y[i]);
            if (d > m) {
                m = d;
            }
        }
        return m;
    }
    var s = 0;
    for (var i = 0; i < x.length; i++) {
        s += Math.pow(Math.abs(x[i] - y[i]), p);
    }
    return Math.pow(s, 1 / p);
}

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

int main(){
    int n, ans=1, k=0, l=0;
    cin >> n;
    for(int i=2 ; i<=n ; i+=2){
        int j=i;
        k=0;
        while(j%2==0){
            j/=2;
            k++;
        }
        if(k>l){
            ans=i;
            l=k;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	int N;
	scanf("%d",&N);
	int h[N],i;
	for(i=0;i < N;i++){
		scanf("%d",&h[i]);
	}
	int j=0,k=1;
	if(N == 1){
		printf("%d",N);
	}else{
		for(i = 1;i < N;i++){
			if(h[j] <= h[i]){
				j = i;
				k++;
			}
		}
		printf("%d",k);
	}
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> Pair;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll INFL = 1e18;


int main(){
    int n,q;
    cin >> n >> q;
    vector<vector<int>> to(n);
    vector<int> scores(n);
    for(int i=0; i<n-1; i++){
        int a,b; cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    for(int i=0; i<q; i++){
        int p,x; cin >> p >> x;
        --p;
        scores[p] += x;
    }
    vector<bool> isused(n,false);
    isused[0] = true;
    queue<int> que;
    que.emplace(0);
    isused[0] = true;
    while(!que.empty()){
        int node = que.front();
        que.pop();
        for(int i=0; i<int(to[node].size()); i++){
            int next = to[node][i];
            if(isused[next]) continue;
            isused[next] = true;
            scores[next] += scores[node];
            que.emplace(next);
        }
    }
    for(int i=0; i<n; i++){
        printf("%d%c",scores[i],i==n-1?'\n':' ');
    }
    return 0;
}  

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

int main()
{
   char a;
   cin >> a;
   char ans;
   switch(a){
     case 'A':
     ans='T';
     break;
     case 'T':
     ans='A';
     break;
     case 'G':
     ans='C';
     break;
     case 'C':
     ans='G';
     break;
   }
 cout << ans << endl;
}



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

int main() {
  
  int64_t A, B; cin >> A >> B;
  
  for (int64_t i = 1; i <= B; i++) {
    if ((A * i) % B == 0) {
      cout << A * i << endl;
      break;
    }
  }
  
}

Measured memory_bytes: 256
INF=10**18
n,m=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
k=sum(v)
dp=[INF]*(k+1)
dp[0]=0
for i in range(n):
  for j in range(k,-1,-1):
    if j>=v[i] and dp[j-v[i]]!=INF:dp[j]=min(dp[j],dp[j-v[i]]+w[i])
for i,x in enumerate(dp):
  if x<=m:ans=i
print(ans)

Measured memory_bytes: 71664
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while(true){
            int a=in.nextInt();
        char ch=in.next().charAt(0);
        int b=in.nextInt();
        if(ch=='+'){
            System.out.println((a+b));
        }
        else if(ch=='-'){
            System.out.println((a-b));
        }
        else if(ch=='*'){
            System.out.println((a*b));
        }
        else if(ch=='/'){
            System.out.println((a/b));
        }
        else{
            break;
        }
        
        }
        
    }
}


Measured memory_bytes: 26272
// Problem : C - Peaks
// Contest : AtCoder - AtCoder Beginner Contest 166
// URL : https://atcoder.jp/contests/abc166/tasks/abc166_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//look at my code
//my code is amazing
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define mod 1000000007 //998244353
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f(i,n) for(ll i=0;i<n;i++)
#define nl "\n"
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define cout1(a) cout<<a<<nl
#define cout2(a,b) cout<<a<<" "<<b<<nl
#define cout3(a,b,c) cout<<a<<" "<<b<<" "<<c<<nl
#define cout4(a,b,c,d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<nl
#define vcout(v,i) cout<<v[i].fi<<" "<<v[i].se<<nl
#define x first
#define y second
#define vc vector
#define pb push_back
#define ar array
#define all(a) (a).begin(), (a).end()
#define ms(v,n,x) fill(v,v+n,x);
#define init(c,a) memset(c,a,sizeof(c))
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define sll set<ll>
#define vll vector<ll>
#define vpll vector<pll>
#define maxi(a,b,c) max(a,max(b,c))
#define maxii(a,b,c,d) max(max(a,b),max(c,d))
#define mini(a,b,c) min(a,min(b,c))
#define md(a,b)  ((a%mod)*(b%mod)+mod)%mod 
#define inf 9e12
#define cases ll T;cin>>T;while(T--)
#define BLOCK 500
//const double PI = 3.141592653589793238460;
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
const int N=1e5+5;
vll g[N];
ll a[N],vis[N],ans;
map<ll,ll>cnt;

// void dfs(ll i,ll m=-inf){
// 	
	// vis[i]=1;
	// ll f=0;
	// if(m>=a[i])
	// f=1;
// 	
	// for(auto j:v[i]){
		// if(!vis[j]){
			// dfs(j,a[i]);
// 			
		// }
// 		
	// }
// 	
// }
// 
int32_t main()
{
    
	fast
	
	ll n,m;
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
	cin>>a[i];
	
	f(i,m){
		ll a,b;
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
		
	}
	
	for(ll i=1;i<=n;i++)
	{
		ll f=0;
		for(auto j:g[i]){
			if(a[j]>=a[i]){
			
			f=1;
			break;
			}
		}
		if(!f)
		ans++;
		
	}
	
	
	cout<<ans;

	



    

	return 0;
    
}

Measured memory_bytes: 10276
#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)//rep(i,回数){処理}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    ll x, k, d; cin >> x >> k >> d;
    ll ans;
    x = abs(x);//原点からーや＋であっても同じ
    //往復せずに終わる場合
    if (x / d > k) {
        ans = x - d * k;
    }
    //往復する場合
    else {
        ll e = x / d;//往復するまでの回数
        k = k - e;//往復できる回数
        x = x - e * d;//今の座標は？
        if (k % 2 == 1) { x = abs(x - d); }
        ans = x;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3604
#include<stdio.h>
int main(){
  int n,yy,y,m,d,d3,ans,i;
  d3=(20+19)*15+5;
  scanf("%d",&n);
  while(n--){
    scanf("%d %d %d",&y,&m,&d);
    yy=1000-y;
    ans=yy/3*d3;
    if(yy%3)ans+=yy%3*(39*5)+5;
    if(y%3){
      for(i=1;i<m;i++)ans-=19+i%2;
      ans-=d-1;
    }
    else ans-=20*(m-1)+d-1;
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n; 
  cin >> n;

  int s1,s2,s3,s4;
  
  s1 = n / 1000;
  s2 = (n / 100) % 10;
  s3 = (n / 10) % 10;
  s4 = n % 10;
  
  bool ret = false;
  
  if (s1 == s2 && s2 == s3) {
    ret = true;
  } else if (s2 == s3 && s3 == s4) {
    ret = true;
  }

  if (ret) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


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

if n == 1:
    print(0)
    exit()

import math
def div(m):
    d = {}
    temp = int(math.sqrt(m))+1
    for i in range(2, temp):
        while m%i== 0:
            m //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[m] = 1
    else:
        if m in d:
            d[m] += 1
        elif m != 1:
            d[m] =1
    return d

d = div(n)
#print(d)
ans = 0
for k, v in d.items():
    temp = 0
    i = 1
    while True:
        temp += i
        if temp > v:
            break
        i += 1
    #print(k, v, temp, i)
    ans += (i-1)
print(ans)


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

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  for(int i = 0; 1; i++) {
    for(int j = 0; j < n; j++)
    if(v[j] % 2 == 1) {
      cout << i;
      return 0;
    }
    for(int j = 0; j < n; j++) {
      v[j] = v[j] / 2;
    }
  }
}
    

Measured memory_bytes: 256
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

class UnionFind {
private:
	unsigned size_; 
	std::vector<unsigned> par, rank;
public:
	UnionFind() : size_(0), par(std::vector<unsigned>()), rank(std::vector<unsigned>()) {};
	UnionFind(unsigned size__) : size_(size__) {
		par.resize(size_); rank.resize(size_);
		for (unsigned i = 0; i < size_; i++) par[i] = i, rank[i] = 0;
	}
	unsigned size() { return size_; }
	//unsigned root(unsigned x) { return par[x] == x ? x : par[x] = root(par[x]); }
	unsigned root(unsigned x)
	{
		while(par[x] != x)
		{
			par[x] = par[par[x]];
			x = par[x];
		}
		return x;
	}
	bool same(unsigned x, unsigned y) { return root(x) == root(y); }
	void unite(unsigned x, unsigned y) {
		x = root(x), y = root(y);
		if (x == y) return;
		if (rank[x] < rank[y]) par[x] = y;
		else if (rank[x] == rank[y]) par[y] = x, rank[x]++;
		else par[y] = x;
	}
	bool operator==(const UnionFind &u) { return par == u.par; }
	bool operator!=(const UnionFind &u) { return par != u.par; }
};

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	string s;
	
	cin >> s;

	int l = 0, r = s.size() - 1;
	int count = 0;

	while(l<=r)
	{
		if (s[l] == s[r])
		{
			l++;
			r--;
		}
		else if (s[l] == 'x')
		{
			l++;
			count++;
		}
		else if (s[r] == 'x')
		{
			r--;
			count++;
		}
		else
		{
			break;
		}
	}

	if (l > r)
	{
		cout << count << endl;
	} 
	else
	{
		cout << -1 << endl;
	}

	
	return 0;
}


Measured memory_bytes: 592
#include<iostream>
#include<vector>
#include <cmath>
#include <map>

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

using namespace std;


int main() {
	int k, n;
	cin >> k >> n;
	vector<int> a(n);
	int max = 0;
	rep(i, n) {
		cin >> a[i];
	}
	max = k - a[n - 1] + a[0];
	rep(i, n-1) {
		if (a[i + 1] - a[i] > max) {
			max = a[i + 1] - a[i];
		}
	}

	cout << k - max << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;
const int NMAX=20;
int v[NMAX]={400,600,800,1000,1200,1400,1600,1800},f[NMAX]={599,799,999,1199,1399,1599,1799,1999};

int main()
{
    long long x,i,q=0;
    cin>>x;
    for(i=7;i>=0;i--){
        q++;
        if(v[i]<=x&&x<=f[i]){
            cout<<q;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 3628
from sys import stdin
from heapq import heappush,heappop

while(True):
    c,n,m,s,d = map(int, stdin.readline().split())
    if not c: break
    ma = [[] for _ in range(n)]
    s -= 1
    d -= 1
    for _ in range(m):
        a,b,f = map(int, stdin.readline().split())
        a -= 1
        b -= 1
        ma[a].append([f,b])
        ma[b].append([f,a])
    cost = [[10**10]*(c+1) for _ in range(n)]
    cost[s][c] = 0
    que = [[ cost[s][c], s, c ]]
    while que:
        co, pl, ti = heappop(que)
        for fee, town in ma[pl]:
            if cost[town][ti] > co+fee:
                cost[town][ti] = co+fee
                heappush(que,[cost[town][ti],town,ti])
            if ti and cost[town][ti-1] > co+fee//2:
                cost[town][ti-1] = co+fee//2
                heappush(que,[cost[town][ti-1],town,ti-1])
    print(min(cost[d]))


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

int main(){
	int n, m;
	while( scanf("%d %d", &n, &m) , n || m ){
		// g[prev][now] := 成長度
		double g[101][101];
		
		for(int y=0 ; y < n ; y++ ){
			for(int x=0 ; x < n ; x++ ){
				scanf("%lf", &g[y][x] );
			}
		}
		
		// dp[i][prev] := 直前の肥料 prev で i 回の肥料を与えた時の苗木
		double dp[101][101] = {0};
		for(int i=0 ; i < n ; i++ ){
			dp[1][i] = 1.0; 
		}
		
		for(int i=1 ; i < m ; i++ ){
			for(int prev=0 ; prev < n ; prev++ ){
				for(int now=0 ; now < n ; now++ ){
					dp[i+1][now] = max( dp[i+1][now] , dp[i][prev] * g[prev][now] );
				}
			}
		}
		double ans = 0.0;
		for(int i=0 ; i < n ; i++ ){
			ans = max( ans , dp[m][i] );
		}
		printf("%.2f\n", ans);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,p=100000000;
  cin>>n;
  for(int i=1;i<n;i++){
    int a,b,c,d,e,v,w,x,y,z,s=0;
    a=i/10000;
    b=i/1000-10*a;
    c=i/100-100*a-10*b;
    d=i/10-1000*a-100*b-10*c;
    e=i-10000*a-1000*b-100*c-10*d;
    v=(n-i)/10000;
    w=(n-i)/1000-10*v;
    x=(n-i)/100-100*v-10*w;
    y=(n-i)/10-1000*v-100*w-10*x;
    z=(n-i)-10000*v-1000*w-100*x-10*y;
    s=a+b+c+d+e+v+w+x+y+z;
    if(s<=p){
      p=s;
    }
  }
  cout<<p<<endl;
}
      
  
  

Measured memory_bytes: 256
def bubbleSort(A, N):
    flg = 1
    i = 0
    cnt = 0
    while flg:
        flg = 0
        for j in range(N-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                flg = 1
                cnt += 1
        i += 1
    return cnt

n = int(input())
a = [int(x) for x in input().split(' ')]

c = bubbleSort(a, n)

print(" ".join(map(str, a)))
print(c)



Measured memory_bytes: 5604
#include <iostream>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

using namespace std;

signed main() {
  IOS;
  int cnt1=0, cnt2=0, i;
  string S;
  cin >> S;
  for (i = 0; i < S.length(); i++) {
    if ((S[i]-'0') == (i%2)) cnt1++;
    else cnt2++;
  }
  cout << min(cnt1,cnt2) << endl;
  return 0;
}


Measured memory_bytes: 512
#include<cstdio>
const int M=1e9+7,N=80002;
int n,k,f[102][N],i,j,las,l[N],r[N],cnt,num[N],t,ans;
int min(int x,int y){return x<y?x:y;}
int main(){
	scanf("%d%d",&n,&k);
	for (i=1;i<=n;i=j+1) j=n/(n/i),l[++cnt]=i,r[cnt]=j,num[cnt]=n/i,f[k][cnt]=num[cnt];
	for (t=k-1;t;t--)
		for (las=0,i=cnt,j=1;i;i--){
			f[t][i]=(f[t][i+1]-las+M)%M;
			for (;j<=cnt && l[j]<=num[i];j++) (f[t][i]+=las=1ll*f[t+1][j]*(min(num[i],r[j])-l[j]+1)%M)%=M;
			j--;
		}
	printf("%d",f[1][1]);
}

Measured memory_bytes: 32256