akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n;

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

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        solve();
    }

    void solve() {
        if (n >= 1000) {
            System.out.println("ABD");
        } else {
            System.out.println("ABC");
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 22996
a, b, c = map(int, input().split())
 
if a % 2 == 1 or b % 2 == 1 or c % 2 == 1:
    print(0)
elif a == b == c:
    print(-1)
else:
    num = 0
    while (a % 2 == 0 and b % 2 == 0 and c % 2 == 0):
        a, b, c = (b+c)/2, (a+c)/2, (a+b)/2
        num += 1
    print(num)

Measured memory_bytes: 9136
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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 int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

int N;
int odd, mul2, mul4;

int main() {
  cin >> N;
  rep(i, 0, N) {
    int a;
    cin >> a;
    if (a % 4 == 0) {
      ++mul4;
    } else if (a % 2 == 0) {
      ++mul2;
    } else {
      ++odd;
    }
  }

  if (mul2 > 0) {
    mul2 = 1;
  }

  bool can = mul2 + odd <= mul4 + 1;

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


Measured memory_bytes: 3596
using System;

namespace PrimeNumber
{
    class Program
    {
        private static bool?[] arr = new bool?[1000000];

        private static bool Save(int n, bool b)
        {
            arr[n] = b;
            return b;
        }

        private static bool IsPrime(int n)
        {
            if (arr[n] != null) return (bool)arr[n];
            if (n < 2) return Save(n, false);
            if (n == 2) return Save(n, true);
            if (n % 2 == 0) return Save(n, false);

            double l = Math.Sqrt(n);

            for (var i = 3; i <= l; i += 2)
                if (n % i == 0) return Save(n, false);
       
            return Save(n, true);
        }

        static void Main(string[] args)
        {
            int num;
            
            while (int.TryParse(Console.ReadLine(), out num))
            {
                var count = num >= 2 ? 1 : 0;
                for (var i = 3; i <= num; i+=2)
                    if (IsPrime(i)) count++;
                Console.WriteLine(count);
            }
        }
    }
}


Measured memory_bytes: 10980
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <functional>
#include <map>
#include <set>
#include <stack>
#include <deque>

#define INF 1000000000;
#define MOD 1000000007;
typedef long long ll;
using namespace std;

int main()
{
    int n; cin >> n;
    int odd = 0, even = 0;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        if (a % 2 == 0) {
            even++;
        }
        else {
            odd++;
        }
    }
    string ans = "NO";
    if (odd % 2 == 0) {
        ans = "YES";
    }
    else {
        ans = "NO";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
from collections import deque
K = int(input())
q = deque([1,2,3,4,5,6,7,8,9])

for i in range(K):
  num = q.popleft()
  if num%10 != 0:
    q.append(num*10+num%10-1)
  q.append(num*10+num%10)
  if num%10 != 9:
    q.append(num*10+num%10+1)

print(num)

Measured memory_bytes: 18916
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
  public static void Main(){

    int n = int.Parse(Console.ReadLine());
    var input = Console.ReadLine().Split();
    var b = new int[n];
    int k = 0;
    if(n % 2 == 1) k = 1;
    for(int i = 0; i < n; i++){
      if((i + k) % 2 == 0){
        b[n/2 + (i+1)/2] = int.Parse(input[i]);
      }
      else{
        b[n/2 -(i+1)/2] = int.Parse(input[i]);
      } 
    }
    for(int i = 0; i < n; i++){
      Console.Write(b[i]);
      if(i != n-1) Console.Write(" ");
    }
  }
}


Measured memory_bytes: 35896
wlist=[ i for i in input()]
klist=["k","e","y","e","n","c","e"]
a=[]
for i in range(len(wlist)-1):
    for j in range(i+1,len(wlist)):
        if wlist[0:i+1]+wlist[j:]==klist:
                a.append(1)
        else:
                a.append(0)
                
if 1 in a:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
#![allow(unused)]

#[allow(unused_imports)]
use std::{cmp, collections, fmt, io, iter, ops, str};
use cmp::Ordering::*;
use collections::{HashMap, HashSet};
use io::{Read, Write};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($fmt: expr) => { eprintln!($fmt) };
    ($fmt: expr, $($arg: tt)*) => { eprintln!($fmt, $($arg)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($fmt: expr) => {};
    ($fmt: expr, $($arg: tt)*) => {};
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if buf.len() > 0 {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn main() {
    let mut abc = parse_vec::<i32>();
    abc.sort();

    let c_b = abc[2] - abc[1];
    let c_a = abc[2] - abc[0];

    let cnt = c_b / 2 + c_a / 2 + match (c_b % 2, c_a % 2) {
        (0, 0) => 0,
        (0, 1) | (1, 0) => 2,
        (1, 1) => 1,
        _ => unreachable!(),
    };

    println!("{}", cnt);
}


Measured memory_bytes: 4352
//1.read question_2.read I/O_3.read test cases_4.read constraints(to decide TC of solution)_5.decide method_6.dry run_
//7.code_8.test_9.submit
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int lli;
#define mod 1000000007
#define F first
#define S second
#define _READ freopen("input.txt","r", stdin);
#define pb push_back
#define MP make_pair
#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
    lli n;cin>>n;
    lli m=log2(n);
    m++;
    m=1ll<<m;
    m--;
    cout<<m;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
dp = [i for i in range(n+1)]
for i in range(n+1):
    power = 1
    while 6**power <= i:
        dp[i] = min(1+dp[i-6**power],dp[i])
        power += 1
    power = 1
    while 9**power <= i:
        dp[i] = min(1+dp[i-9**power],dp[i])
        power += 1
print(dp[n])

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

#define pb push_back
typedef long long int ll;
typedef vector<ll> vl;
typedef map<ll,ll> ii;
const ll mod = 1e9+7;
ll mod_mul(ll x,ll y){
    return ((x%mod)*(y%mod))%mod; 
}

ll mod_add(ll x,ll y){
    return ((x%mod)+(y%mod))%mod;
}

ll fast_expo(ll x, ll y){
    
    ll res=1;
    while(y>0){
        if(y&1){
            res*=x;
        }
        x*=x;
        y>>=1;
    }
    return res;
}
//fast expo function
ll fast_expo(ll x, ll y, ll m){
    x%=m;
    ll res=1;
    while(y>0){
        if(y&1){
            res=((res%m)*(x%m))%m;
        }
        x=((x%m)*(x%m))%m;
        y>>=1;
    }
    return res;
}

//sieve function
void sieve(ll x,vl &v){
    bool sieve[x+1];
    memset(sieve,true,sizeof(sieve));
    int i=2;
    while(i*i<=x){
        if (sieve[i]==true){
            for(int j=i+i;j<=x;j+=i){
                sieve[j]=false;
            }
            
        }
    i++;    
    }
    
    for(int i=2;i<=x;i++){
        if(sieve[i])
            v.pb(i);
    }
    
}
//GCD function
int gcd(int x,int y){
    if(x==0)return y;
    return gcd(y%x,x);
}
//main code
int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int t;cin>>t;
    vl a;
    for(int i=0;i<t;i++){
        ll k;cin>>k;
        a.push_back(k);
    }
    ii m;
    vl v;
    sieve(100001,v);
    
    
    for(ll i:a){
        int j=0;
        
        while(v[j]*v[j]<=i){
            ll k=v[j];
            ll c=0;
            if (i%k==0){
                while(i%k==0){
                    c++;
                    i/=k;
                }
            
                ll h=m[k];
                m[k]=max(c,h);
            }
            j++;
        }
        if (i>=2){
            ll c=1;
            m[i]=max(m[i],c);
        }
    }
    ll z=1;
    for(auto i:m){
        z=mod_mul(z,fast_expo(i.first,i.second));
    }
    ll y=0;
    for(ll i:a){
        y=mod_add(y,mod_mul(z,fast_expo(i,mod-2,mod)));
    }    
    
    cout<<y;
    return 0;
    
}
    

Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	int h[10];
	int a;

	for(int k=0;k<10;k++){
		cin>>h[k];
	}
	for(int i=0;i<10;i++){
		for(int j=i+1;j<10;j++){
			if(h[i]<h[j]){
				a = h[i];
				h[i] = h[j];
				h[j] = a;
			}
		}
	}
	cout<<h[0]<<endl;
	cout<<h[1]<<endl;
	cout<<h[2]<<endl;

	return 0;
}

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

#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'

template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

typedef long long ll;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  
  int d, n; cin >> d >> n;
  if(n==100)  n++;
  cout << int(n*pow(100, d)) << "\n";
  return 0;
}

Measured memory_bytes: 3592
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		String[] s = stdIn.next().split("");
		
		int cnt = 0;
		
		for(int i = 0; i < s.length-1; i++) {
			
			if(s[i].equals("h")&& s[i+1].equals("i")) {
				i++;
			}else {
				System.out.println("No");
				return;
			}
			
			
		}
		
		int cnth = 0;
		int cnti = 0;
		int els = 0;
		
		
		for(int i = 0; i < s.length; i++) {
			if(s[i].equals("h")) {
				cnth++;
			}
			else if(s[i].equals("i")) {
				cnti++;
			}else {
				els++;
			}
		}
		
		if(cnth == cnti && els == 0) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
		
	}

}


Measured memory_bytes: 23124
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#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() {
  double L;
  cin >> L;
  cout << fixed << setprecision(12) << pow(L/3.0, 3) << endl;
  return 0;
}

Measured memory_bytes: 3688
/*input
1 3
*/
fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_.pop();
    return_
}

fn main() {
    let v: Vec<i32> = read_line()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    println!("{}", (v[0] + v[1]) / 2);
}



Measured memory_bytes: 5028
import java.util.Scanner;

public class Main {

    private static final double LOG_OF_2 = Math.log(2);
    private static final double PROBABILITY_HEAD = 0.5;

    public static String process(int N, int K) {
        double sum = 0;
        for (int i = 1; i <= Math.min(N, K); ++i) {
            double numTimesNeeded = Math.ceil(Math.log((double) K / (double) i) / LOG_OF_2);
            sum += Math.pow(PROBABILITY_HEAD, numTimesNeeded) / (double) N;
        }
        sum += (double) Math.max(0, N - K) / (double) (N);
        return String.valueOf(sum);
    }

    // Util func

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

        int N = sc.nextInt();
        int K = sc.nextInt();

        final String result = process(N, K);

        output(result);
    }

    private static void output(String result) {
        System.out.println(result);
    }
}


Measured memory_bytes: 21844
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        if cost[now][ns] <= nt : continue
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

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

int main(void){
    int n,x;
    cin >> n >> x;
    vector<int> vec(n);
    int total = 0;
    int min = 100000;
    for (int i = 0; i < n; i++){
        cin >> vec.at(i);
        total += vec.at(i);
        if(min > vec.at(i)) min = vec.at(i);
    }
    int canmake=0;
    int count = 0;
    canmake = x - total;
    while (1){
        if (canmake >= min){
            canmake -= min;
            count++;
        }else{
            break;
        }
    }
    cout << count + n << endl;
    
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 505;

int n , m , ans;
int num[N][N];
struct data{
	int x1,y1;
	int x2,y2;
}kkk[N * N];

int main ( void ) {
	scanf ( "%d%d" , &n , &m );
	for ( int i = 1 ; i <= n ; i++ ) 
		for ( int j = 1 ; j <= m ; j++ ) 
			scanf ( "%d" , &num[i][j] );
	for ( int i = 1 ; i < n ; i++ )
	  for ( int j = 1 ; j <= m ; j++ )
	  	if ( num[i][j] & 1 ) {
	  		ans++;
		 	num[i + 1][j]++;
		  	kkk[ans].x1 = i;
		  	kkk[ans].y1 = j;
		  	kkk[ans].x2 = i + 1;
		  	kkk[ans].y2 = j;
	}
	for ( int j = 1 ; j < m ; j++ )
		 if ( num[n][j] & 1 ) {
		 	ans++;
		 	num[n][j + 1]++;
			kkk[ans].x1 = n;
			kkk[ans].y1 = j;
			kkk[ans].x2 = n;
			kkk[ans].y2 = j + 1;
		}
	printf ( "%d\n" , ans );
	for ( int i = 1 ; i <= ans ; i++ )
		 printf ( "%d %d %d %d\n" , kkk[i].x1 , kkk[i].y1 , kkk[i].x2 , kkk[i].y2 ); 	
	return 0;
}


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

using namespace std;

int main() {
	int n;
  	cin >> n;
  	int x, y;
  	vector<int> v;
  	for (int i=1; i<=n; ++i) {
    	cin >> x >> y;
      	v.push_back(x-y);
    }
  	bool flag = false;
  	for (int i=0; i<n-2; ++i) {
    	if (v[i] == v[i+1] && v[i+1] == v[i+2] && v[i+2] == 0) {
        	cout << "Yes";
          	flag = true;
          	break;
        }
    }
  	if (!flag)
    	cout << "No";
  	return 0;
}

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

int main(){
    int s;
    cin>>s;
    int b=s%100;
    int f=s/100;
    string ans="NA";
    if(b<=12&&f<=12&&b>0&&f>0) ans="AMBIGUOUS";
    else if(b<=12&&(f>12||f==0)&&b>0) ans="YYMM";
    else if((b>12||b==0)&&f<=12&&f>0) ans="MMYY";
    cout<<ans<<endl;
}

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

long long int N, a[114514], i, n, r, m;

int main(){
    scanf("%lld", &N);
    for(; i < N; ++i){
        scanf("%lld", a + i);
    }
    n = max(1LL, *a);
    r = n - *a;
    for(i = 1; i < N; ++i){
        //cout << i << " : " << n << " : ";
        if(n * (n + a[i]) >= 0){
            //cout << n << " " << n + a[i] << " ";
            if(n > 0){
                r += a[i] + n + 1;
                n = -1;
            }else{
                r += 1 - n - a[i];
                n = 1;
            }
            //cout << r << " ";
        }else{
            n += a[i];
        }
        //cout << endl;
    }
    n = min(-1LL, *a);
    m = *a - n;
    for(i = 1; i < N; ++i){
        //cout << i << " ";
        if(n * (n + a[i]) >= 0){
            //cout << n << " " << n + a[i] << " ";
            if(n > 0){
                m += a[i] + n + 1;
                n = -1;
            }else{
                m += 1 - n - a[i];
                n = 1;
            }
            //cout << m << " ";
        }else{
            n += a[i];
        }
        //cout << endl;
    }
    cout << min(r, m) << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int N;
    cin >> N;
    ll cnt = 0;
    for(int i=1;i<=N;i++){
        cnt = cnt + i;
        if(cnt>=N){
            cout << i << endl;
            return 0;
        }
    }
}

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

int main()
{
    int n, k;
    cin >> n >> k;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        bool flg = x < abs(k - x);
        sum += flg ? x * 2 : (k - x) * 2;
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define MOD 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(var) (var).begin(), (var).end()
#define MAXX 9000000000000000000
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pair<int,int> > 
#define vvpi vector<vector<pair<int,int> > >

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int a=0,b=0,c=0,d=0,n;
	cin >> n;
	while(n--)
	{
		string s;
		cin >> s;
		if(s == "AC")
		{
			a++;
		}
		if(s == "WA")
		{
			b++;
		}
		if(s == "TLE")
		{
			c++;
		}
		if(s == "RE")
		{
			d++;
		}
	}

	cout << "AC x " << a << endl;
	cout << "WA x " << b << endl;
	cout << "TLE x " << c << endl;
	cout << "RE x " << d << endl;

	return 0;
}

Measured memory_bytes: 3600
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール
// 拡張ユークリッド互除法
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (a < b) return extgcd(b, a, y, x);
    if (b) {
        ll g = extgcd(b, a%b, y, x);
        y -= a / b * x;
        return g;
    } else {
        x = 1, y = 0;
        return a;
    }
}

// 処理内容
int main() {
    
    ll a, b; cin >> a >> b;

    if (b % a == 0) { // jimei
        cout << -1 << endl;
        return 0;
    }
    
    ll n = 1;
    ll m = (n * b + a-1) / a;
    if (m*a-n*b > m-n) {
        cout << m*a << endl;
    } else {
        cout << -1 << endl;
    }
    
}


Measured memory_bytes: 3136
import java.util.*;
public class Main {
	private static Scanner sc;
    public static void main(String[] args){
    	TreeSet<String> all = new TreeSet<String>();
    	sc = new Scanner(System.in);
    	int a=sc.nextInt();
    	for (int j=0; j<a; j++){
    		String word=sc.next();
    		for (int i=1; i<word.length(); i++){
    			String front =  word.substring(0, i);
    			String revfront = new StringBuffer(front).reverse().toString();
    			String back = word.substring(i,word.length());
    			String revback = new StringBuffer(back).reverse().toString();
    			all.add(front+back);
    			all.add(back+front);
    			all.add(front+revback);
    			all.add(revback+front);
    			all.add(revfront+back);
    			all.add(back+revfront);
    			all.add(revfront+revback);
    			all.add(revback+revfront);
    		}
    		System.out.println(all.size());
    		all.clear();
    	}	
    }
}

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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=102,M=11;
int a[N];
int main()
{
	int n,k;
	cin>>n>>k;
	while(k--)
	{
		int x;
		cin>>x;
		while(x--)
		{
			int y;
			cin>>y;
			a[y]++;
		}
	}
	int r=0;
	while(n)
	{
		r+=(a[n]==0);
		n--;
	}
	cout<<r;

	return 0;
}

Measured memory_bytes: 3624
n=int(input())
s=input()
ans=0
d=dict()
for i in range(1000):
  num='0'*(3-len(str(i)))+str(i)
  if num[0] in s:
    j=s.index(num[0])
    if num[1] in s[j+1:]:
      k=s[j+1:].index(num[1])
      if num[2] in s[j+2+k:]:
        ans+=1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for(int i=0; i<N; i++) cin >> P[i];
  
  int min=P[0];
  int cnt=0;
  for(int j=0; j<N; j++){ 
    if(min>=P[j]){
      cnt++;
      min=P[j];
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 1024
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/icl/interval_map.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::integer;

using ll = long long;
namespace bst = boost;
namespace icl = boost::icl;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<ll> N, M, K;
  invec<ll> A(N), B(M);
  
  for (int i = 1; i < N; i++)
    A[i] += A[i-1];
  for (int i = 1; i < M; i++)
    B[i] += B[i-1];

  ll now = bst::lower_bound(A, K) - A.begin();
  ll r = max((ll)(bst::upper_bound(A, K) - A.begin()), (ll)(bst::upper_bound(B, K) - B.begin()));

//  if (K < A[0] && K < A[1])
//    return 0LL;
  
  if (now == N)
    now--;
  for (int i = now; i >= 0; i--) {
    ll time = A[i];
    ll nb = bst::upper_bound(B, K - time) - B.begin();
    
    if (nb > 0 && time + B[nb-1] <= K)
    r = max((ll)r, (ll)i + 1 + nb);
  }

  return r;
}

template<typename T> void plot(const T& func) { cout << setprecision(9) << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }

int main() {
  plot(solve);

  return 0;
}





Measured memory_bytes: 6424
import sys
input = sys.stdin.readline
import math
from fractions import gcd
import operator
from functools import reduce
from itertools import accumulate

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, gcd))
    sr = list(reversed(list(accumulate(reversed(A), gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        # gcdの単位元は0
        v = 0
        if i > 0:
            v = gcd(v, sl[i-1])
        if i < N-1:
            v = gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


Measured memory_bytes: 16144
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a)), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long
#define INF             __LONG_LONG_MAX__

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

ll gcd(ll a, ll b) {
  if (a < b) return gcd(b, a);
  if (b == 0) return a;
  return gcd(b, a % b);
}

void solve() {
  ll k; cin >> k;
  ll sum = 0;
  for (int a = 1; a <= k; a++) {
    for (int b = 1; b <= k; b++) {
      ll d = gcd(a, b);
      for (int c = 1; c <= k; c++) {
        sum += gcd(c, d);
      }
    }
  }
  outl(sum);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 3164
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


n, m = zz()
A, B = [], []
for i in range(n):
    a, b = zz()
    A.append(a)
    B.append(b)
C, D = [], []
for i in range(m):
    c, d = zz()
    C.append(c)
    D.append(d)

dist = [[0]*m for i in range(n)]
for i in range(n):
    for j in range(m):
        dist[i][j] = abs(A[i] - C[j]) + abs(B[i] - D[j])


for i in range(n):
    print(np.argmin(dist[i])+1)


Measured memory_bytes: 42392
/*ॐ नमो भगवते वासुदेवाय नमः*/
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()
#define pb push_back
#define pf push_front
#define fori(i, a, n) for(int i = a; i < n; ++i)
#define MAX(x) (*max_element(all(x)))
#define MIN(x) (*min_element(all(x)))
#define sortarr(a, n) sort(a, a + n)
#define sortvec(V) sort(all(V))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef unordered_map<int, int, custom_hash> u_map;
typedef unordered_set<int, int, custom_hash> u_set;
typedef vector<int> V;
typedef pair<int , int> pairi;
typedef set<int> seti;
typedef priority_queue<int> p_queue;
typedef deque<int> deqi;

const int MOD = 1e9+7;
const int INF = 1e9+8;
const double pi = 3.14159265359;

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

void solve()
{
    int n, x, t;
    cin >> n >> x >> t;
    int sum = t;
    n -= x;
    while(n > 0){
        sum += t;
        n -= x;
    }
    cout << sum << endl;

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
    cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n ";
}

Measured memory_bytes: 3792
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9

def main():
    n = int(input())
    S = input()

    if n%2 == 0:
        if S[:n//2] == S[n//2:]:
            print('Yes')
            return
    print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 62092
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;

    if(a>=(-100) && a<=100 && b>=(-100) && b<=100 && c>=(-100) && c<=100)
    {
        if(c>a && b>c)
        {
            if(a==c && b==c)

                     cout<<"Yes"<<endl;
            else
              cout<<"Yes"<<endl;
        }
        else
        {
             if(a==c && b==c)

                         cout<<"Yes"<<endl;
            else
               cout<<"No"<<endl;
        }

    }
    else
        return 0;
}


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

using namespace std;

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define FOR(i,n) for (int i = 0; i < n; i++)
#define FORR(i,a,b) for (int i = a; i <= b; i++)
#define ALL(v) v.begin(), v.end()
#define pb(x) push_back(x)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ii> vii;

const int MX = 200005;
int n, m, a, b, c[MX], x[MX][2];
char ch;
vi adj[MX];
bitset<MX> ex;
queue<int> q;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> ch;
		c[i] = ch == 'A';
		ex[i] = 1;
	}

	while (m--) {
		cin >> a >> b;
		adj[a].pb(b);
		if (a != b) adj[b].pb(a);

		x[a][c[b]]++;
		if (a != b) x[b][c[a]]++;
	}

	for (int i = 1; i <= n; i++)
		if (!x[i][0] || !x[i][1]) {
			q.push(i);
			ex[i] = 0;
		}

	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int v : adj[u]) {
			x[v][c[u]]--;
			if ((!x[v][0] || !x[v][1]) && ex[v]) {
				q.push(v);
				ex[v] = 0;
			}
		}
	}

	if (ex.count()) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 12928
#include<bits/stdc++.h>
#include<vector>
#include<cmath>
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;
typedef long long ll;
void chmin(int &a,int b){if(a>b) a=b;} //Compare two numbers and return smaller one in reference variety a

int N,M;
int a[60],b[60];
bool G[60][60];
bool visited[60];

void dfs(int to)
{
    
    visited[to]=true;

    for(int i=0;i<N;i++)
    {
        if(G[to][i]==false) continue; 
        
        if(visited[i]==true)continue;
        dfs(i);
    }
    return;
}


int main()
{
    int count=0;
    cin>>N>>M;
    for(int i=0;i<M;i++)
    {
        cin>>a[i]>>b[i];
        a[i]--,b[i]--;
        G[a[i]][b[i]]=G[b[i]][a[i]]=true;

    }

    for(int i=0;i<M;i++)
    {
        int temp=0;
        G[a[i]][b[i]]=G[b[i]][a[i]]=false;
        dfs(0);
        rep(j,0,N){
            
           // cout<<visited[j]<<endl;
            if(visited[j]==false)
            {
                temp++;
            }
            visited[j]=false;
        }
        if(temp>0)count++;
        G[a[i]][b[i]]=G[b[i]][a[i]]=true;
    }
    cout<<count<<endl;
}



Measured memory_bytes: 256
from collections import defaultdict as dd
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)

  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
    
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
N, K, L = map(int, input().split())
k = UnionFind(N)
l = UnionFind(N)
checkset = set()
res = [1] * (N + 1)
roots = dd(int)
for _ in range(K):
  x, y = map(int, input().split())
  k.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for _ in range(L):
  x, y = map(int, input().split())
  l.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for i in list(checkset):
  kr = k.Find_Root(i)
  lr = l.Find_Root(i)
  roots[(kr, lr)] += 1
#print(roots)
for i in list(checkset):
  kr = k.Find_Root(i)
  lr = l.Find_Root(i)
  res[i] = roots[(kr, lr)]
  
print(*(res[1: ]))



Measured memory_bytes: 126076
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    String s = sc.next();

    if (s.charAt(s.length() - 1) == 's') {
      s += "es";
    } else {
      s += "s";
    }

    System.out.println(s);

  }
}

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

using namespace std;

using ll = long long;

ll calc(vector<ll>& a, ll b) {
    ll res = 0;
    for (ll x : a) {
        res += abs(x - b);
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= i + 1;
    }
    sort(a.begin(), a.end());
    if (n % 2 == 0) {
        cout << min({calc(a, a[n / 2]), calc(a, a[n / 2 - 1])}) << endl;
    } else {
        cout << calc(a, a[n / 2]) << endl;
    }
    return 0;
}


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

using namespace std;

long long mod=1e9+7;

int main(){
    long long A,B,K;
    cin>>A>>B>>K;
    if(A>=K)
        cout<<A-K<<" "<<B;
    else{
        K-=A;
        A=0;
        if(B>=K)
            B-=K;
        else
            B=0;
        cout<<A<<" "<<B;
    }
	return 0;
}





Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i=l;i<=r;i++)
using namespace std;
const int maxn=200500;
typedef long long ll;
int n;
ll m;
struct node{int id; ll l,r,b,val;}a[maxn];
bool cmp(node a,node b){
    return a.val>b.val;
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        scanf("%lld%lld%lld",&a[i].b,&a[i].l,&a[i].r);
        a[i].val=a[i].l*a[i].b+a[i].r*(m-a[i].b); 
    }
    sort(a+1,a+1+n,cmp);
    ll l=0,r=n*m,ans=l; 
    while (l<=r){
        ll mid=(l+r)>>1,sum=0;
        ll cnt=mid/m,rm=mid%m,now;
        rep(i,1,n) {
            if (i<=cnt) sum+=a[i].r*(m-a[i].b);
            else sum-=a[i].b*a[i].l;
        }
        ll mx=sum;
        if (rm){
            rep(i,1,n){
                now=sum;
                if (i<=cnt) now+=a[cnt+1].val-a[i].val;
                now+=a[i].b*a[i].l;
                if (rm<=a[i].b) now+=a[i].l*(rm-a[i].b);
                else now+=a[i].r*(rm-a[i].b);
                mx=max(mx,now);
            }
        }
        if (mx>=0) r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4352
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scanf("%d %d", &a, &b)

	if a > 12 {
		fmt.Println(b)
	} else if a >= 6 {
		fmt.Println(b / 2)
	} else {
		fmt.Println(0)
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define endl "\n";
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define double long double
#define M_PI 3.14159265358979323846 
const int mod = 1e9 + 7;

int32_t main()
{
    fastio;

    int k; cin >> k;
    string s; cin >> s;
    if(s.size() <= k){
    	cout << s << endl;
    }else{
    	cout << s.substr(0,k)+"..." << endl;
    }
    return 0;
}

/*
3 1 2 4
1 2 3
*/

Measured memory_bytes: 3656
from collections import defaultdict

n, k = map(int, input().split())
a = list(map(int, input().split()))
h = defaultdict(int)
for x in a:
    h[x] += 1
ans = 0
i = 0
for key, v in sorted(h.items(), key=lambda x: -x[1]):
    i += 1
    if i > k:
        ans += v
print(ans)

Measured memory_bytes: 39352
let N = stdin.ReadLine() |> int

let xy =
    [| for _ in [ 1..N ] do
        yield (stdin.ReadLine().Split() |> Array.map int) |]

let rec fact r n =
    if n = 1 then r
    else fact (r * n) (n - 1)

let rec resolver r i j =
    if i = N then r / float (fact 1 N)
    else
        let rec loop r j =
            if j = N then resolver r (i + 1) 0
            elif i = j then loop r (j + 1)
            else
                let x = abs (xy.[i].[0] - xy.[j].[0]) * abs (xy.[i].[0] - xy.[j].[0])
                let y = abs (xy.[i].[1] - xy.[j].[1]) * abs (xy.[i].[1] - xy.[j].[1])
                loop (r + float (fact 1 (N - 1)) * sqrt (float (x + y))) (j + 1)
        loop r j

resolver 0.0 0 0 |> stdout.WriteLine


Measured memory_bytes: 13524
#include <stdio.h>
int main(void)
{
	int i,n;
	scanf("%d",&n);
	float x1[100],y1[100],x2[100],y2[100],x3[100],y3[100],x4[100],y4[100];
	for(i=0;i<n;i++){
		scanf("%f %f %f %f %f %f %f %f",&x1[i],&y1[i],&x2[i],&y2[i],&x3[i],&y3[i],&x4[i],&y4[i]);
	}
	double a1[100],a2[100],b1[100],b2[100];
	for(i=0;i<n;i++){
		a1[i]=x2[i]-x1[i];
		a2[i]=y2[i]-y1[i];
		b1[i]=x4[i]-x3[i];
		b2[i]=y4[i]-y3[i];
		if((a1[i]*b2[i])-(a2[i]*b1[i])==0){
			puts("YES");
		}
		else{
			puts("NO");
		}
	}
	return 0;
}


Measured memory_bytes: 1980
nq = str(input()).split()
n = int(nq[0])
q = int(nq[1])
p = [str(input()).split() for i in range(n)]
p = [(str(i[0]), int(i[1])) for i in p]
ans = []
time = 0
while len(p) != 0:
    t = p.pop(0)
    if t[1] > q:
        #p = [(s[0], s[1], s[2]+q) for s in p]
        time += q
        p.append((t[0], t[1]-q))
    elif t[1] <= q:
        #p = [(s[0], s[1], s[2]+t[1]) for s in p]
        ans.append((t[0], t[1]+time))
        time += t[1]
for t in ans:
    print('{0} {1}'.format(t[0], t[1]))

Measured memory_bytes: 23060
n=int(input())
v=list(map(int, input().split()))

def mergesort(a):
    def _merge_sort(a, left: int, right: int):
        if left < right:
            center = (left+right)//2

            _merge_sort(a,left,center)
            _merge_sort(a,center+1,right)

            #pは前半部をbuffにコピーする際のインデックス、jで取り出す
            p=j=0
            i=k=left

            #配列の前半部をbuffにコピー
            while i <= center:
                buff[p]=a[i]
                p+=1
                i+=1

            #後半部をコピーされた前半部と比較、小さい方をaに格納していく
            while i<= right and j < p:
                if buff[j] <= a[i]:
                    a[k]=buff[j]
                    j+=1
                else:
                    a[k]=a[i]
                    i+=1
                k+=1

            while j < p:
                a[k] =buff[j]
                k+=1
                j+=1

    n=len(a)
    #merge結果を一時的に格納
    buff=[None]*n
    _merge_sort(a,0,n-1)
    del buff

mergesort(v)

for i in range(n-1):
    v[i+1]=(v[i]+v[i+1])/2

print(v[n-1])

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

ll a[110];
// dp[i][j]???i???????????§??§j??¨????????????????????°
ll dp[110][21];

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

	int n;
	cin >> n;

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

	dp[0][a[0]] = 1;
	for(int i = 1; i < n - 1; ++i){
		for(int j = 0; j <= 20; ++j){
			ll p = j + a[i];
			if(p >= 0 && p <= 20){
				dp[i][p] += dp[i - 1][j];
			}

			ll m = j - a[i];
			if(m >= 0 && m <= 20){
				dp[i][m] += dp[i - 1][j];
			}
		}
	}

	cout << dp[n - 2][a[n - 1]] << endl;
	/*
	for(int i = 0; i < n - 1; ++i){
		for(int j = 0; j <= 20; ++j){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
*/
	return 0;
}

Measured memory_bytes: 3156
#include<stdio.h>
int a,s,d,f,g[200000],h[200000],i,j,k[200000],l,z;
int main(void)
{

	scanf("%d %d %d",&a,&s,&d);
	for(i=0;i<a;i++){
		g[i]=1;
		h[i]=i+1;
		k[i]=i-1;
	}
	k[0]=a-1;
	h[a-1]=0;
	l=0;
	/*for(i=0;i<a;i++)
		printf("k  %d h  %d\n",k[i],h[i]);*/
	for(i=0;i<s;i++){
		scanf("%d",&f);
		z=f%2;
		for(j=0;j<f;j++){
			if(z==0)	l=h[l];
			else	l=k[l];
		//	printf("j  %d\n",l);
		}
		g[l]=0;
		h[k[l]]=h[l];
		k[h[l]]=k[l];
		//printf("i=%d l=%d h=%d k=%d\n",i,l,h[k[l]],k[h[l]]);
		l=h[l];
	}
	for(i=0;i<d;i++){
		scanf("%d",&f);
		printf("%d\n",g[f]);
	}
	return 0;
}

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

using namespace std;

using dbl = long double;
using Pi = pair<int, int>;

const dbl eps = 1e-15;
#define lt(a, b) ((a)-(b) < -eps)
#define eq(a, b) (fabs((a)-(b)) < eps)

int W, H;
char mas[505][505];
Pi S, G;
vector<Pi> Bs;

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

bool in(int y, int x) {
  return 0<=y&&y<H&&0<=x&&x<W;
}

vector<vector<dbl> > bfs(const vector<Pi>& s) {
  //cout<<"!!!!!"<<endl;
  queue<Pi> que;
  vector<vector<dbl> > dist(H, vector<dbl>(W, -1));
  for(Pi p : s) {
    que.emplace(p);
    dist[p.first][p.second] = 0;
  }
  while(!que.empty()) {
    int y, x;
    tie(y, x) = que.front(); que.pop();
    //cout<<mas[y][x]<<" "<<y<<" "<<x<<endl;    
    for(int i = 0; i < 4; ++i) {
      int ny = y+dy[i], nx = x+dx[i];
      if(!in(ny, nx) || mas[ny][nx] == '#' || mas[ny][nx] == '*') continue;
      if(dist[ny][nx] == -1) {
	dist[ny][nx] = dist[y][x]+1;
	que.emplace(ny, nx);
      }
    }
  }
  return dist;
}

vector<vector<dbl> > db;
vector<vector<dbl> > dg;

bool check(dbl mb) {
  dbl sum = 0;
  int num = 0;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      if(mas[i][j] == '.') {
	if(dg[i][j] == -1 && db[i][j] == -1) continue;//assert(false);
	else if(dg[i][j] == -1) sum += db[i][j]+mb;
	else if(db[i][j] == -1) sum += dg[i][j];
	else sum += min(dg[i][j], db[i][j]+mb);
	++num;
      }
    }
  }
  assert(num > 0);
  sum /= num;
  return sum >= mb;
}

int main() {
  cin >> W >> H;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      cin >> mas[i][j];
      if(mas[i][j] == 's') S = Pi(i, j), mas[i][j] = '.';
      else if(mas[i][j] == 'g') G = Pi(i, j);
      else if(mas[i][j] == '*') Bs.emplace_back(i, j);
    }
  }

  db = bfs(Bs);
  dg = bfs({G});

  dbl ans = dg[S.first][S.second];
  //cout<<ans<<endl;
  /*
  bool flag = false;  
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      if(mas[i][j] == '.' && dg[i][j] == -1 && db[i][j] == -1) flag = true;
    }
  }
  */
  if(ans == -1) ans = DBL_MAX/2;
  else if(db[S.first][S.second] == -1) {
  //else if(flag) {
    cout << fixed << setprecision(12) << ans << endl;
    return 0;
  }

  dbl lb = 0, ub = 1e20;
  for(int i = 0; i < 200; ++i) {
    dbl mb = (lb+ub)/2;
    if(check(mb)) lb = mb;
    else ub = mb;
  }

  ans = min(ans, db[S.first][S.second]+lb);

  cout << fixed << setprecision(12) << ans << endl;  
  
  return 0;
}



Measured memory_bytes: 11068
#include <iostream>
#include <algorithm>

using namespace std;

int abs(int x){return x>=0?x:-x;}

int main() {
    int A[3], res = 0;
    cin >> A[0] >> A[1] >> A[2];
    sort(A, A+3);
    res += abs(A[0]-A[1]) + abs(A[1]-A[2]);
    cout << res << "\n";
}

Measured memory_bytes: 256
_,*S=*$<;p~((0...S.size).map{|i|d,p,q,r=0,0,1<<i;(d,p,q,r=d-1,p|q,0,p&q^q;s=r;(q|=S[-i.bit_length].to_i 2;s^=i)while(i=s&-s)>0;0<q&r&&x)while 0<q;d}.min rescue 0)

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

int main() {
	int N;
	cin >> N;
	vector<long> A(N);
	for (long& i : A) cin >> i;
	for (int i = 1; i < N; i++) A[i] += A[i - 1];
	long ans = count(A.begin(), A.end(), 0);
	unordered_map<long, long> a;
	for (long& i : A) a[i]++;
	for (const pair<long, long>& i : a) ans += (i.second - 1) * i.second / 2;
	cout << ans;
}

Measured memory_bytes: 10056