akhauriyash/Code-Regression huggingface dataset:
import std.stdio, std.conv, std.string, std.array, std.math, std.regex, std.range, std.ascii, std.numeric, std.random;
import std.typecons, std.functional, std.traits,std.concurrency;
import std.algorithm, std.container;
import core.bitop, core.time, core.memory;
import std.bitmanip;
import std.regex;

enum INF = long.max/3;
enum MOD = 10L^^9+7;

void main()
{
    auto A = scanElem;
    auto B = scanElem;
    auto C = scanElem;
  	if(A+B>=C)writeln("Yes");else writeln("No");
}

T[] scanArray(T = long)()
{
    static char[] scanBuf;
    readln(scanBuf);
    return scanBuf.split.to!(T[]);
}

dchar scanChar()
{
    import core.stdc.stdlib;
    int c = ' ';
    while (isWhite(c) && c != -1)
    {
        c = getchar;
    }
    return cast(dchar)c;
}

T scanElem(T = long)()
{
    import core.stdc.stdlib;
    static auto scanBuf = appender!(char[])([]);

    scanBuf.clear;

    int c = ' ';
    while (isWhite(c) && c != -1)
    {
        c = getchar;
    }
    while (!isWhite(c) && c != -1)
    {
        scanBuf ~= cast(char) c;
        c = getchar;
    }
    return scanBuf.data.to!T;
}

dchar[] scanString(){
    return scanElem!(dchar[]);
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define ms(a,v) memset(a,v,sizeof(a))
#define mp make_pair
#define write(x) cout<<(x)<<endl
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; }return 0; }
constexpr ll pow2(const int n) { return 1ll << n; }
const int INF = 1 << 28; const ll LINF = 1ll << 60;
const int MAX = 1e5 + 5; const int MOD = 1e9 + 7; const double EPS = 1e-6;
const int dy[4] = { 0,1,0,-1 }; const int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;
// 1. 問題よくよめえええええええええええええええええええええええええ
// 2. intオーバーフロー << * + あたり
// 3. 落ち着け

int N;
vi C;
vector<ll> cnt; // cnt[C[i]]

int main() {
    cin >> N;
    C.resize(N);
    rep(i, N) cin >> C[i];
    
    auto unq = unique(all(C));
    C.erase(unq, C.end());
    N = C.size();

    //dp.resize(N, 0);
    //dp_int.resize(N, 0);
    cnt.resize(2e5 + 5, 0);
    

    //dp[0] = 1; // ????????
    
    ll ans = 1;
    cnt[C[0] - 1]++;

    for (int i = 1; i < N; ++i) {
        ans = ans + cnt[C[i] - 1];
        ans %= MOD;
        cnt[C[i] - 1] = ans;
    }

    write(ans);
}

Measured memory_bytes: 2688
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
int main(){
    char word[500]={0};
    int total=0,N;
    while(scanf("%s",word)!=EOF){
        for(int i=0;i<strlen(word);i++){
            if(isdigit(word[i])){
                N=atoi(&word[i]);
                total+=N;
                for(;;){
                    if(isdigit(word[i+1]))i++;
                    else break;
                }
            }
        }
    }
    cout<<total<<endl;
    return 0;
}

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

using namespace std;

int main(){
	int x; cin >> x;
	int b = 1, p = 1;
	int ans = 1;
	for(int i = 2; i < 32; ++i){
		for(int j = 2; pow(i, j) <= x; ++j){
			int bef_ans = ans;
			ans = max(ans, (int)pow(i, j));
			if(bef_ans != ans){
				b = i; p = j;
			}
		}
	}
	cout << pow(b, p) << endl;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;
typedef pair<int,int> ii;

#define MAX 200010
int N;
ll K;
bool debug = 0;
vector<int> A;
vector<int> G[MAX];
bool visited[MAX];

void solve() {
  deque<int> ans, deq;
  memset(visited, false, sizeof visited);
  visited[0] = true;
  deq.pb(0);
  ans.pb(0);
  int last = -1;
  while( !deq.empty() ) {
    int cur = deq.front(); deq.pop_front();
    int nex = A[cur];
    if( visited[nex] ) {
      last = nex;
      break;
    }
    visited[nex] = true;
    deq.pb(nex);
    ans.pb(nex);
  }
  if( debug  ) {
    cout << "last = " << last << endl;
    rep(i,(int)ans.size()) {
      cout << ans[i] << " ";
    } puts("");
  }
  while( !ans.empty() && ans.front() != last ) {
    --K;
    ans.pop_front();
    if( K == 0 ) {
      cout << ans.front()+1 << endl;
      return;
    }
  }
  K %= (ll)ans.size();
  cout << ans[K]+1LL << endl;
}

int main() {
  cin >> N >> K;
  A.resize(N);
  rep(i,N) {
    cin >> A[i];
    --A[i];
  }
  solve();
  return 0;
}


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

using namespace std;

typedef long long ll;

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

ll a,b,i,temp=1;
cin>>a>>b;
ll c=min(a,b);
for(i=c;i>=1;i--)
{
  if(a%i==0&&b%i==0)
  {
    temp=i;
  break;
  }
}
cout<<a*b/temp<<endl;
return 0;
}
     


    

    

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

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

    int res=0;
    while(true)
    {
        if (*max_element(vec.begin(),vec.end())==0) break;

        int i=0;
        while(N>i)
        {
            if(vec[i]==0) ++i;
            else{
                ++res;
                while(N > i && vec[i] > 0)
                {
                    --vec[i];
                    ++i;
                }
            }
        }
    }

    cout << res << endl;
    return 0;
}


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

// ユークリッドの互除法
int gcd(int a, int b) { return b?gcd(b,a%b):a; }
int lcm(int a, int b) { return a/gcd(a,b)*b; }

int main(){
	int n,X;
    cin >> n >> X;
    VI x(n);
    rep(i,n){
        int z;
        cin >> z;
        x[i] = abs(z - X);
    }

    int ans = x[0];
    rep(i,n-1){
        ans = gcd(ans, x[i+1]);
    }

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {

  int n=0,sum=0;
  char c;

  while((c=getchar())!=EOF) {

    if('0'<=c && c<='9') {
      n*=10;
      n+=c-'0';
    }

    else {
      sum+=n;
      n=0;
    }
  }

  printf("%d\n",sum);
  return 0;

}
    
	

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define rev(i,s,e) for(i64 (i) = (s);(i) --> (e);)
#define all(x) x.begin(),x.end()

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

  K = (N - 1) * (N - 2) / 2 - K;
  if(K < 0) {
    cout << -1 << endl;
    return 0;
  }
  vector<pair<i64, i64>> ans;
  auto f = [&](i64 i, i64 j) { ans.push_back({i + 1, j + 1}); };
  
  rep(i,1,N) f(0, i);
  rep(i,1,N) rep(j,i + 1, N) {
    if(K == 0) goto FINAL;
    f(i, j);
    K--;
  }
FINAL:
  cout << ans.size() << endl;
  for(auto p: ans){
    cout << p.first << " " << p.second << endl;
  }
}


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

int main(){
    int a,b;
    cin >> a >> b;
    string ans;
    if(a>0){
        ans="Positive";
    }
    else if(a<=0&&b>=0){
        ans="Zero";
    }
    else{
        int count=1;
        for(int i=a;i<=b;i++){
            count *=-1;
        }
        if(count==1) ans="Positive";
        else if(count==-1) ans="Negative";
    }
    cout << ans << endl;
    return 0;
}


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

vector<pair<long long,long long> >prime_factorize(long long N){
    vector<pair<long long, long long>> res;
    for(long long a=2;a*a<=N;a++){
        if(N%a!=0) continue;
        long long ex=0;
        while(N%a==0){
            ex++;
            N /= a;
        }
        res.push_back({a,ex});
    }
    if(N!=1) res.push_back({N,1});
    return res;
}

int main(){
   long long N,P;
   cin >> N >> P;
   long long res=1;
   const auto &pf = prime_factorize(P);
   for(auto p:pf){
       for(int j=0;j<p.second/N;j++) res*=p.first;
   }
   cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
    int A[9];
    for (int i = 0; i < 9; ++i) cin >> A[i];
    int N;
    cin >> N;
    int b[N];
    for (int i = 0; i < N; ++i) cin >> b[i];

    bool check[9];
    for (int i = 0; i < 9; ++i) check[i] = false;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < N; ++j) {
            if (b[j] == A[i]) check[i] = true;
        }
    }
    bool bingo = false;
    if (check[0] && check[1] && check[2]) bingo = true;
    if (check[3] && check[4] && check[5]) bingo = true;
    if (check[6] && check[7] && check[8]) bingo = true;

    if (check[0] && check[3] && check[6]) bingo = true;
    if (check[1] && check[4] && check[7]) bingo = true;
    if (check[2] && check[5] && check[8]) bingo = true;

    if (check[0] && check[4] && check[8]) bingo = true;
    if (check[2] && check[4] && check[6]) bingo = true;

    if (bingo) cout << "Yes";
    else cout << "No";

    return 0;
}


Measured memory_bytes: 256
// Problem: A - Don't be late
// Contest: AtCoder - AtCoder Beginner Contest 177
// URL: https://atcoder.jp/contests/abc177/tasks/abc177_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define int long long
#define endl "\n"
#define deb(x) cout << #x << " -> " << x << endl;
#define print(x)                         \
    for (auto x_ : x) cout << x_ << " "; \
    cout << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define mod 1000000007  // 1e9 + 7
#define prec(x, y) fixed << setprecision(y) << x

void solve() {
    int d, t, s;
    cin >> d >> t >> s;
    (d <= t * s) ? cout << "Yes\n" : cout << "No\n";
}

int32_t main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
}

Measured memory_bytes: 3596
#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

#なお、任意の整数 M に対して M の −2 進数表現が一意に定まることが証明できます。
#2桁ごとに見るとよかった（もう実験したよ）
def resolve():
    N,A,B=pin()
    S=input()
    a=0
    b=0
    for s in S:
        #print(s)
        if s=="c":
            print("No")
            continue
        elif s=="a":
            a+=1
        else:
            
            if b>=B:
                print("No")
                continue
            b+=1
        #print(s,a+b)
        if (a+b)<=(A+B):
            print("Yes")
        else:print("No")
    

#%%submit!
resolve()

Measured memory_bytes: 53464
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import bisect

n=int(input())
arr=factorization(n) 
#print(arr)

ans=0
li=[1,3,6,10,15,21,28,36,45]

for ar in arr:
    e=ar[1]
    ans+=bisect.bisect(li,e)
if n==1:
    print('0')
else:    
    print(ans)
    

Measured memory_bytes: 9492
import math
N=int(input())
def beki(x):
    b=2
    while b <= math.sqrt(x):
        p=2
        while b**p <=x:
            if b**p == x:
                return True
                break
            else:
                p+=1
        else:
            b+=1
    else:
        return False
while N>=2:
    if beki(N)==True:
        print(N)
        break
    else:
        N-=1
else:
    print(1)

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#define MP make_pair
using ll = long long;
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int>A(N);
  for(int i=0; i < N; i++){
    cin >> A[i];
  }
  int i=1;
  int prei = 0;
  int cnt = 0;
  for(;;){
    prei = i;
    i = A[i-1];
    A[prei-1] = -1;
    if(A[i-1] == -1){
      cout << -1 << endl;
      break;
    }
    cnt++;
    if(i == 2){
      cout << cnt << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 640
//#define anjn
//      Anjan Agarwala - anjn98

//#define opti
#ifdef opti
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, 
                  tree_order_statistics_node_update> ordered_set;

//ll power(ll x,ll y,ll p){ll r=1; x=x%p; while(y){ if(y&1) r= r*x%p; y=y>>1; x=x*x%p; } return r; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int csrand(int l=0, int r=1e9){
  uniform_int_distribution<int> uid(l, r);
  return uid(rng);
}

#define PR(x) cout<<#x<<": "<<x<<"\n";
#define PR1(x,y) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"\n";
#define PR2(x,y,z) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<"\n";
#define ED cout<<'\n';

#define IO              ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FILEIO          freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define all(v)          v.begin(),v.end()
#define endl            '\n'
#define fr1(j,n)        for(int j=0;j<n;j++)
#define fr(n)           for(int i=0;i<n;i++)
#define trav(x,s)       for(auto x:s)
#define PB              push_back
#define pii             pair<int,int>
#define pll             pair<long long int,long long int>
#define F               first
#define S               second 
#define binf            2000000000000000001
#define mod             1000000007

const int N=2e5+99; 



int32_t main() 
{
    IO

        

    int n,d;
    cin>>n>>d;

    vector<vector<double>> a;
    a.resize(n);

    fr(n)
    {
        a[i].resize(d);
        fr1(j,d) cin>>a[i][j];

    }

    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            ll aa;
            double bb=0;

            fr1(k,d)  bb+=pow(a[i][k]-a[j][k],2);

            aa=bb;
          //  PR1(aa,bb)
            aa=sqrt(aa);
            bb=sqrt(bb);
           // PR1(aa,bb)
            if(bb-aa == 0.0f ) ans++;
        }
    cout<<ans<<endl;


}




 
    
    

Measured memory_bytes: 256
n, m = map(int, input().split())
inf = 10**10
G = [{} for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    G[l-1][r-1] = d
    G[r-1][l-1] = -d
V = [False for i in range(n)]
D = [inf for i in range(n)]
for i in range(n):
    if V[i]:
        continue
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        V[j] = True
        for k in G[j].keys():
            if not V[k]:
                Q.append(k)
            if D[k] == inf:
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')

Measured memory_bytes: 67604
fun main(arg: Array<String>) {
    val N = nextInt()
    val P = listOfInt(-1).toIntArray()
    var ans = 0
    for (n in 0 until N) {
        if (P[n] == n) {
            ans += 1
            if (n < N - 1) P.swap(n, n + 1)
        }
    }
    println(ans)
}
fun IntArray.swap(n: Int, m: Int) {
    val w = this[n]
    this[n] = this[m]
    this[m] = w
}

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun listOfString() = next().split(" ")
fun listOfInt(D: Int = 0) = listOfString().map { Integer.parseInt(it) + D }
fun listOfInt(vararg deltas: Int) = listOfString().map { Integer.parseInt(it) }.mapIndexed { index, int -> int + deltas[index % deltas.size] }


Measured memory_bytes: 51716
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <cmath>
#include <stdio.h>
#include <functional>

#define REP(i,a) for(int (i)=0;(i)<(a);i++)
#define RREP(i,a,b) for(int (i)=(a);(i)<(b);i++)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define vi vector<int> 
typedef long long ll;
using namespace std;

int main(void){
    ll H,W;
    cin>>H>>W;
    ll ans=99999999;
    if(H%3==0 || W%3==0){
        cout<<"0";
    }else{
        ll S1=0,S2=0,S3=0;
        ll H2=(int)H/2;
        ll W2=(int)W/2;
        ll tmp;
        RREP(i,1,W){
            S1=H2*i;
            S2=(H-H2)*i;
            S3=(W-i)*H;
            tmp=max({S1,S2,S3})-min({S1,S2,S3});
            ans=min(ans,tmp);
        }
        RREP(i,1,H){
            S1=W2*i;
            S2=(W-W2)*i;
            S3=(H-i)*W;
            tmp=max({S1,S2,S3})-min({S1,S2,S3});
            ans=min(ans,tmp);
        }
        ll I1= (ll)H/3,I2=(ll)(H-I1)/2,I3=H-I1-I2;
        S1=I1*W;
        S2=I2*W;
        S3=I3*W;
        tmp=max({S1,S2,S3})-min({S1,S2,S3});
        ans=min(ans,tmp);
        ll X1= (ll)W/3,X2=(ll)(W-X1)/2,X3=W-X1-X2;
        S1=X1*H;
        S2=X2*H;
        S3=X3*H;
        tmp=max({S1,S2,S3})-min({S1,S2,S3});
        ans=min(ans,tmp);

        cout<<ans;
    }


    return 0;
}

Measured memory_bytes: 384
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b = LS()

    return "".join([b,a])


print(main())




Measured memory_bytes: 7756
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
"""
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = monster[k][1]
    ans += monster[k][1]
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = min(nextk, j)
        break
    k = nextk
"""
final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


print(ans)


Measured memory_bytes: 129636
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REPS(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
using ll = long long;
using ld = long double;

int main(void) {
    ll K, N;
    cin >> K >> N;
    ll A[N];
    REP (i, N) {
        cin >> A[i];
    }
    ll d = 0;
    for (int i = 1; i < N; i++) {
        d = max(d, A[i] - A[i-1]);
    }
    d = max(d, K-A[N-1]+A[0]);
    cout << K - d << endl;
}

Measured memory_bytes: 1920
#include<stdio.h>
int pop(void);
void push(int);

int stack_size=0,stack[20000];

int main(){

  int i,j,n;
  int k_size=0,k1[20000],k2[20000];
  int total=0;
  char s[20000];

  scanf("%s",s);
  for(i=0;s[i]!='\0';i++){
    if(stack_size<=0 && s[i]=='/'){
      continue;
    }
    else if(s[i]==92){
      push(i);
    }
    else if(s[i]=='/'){
      n=pop();
      if(n>k1[k_size-1] || k_size==0){
	k1[k_size]=n;
	k2[k_size]=i-n;
	k_size++;
      }
      else{
	k1[k_size-1]=n;
	k2[k_size-1]=i-n+k2[k_size-1];
	while(k1[k_size-1]<k1[k_size-2] && k_size>=2){
	  k1[k_size-2]=k1[k_size-1];
	  k2[k_size-2]=k2[k_size-1]+k2[k_size-2];
	  k_size--;
	}
      }
    }
  }
  for(i=0;i<k_size;i++){
    total+=k2[i];
  }
  printf("%d\n",total);
  if(k_size==0) printf("%d\n",k_size);
  else printf("%d ",k_size);
  
  for(i=0;i<k_size;i++){
    if(i==k_size-1) printf("%d\n",k2[i]);
    else printf("%d ",k2[i]);
  }
  
  return 0;
}
int pop(){
  if(stack_size<=0) return 0;
  return stack[--stack_size];
}
void push(int i){
  stack[stack_size]=i;
  stack_size++;
}



Measured memory_bytes: 2108
#include <iostream>
#include <string>
using namespace std;
int main(){
string a;
cin >> a;
int b;
b=a.size();
int c;
c=0;
int e[b];
while(c<b){
string d(a,c,1);
if(d=="J"){e[c]=1;}
if(d=="O"){e[c]=2;}
if(d=="I"){e[c]=3;}
c=c+1;}
int f;
f=0;
int g;
g=0;
int  h;
int i;
c=0;
while(c<b){
h=0;
i=0;
if(e[c]==2){f=f+1;}
if(e[c]==3){if(f>g){if(c>2*f-1){if(c<b-f+1){while(h<f){if(e[c-f-1-h]!=1){i=1;} if(e[c+h]!=3){i=1;} h=h+1;} if(i==0){g=f;} f=0;}}}}
if(e[c]==1){f=0;}
c=c+1;
}
cout << g<<endl;
}

Measured memory_bytes: 6196
#include <cstdio>
#include <cassert>
#include <functional>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <iterator>
#include <queue>
#include <utility>

using namespace std;

#define whole(xs) xs.begin(), xs.end()

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{ ";
    for (int i = 0; i < v.size(); i++) {
        os << v[i] << " ";
    }
    os << "}";
    return os;
}

int N;
vector<string> SS;
int L[10][10];
string cache[10][1 << 10];

int common(const string& s, const string& t) {
    int l = min(s.size(), t.size());
    for (int i = l; i >= 0; i--) {
        bool flag = true;
        for (int j = 0; j < i; j++) {
            if (s[s.size() - i + j] != t[j]) {
                flag = false;
                break;
            }
        }
        if (flag) return i;
    }
    assert(0);
}

bool input() {
    cin >> N;
    if (N == 0) return false;
    vector<string> v(N);
    SS.clear();
    for (int i = 0; i < N; i++) cin >> v[i];
    vector<bool> remove(N, false);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            if (v[i] != v[j] && search( whole(v[i]), whole(v[j]) ) != v[i].end()) {
                remove[j] = true;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        if (!remove[i]) {
            SS.push_back(v[i]);
        }
    }
    N = SS.size();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            L[i][j] = common(SS[i], SS[j]);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < (1 << N); j++) {
            cache[i][j] = "_";
        }
    }
    return true;
}

bool comp(const string& s, const string& t) {
    if (s == "_") return false;
    if (t == "_") return true;
    if (s.size() == t.size()) return s < t;
    return s.size() < t.size();
}
#define MIN(s, t) min((s), (t), comp)

string dfs(int v, int used) {
    if (used == (1 << N) - 1) return "";
    if (cache[v][used] != "_") return cache[v][used];
    string ret = "_";
    for (int i = 0; i < N; i++) {
        if (used & (1 << i)) continue;
        const string& t = SS[i];
        int l = L[v][i];
        ret = MIN(ret, t.substr(l, t.size() - l) + dfs(i, used | 1 << i));
    }
    return cache[v][used] = ret;
}

int main() {
    while (input()) {
        string ans = "_";
        for (int i = 0; i < N; i++) {
            ans = MIN(ans, SS[i] + dfs(i, 1<<i));
        }
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int x;
  cin >> x;
  if (x <= 599) {
    cout << 8 << '\n';
  } else if (x <= 799) {
    cout << 7 << '\n';
  } else if (x <= 999) {
    cout << 6 << '\n';
  } else if (x <= 1199) {
    cout << 5 << '\n';
  } else if (x <= 1399) {
    cout << 4 << '\n';
  } else if (x <= 1599) {
    cout << 3 << '\n';
  } else if (x <= 1799) {
    cout << 2 << '\n';
  } else if (x <= 1999) {
    cout << 1 << '\n';
  }

  return 0;
}

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

#define ED return 0;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) long(pow(x,y))
const long long int mod = 1000000007;
unsigned long long int gcd(unsigned long long int a, unsigned long long int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

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

    int N, x;
    cin >> N >> x;
    int ans = 0;
    vector<int> vec (N);
    for(int i = 0;i < N;i++){
        cin >> vec.at(i);
    }
    SORT(vec);
    for(int i = 0;i < N;i++){
        if(vec.at(i) <= x){
            x -= vec.at(i);
            ans++;
        }
        else{
            break;
        }
    }
    if(x > 0 && ans == N)ans--;
    cout << ans << endl;
}


Measured memory_bytes: 256
//Joy Shree Kriskna
    #include<bits/stdc++.h>
    #define fast  ios_base::sync_with_stdio(false);cin.tie(NULL)
    #define rep(i,n) for(i=0;i<n;i++)
    #define rep1(i,n) for(i=n-1;i>=0;i--)
    #define rep2(j,t) for(j=1;j<=t;j++)
    #define rep3(i,a,b) for(i=a;i<=b;i++)
    #define PI acos(-1)
    #define remove(s) s.erase(unique(s.begin(),s.end()),s.end());
    #define e return 0
    //#define lcm(a,b) ((a*b)/__gcd(a,b))
    #define endl "\n"
    #define al(v) v.begin(),v.end()
    #define ll long long
    using namespace std;
    void solve()
    {
       int n,k;
       string s;
       cin>>s;
        int c=0,i;
       if(s[1]=='R')
       {c++;
      if(s[0]=='R')c++;
      if(s[2]=='R')c++;
       }
       else
       {
           for(i=0;i<=2;i++)
            if(s[i]=='R')c=1;
       }
       cout<<c<<endl;
    }

    int main()
      {
           fast;
           int i,n,t;
           solve();
      }
//arupsaha52
//1704052_Arup


Measured memory_bytes: 3648
#include <bits/stdc++.h>
 
using namespace std;
 
using usize = ::std::size_t;
using u64 = ::std::int_least64_t;
//using u64 = int;
static constexpr u64 Inf = ::std::numeric_limits<u64>::max() / 2;


int main(int argc, char *argv[])
{
    
 
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> low(N+2, 0), up(N+2,0);
    vector<vector<int>> dp(N+2, vector<int>(N + 2, 0)),dp_buffer(N+2, vector<int>(N + 2, 0));
    for (int i = 1; i <= M; i++) {
        int L, R;
        cin >> L >> R;
        dp_buffer[L][R]++;
        dp[L][R]++;
    }
    
    for (int i = 0; i <= N+1; i++) {
        for (int j = i; j <= N+1; j++) {
            if(!dp_buffer[i][j]) continue;
            for (int ii = 0; ii <= i; ii++) {
                for (int jj = j; jj <= N+1; jj++) {
                    if(ii == i && jj == j) continue;
                    dp[ii][jj] += dp_buffer[i][j];
                }
            }
        }
    }
    
    while (Q--) {
        int p, q;
        cin >> p >> q;
        cout << dp[p][q] << endl;
    }
    
    return 0;
    
}


Measured memory_bytes: 5280
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 10007
#define INF 1e18
#define fcout cout << fixed << setprecision(15)
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

int n;
string s;
vector<int> a;
int dp[1010][8];

void print(int n) {
	if(!n) return ;
	if(n & 1) cout << "J";
	if(n & 2) cout << "O";
	if(n & 4) cout << "I";
	cout << " ";
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> n >> s;
	a.push_back(1);
	rep(i, n) {
		if(s[i] == 'J') a.push_back(1);
		if(s[i] == 'O') a.push_back(2);
		if(s[i] == 'I') a.push_back(4);
	}

	dp[0][1] = 1;

	rep(i, n) {
		rep(now, 8) {
			rep(nxt, 8) {
				if((nxt & a[i+1]) && (now & nxt)) {
					dp[i+1][nxt] += dp[i][now], dp[i+1][nxt] %= MOD;
				}
			}
		}
	}

	// rep(i, n+1) {
	// 	rep(j, 8) {
	// 		if(dp[i][j]) print(j);
	// 	}
	// 	cout << endl;
	// }

	int ans = 0;
	rep(i, 8) ans += dp[n][i], ans %= MOD;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3156
IDENTIFICATION DIVISION.
PROGRAM-ID. 173C.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP        PIC X(21).
01 H          PIC 9(02).
01 W          PIC 9(02).
01 K          PIC 9(02).
01 CW         PIC 9(02).
01 CB         PIC 9(02).
01 CB-W       PIC 9(02).
01 TBL1.
   03 TBL2    OCCURS 6.
      05 CS   PIC X(06).
      05 C-R  REDEFINES CS.
         07 C PIC X(01) OCCURS 6. 
01 TBL-SV     PIC X(36).
01 I          PIC 9(04) COMP.
01 J          PIC 9(04) COMP.
01 I1         PIC 9(04) COMP.
01 J1         PIC 9(04) COMP.
01 S          PIC 9(02).
01 AMR        PIC 9(01).
01 CNT        PIC 9(04) COMP.
01 OUT        PIC ZZZ9.
*>
PROCEDURE DIVISION.
  ACCEPT INP.
  UNSTRING INP DELIMITED BY ' '
      INTO H W K.
*>
  PERFORM VARYING I FROM 1 BY 1 UNTIL I > H
    ACCEPT CS(I)
    PERFORM VARYING J FROM 1 BY 1 UNTIL J > W
      IF (C(I J) = '#')
        ADD 1 TO CB
      ELSE
        ADD 1 TO CW
      END-IF
    END-PERFORM
  END-PERFORM.
*>
  MOVE TBL1 TO TBL-SV.
*>
  IF (CB < K)
    MOVE 0 TO CNT         
  ELSE
    PERFORM VARYING I FROM 0 BY 1 UNTIL I > 2 ** H - 1
      PERFORM VARYING J FROM 0 BY 1 UNTIL J > 2 ** W - 1
        MOVE TBL-SV TO TBL1
*>
        MOVE I TO S
        PERFORM VARYING I1 FROM 1 BY 1 UNTIL I1 > H
          DIVIDE S BY 2 GIVING S REMAINDER AMR
          IF AMR = 1
            PERFORM VARYING J1 FROM 1 BY 1 UNTIL J1 > W  
              MOVE '*' TO C(H - I1 + 1 J1)
            END-PERFORM
          END-IF
        END-PERFORM
*>
        MOVE J TO S
        PERFORM VARYING J1 FROM 1 BY 1 UNTIL J1 > W
          DIVIDE S BY 2 GIVING S REMAINDER AMR
          IF AMR = 1
            PERFORM VARYING I1 FROM 1 BY 1 UNTIL I1 > H  
              MOVE '*' TO C(I1 W - J1 + 1)
            END-PERFORM
          END-IF
        END-PERFORM
*>
        MOVE 0 TO CB-W
        INSPECT TBL1 TALLYING CB-W FOR ALL '#'
        IF (CB-W = K)
          ADD 1 TO CNT
        END-IF
      END-PERFORM
    END-PERFORM
  END-IF.
*>
  MOVE CNT TO OUT.
  DISPLAY FUNCTION TRIM(OUT).
  STOP RUN.


Measured memory_bytes: 3880
/*
g++ -std=c++11 -o2 -Wall ABC098B.cpp -o ./out/ABC098B.out
./out/ABC098B.out
*/

#include <bits/stdc++.h>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define tr(c, i) for (iter(c) != (c).begin(); i != (c).end(); ++i)
#define pb push_back
#define mp make_pair

typedef long long ll;

int xx[26];
int yy[26];

int main() {
//  freopen("./input/input.txt", "r", stdin);
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  string s;
  cin >> n;
  cin >> s;
  int ans = 0;
  for (int i = 1; i < n; ++i) {
    fill(xx, xx + 26, 0);
    fill(yy, yy + 26, 0);
    for (int j = 0; j < i; ++j) {
      int c = s[j] - 'a';
      ++xx[c];
    }
    for (int j = i; j < n; ++j) {
      int c = s[j] - 'a';
      ++yy[c];
    }
    int temp = 0;
    for (int k = 0; k < 26; ++k) {
      if (xx[k] > 0 && yy[k] > 0) {
          ++temp;
      }
    }
    ans = max(ans, temp);
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define ll long long int
long long  INF=1e9+5;
void max_self(ll& a,ll b)
{
    a=max(a,b);
}

int main()
{   ios_base::sync_with_stdio(0);
     cin.tie(0);
    ll n,w;
    cin>>n>>w;
    vector<ll> dp(w+1);
    for(ll item=0;item<n;item++)
    {
        ll weight,value;
        cin>>weight>>value;
      for(ll weight_alredy=w-weight;weight_alredy>=0;weight_alredy--)
        {
            max_self(dp[weight_alredy+weight],dp[weight_alredy]+value);
        }
    }
    ll answer =0;
    for(ll i=0;i<=w;i++)
    {
        max_self(answer,dp[i]);
    }
    cout<<answer<<"\n";
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M;
  cin >> N >> M;
  vector<int> num_roads(N);
    
  for(int i=0;i<M;i++){
    int a, b;
    cin >> a >> b;
    num_roads.at(a-1)++;
    num_roads.at(b-1)++;
  }
  
  for(int i=0;i<N;i++){
    cout << num_roads.at(i) << endl;
  }
  
}


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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    auto na = count(s.begin(), s.end(), 'a');
    auto nb = count(s.begin(), s.end(), 'b');
    auto nc = count(s.begin(), s.end(), 'c');

    if (max({na, nb, nc}) - min({na, nb, nc}) <= 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
const ll mod=1e+9+7;
int main(void){
    int n;cin>>n;
    map<pair<ll,ll>,int> mp;
    int zero=0;
    rep(i,n){
        ll a,b;cin>>a>>b;
        if(a==0&&b==0){
            zero++;
            continue;
        }
        ll g=gcd(a,b);//片方が0だともう片方の絶対値が出てくる
        a/=g;b/=g;
        /*if(b<0||(b==0&&a<0)){
            b*=-1;a*=-1;//第3象限と第4象限の座標をそれぞれ第1象限と第2象限にまとめる
        }*/
        mp[{a,b}]++;
        mp[{-a,-b}]+=0;
        mp[{b,-a}]+=0;
        mp[{-b,a}]+=0;
    }
    vector<ll> s(2*n+1,1);
    rep(i,n*2){
        s[i+1]=s[i]*2;
        s[i+1]%=mod;
    }
    ll res=1;
    for(auto& p:mp){
        ll a=p.first.first,b=p.first.second;
        int x=p.second;
        if(x==-1)continue;//すでにtで見られている
        x+=mp[{-a,-b}];
        int t=mp[{-b,a}]+mp[{b,-a}];
        ll tmp=1;
        tmp+=s[x]-1;tmp%=mod;
        tmp+=s[t]-1;tmp%=mod;
        res*=tmp;res%=mod;
        mp[{-b,a}]=-1;mp[{-a,-b}]=-1;mp[{a,b}]=-1;mp[{b,-a}]=-1;
        //cout<<a<<" "<<b<<" "<<x<<" "<<t<<" "<<res<<endl;
    }
    res+=zero;
    res=(res+mod-1)%mod;
    cout<<res<<endl;
}


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

using namespace std;

#define int long long

signed main()
{
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		if (i % 3 != 0 && i % 5 != 0) sum += i;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

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

typedef long long ll;



int main() {
    char zero = '0';
    string N;
    cin >> N;
    int SN=0;
    REP(i,N.size()) SN+=N[i]-zero;
    int iN = stoi(N);
    if (iN%SN == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll MOD = 1e9 + 7;
ll H, N, M, L, K, W, X, Y, Z;
ll ans = 0;
int main() {
	cin >> N >> M >> X >> Y;
	int maxX = -100;
	int minY = 100;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		maxX = max(x, maxX);
	}
	for (int i = 0; i < M; i++) {
		int y;
		cin >> y;
		minY = min(y, minY);
	}
	if ((maxX < Y && X < minY) && X < Y&&maxX < minY)cout << "No War" << endl;
	else cout << "War" << endl;
}


Measured memory_bytes: 256
n, p = map(int, input().split())
if n==1:
  print(p)
  exit()
elif p==1 or n>=60:
  print(1)
  exit()
for i in range(int(p**(1/n))+2)[::-1]:
  if p%(i**n)==0:
    print(i)
    exit()

Measured memory_bytes: 9408
import java.util.Scanner;

public class Main{
	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		String str = scn.nextLine();
		char[] S = str.toCharArray();
		long K = scn.nextLong();
		int ans = 0;
		for(int i = 0;i < str.length();i++) {
			if((S[i])=='1') {
				K--;
			}else{
				ans = i;
				break;
			}
			if(K==0) {
				ans = i;
				break;
			}
		}
		System.out.println(S[ans]);
		scn.close();
	}
}


Measured memory_bytes: 24148
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

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

def main():
    s,w = readInt()
    if s>w:
        print('safe')
    else:
        print('unsafe')
    return

if __name__=='__main__':
    main()

Measured memory_bytes: 9116
#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n;
	cin>>n;
	string s="";
	while(n!=0){
		int k=n%26;
		if(k==0){
			k=26;
			n--;
		}
		s=(char)(k+'a'-1)+s;
		n/=26;
	}
	cout<<s<<endl;
	return 0;
}

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

typedef pair<int, int> P;
typedef pair<P, P> PP;
int n;
const int INF=10000000;
vector<P> G[101];
int d[101][3][3];

int dijkstra(){
	priority_queue<PP, vector<PP>, greater<PP> > que;
	for(int i=0;i<=100;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				d[i][j][k]=INF;
			}
		}
	}
	que.push(PP(P(1,0),P(0,0)));
	while(que.size()){
		PP p=que.top();que.pop();
		int pn=p.first.first,pc=p.first.second,pq=p.second.first,pu=p.second.second;
		if(pq!=1 && pn==n)return pc;
		if(pu && pq<2){
			pq++;
			for(int i=0;i<G[pn].size();i++){
				int t=G[pn][i].first;
				int c=pc;
				if(d[t][pu][pq]>c){
					d[t][pu][pq]=c;
					que.push( PP(P(t,c),P(pq,pu)) );
				}
			}
			continue;
		}
		for(int i=0;i<G[pn].size();i++){
			int t=G[pn][i].first;
			int c=pc+G[pn][i].second;
			if(d[t][pu][pq]>c){
				d[t][pu][pq]=c;
				que.push( PP(P(t,c),P(pq,pu)) );
			}
		}
		if(!pu){
			pq++,pu++;
			for(int i=0;i<G[pn].size();i++){
				int t=G[pn][i].first;
				int c=pc;
				if(d[t][pu][pq]>c){
					d[t][pu][pq]=c;
					que.push( PP(P(t,c),P(pq,pu)) );
				}
			}
		}
	}
	return -1;
}

int main(void){
	int m;
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)break;
		for(int i=0;i<m;i++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			G[a].push_back( P(b,c) );
			G[b].push_back( P(a,c) );
		}
		printf("%d\n",dijkstra());
		for(int i=0;i<101;i++)G[i].clear();
	}
    return 0;
}

Measured memory_bytes: 0
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())

ans = 0
s = set()

while N not in s:
    s.add(N)
    if N%2==0:
        N //= 2
    else:
        N = N*3+1
    ans += 1

print(ans+1)

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

using namespace std;

#define pb push_back

const int N = 1e5 + 5, mod = 1e9 + 7;
int n, dp[2][N];
vector<int> gr[N];

void dfs (int u, int prv) {
    dp[0][u] = dp[1][u] = 1;
    for (int v : gr[u]) if (v != prv) {
        dfs(v, u);
        dp[1][u] = 1LL * dp[1][u] * dp[0][v] % mod;
        dp[0][u] = 1LL * dp[0][u] * (dp[1][v] + dp[0][v]) % mod;
    }
}

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

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        gr[u].pb(v);
        gr[v].pb(u);
    }

    dfs(1, 1);

    cout << (dp[1][1] + dp[0][1]) % mod;

    return 0;
}


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

int main() 
{
	int A,B; 
	cin>>A>>B;
	
	int a1=100*A/8;
	if ((100*A)%8!=0) 
		a1++;
		
	int a2=100*(A+1)/8;
	if ((100*(A+1))%8==0) 
		a2--;
		
	int b1=10*B,b2=10*(B+1); 
	
	b2--;
	
	if (a1>b1) 
		swap(a1,b1), swap(a2,b2);
	
	if (a2<b1)
		cout<<-1<<endl;
	else 
		cout<<b1<<endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var i, j int
	fmt.Scanf("%2d%2d", &i, &j)
	if i >= 1 && i <= 12 && j >= 1 && j <= 12 {
		fmt.Printf("AMBIGUOUS\n")
	} else if i >= 1 && i <= 12 && (j == 0 || j >= 13) {
		fmt.Printf("MMYY\n")
	} else if (i == 0 || i >= 13) && j >= 1 && j <= 12 {
		fmt.Printf("YYMM\n")
	} else {
		fmt.Printf("NA\n")
	}
}


Measured memory_bytes: 512
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
int n;
#define MAXN 19
struct state
{
	long long x,y;
	friend state operator + (state a,state b)
	{
		state res;
		if(a.x >= b.x){res.x = a.x;res.y = max(a.y,b.x);}
		else {res.x = b.x;res.y = max(a.x,b.y);}
		return res;
	}
}f[1 << MAXN];
void FMT(state f[],int l)
{
	for(int i = 0;i < l;++i)
	{
		for(int j = 0;j < (1 << l);++j)
		{
			if(((j >> i) & 1) == 0)f[j | (1 << i)] = f[j | (1 << i)] + f[j];
		}
	}
	return;
}
long long ans[1 << MAXN];
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < (1 << n);++i)
	{
		scanf("%lld",&f[i].x);
		f[i].y = -9999999999;
	}
	FMT(f,n);
	for(int i = 0;i < (1 << n);++i)ans[i] = f[i].x + f[i].y;
	for(int i = 1;i < (1 << n);++i)ans[i] = max(ans[i],ans[i - 1]);
	for(int i = 1;i < (1 << n);++i)printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 13312
N,W = list(map(int,input().split()))
w = [0]*N
v = [0]*N

v_max = 0
for i in range(N):
	w[i],v[i] = list(map(int,input().split()))
	v_max += v[i]

inf = float("inf")
dp = [[inf]*(v_max+1) for i in range(N)]
dp[0][v[0]] = w[0]
for i in range(N):
	dp[i][0] = 0

for i in range(1,N):
	for v_temp in range(1,v_max+1):
		if v_temp-v[i] >= 0:
			dp[i][v_temp] = min(dp[i-1][v_temp],dp[i-1][v_temp-v[i]]+w[i])
		else:
			dp[i][v_temp] = dp[i-1][v_temp]

ans = 0
for v_temp in range(v_max+1):
	if dp[N-1][v_temp] <= W:
		ans = v_temp

print(ans)
	


Measured memory_bytes: 372424
N=int(input())
if N%2==0:
    L=[]
    for i in range(int(N//2)):
        L.append([1+i,N-i])
    #print(L)
else:
    L=[[N]]
    for i in range(int(N//2)):
        L.append([1+i,N-1-i])
    #print(L)

if N==3 or N==4:
    print((N-2)*2)
else:
    if N%2==0:
        print(N*2)
    else:
        print((N-1)*2)
    
for i in range(len(L)-1):
    for j in range(len(L[i])):
        for k in range(len(L[i+1])):
            print(L[i][j],L[i+1][k])
if N==3 or N==4:
    exit()
else:
    for j in range(len(L[len(L)-1])):
        for k in range(len(L[0])):
            print(L[len(L)-1][j],L[0][k])

Measured memory_bytes: 3064
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <ctime>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <iomanip>
#include <bitset>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define SZ(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define pi acos(-1)
#define mod 1000000007
#define inf 1000000007
#define ll long long
#define ull unsigned long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define N 200010
#define _DEBUG
template <class U,class T> void Max(U &x, T y){if(x<y)x=y;}
template <class U,class T> void Min(U &x, T y){if(x>y)x=y;}
template <class T> void add(int &a,T b){a=(a+b)%mod;}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

int pow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1LL*ans*a%mod;
        a=1LL*a*a%mod;b>>=1;
    }
    return ans;
}
int pow(int a,int b,int c){
    int ans=1;
    while(b){
        if(b&1)ans=1LL*ans*a%c;
        a=1LL*a*a%c;b>>=1;
    }
    return ans;
}

char s[N];
pair<char,int>a[N];
int main(){
    //srand(time(NULL)+clock());
    int T,ca=0,k,i,j,m=0,n,K;
    //double start=clock();
    scanf("%d%d%s",&n,&m,s);
    char c,b;
    rep(i,0,m){
        getchar();
        scanf("%c %c",&c,&b);
        a[i]={c,b=='L'?-1:1};
    }
    int l=0,r=n-1;
    while(l<=r){
        int x=(l+r)>>1, y=x;
        rep(i,0,m)if(a[i].x==s[x]){
            x+=a[i].y;
            if(x<0||x>=n)break;
        }
        if(x<0)l=y+1;
        else r=y-1;
    }
    int L=l;
    l=L,r=n-1;
    while(l<=r){
        int x=(l+r)>>1, y=x;
        rep(i,0,m)if(a[i].x==s[x]){
            x+=a[i].y;
            if(x<0||x>=n)break;
        }
        if(x>=n)r=y-1;
        else l=y+1;
    }
    int R=r;
    printf("%d\n",max(0,R-L+1));
    //cerr<<(1.*clock()-start)/CLOCKS_PER_SEC<<"\n";
}



Measured memory_bytes: 2048
(function main() {
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n1 = Number(lines.shift());
  const arr1 = lines.shift().split(' ').map(Number);
  const n2 = Number(lines.shift());
  const arr2 = lines.shift().split(' ').map(Number);

  const solve = (i, m) => {
    if (m == 0) return true;
    if (i >= n1) return false;
    let res = solve(i + 1, m) || solve(i + 1, m - arr1[i])
    return res
  };

  arr2.map(m => solve(0, m) ? 'yes' : 'no').forEach(res => console.log(res));
})();



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

int main(){

    int n;
    int maxm=0;
    cin>>n;
    map<string,int> m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        m[s]++;
    }
    for(pair<string,int>p:m){
        maxm=max(maxm,p.second);
    }
    for(pair<string,int>p:m){
        if(p.second==maxm) cout<<p.first<<endl;
    }

    return 0;
}

Measured memory_bytes: 25216