akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

n,m = readInts()
s = readChar()
t = readChar()

d = defaultdict(str)

l = n*m//math.gcd(n,m)
j = 0
for i in range(1,(n-1)*(l//n)+1+1,l//n):
  d[i]=s[j]
  j+=1
j = 0
for i in range(1,(m-1)*(l//m)+1+1,l//m):
  if not (d[i]=="" or d[i]==t[j]):
    #おつかれサンバ
    print(-1)
    exit()
  j+=1
print(l)

Measured memory_bytes: 19872
a, b, n = map(int, input().split())


def function(x, a=a, b=b):
    return int(a * x / b) - a * int(x / b)
    

ans = function(0)
for i in range(b):
    if i * b - 1 > n:
        ans = max(ans, function(n))
        break
    ans = max(ans, function(i * b - 1))

print(ans)

Measured memory_bytes: 61840
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
using namespace std;
int main(){
   int n, v[30], c[30];
   cin >> n;
   for(int i = 0; i < n; i++) cin >> v[i];
   for(int i = 0; i < n; i++) cin >> c[i];
   int a[30] = {0};
   for(int i = 0; i < n; i++) a[i] = v[i]-c[i];
   
   int ans = 0;
   for(int i = 0; i < n; i++){
       if(a[i] > 0) ans += a[i];
   }
   cout << ans << endl;
}

Measured memory_bytes: 256
import sys

def solve():
    input  = sys.stdin.readline
    N = int(input())
    array = [[int(a) for a in input().split()] for _ in range(N)]
    count = 0
    for i in reversed(range(N)):
        a, b = array[i]
        if (a + count) % b == 0: continue
        else: count += b - ((a + count) % b)
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 21108
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007


    
int main()
{
    
 ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll N,i,j,k,W;
    cin>>N>>W;
    ll w[N],v[N];
    for(i=0;i<N;i++)
    {
        cin>>w[i]>>v[i];
    }
    ll dp[W+1][N+1];
    for(i=0;i<=W;i++)
    {
        for(j=0;j<=N;j++)
        {
            if(i==0||j==0)
            dp[i][j]=0;
            else if(w[j-1]<=i)
            {
                dp[i][j]=max(v[j-1]+dp[i-w[j-1]][j-1],dp[i][j-1]);
            }
            else
            {
                dp[i][j]=dp[i][j-1];
            }
        }
    }
    cout<<dp[W][N]<<endl;
    return 0;
   
}

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

int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int ans = 1001001001;
    int ac, bc, cc;
    for (int ab_cnt = 0; ab_cnt <= max(x, y)*2; ab_cnt+=2) {
        int sum_price = ab_cnt * c + max((x - ab_cnt/2), 0) * a + max((y - ab_cnt/2), 0) * b;
        ans = min(sum_price, ans);
    }
    cout << ans << endl;
}

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

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int> ;
using vl = vector<ll>;

ll dp[1000010][2][2];

int main(){
    rep(i,1000010){
        rep(j,2){
            rep(k,2){
                dp[i][j][k] = 0;
            }
        }
    }
    dp[1][0][0] = 8;
    dp[1][1][0] = 1;
    dp[1][0][1] = 1;

    ll mod = 1e9+7;
    ll n;
    cin >> n;
    reps(i,1,1000010){
        dp[i+1][1][1] = (dp[i][1][1] * 10 ) % mod;
        dp[i+1][1][1] = (dp[i+1][1][1] + dp[i][1][0]) % mod;
        dp[i+1][1][1] = (dp[i+1][1][1] + dp[i][0][1]) % mod;

        dp[i+1][1][0] = (dp[i][1][0] * 9)%mod;
        dp[i+1][1][0] = (dp[i+1][1][0] +dp[i][0][0])%mod;

        dp[i+1][0][1] = (dp[i][0][1] * 9)%mod;
        dp[i+1][0][1] = (dp[i+1][0][1] + dp[i][0][0]) % mod;

        dp[i+1][0][0] = (dp[i][0][0] * 8) % mod;
    }
    
    cout << dp[n][1][1] << endl;
    
    return 0;
}


Measured memory_bytes: 34836
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
#define MAX 200
#define MAX_T 60
typedef pair<int,int> P;
 
int T[MAX],D,dp[MAX][MAX];
vector<P> vec[MAX_T+1];
 
int solve(int d,P prev){
    if(d == D) return 0;
    if(dp[d][prev.second] >= 0) return dp[d][prev.second];
    int res = 0;
    for(int i = 0 ; i < (int)vec[T[d]].size() ; i++){
	int diff = abs(vec[T[d]][i].first-prev.first);
	res = max(res,solve(d+1,vec[T[d]][i])+diff);
    }
    return dp[d][prev.second] = res; 
}
 
int main(){
    int N,A,B,C;
    memset(dp,-1,sizeof(dp));
 
    scanf("%d%d",&D,&N);
    for(int i = 0 ; i < D ; i++){
	scanf("%d",&T[i]);
    }
    for(int i = 0 ; i < N ; i++){
	scanf("%d%d%d",&A,&B,&C);
	for(int j = A ; j <= B ; j++){
	    vec[j].push_back(P(C,i));
	}
    }
    int ans = 0;
    for(int i = 0 ; i < (int)vec[T[0]].size() ; i++){
	ans = max(ans,solve(1,vec[T[0]][i]));
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 2916
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int H, W;
char c[50][50];
int dist[50][50];

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

int main(void){
	cin >> H >> W;
	int res = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			dist[i][j] = INF;
			cin >> c[i][j];
			if(c[i][j] == '.') res++;
		}
	}

	queue<P> que;
	que.push(P(0, 0));
	dist[0][0] = 0;

	while(not que.empty()){
		P p = que.front();
		que.pop();
		int y = p.first, x = p.second;
		if(y == H-1 and x == W-1) break;
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i], nx = x + dx[i];
			if(ny < 0 or H <= ny or nx < 0 or W <= nx or c[ny][nx] == '#' or dist[ny][nx] < INF) continue;
			dist[ny][nx] = dist[y][x] + 1;
			que.push(P(ny, nx));
		}
	}

	cout << (dist[H-1][W-1] == INF ? -1 : res - dist[H-1][W-1] - 1)  << '\n';

	return 0;
}

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

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

public class Solver
{
	public void Solve()
	{
		WriteLine(GetLong() >= 30 ? "Yes" : "No");
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

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

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 27568
// -----------------------------------
// Author     : MatsuTaku
// Country    : Japan
// Created    : 04/26/20 20:17:32
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  ll n,m,s; cin>>n>>m>>s;
  struct Train {
    ll s, c, d;
    Train(ll s,ll c,ll d):s(s),c(c),d(d){}
    bool operator>(const Train& x) const {return d>x.d;}
  };
  vector<Train> graph[n];
  for (int i = 0; i < m; i++) {
    ll u,v,a,b; cin>>u>>v>>a>>b; u--; v--;
    graph[u].emplace_back(v,a,b);
    graph[v].emplace_back(u,a,b);
  }
  for (int i = 0; i < n; i++) {
    int c,d; cin>>c>>d;
    graph[i].emplace_back(i,-c,d);
  }
  constexpr ll MAX = 250;
  constexpr ll INF = 1e18;
  vector<array<ll, MAX+1>> dp(n);
  for (auto& arr:dp) arr.fill(INF);
  dp[0][min(s,MAX)] = 0;
  priority_queue<Train, vector<Train>, greater<>> qs;
  qs.emplace(0,s,0);
  while (not qs.empty()) {
    auto [s,c,d] = qs.top(); qs.pop();
    if (d > dp[s][min(c,MAX)]) continue;
    for (auto t:graph[s]) {
      if (c-t.c<0) continue;
      if (d+t.d >= dp[t.s][min(c-t.c,MAX)]) continue;
      dp[t.s][min(c-t.c,MAX)] = d+t.d;
      qs.emplace(t.s, c-t.c, d+t.d);
    }
  }
  for (int i = 1; i < n; i++) {
    cout << *min_element(dp[i].begin(), dp[i].end()) << endl;
  }

  return 0;
}


Measured memory_bytes: 3880
import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.next());
        List<Integer> a = new ArrayList<>();
        
        for(int i=0; i<n; i++){
            a.add(Integer.parseInt(sc.next()));
        }
        
        int q = Integer.parseInt(sc.next());
        int com,b,e,min,max;
        for(int i=0; i<q; i++){
            com = Integer.parseInt(sc.next());
            b = Integer.parseInt(sc.next());
            e = Integer.parseInt(sc.next());
            min = a.get(b);
            max = a.get(b);
            
            for(int j=b; j<e; j++){
                if(com == 0) min = Math.min(min,a.get(j));
                else max = Math.max(max,a.get(j));
            }
            if(com == 0) System.out.println(min);
            else System.out.println(max);
        }
    }

}



Measured memory_bytes: 38280
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

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

    ll k, j;
    cin >> k;
    ll i, n, a;
    n = 1 << k;
    vector<ll> v;
    multiset<ll> s;
    for (i = 0; i < n; i++) {
        cin >> a;
        s.insert(-1 * a);
    }
    v.push_back(*s.begin());
    s.erase(s.begin());
    for (i = 0; i < k; i++) {
        vector<ll> temp;
        for (j = 0; j < v.size(); j++) {
            auto it = s.upper_bound(v[j]);
            if (it == s.end()) {
                cout << "No" << endl;
                return 0;
            }
            temp.push_back(*it);
            s.erase(it);
        }
        for (j = 0; j < temp.size(); j++) v.push_back(temp[j]);
        sort(v.begin(), v.end());
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 15560
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize, k: i64,
        wd: [(i64, i64); n],
    }
    let mut pass = 1 << 61;
    let mut fail = 0;
    while pass - fail > 1 {
        let mid = (pass + fail) / 2;
        let mut count = 0;
        for &(w, d) in &wd {
            if mid >= w {
                count += 1 + (mid - w) / d;
            }
        }
        if count >= k {
            pass = mid;
        } else {
            fail = mid;
        }
    }
    puts!("{}\n", pass);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 10620
#include <stdio.h>

int search(int A[], int n, int key){
    int i = 0;
    A[n] = key;
    while(A[i] != key) i++;
    return i !=n;
}

int main(){
    int i, n, A[10000+1], q, key, sum = 0;
    
    scanf("%d", &n);
    for(i = 0; i < n; i++) scanf("%d", &A[i]);
    
    scanf("%d", &q);
    for(i = 0; i < q; i++){
        scanf("%d", &key);
        if(search(A, n, key)) sum++;
    }
    printf("%d\n", sum);
    
    return 0;
}


Measured memory_bytes: 2048
S = input()
alf = 'abcdefghijklmnopqrstuvwxyz'

s = set()
a = set()

for i in range(len(S)):
  s.add(S[i])
for i in range(len(alf)):
  a.add(alf[i])

str = ''
hoge = a ^ s
for h in hoge:
  str += h
  
str=sorted(str)
if str:
  print(str[0])
else:
  print('None')

Measured memory_bytes: 8932
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rept(i,s,n) for (int i = (s); i < (n); ++i)

#include <iostream>
#include <cmath>
#include <bitset>
#include <algorithm>
using namespace std;

int main() {

  string s;
  cin >> s;
    
    bool ok = true;
    
    if(s.at(0)!='A'){
        ok = false;
    }
    
    int cCount = 0;
    int cIdx = -1;
    int i;
    for(i=2; i<=s.length()-2; ++i){
        if(s.at(i)=='C'){
            cCount++;
            cIdx = i;
        }
    }
    if(cCount!=1){
        ok = false;
    }
    
    for(i=1;i<s.length();++i){
        if(i!=cIdx){
            if(s.at(i)<97 || s.at(i) >122){
                ok = false;
            }
        }
    }
    
    
    if(ok)
        cout << "AC" << endl;
    else
        cout << "WA" << endl;
    
    
  
  return 0;
}


Measured memory_bytes: 256
s = input().strip()
C = {chr(i):[] for i in range(97,123)}
for j in range(len(s)):
    C[s[j]].append(j)
flag = 0
for i in range(97,123):
    a = chr(i)
    n = len(C[a])
    if n>1:
        for j in range(1,n):
            if C[a][j]-C[a][j-1]<=2:
                flag = 1
                x = C[a][j-1]
                y = C[a][j]
                break
    if flag==1:
        break
if flag==0:
    print(-1,-1)
else:
    print(x+1,y+1)

Measured memory_bytes: 43376
#include<stdio.h>
int main(void){
int a[100000] = {};
int n,i,s,m,j;
scanf ("%d",&s);
a[0] = s;
n = 0;
for (i = 0;i < 1000;i++)
{
    if (a[i]%2 != 0)
    {
        a[i+1] = (3*a[i])+1;
    }
    else
    {
        a[i+1] = a[i]/2;
    }
}
for (i = 0;i < 1000;i++)
{
    for (j = i+1;j < 1000;j++)
    {
        if (a[i] == a[j])
        break;
    }
if (a[i] == a[j])
break;
}
printf ("%d",j+1);
    return 0;
}

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

int main(){
    int n, m;
    bool ans = false;
    cin >> n >> m;
    vector<bool> aa(n);
    vector<bool> nn(n);
    for(int i = 0 ; i < m ; i++){
        int a, b;
        cin >> a >> b;
        if(a == 1){
            aa[b-1] = true;
        }
        if(b == n){
            nn[a-1] = true;
        }
    }
    for(int i = 0 ; i < n ; i++){
        if(aa[i] && nn[i]){
            ans = true;
            break;
        }
    }
    if(ans){
        cout << "POSSIBLE" << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl
#define dd(x) cout<<#x<<"="<<x<<" "
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp(u,v) make_pair(u,v)
#define sz(a) (int)a.size()
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
#define all(a) a.begin(),a.end()
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;

const ll mod = 1000000007;
const int N = 81;
const int M = 2e6+6;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;

bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }
bool ls(const db &a, const db &b) { return a + eps < b; }
bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }
ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); };
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//inv[1]=1;
//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ll n, x, d;
int main() {
	while(~scanf("%lld%lld%lld",&n, &x, &d)) {
		if(!d) {
			if(!x) printf("1\n");
			else printf("%lld\n",n+1ll);
		} else {
			map<int, ll> _map;
			ll ret = 0;
			if(d < 0) x = -x, d = -d;
			ll mn = 0, mx = 0;
			vector< pair<ll,pll> > cur;
			rep(k, 1, n + 1) {
				mn += k - 1;
				mx += n - k;
				ll kx = k * x;
				ll yushu = kx % d;
				ll be = kx / d;
				ll l = be + mn;
				ll r = be + mx;
				cur.pb({yushu,{l,r}});
			}
			cur.pb({0,{0,0}});
			sort(all(cur));
			rep(i, 0, sz(cur)) {
				ll yushu = cur[i].fi;
				ll l = cur[i].se.fi, r = cur[i].se.se;
				int t;
				if(!_map.count(yushu)) {
					ret += (r - l + 1);
					_map[yushu] = r + 1;
				} else {
					ret += max(0ll, r - max(_map[yushu], l) + 1);
					_map[yushu] = max(_map[yushu], r + 1);
				}
			}
			printf("%lld\n", ret);
		}
	}
    return 0;
}


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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int i=0; i<n; i++)
#define FOR1(i, n) for(int i=1; i<=n; i++)
#define FORI(i, n) for(int i=n-1; i>=0; i--)
template<class T, class U> void umin(T& x, const U& y){ x = min(x, (T)y);}
template<class T, class U> void umax(T& x, const U& y){ x = max(x, (T)y);}
template<class T, class U> void init(vector<T> &v, U x, size_t n) { v=vector<T>(n, x); }
template<class T, class U> void init(vector<T> &v, U x, size_t n, size_t m...) { v=vector<T>(n); for(auto& a : v) init(a, x, m);}

pii tf(ll x){
    pii ret = {-9, -9};
    while(x%2==0){
        x/=2;
        ret.first++;
    }
    while(x%5==0){
        x/=5;
        ret.second++;
    }
    return ret;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    int T = 1;
//    cin >> T;
    FOR1(tt, T){
        int n;
        cin >> n;
        vector<double> a(n);
        FOR(i, n) cin >> a[i];
        sort(a.begin(), a.end());

        map<pii, int> H;
        int m2 = 0, m5 = 0;
        FOR(i, n){
           ll num = round(a[i] * 1e9);
           auto key = tf(num);
           umax(m2, key.first);
           umax(m5, key.second);
           H[key]++;
        }

        ll sol = 0;
        for(auto it : H){
            int x2 = it.first.first;
            int x5 = it.first.second;
            ll others = 0;
            for(int y2 = -x2; y2 <= m2; y2++){
                for(int y5 = -x5; y5 <= m5; y5++) if (H.count({y2, y5})){
                    others +=  H[{y2, y5}] * (x2 != y2 || x5 != y5);
                }
            }
//            cout << it.first.first << " " << it.first.second << " " << it.second << " " << others << endl;
            sol += it.second * others;

            if (x2 >=0 && x5 >= 0)
                sol += it.second * (it.second-1LL);
        }
        sol /= 2;
        cout << sol << endl;

//        FOR(i, n){
//            for(int j=i+1; j<n; j++){
//                auto qi = tf(a[i] * 1e9);
//                auto qj = tf(a[j] * 1e9);
//                cout << a[i] * a[j] << " " << qi.first << " " << qi.second << " "
//                << qj.first << " " << qj.second << endl;
//            }
//        }
    }



    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}



Measured memory_bytes: 4780
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[]) {
  string s, t;
  cin >> s;
  reverse(s.begin(),s.end());
  vector<string> tset = {"dream", "dreamer", "erase", "eraser"};
  for (size_t i = 0; i < tset.size(); i++) reverse(tset[i].begin(), tset[i].end());
  bool tf = true;
  while (s.size()>0 and tf) {
    bool check = false;
    for (size_t i = 0; i < tset.size(); i++) {
      if (tset[i]==s.substr(0, tset[i].size())) {
        check=true;
        s.erase(s.begin(), s.begin()+tset[i].size());
        break;
      }
    }
    if (!check) tf = false;
  }
  if (tf) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int n;
    cin >> n;
    vector<pair<ll, int>> ab(n);
    vector<ll> a(n), b(n);
    rep(i, n) {
        cin >> a[i] >> b[i];
        ab[i].first = a[i]+b[i];;
        ab[i].second = i;
    }
    sort(ab.rbegin(), ab.rend());
    ll ans = 0;
    rep(i, n) {
        if (i%2==0) ans += a[ab[i].second];
        else ans -= b[ab[i].second];
    }
    cout << ans << endl;

}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int lcm(int a, int b)
{
    return a / std::__gcd(a, b) * b;
}

int main()
{
    int N, M;
    std::cin >> N >> M;
    
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }
    
    int res = 0;
    int max = INT_MIN, min = INT_MAX;
    for (int i = 0, j = 0; i < lcm(N, M); i++, j++) {
        max = std::max(max, A[i % N]);
        min = std::min(min, A[i % N]);
        
        if (j + 1 == M) {
            res += max - min;
            j = -1;
            max = INT_MIN;
            min = INT_MAX;
        }
    }
    std::cout << res << std::endl;    
    return 0;
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

bool uneven(int n, int k) {
	int T = n|k;
	return (T==n);
}

int solve(string s) {
	int x = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (uneven(s.size() - 1, i)) {
			x ^= (s[i] - '0');
		}
	}
	return x;
}

int main(){
#ifdef LOCAL
	freopen("A_input.txt", "r", stdin);
	//freopen("A_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	string s;
	cin >> n >> s;

	for (int i = 0; i < s.size(); ++i) {
		s[i]--;
	}

	int ed = 0;
	for (int i = 0; i < s.size(); ++i) if (s[i] == '1') ed++;

	if (ed == 0) {
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '2') s[i] = '1';
		}
		cout << 2*solve(s);
	}
	else{
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '2') s[i] = '0';
		}
		cout << solve(s);
	}

}


Measured memory_bytes: 2332
// Problem : B - Homework
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

typedef long long ll;
const int INF=1<<30;

int main()
{
	int n,m;cin>>n>>m;
	rep(i,1,m){
		n-=read();
	}
	cout<<max(-1,n)<<endl;
	return 0;
}



Measured memory_bytes: 3636
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] h = new int[n];
    int max = 0;
    for (int i = 0; i < n; i++) {
      int num = sc.nextInt();
      h[i] = num;
    }
    int curr = h[0];
    int index = 1;
    int count = 0;
    while(index < n) {
      while(index < n && curr >= h[index]) {
        count++;
        curr = h[index];
        index++;
      }
      max = Math.max(count, max);
      if (index < n) curr = h[index];
      index++;
      count = 0;
    }
    System.out.println(max);
  }
}


Measured memory_bytes: 50400
import numpy as np

N, M = map(int, input().split())
X = list(map(int, input().split()))

if N >= M:
  print(0)
  exit()

## マスの間の距離を計算して、そのうち小さいもの(M-N)個だけ移動する
X.sort()
dist = [X[i+1]-X[i] for i in range(M-1)]
dist_small = np.array(dist.sort())
dist_cumsum = np.cumsum(dist)
print(dist_cumsum[M-N-1])




Measured memory_bytes: 23072
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int main()
{
    she_told_me_dont_worry
    int n;
    cin>>n;
    int ans = n/2;
    if(n%2) ans++;
    cout<<ans<<endl;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

A, B, C, D, E, F = MAP()

water = set()

for a in range(F//(100*A)+1):
	for b in range((F-100*a*A)//(100*B)+1):
		water.add(100*(a*A+b*B))

sugar = [0]*(F+1)
sugar[0] = 1
for i in range(1, F+1):
	sugar[i] = 0<(sugar[i-C]*(0<i) + sugar[i-D]*(0<i))

sugar_acc = [0]*(F+1)
tmp = 0
for i in range(F//2+1):
	if sugar[i] == 1:
		tmp = i
	sugar_acc[i] = tmp

#print(water)
#print(sugar_acc)

ans = 0
den = 0
water_ans = 0
sugar_ans = 0
water = sorted(list(water))

for water_tmp in water[1:]:
	t = min(E*water_tmp//100, F-water_tmp)
	sugar_tmp = sugar_acc[t]
	den_tmp = sugar_tmp/(sugar_tmp+water_tmp)

	if den <= den_tmp:
		den = den_tmp
		water_ans = water_tmp
		sugar_ans = sugar_tmp

print(water_ans+sugar_ans, sugar_ans)


Measured memory_bytes: 10532
#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()
{
    string str;

    while (getline(cin, str))
    {
        if(str == "0"){
            break;
        }
        int val = 0;
        for (auto c : str)
        {
            val += c - '0';
        }
        cout << val << endl;
    }
}


Measured memory_bytes: 3128
import numpy as np
import math

N,K = map(int,input().split())
A = list(map(int,input().split()))


visited = {}
next=1
start=-1
loop_num=0
while(K>0):
	#print(next,start)
	if next==start:
		break
	if not next in visited.keys():
		visited[next] = 1
	elif start==-1:
		start=next
		loop_num=0
	next = A[next-1]
	K-=1
	loop_num+=1


if K==0:
	print(next)
else:
	K%=loop_num
	next=start
	for i in range(K):
		next = A[next-1]
	print(next)

Measured memory_bytes: 51104
#include<stdio.h>
#include<math.h>
#define PI 3.14159265358979323846264338327950
int main(void){
   double a,b,h,w;

  scanf("%lf%lf%lf%lf",&a,&b,&h,&w);
   double s; //なす角
  s=fabs(360*h/12+0.5*w-360*w/60);
 /* if(s==180||s==0){
    printf("%.20Lf",fabsl(a-b));
    return 0;
  }*/
  if(s>180)s=360-s;
  //printf("%.10lf\n",s*M_PI);
 // printf("%.10lf\n",s*M_PI/180);
  double sita=s*PI/180;
  //printf("%lf %f %lf %lf\n",s,cos(sita),
    //  a*a+b*b,sqrt(a*a+b*b));
  
 
  long double ans=sqrt(a*a+b*b-2*a*b*cosl(sita));
  printf("%.20Lf",ans);
  return 0;
}

Measured memory_bytes: 2516
var
	N,M,K,i,t:Longint;
begin
	read(N,M,K);
	if((K mod M=0)and(K div M<=N))or((K mod N=0)and(K div N<=M))then begin
		writeln('Yes');
		exit;
	end;
	for i:=0 to N do begin
		if(N<>2*i)and((K-M*i)mod(N-2*i)=0)then begin
			t:=(K-M*i)div(N-2*i);
			if(0<=t)and(t<=M)then begin
				writeln('Yes');
				exit;
			end;
		end;
	end;
	writeln('No');
end.

Measured memory_bytes: 128
s=input()
sl=len(s)

if sl==1:
  print(int(s))
  exit()

ans=0
for i in range(2**(sl-1)):
  l=['' for j in range(sl-1)]
  for k in range(sl-1):
    if (i>>k)&1:
      l[k]='+'

  t_ans=0
  t_s=s[0]

  for k in range(1,sl):
    if l[k-1]=='+':
      t_ans+=int(t_s)
      t_s=s[k]
    else:
      t_s+=s[k]

    if k==sl-1:
      t_ans+=int(t_s)

  ans+=t_ans

print(ans)

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

using namespace std;

//=================================================================
// Begginer Contest 115 C
int main(){
    int N,K;
    cin >> N >> K;
    vector<int> h(N,0);
    for(int i=0;i<N;i++){
        cin >> h[i];
    }
    sort(h.begin(),h.end());
    int min=10000000000;
    int tmp=0;
    for(int i=0;i<N-K+1;i++){
        tmp = h[i+K-1]-h[i];
        if(tmp<min){
            min = tmp;
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using P=pair<int,int>;
using G=vector<vector<int>>;
using ll=long long;

const ll MAX = 1000000;
const ll MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}


pair<ll,ll> route(ll x,ll y){
	ll pl=x+y;
	if(x%3==0){
		ll m=(2*x-y)/3;
		ll n=(2*y-x)/3;
		return make_pair(n,m);
	}else{
		return make_pair(0,0);
	}
}




int main(int argc, char **argv){
	ll x,y;cin>>x>>y;

	if((x+y)%3 != 0){
		cout<<0<<endl;
		return 0;
	}

	COMinit();

	ll dx,dy;
	dx=(2*y-x)/3; dy=(2*x-y)/3;

	if(dx<0||dy<0){
		cout<<0<<endl;
		return 0;
	}
	
	cout<<COM(dx+dy,dy)<<endl;
}


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

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;

#define endl '\n'
#define ff first
#define ss second
#define int long long
#define pb push_back
#define f(i,l,r) for(ll i=l;i<=r;i++)
#define rf(i,r,l) for(ll i=r;i>=l;i--)
#define Max 5000001
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

#define d0(a) cout<<a<<' ';
#define d1(a) cout<<a<<endl;
#define d2(a,b) cout<<a<<' '<<b<<endl;
#define d3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define d4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
#define d5(a,b,c,d,e) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;
#define d6(a,b,c,d,e,f) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<endl;

const ll N=2e5+5,mod=998244353,bit=61;

ll fact[N],ifact[N];

ll powerm(ll a,ll b,ll m=mod)
{
	a%=m;
	ll res=1%m;
	while(b>0)
	{
		if(b & 1)
		{
			res=(res*a)%m;
		}
		b>>=1;
		a=(a*a)%m;
	}
	return res;
}

void pre()
{
    fact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=(fact[i-1]*i)%mod;
    }
    ifact[N-1]=powerm(fact[N-1],mod-2);
    for(int i=N-2;i>=0;i--)
    {
        ifact[i]=(ifact[i+1] * (i+1))%mod;
    }
}

ll ncr(ll n,ll r)
{
    if(r>n)
    {
        return 0;
    }
    ll ans=(ifact[r] * ifact[n-r])%mod;
    ans=(ans * fact[n])%mod;
    return ans;
}

signed main()
{
    fast;

    pre();
    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll n,m,k;
        cin>>n>>m>>k;
        ll ans=0;
        f(i,0,k)
        {
            ll x=(ncr(n-1,n-1-i)*m)%mod;
            x=(x * powerm(m-1,n-1-i))%mod;
            ans=(ans+x)%mod;
        }
        d1(ans);
    }
    return 0;
}


















Measured memory_bytes: 6780
#include <stdio.h>
int main(int argc, char const *argv[]) {

  int i,j;
  int count = 0;
  int num_S;
  int num_T;

  scanf("%d",&num_S);
  int S[num_S];
  for( i = 0 ; i < num_S ; i++ ){
    scanf("%d",&S[i]);
  }

  scanf("%d",&num_T);
  int T[num_T];
  for( i = 0 ; i < num_T ; i++ ){
    scanf("%d",&T[i]);
  }

  for( i = 0 ; i < num_T ; i++ ){

    for( j = 0 ; j < num_S ; j++ ){

      if( T[i] == S[j] ){
        count++;
        break;
      }

    }


  }

  printf("%d\n",count);

  return 0;
}

Measured memory_bytes: 640
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      n: usize,
      mut abs: [(usize,usize); n],
    }
    abs.sort_by_key(|v| v.1);

    let mut cur = 0;
    for (a, b) in abs {
        cur += a;
        if cur > b {
            return println!("{}", "No");
        }
    }
    println!("{}", "Yes");
}


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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a+b < c+d){
        cout << "Right" << endl;
    } else if(a+b > c+d){
        cout << "Left" << endl;
    } else {
        cout << "Balanced" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
function main(arg){
  	var out = arg.trim().split('\n');
	var ball = out[0].split(' ');
  	var num = out[1].split(' ').map(str => parseInt(str, 10)); 
  	var fall = out[2];

  	var result;
  	if(ball[0] === fall) {
    	num[0]--;
      	result = num.join(' ');
    } else if (ball[1] === fall){
    	num[1]--;
      	result = num.join(' ');
    }
	console.log(result);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    //cout.precision(10);
    int n, k;
    cin >> n >> k;
    if((n % k) == 0){
      cout << 0 << endl;
      return 0;
    }
    cout << 1 << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;

int main(void)
{
    int n;
    cin >> n;
    map<string, int> dic;
    for (int i = 0; i < n;i++){
        string s;
        cin >> s;
        dic[s]++;
    }
    int max_v = 0;
    for(auto it:dic){
        int t = it.second;
        max_v = max(max_v,t);
    }
    for (auto it :dic){
        if(it.second == max_v){
            cout << it.first << endl;
        }
    }
    return 0;
}

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

#define SIZE 100100
#define POS 1
#define NEG 0

int n;
long long arr[SIZE];

long long solve(long long sum, int index, int should){
    if(index == n){
        return 0;
    }

    long long ans = 0LL;

    sum += arr[index];
    if(sum <= 0 && should == POS){
        ans += (abs(sum) + 1);
        ans += solve(1, index + 1, NEG);
    }else if(sum >= 0 && should == NEG){
        ans += (abs(sum) + 1);
        ans += solve(-1, index + 1, POS);
    }else{
        ans += solve(sum, index + 1, 1 - should);
    }

    return ans;
}

int main(){
    #ifdef magUNbos
    freopen("a.in.c","r",stdin);
    #endif // magUNbos

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    long long a1 = solve(0LL, 0, POS);
    long long a2 = solve(0LL, 0, NEG);

    cout << min(a1, a2) << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll m=1e9+7;
ll mod(ll n){
    return (n%m+m)%m;
}
ll mul(ll a, ll b){
    return mod(mod(a)*mod(b));
}
int main() {
    int n,k;
    cin>>n>>k;
    vector<ll> pos,neg;
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        if(x>=0){
            pos.push_back(x);
        }
        else{
            neg.push_back(x);
        }
    }
    if(pos.size()==0){
        sort(neg.begin(),neg.end());
        if(k&1){
            reverse(neg.begin(),neg.end());
        }
        ll p=1;
        for(int i=0;i<k;i++){
            p=mul(p,neg[i]);
        }
        cout<<p<<endl;
    }
    else if(neg.size()==0){
        sort(pos.begin(),pos.end(),greater<ll>());
        ll p=1;
        for(int i=0;i<k;i++){
            p=mul(p,pos[i]);
        }
        cout<<p<<endl;
    }
    else{
        ll ans=1;
        if(k&1){
            sort(pos.begin(),pos.end());
            ans=mul(ans,pos[pos.size()-1]);
            pos.pop_back();
            k--;
        }
        vector<ll> ok;
        sort(pos.begin(),pos.end(),greater<ll>());
        sort(neg.begin(),neg.end());

        for(int i=0;i<(int)pos.size()-1;i+=2){
            ok.push_back(pos[i]*pos[i+1]);
        }
        for(int i=0;i<(int)neg.size()-1;i+=2){
            ok.push_back(neg[i]*neg[i+1]);
        }
        if(pos.size()%2 && neg.size()%2){
            ok.push_back(pos[pos.size()-1]*neg[neg.size()-1]);
        }
        sort(ok.begin(),ok.end(),greater<ll>());
        for(int i=0;i<(k/2);i++){
            ans=mul(ans,ok[i]);
        }
        cout<<ans<<endl;
    }
}


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

using namespace std;

const int max_n = 222, inf = 1000111222;

int n, dist[max_n];
string a[max_n];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = -1;
    for (int start = 0; start < n; ++start) {
        memset(dist, -1, sizeof(dist));
        queue<int> q;
        q.push(start);
        dist[start] = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int to = 0; to < n; ++to) {
                if (a[v][to] == '1' && dist[to] == -1) {
                    dist[to] = dist[v] + 1;
                    q.push(to);
                }
            }
        }
        bool ok = true;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res = max(res, dist[i]);
            for (int j = 0; j < n; ++j) {
                if (a[i][j] == '1' && abs(dist[i] - dist[j]) != 1) {
                    //if (start == 5) cout << "$" << i << " " << j << " " << dist[i] << " " << dist[j] << endl;
                    ok = false;
                }
            }
        }
        if (ok) {
            ans = max(ans, res);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <cctype>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define rep_down(i, n) for(int i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(int i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()

string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";
string numbers = "0123456789";
/*
for (iterator = hash.begin(); iterator != hash.end(); iterator++)
{
// ここで、要素毎の操作を行います。
std::pair<std::string, CMyClass> element = *iterator;

}
*/
/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int keta_sum(int num){
  int dig, sum = 0;
  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
  }
  return sum;
}

ll binary_search(ll left_key, ll border, ll low, ll high) {
     // 配列 a の左端と右端
    ll mid = (low+high)/2;
    while (high > low+1) {
       mid = (low+high)/2;
        if (left_key*mid>border) high = mid;
        else if (left_key*mid<border) low = mid;
        else {
          mid =mid-1;
          break;
        }
    }
    return mid;
}

bool IsPrime(ll a){
  ll b = sqrt(a);
  b++;
  while(b-->=2){
    if (a%b==0) return false;
  }
  return true;
}

ll gcd(ll a, ll b){
  ll tmp;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  ll r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(void){
  ll N, M, A, B, C, D, E, F, K,L, W, H, P, Q, R, X, Y;
  ll ans;
  string S, T;
  cin >> N >> M;
  cout << (N-1)*(M-1) << endl;

}


Measured memory_bytes: 256
h,w = map(int,input().split())
f = [[0]*(w+3) for i in range(h+3)]
lines = []
for s in range(h):
    l = input()
    lines.append(l)
    for i in range(w):
        if l[i] == "#":
            f[s][i] += 1
            f[s+3][i] -= 1
            f[s][i+3] -= 1
            f[s+3][i+3] += 1

for j in range(h+1):
    for i in range(w):
        f[j][i+1] += f[j][i]
for i in range(w+1):
    for j in range(h):
        f[j+1][i] += f[j][i]
for j in range(h):
    line = ""
    for i in range(w):
        line += "#" if lines[j][i] == "#" else str(f[j+1][i+1])
    print(line)


Measured memory_bytes: 3064