akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define N 3010

ll inv[N], fac[N], finv[N];

void make()
{
	fac[0] = fac[1] = 1;
	inv[1] = 1;
	finv[1] = finv[0] = 1;
	for(int i = 2; i < N; ++i)
	{
		fac[i] = i * fac[i - 1] % MOD;
		inv[i] = MOD - MOD/i * inv[MOD % i] % MOD;
		finv[i] = inv[i] * finv[i - 1] % MOD;
	}
}

ll C(ll n, ll k)
{
	if(n < k || n < 0) return 0;
	return fac[n] * finv[n - k] % MOD* finv[k] % MOD;
}

ll gcd(ll a, ll b)
{
	if(b == 0)
		return a;
	return gcd(b, a % b);
}
int n, m;
char a[N][N];
double dp[N][N];
double p[N];
double dpf(int i, int j)
{
	if(i == n)
		if(j >= m)
			return 1;
		else
			return 0;

	if(dp[i][j] >= 0)
		return dp[i][j];
	return dp[i][j] = p[i] * dpf(i + 1, j + 1) + (1 - p[i]) * dpf(i + 1, j);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(10);
	cin >> n;
	m = n/2 + 1; //>> m;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; ++i)
	{
		cin >> p[i];
	}
	double ans = dpf(0, 0);
	cout << ans << "\n";
	return 0;
}

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

using namespace std;

const int N = 555;

char a[N][N];
int n, ans, tot;
bool have[N];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", a[i]);
	}
	tot = 0;
	for (int c = 0; c < n; c++) {
		int cnt = 0;
		for (int r = 0; r < n; r++) {
			cnt += a[r][c] == '#';
		}
		tot += (cnt == n);
		have[c] = cnt >= 1;
	}
	ans = -1;
	for (int r = 0; r < n; r++) {
		int black = 0;
		for (int c = 0; c < n; c++) {
			black += a[r][c] == '#';
		}
		if (black == n) {
			int t = n - tot;
			if (ans == -1 || t < ans) ans = t;
		}
	}
	for (int j = 0; j < n; j++) {
		int white = 0;
		for (int i = 0; i < n; i++) {
			if (a[j][i] == '.') white++;
		}
		for (int i = 0; i < n; i++) {
			int extra = 0;
			if (a[i][j] == '.' && !have[i]) continue;
			if (a[i][j] == '.') extra = 1;
			int t = white + n - tot + extra;
			if (ans == -1 || t < ans) {
				ans = t;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 512
import java.io.*;
import java.util.StringTokenizer;


public class Main {


  private void solve(InputReader in, PrintWriter out) {
    int n = in.nextInt();
    int m = in.nextInt();
    out.println(n + m / 2);
  }


  public static void main(String[] args) throws FileNotFoundException {
    new Main().run();
  }

  private void run() throws FileNotFoundException {

    //new FileInputStream(new File("input.txt"))
    //
    try (InputReader in = new InputReader(System.in);
         PrintWriter out = new PrintWriter(System.out)) {
      solve(in, out);
    }
  }


  static class InputReader implements AutoCloseable {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

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

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

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

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

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

    @Override
    public void close() {
    }
  }

}


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

double dis(int A, int B, double S)
{
    double alpha = A * A + B * B - 2 * A * B * cos(S);
    return sqrt(alpha);
}

int main()
{
    int A, B, H, M;
    double S;
    cin >> A >> B >> H >> M;
    S = abs((H + M / 60.0) * 2 * M_PI / 12.0 - M * 2 * M_PI / 60.0);
    cout << fixed << setprecision(10) << dis(A, B, S) << endl;
    return 0;
}


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

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

  if (K == 1)
    cout << 0 << endl;
  else
    cout << N - K << endl;
  return 0;
}

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

int main() {
	int K;
	cin >> K;
	int GCD[K][K] = {};
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			GCD[i][j] = gcd(i + 1, j + 1);
		}
	}

	long long ans = 0;
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			int tmp = GCD[i][j];
			for (int k = 0; k < K; k++) {
				ans += GCD[tmp - 1][k];
			}
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 3748
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
signed main(){
  ll a,b,c;
  cin >> a >> b >> c;
  if(a<b) swap(a,b);
  if(a<c) swap(a,c);
  if(a==7&&b==5&&c==5) cout <<"YES\n";
  else cout <<"NO\n";
}


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

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

    int n;
    cin >> n;
    int max_len = -1;
    int sum_len = 0;

    rep(i, n){
        int l;
        cin >> l;

        max_len = max(max_len, l);
        sum_len += l;
    }

    sum_len -= max_len;

    if(max_len >= sum_len) puts("No");
    else puts("Yes");
}

Measured memory_bytes: 256
require 'pp'

N,M = readline.chomp.split.map(&:to_i)
links = M.times.map {|i| readline.split.map{|s| s.to_i-1 } }

$current = N * (N-1)

$parent = Array.new(N) {|i| i}
$csize = Array.new(N,1)
$inconvs = Array.new(M)

#pp $parent, $csize

def root(i)
  while $parent[i] != i
    i = $parent[i] 
  end
  i
end

links.size.times do |t|
  $inconvs[-t-1] = $current / 2
  i,j = links[-t-1]
  #pp "i,j: #{[i,j]}"
  ri = root(i)
  rj = root(j)
  #pp "ri,rj: #{[ri,rj]}"
  if ri == rj
    next
  end
  if ri < rj
    s = ri
    l = rj
  else
    s = rj
    l = ri
  end
  $parent[l] = s
  $parent[i] = s
  $parent[j] = s
  d_inconv = $csize[s]*(N-$csize[s]) + $csize[l]*(N-$csize[l])
  $csize[s] += $csize[l]
  $csize[l] = -1
  $current += $csize[s]*(N-$csize[s]) - d_inconv
end

puts $inconvs


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

int main(int argc, char *argv[]){
  long long x;
  cin>>x;
  if(x>=1 && x<=6){
    cout<<1<<endl;
    return 0;
  }
  if(x>=7 && x<=11){
    cout<<2<<endl;
    return 0;
  }
  long long sum=0;
  int con=5;
  long long count=0;
  count=(x/11)*2;
  if(x%11==0){
    cout<<count<<endl;
    return 0;
  }
  if(x%11>6){
	cout<<count+2<<endl;
    return 0;
  }
  else if(x%11<=6){
    cout<<count+1<<endl;
  }
}
 


Measured memory_bytes: 256
S = input()
ret = False
while(len(S) > 0):
  if S[-5:] == 'dream':
    if len(S) == 5:
      ret = True
      break
    else:
      S = S[:-5]
  elif S[-7:] == 'dreamer':
    if len(S) == 7:
      ret = True
      break
    else:
      S = S[:-7]
  elif S[-5:] == 'erase':
    if len(S) == 5:
      ret = True
      break
    else:
      S = S[:-5]
  elif S[-6:] == 'eraser':
    if len(S) == 6:
      ret = True
      break
    else:
      S = S[:-6]
  else:
    break
      
if ret:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 133980
import sys

if __name__ == "__main__":
    N, M, K = [int(x) for x in input().split(" ")]
    if M < N:
        N, M = M, N
    for x in range(0, N + 1):
        for y in range(0, M + 1):
            if x * (M - y) + (y * (N - x)) == K:
                print("Yes")
                sys.exit(0)
    print("No")


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


#define ALL(a) 		(a.begin() , a.end())
#define ll 			long long int
#define ff          first
#define ss          second
#define pb          push_back
#define ar 			array
#define mp 			make_pair
#define f(i,a,b)   	for(ll i =a;i<=b;i++)
#define inf 		INT_MAX
#define pll 		pair<ll,ll>
#define mat 		vector<vector<ll>>

const ll INF = 1e18;
void init(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE 
		freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
}
 
bool checkp2(ll n){
	return n && !(n & (n-1));
}

ll numsetbit(ll n){
	ll count = 0;
	for(;n;count++){
		n = n & (n-1);
	}
	return count;
}
 
ll power(ll x , ll n , ll mod){
    x = x % mod;
	ll po = 1;
	while(n){
		if(n & 1){
			po = (po*x) % mod;
		}
		n = n>>1;
		x = ((x % mod) * (x % mod)) % mod;
	}
	return po;
}
 
bool isPrime(ll x){
	if(x < 2)
		return 0;
	for(ll y = 2; y * y <= x; y++){
		if(x % y == 0){
			return 0;
		}
	}
	return true;
}





void solve(){


	ll n,x,t;
	cin>>n>>x>>t;
	ll count = n /x;
	if(n % x != 0){
		count++;
	}
	cout<<count * t<<endl;






}

int main(){
	
	init();
	ll t = 1;
	//cin>>t;
	for(ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Measured memory_bytes: 3648
from sys import exit
import math
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

l,r,d = mi()

cnt=0
while 1:
    if l%d==0:
        cnt+=1
    if l==r:
        print(cnt)
        exit()
    l+=1

Measured memory_bytes: 9112
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;


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

    long long N,T;
    cin >> N >> T;
    long long t[N];
    long long sum=T;
    rep(i,N) {
        cin >> t[i];
    }
    for(int i=1;i<N;i++){
        sum+=min(t[i]-t[i-1],T);
    }
    cout << sum << endl;


}


Measured memory_bytes: 1792
len_arr = int(input())
arr = [int(x) for x in input().split(' ')]

diffs = [arr[i] - arr[i+1] for i in range(0, len_arr-1)]
# print(diffs)

cont = 0
max_len = 0
for d in diffs:
    if d >= 0:
        cont += 1
    else:
        max_len = max(max_len, cont)
        cont = 0
else:
    max_len = max(max_len, cont)

print(max_len)
exit(0)


Measured memory_bytes: 14224
class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


N, K, *A = map(int, open(0).read().split())
st = SegmentTree(300000 + 1, max, 0)

for a in A:
    st.update(a, st.query(max(a - K, 0), min(a + K + 1, 300000 + 1)) + 1)

print(st.query(0, 300000 + 1))


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




int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    int a[n + 1];
    int cur = 1e9;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 2; i <= n; i++){
        if(a[i] == a[i - 1]){
            a[i] = ++cur;
            ans++;
        }
    }
    cout << ans;
}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	int t=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		t^=x;
	} 
	if(t==0) printf("Yes");
	else printf("No");
	return 0;
}


Measured memory_bytes: 128
S = input()
s0, s1 = 1, 0
second = ""
for i in range(1, 4):
  if S[i] == S[0]: s0 += 1
for i in range(1, 4):
  if S[i] != S[0]: 
    second = S[i]
    break
for i in range(1, 4):
  if S[i] == second: s1 += 1
if s0 == 2 and s1 == 2: print("Yes")
else: print("No")

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = l[0], v = l[1], u = l[2];
            var tree = new List<List<int>>();
            for (var i = 0; i < N; i++)
                tree.Add(new List<int>());
            for (var i = 0; i < N-1; i++) {
               var x = Console.ReadLine().Split().Select(int.Parse).ToList();
               x[0]--;
               x[1]--;
               tree[x[0]].Add(x[1]);
               tree[x[1]].Add(x[0]);
            }

            var t = Bfs(tree, v-1);
            var s = Bfs(tree, u-1);
            
            var ans = 0;
            for (var i = 0; i < t.Length; i++) {
            //Console.WriteLine($"{t[i]} {s[i]}");
               if (t[i] < s[i])
                   ans = Math.Max(ans, s[i]-1);
            }
            
            Console.WriteLine(ans);
        }

        static int[] Bfs(List<List<int>> tree, int s) {
            var q = new Queue<int>();
            q.Enqueue(s);
            var ret = new int[tree.Count];
            
            while (q.Count > 0) {
               var  w = q.Dequeue();
               foreach (var d in tree[w]) {
                  if (ret[d] != 0 || d == s) continue;
                  ret[d] = ret[w] + 1;
                  q.Enqueue(d);
               }
            }
            
            return ret;
        }
    }
}


Measured memory_bytes: 30344
#include <bits/stdc++.h>  
 
using namespace std;
 
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define FORr(i, j, k) for(int i = j; i >= k; --i)
#define repr(i, j) FOR(i, j, 0)
#define INF (1 << 30)
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
 
const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};
 
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
 
int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	int l[50];
	rep(i, N) scanf("%d", &l[i]);
	sort(l, l + N);
	int res = 0;
	rep(i, K) res += l[N - 1 - i];
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 256
local n, k = io.read("*n", "*n")
local rem = (n - 2) * (n - 1) // 2 - k
if rem < 0 then print(-1) os.exit() end
print(n - 1 + rem)
for i = 1, n - 1 do
  print(i .. " " .. n)
end
if 0 < rem then
  for i = 1, n - 2 do
    for j = i + 1, n - 1 do
      print(i .. " " .. j)
      rem = rem - 1
      if rem == 0 then os.exit() end
    end
  end
end


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

int main(){
  ll n,ans=0;
  cin >> n;
  
  for(ll a=1;a<n;a++){
    ans += (n-1)/a;
  }
  
  cout << ans << endl;      
  
  return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <limits.h>
using namespace std;
int main(void){
    unsigned long long m[30], msum = 0, m2sum = 0, bsum = 0;
    char a[200010];
    cin >> a;
    
    for (int i = 1; i <= 26; i++) m[i] = 0;
    
    for (int i = 0; a[i] != '\0'; i++) {
        m[a[i] - 'a' + 1]++;
    }
    
    for (int i = 1; i <= 26; i++) {
        if (m[i] > 0) bsum++;
        msum += m[i];
        m2sum += (m[i] * m[i]);
    }
    
  	if (bsum == 1) cout << 1;
    else cout << (msum * msum - m2sum) / 2 + 1;
    return 0;
}



Measured memory_bytes: 384
import java.util.Scanner;


public class Main {
	
	private static int[] cache;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 

		int n = sc.nextInt();

		// 再帰的トップダウン型、履歴管理
		cache = new int[n + 1];
		cache[0] = 1;
		cache[1] = 1;
		int ret = fibonacciNum(n);
		
		System.out.println(ret);
		
         sc.close();
	}
	
	private static int fibonacciNum(int n) {
		if (cache[n] != 0) {
			return cache[n];
		}
		
		cache[n] = fibonacciNum(n - 1) + fibonacciNum(n - 2);
		return cache[n];
	}
}

Measured memory_bytes: 17352
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAX 100005
using namespace std;
//char nc()
//{
//	static char buf[100000],*p1=buf,*p2=buf;
//	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
char nc(){return getchar();}
int read()
{
	int x=0,y=1;
	char c=nc();
	while(!isdigit(c))
	{
		if(c=='-')y=-1;
		c=nc();
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=nc();
	}
	return x*y;
}
int n,m,a[MAX<<1],ANS=0;
bool check(int mid)
{
	for(int i=mid*2+1,j=n*2;i<j;i++,j--)
		if(a[i]+a[j]<m) return false;
	return true;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n*2;i++)
		a[i]=read();
	sort(a+1,a+n*2+1);
	int l=0,r=n,mid,ans=0;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))
			ans=mid,r=mid-1;
		else
			l=mid+1;
	}
	for(int i=1,j=ans*2;i<j;i++,j--)
		ANS=max(ANS,a[i]+a[j]);
	for(int i=ans*2+1,j=n*2;i<j;i++,j--)
		ANS=max(ANS,a[i]+a[j]-m);
	printf("%d",ANS);
	return 0;
}

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

int main() {
    using namespace std;
    unsigned long N, ans{0};
    cin >> N;
    ++N;
    for(unsigned long i = 0, j = 1, p = 1; i < 10; ++i){
        j *= 10;
        j = min(N, j);
        if(~i & 1)ans += j - p;
        p = j;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//Candies

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
template<class T>inline bool chmin(T& a,T b,bool f){
if(f==1){if(a>b){a=b;return true;}return false;}
else if(f==0){if(a<b){a=b;return true;}return false;}return false;}
typedef pair<int,string> p;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

int main (){
    int n;cin>>n;
    vector<int>a(n),b(n);
    rep(i,0,n)cin>>a[i];
    rep(i,0,n)cin>>b[i];
    ll ans=0,c=0;
    rep(i,0,n){
        c=0;
        rep(j,0,i)c+=a[j];
        c+=a[i];
        rep(j,i,n)c+=b[j];
        ans = max(ans,c);
    }
    cout<<ans<<nnn;
    return 0;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N;
  cin>>N;
  ll ans=0;
  for(int i=1;i<N;i++)ans+=i;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>

#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}


int main(void) {


	int N;
	cin >> N;

	cout << (N - 1) / 2 << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)
#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)
#define mem(a,n) memset( a, n, sizeof(a))

typedef long long ll;
const int INF = 1e9;
const ll LLINF = 1e18;

int main() {
    int N, K;
    cin>>N>>K;
    
    vector<char> nums;
    rep(i,N){
        char x; cin>>x;
        nums.push_back(x);
    }
    
    for(int value=N;; value++){
        string tmp = to_string(value);
        bool f=true;
        rep(i,N){
            if(tmp.find(nums[i])!=string::npos){
                f=false; break;
            }
        }
        if(f){
            cout1(value); return 0;
        }
    }
}

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

int k;
deque<pair<int,int> > q;
bool used[100010];

int main() {
	cin>>k;
	
	q.push_back({1,1});
	while(!q.empty()) {
		pair<int,int> x=q.front();q.pop_front();
		if(!x.first) {cout<<x.second;return 0;}
		
		if(!used[x.first]) {
			used[x.first]=1;
			q.push_front({(x.first*10)%k,x.second});
			q.push_back({x.first+1,x.second+1});
		}
	}
	
	return 0;
}


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

namespace ABC085A
{
    class Program
    {
        static void Main(string[] args)
        {
            String s;
            s = Console.ReadLine();

            char[] cs = s.ToCharArray();
            cs[3] = '8';
            Console.WriteLine(cs);
            Console.ReadKey();
        }
    }
}


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

using namespace std;

int main()
{
    string s,t;
    cin>>s>>t;
    int n=s.length();
    int m=t.length();
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
            {
                dp[i][j]=0;
            }
            else if(s[i-1]==t[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    string res;
    int i=n,j=m;
    while(i>0&&j>0)
    {
        if(s[i-1]==t[j-1])
        {
            res+=s[i-1];
            i--;
            j--;
        }
        else
        {
            if(dp[i-1][j]>dp[i][j-1])
            {
                i--;
            }
            else
            {
                j--;
            }
        }
    }
    reverse(res.begin(),res.end());
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 38740
#include<iostream>
#include<stdio.h>
#include<fstream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<map>
#include<iomanip>
#include<cassert>
#include<complex>
#include<functional>
#include<list>
#include<cmath>
#include<stack>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
int n,m,par[100001],r[100001];
ll weight[100001];
void init()
{
	for (int i=0;i<n;i++) par[i]=i;
}
int find(int x)
{
	if (par[x]==x) return x;
	else
	{
		int parent=find(par[x]);
		weight[x]+=weight[par[x]];
		return par[x]=parent;
	}
}
bool same(int x,int y)
{
	return find(x)==find(y);
}
bool unite(int x,int y,ll w)
{
	int xp=find(x),yp=find(y);
	w=w-weight[y]+weight[x];
	if (xp==yp)
	{
		if (weight[yp]-weight[xp]==w) return true;
		else return false;
	}
	if (r[xp]>r[yp]) par[yp]=xp,weight[yp]=w;
	else par[xp]=yp,weight[xp]=-w,r[yp]++;
	return true;
}
int main()
{
	cin>>n>>m;
	init();
	for (int i=0;i<m;i++)
	{
		int l,r,d;
		cin>>l>>r>>d;
		l--; r--;
		if (!unite(l,r,d))
		{
			cout<<"No";
    		return 0;
		}
	}
	cout<<"Yes";
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#define REP(i,n) for(int i = 0; i < (n); i++)
using namespace std;
int imos[2][100005];
int main(){
  string s[2];
  cin >> s[0] >> s[1];
  REP(i,2){
    REP(j, s[i].size()){
      imos[i][j + 1] = s[i][j] == 'A' ? 1 : 2;
    }
    REP(j, s[i].size()){
      imos[i][j + 1] += imos[i][j];
    }
  }
  int Q;
  cin >> Q;
  for(int i = 0; i < Q;i ++){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--;b--;c--;d--;
    if((imos[0][b + 1] - imos[0][a])%3 == (imos[1][d + 1] - imos[1][c])%3){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1664
#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 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<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<<62;
const int INF = 1<<30;
const double PI=acos(-1);
ll a, b, n;
ll func(ll x){
	return(((a*x)/b)-a*(x/b));
}
int main(){
	ll ans=0LL;
	cin >>a>>b>>n;
/*
	for(ll i=1LL;i<=30LL;i++){
		cout<<(a*i/b-a*(i/b))<<endl;
	}
	*/
	ans=func(n);
	if(b-1 <n){
		chmax(ans,func(b-1));
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	int N, A[10000];

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

	int count = N;

	for (int i = 0;i < N;i++) {
		
		int j = 2;

		//cout << endl;
		//cout << A[i] << "??????";
		//cout << count;
		
		while(sqrt(A[i]) >= j) {
			if (A[i] % j == 0) {
				//cout << j;
				count--;
				break;
			}
			j++;
		}
	}
	//cout << endl;
	//cout << endl;
	cout << count << endl;

    return 0;
}

Measured memory_bytes: 3116
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

char a[10005],b[10005];
int flag = 0;
int main()
{
	scanf("%s",a);
	scanf("%s",b);
	int len1 = strlen(a);
	int len2 = strlen(b);
	if(len1 == len2){
		for(int i = 0; i < len1; i++)
		{
			int x = a[i], y = b[i];
			if(x > y){  printf("GREATER\n");
			            flag = 1;
                        break;
			}
		    if(x < y){  printf("LESS\n");
                         flag = 1;
                         break;
			 }
		}
	    if(flag == 0) printf("EQUAL\n");
	}
    else if(len1 > len2) printf("GREATER\n");
	else  printf("LESS\n");
	return 0;
}


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a+b>=10){
    cout << "error" << endl;
  }else{
    cout << a+b << endl;
  }
}

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

int main() {
    long double A; cin >> A;
    //cout << A << endl;
    long double B; cin >> B;
    A *= B;
    //cout << A << endl;
    ll ans = A;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3780
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

ll fac[510000], finv[510000], inv[510000];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < 510000; ++i) {
		fac[i] = fac[i - 1] * i%INF;//i!のmod INF
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}


int main() {
	ll N, K, S; cin >> N >> K >> S;
	ll A[100010];
	if (S != 1e9) {
		for (int i = 0; i < K; ++i) {
			A[i] = S;
		}
		for (int i = K; i < N; ++i) {
			A[i] = S + 1;
		}
	}
	else {
		for (int i = 0; i < K; ++i) {
			A[i] = S;
		}
		for (int i = K; i < N; ++i) {
			A[i] = 1;
		}
	}
	REP(i, N) {
		cout << A[i] << " ";
	}
	cout << endl;
	return 0;
}


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

using namespace std;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)
  
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
  
#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

typedef long double Real;
#define EPS 1e-13
#define EQ(x) (-EPS<x && x<EPS)
typedef complex<Real> P;
Real dot(P a,P b){return real(conj(a)*b);}
Real cross(P a,P b){return imag(conj(a)*b);}

#define MP make_pair<int,int>

int mp[830][252];
bool vstd[830][252];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int dw[255];

int main(){
  dw['.'] = -1;
  dw['>'] = 0;
  dw['<'] = 2;
  dw['v'] = 1;
  dw['^'] = 3;
  while(true){
    int h,w;
    cin>>h>>w;
    if(!(h+w))break;
    REP(i,h)REP(j,w)vstd[i][j] = false;
    REP(i,h){
      string s;
      cin>>s;
      REP(j,w) mp[i][j] = dw[s[j]];
    }
    int x,y;
    x=y=0;
    while(mp[y][x]!=-1){
      if(vstd[y][x]){
        x=y=-1;
        break;
      }
      vstd[y][x] = true;
      int c = mp[y][x];
      x += dx[c];
      y += dy[c];
    }
    if(x==-1){
      cout<<"LOOP"<<endl;
    }else{
      printf("%d %d\n",x,y);
    }
  }
  return 0;
}

Measured memory_bytes: 1360
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int H,W,N;
    cin>>H>>W>>N;
    int a[N];
    int b[H*W];
    int cou=0;
    rep(i,N) {
        cin>>a[i];
        rep(j,a[i]){
            b[cou+j]=i+1;
        }
        cou+=a[i];
    }
    cou=0;
    rep(i,H){
        if(i%2==0){
            rep(j,W){
                cout << b[i*W+j] << " ";
            }
        }else{
            for(int j=W-1;j>=0;j--){
                cout << b[i*W+j] << " ";
            }
        }
        cout << endl;

    }

    




}


Measured memory_bytes: 512
N,M=map(int,input().split())
s=[0]*M
c=[0]*M
a=0
for i in range(M):
	s[i],c[i]=map(int,input().split())
ans=-1
if M==0:
	ans=1*(10**(N-1))
	if ans==1:
		ans=0
	print(ans)
	exit()
if max(s)>N:
	print(ans)
	exit()
for j in range(0,1000):
	value=str(j)
	if len(value)==N:
		for S,C in zip(s,c):
			if int(value[S-1])==C:
				a+=1
		if a==M:
			ans=int(j)
			break
		else:
			a=0
	else:
		continue
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  multiset<int> S;
  int q;
  cin >> q;
  for (int i = 0; i < q; i++){
    int t;
    cin >> t;
    if (t == 0){
      int x;
      cin >> x;
      S.insert(x);
      cout << S.size() << endl;
    }
    if (t == 1){
      int x;
      cin >> x;
      cout << S.count(x) << endl;
    }
    if (t == 2){
      int x;
      cin >> x;
      S.erase(x);
    }
    if (t == 3){
      int L, R;
      cin >> L >> R;
      auto itr = S.lower_bound(L);
      while (*itr <= R && itr != S.end()){
        cout << *itr << endl;
        itr++;
        if (R < *itr){
          break;
        }
      }
    }
  }
}


Measured memory_bytes: 12364
import math
n = int(input())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
table = []
three = 0

Manhattan = 0
Euclid = 0
Chebyshev = 0
for i in range(n):
    Manhattan += abs(X[i] - Y[i])
for i in range(n):
    tmp = abs(X[i] - Y[i])
    Euclid += tmp**2

Euclid_r = math.sqrt(Euclid)
for i in range(n):
    table.append(abs(X[i] - Y[i]))

Chebyshev = max(table)

for i in range(n):
    three += abs(X[i] - Y[i])**3

three_r = math.pow(three,1/3)

print(Manhattan)
print(Euclid_r)
print(three_r)
print(Chebyshev)






Measured memory_bytes: 5696
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 300030
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,s[N];
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		int L=read()-1,R=read();
		int r=1;
		for(int l=1;l<=L;l=r+1){
			r=min(L/(L/l),R/(R/l));
			if(L/l<R/l){
				++s[l],--s[r+1];
			}
		}
		s[L+1]++,s[R+1]--;
	}
	for(int i=1;i<=m;++i){
		s[i]+=s[i-1];
		printf("%d\n",s[i]);
	}
	return 0;
}


Measured memory_bytes: 1280
N = int(input())
S = input()

ans = 0
r,g,b = 0,0,0
for i in range(N):
  if(S[i] == 'R'): r += 1
  elif(S[i] == 'G'): g += 1  
  elif(S[i] == 'B'): b += 1 
  
  # i     j    j+(j-i) : R  G  B  (or)  R  B  G (or) ... である場合 ans -= 1   
  for j in range(i+1,N-1):
     i1,i2,i3 = i,j,j+(j-i)
     if(i3 <= N-1):
       tmp = [S[i1],S[i2],S[i3]]
       tmp.sort()
       tmp = tmp[0]+tmp[1]+tmp[2]
       if(tmp == 'BGR'):
         ans -= 1

ans += r*g*b
print(ans)

Measured memory_bytes: 68480
K=int(input())

l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(l[K-1])


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

typedef long long ll;
typedef unsigned long long ull;

int main() {
    int N, K, x, ans = 0;
    cin >> N >> K;
    rep(i, N) {
        cin >> x;
        ans += min(x, K - x) * 2;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int A,B,K,j=1;
	int num[10000];
	scanf("%d %d %d",&A,&B,&K);
	for(int i=1;i<=10000;i++){
		if((A%i==0) && (B%i==0)){
			num[j] = i;
			j++;
		
	}
}

printf("%d\n",num[j-K]);
	return 0;
}

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

typedef long long ll;
int main(void){
    int x;
    int ans = 0;
    for (int i = 0; i < 5; i++) {
        cin >> x;
        if (x != i+1)
            ans = i+1;
    }
    cout << ans;
    
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define testing 1
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
string cts(char x) {string t(1,x); return t;}
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, T b) { a = max(a, b); }
template <typename T> void chmin(T& a, T b) { a = min(a, b); }
const int MAXN = -1;
#if !testing
#define cerr if(0)cout
#endif
 
int32_t main() 
{
	IAMSPEED
    int s,w; cin >> s >> w;
  	if(w>=s) cout << "unsafe";
  	else cout << "safe";
}

Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

int main() {
    int N;
    long long L;
    cin >> N >> L;
    vector<long long> a(N);
    rep(i, N) cin >> a[i];
    
    long long sum = 0;
    rep(i, N) sum += a[i];
    int left = 0;
    int right = N;
    vector<int> ans;
    while (right - left > 1) {
        if (sum < L) {
            cout << "Impossible\n";
            return 0;
        }
        if (a[left] + a[left + 1] < L) {
            sum -= a[left];
            ans.push_back(left + 1);
            ++left;
        } else {
            sum -= a[right - 1];
            ans.push_back(right - 1);
            --right;
        }
    }
    cout << "Possible\n";
    rep(i, N - 1) cout << ans[i] << "\n";
    return 0;
}


Measured memory_bytes: 2168
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct S{
  int y,x,ry,rx,d,rd;
};

struct SS{
  int y,x,d;
};

int main(){
  for(int W,H;cin>>W>>H,W;){
    char g[16][64];
    int y,x;
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
	cin>>g[i][j];
	if(g[i][j]=='K'){
	  y=i;
	  x=j;
	}
      }
    }
    int dy[]={-1,0,1,0};
    int dx[]={0,1,0,-1};
    int d;
    for(d=0;g[y+dy[d]][x+dx[d]]=='#';d++);
    vector<S> v;
    vector<SS> vs{{y,x,d}};
    for(int i=0;i<4;i++){
      v.push_back({y,x,y,x,d,i});
    }
    static bool p[16][64][16][64][4][4];
    bool ps[16][64][4]={};
    fill(p[0][0][0][0][4],p[16][0][0][0][4],false);
    bool reach=false,ret=false;
    while(!vs.empty()){
      auto cs=vs.back();
      reach|=g[cs.y][cs.x]=='M';
      vs.pop_back();
      if(ps[cs.y][cs.x][cs.d]++)continue;
      int ny,nx;
      for(ny=cs.y,nx=cs.x;g[ny+dy[cs.d]][nx+dx[cs.d]]!='#';ny+=dy[cs.d],nx+=dx[cs.d]);
      for(int i=1;i<=3;i+=2){
	vs.push_back({ny,nx,(cs.d+i)%4});
      }
    }

    while(!v.empty()){
      S cs=v.back();
      v.pop_back();
      if(p[cs.y][cs.x][cs.ry][cs.rx][cs.d][cs.rd]++)continue;
      int ny,nx;
      for(ny=cs.y,nx=cs.x;g[ny+dy[cs.d]][nx+dx[cs.d]]!='#';ny+=dy[cs.d],nx+=dx[cs.d]);

      for(int rny=cs.ry,rnx=cs.rx;g[rny][rnx]!='#';rny+=dy[cs.rd],rnx+=dx[cs.rd]){
	ret|=g[ny][nx]=='M'&&g[rny][rnx]=='M'&&g[rny-dy[cs.rd]][rnx-dx[cs.rd]]!='#';
	for(int i=1;i<=3;i+=2){
	  if(g[rny+dy[(cs.rd+i+2)%4]][rnx+dx[(cs.rd+i+2)%4]]=='#'){
	    v.push_back({ny,nx,rny,rnx,(cs.d+i)%4,(cs.rd+i)%4});
	  }
	}
      }
    }
    cout<<(!reach?"He cannot bring tea to his master.":
	   !ret?"He cannot return to the kitchen.":
	   "He can accomplish his mission.")<<endl;
  }
}

Measured memory_bytes: 18244
def SelectionSort(A):
    count_swap = 0
    for i in range(len(A)):
        mini = i
        for j in range(i,len(A)):
            if A[j] < A[mini]:
                mini = j
        if i != mini:
            count_swap += 1
        A[i],A[mini] = A[mini],A[i]
    #print(count_swap)
    return A,count_swap #変更を保存 # 複数の戻り値を返せる
    

try:
    N = int(input())
    array = list(map(int,input().split()))
except ValueError:
    print('数値以外が入力されました')

result = SelectionSort(array)
print(*result[0])
#print(*array)

print(result[1])


Measured memory_bytes: 5608
#!/usr/bin/env python3
#ABC72 C

from itertools import accumulate

n = int(input())
a = list(map(int,input().split()))

x = [0]*(10**5+3)

for i in a:
    x[i] += 1
    x[i+3] -= 1

x = list(accumulate(x))
print(max(x))


Measured memory_bytes: 14256
S = str(input())
K = int(input())

flag = []

N = len(S)
for i in range(N):
    if i == N - 1:
        flag.append(0)
        #if S[i] == S[0]:
            #flag.append(1)
        #else:
            #flag.append(0)
    else:
        if S[i]==S[i+1]:
            flag.append(1)
        else:
            flag.append(0)

flag_2 = []
for i in range(N):
    flag_2.append(0)

for i in range(N):
    if flag[i] == 1:
        k = 0
        count = 0
        while((i == 0 or flag[i-1] == 0) and (i + k) < N and flag[i + k] == 1):
            k += 1
            count += 1
        flag_2[i] = count

#print("flag",flag)
#print("flag2", flag_2)

ans = 0
cara = set()
for i in range(N):
    cara.add(S[i])
if len(cara) == 1:
    ans = N*K//2
else:

    if(S[0] != S[N-1]):
        for i in range(N-1):
            ans += (flag_2[i] + 1)//2

        ans = ans * K

    else:
        last = 0
        for i in range(N):
            if(S[0] != S[N - 1 - i]):
                last = N - i
                break
        #print("last",last)
        temp = flag_2[0] + (N - last) + 1
        ans += temp//2 * (K - 1)
        for i in range(1, last):
            ans += (flag_2[i] + 1)//2 * K
        ans += (flag_2[0] + 1)//2
        ans += (flag_2[last] + 1)//2

print(ans)




Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );
		String[] strlist = str.split(" ");
		long a = Long.parseLong(strlist[0]);
		long b = Long.parseLong(strlist[1]);
		long c = Long.parseLong(strlist[2]);
		long[] abc = {a, b, c};
		Arrays.sort(abc);

		if(a%2==0 || b%2==0 || c%2==0){
			System.out.println(0);
		}else{
			Long long1 = abc[0];
			Long long2 = abc[1];
			BigInteger big1 = new BigInteger(long1.toString());
			BigInteger big2 = new BigInteger(long2.toString());
			System.out.println(big1.multiply(big2));
		}
	}
}


Measured memory_bytes: 22228
#include <bits/stdc++.h>
typedef long long ll;

#define pll pair<ll,ll>
#define ff first
#define snd second
#define pb push_back
#define vll vector<ll>
#define vpll vector<pll>
#define endl "\n"
#define MOD 1000000007
using namespace std;

ll const N = 1e5+1;


void solve()
{
   double n;
   cin>>n;
    
   ll k = ceil(n/1000);
   k*=1000;
   k-=n;
   cout<<k;
}
 
int main() {
            ios_base::sync_with_stdio(false);
            cin.tie(NULL);
	    int t=1;
	    //cin>>t;
	    while(t--)
	    {
	            solve();
	    }
	    return 0;
}

Measured memory_bytes: 3824
#include <iostream>

using namespace std;

using ll = long long;

int main() {
    ll A, B;
    cin >> A >> B;

    if (A == B) {
        cout << 1 << endl;
        return 0;
    }

    // A, Bで異なる一番上の桁を求める
    int h;
    for (h = 63; (A >> h) == (B >> h); --h) {};

    // それより上は全部無視できる
    A &= (1LL << h) - 1;
    B &= (1LL << h) - 1;

    // [A, 2^h - 1]は全部作れる
    ll ans = (1LL << h) - A;

    // Bの1が立っている最上位の桁を求める
    int d;
    for (d = h; d >= 0 && (B >> d) == 0; --d) {};

    // 最上位以降全部1にしたやつにしても問題ない
    // [2^h, 2^h + 2^(d+1) - 1]まで全部作れるため
    B = (1LL << (d + 1)) - 1;

    // [A, 2^h - 1]と[0, B]の交差判定
    if (A > B) {
        ans += ans + B + 1;
    } else {
        ans += (1LL << h);
    }

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

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

int main() {
  int a, b;
  cin >> a >> b;

  int cnt = 0;
  for (int i = 1; i <= a; i++) {
    for (int j = 1; j <= 31; j++) {
      if (i > a) break;
      if (i >= a && b < j) break;
      if (i == j) cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rep2(i,n) for(int i=1; i<=(n); ++i)
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(),(x).end())
#define Sort2(x) sort((x).begin(),(x).end(), greater<int>())
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main()
{
    ll n; cin >> n;
    vector<ll> a(n); rep(i, n) cin >> a[i];
    ll m = 1000; ll s = 0;

    rep(i,n-1){
        if(a[i] < a[i+1]){
            s += m / a[i];
            m = m % a[i];
        }else if(a[i] > a[i+1]){
            m += s * a[i];
            s = 0;
        }
        //cout << m << " " << s << endl;
    }
    m += s * a[n-1];
    cout << m << endl;
}

/*
g++ d.cpp
./a.out

oj d https://atcoder.jp/contests/abc172/tasks/abc172_c
g++ c.cpp
oj t
*/


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

#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define FOR(i, a, b) for (int i = a; i <= (b); i++)
#define ROF(i, a, b) for (int i = a; i >= (b); i--)

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<ll>; using vvll = vector<vll>;

int main() {
    int n, x, t; cin >> n >> x >> t;
    cout << ((n - 1) / x + 1) * t << endl;
}

Measured memory_bytes: 3580