akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>	
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ld long double
#define pii pair <int, int>
#define sz(a) (int)(a.size()) 
#define resize(v) v.resize(unique(all(v)) - v.begin()); 
#define all(a) a.begin(), a.end()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)

// random_device rd; mt19937 g(rd());    
                                        	
using namespace std;
using namespace __gnu_pbds;
 
void Fast_Read_Out()
{
    ios_base::sync_with_stdio(0);
    cin.tie(), cout.tie();
}
 
void Random()
{
    unsigned int seed;                                                                        
    asm("rdtsc" : "=A" (seed));
    srand(seed);        
}
 
unsigned int Time()
{
     unsigned int time = clock() / 1000.00;                           
     return time;
}

template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
const int mod = (int)1e9 + 7;
const int N = (int)4e6 + 123;

int fact[N];

int mult(int a, int b)
{
	return 1ll * a * b % mod;
}

int add(int a, int b)
{
	a += b;
	if(a < 0) a += mod;
	if(a >= mod) a %= mod;
	return a;
}

int Binpow(int a, int n)
{
	if(!n) return 1;
	if(n & 1) return mult(Binpow(a, n - 1), a);
	else
	{
		int b = Binpow(a, n / 2);
		return mult(b, b);
	}
}

int C(int n, int k)       
{
	if(k > n) return 0;
	int up = fact[n];
	int down = mult(fact[k], fact[n - k]);
	return mult(up, Binpow(down, mod - 2));
}

string s;
int k;
long long ans;
set <string> d;

bool Compare(string s1, string s2)
{
	for(int i = 0; i < sz(s1); i++) 
	{
		if(s1[i] > s2[i]) return 1;
		else if(s2[i] > s1[i]) return 0;
	}
	return 0;
}
 
int main ()
{
	#ifdef JUDGE
		freopen("input.txt", "r", stdin);
	#endif	
	Fast_Read_Out();
	Random();   
	fact[0] = 1;
	for(int i = 1; i <= 1000000; i++) fact[i] = mult(fact[i - 1], i);
	cin >> s >> k;
	for(int sz = 1; sz <= sz(s) - 1; sz++) ans += 9 * C(sz - 1, k - 1) * Binpow(9, k - 1);
	if(k == 1) ans += max(s[0] - '0', 0);
	else if(k == 2)
	{           
		ans += max(s[0] - '0' - 1, 0) * (sz(s) - 1) * 9;
		string s1 = "";
		s1 += s[0];
		for(int i = 1; i < sz(s); i++) s1 += '0';
		for(int i = 1; i < sz(s); i++)
		{
			for(char a = '1'; a <= '9'; a++)
			{
				s1[i] = a;
				if(!Compare(s1, s)) ans++;
			}
			s1[i] = '0';																																				
		}
	}
	else
	{
		ans += max(s[0] - '0' - 1, 0) * 9 * 9 * C(sz(s) - 1, 2);
		string s1 = "";
		s1 += s[0];
		for(int i = 1; i < sz(s); i++) s1 += '0';
		for(int i = 1; i < sz(s); i++)
			for(int j = i + 1; j < sz(s); j++)
			{
				if(i == j) continue;
				for(char a = '1'; a <= '9'; a++)
					for(char b = '1'; b <= '9'; b++)
					{
						s1[i] = a;
						s1[j] = b;
						if(!Compare(s1, s)) ans++;
					}
				s1[i] = s1[j] = '0';
			} 
	}	
	cout << ans;
}                                

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

#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define pb push_back
#define mp make_pair
#define VI vector<int>
#define INF 1e9
#define ll long long
const int N=100005;
const int M=200005;

int head[N];
struct node{
    int v,w,next;
}e[M*2];
int cnt;
vector<bool>vis;
vector<int>dis;
void add(int u,int v,int w){
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
bool spfa(int s){
    queue<int>q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(vis[v]&&dis[v]!=dis[u]+e[i].w){
                return false;
            }
            dis[v]=dis[u]+e[i].w;
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    int n,m;
    int a,b,d;
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    cnt=0;
    rep(i,0,m){
        cin>>a>>b>>d;
        add(a,b,d);
        add(b,a,-d);
    }
    bool flag=1;
    vis.resize(n+1,0);
    dis.resize(n+1);
    rep(i,1,n+1) dis[i]=INF;
    rep(i,1,n+1){
        if(vis[i]) continue;
        flag=spfa(i);
        if(!flag) break;
    }
    if(!flag) cout<<"No";
    else cout<<"Yes";
    return 0;
}


Measured memory_bytes: 6144
S = input()
rt = 0
for l in range(1,len(S)+1):
  for i in range(len(S)-l+1):
    tmp = 1 if i == 0 or i+l==len(S) else 2
    tw = 2**(0 if len(S)-l-tmp<0 else len(S)-l-tmp)
    rt+=tw*int(S[i:i+l])

print(rt)

Measured memory_bytes: 9060
N,M,C=list(map(int,input().split(" ")))
B=list(map(int,input().split(" ")))
A=[]
for i in range(N):
    A.append(list(map(int,input().split(" "))))
c=0
for it in A:
    s=0
    for i,its in enumerate(it):
        s+=B[i]*its
    if s+C>0:
        c+=1

print(c)


Measured memory_bytes: 38356
import java.util.*;
public class Main{

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int z,x,c;
        z=input.nextInt();
        int paid=z*800;
        int back=(z/15);
        int pricaback=back*200;
        int total=paid-pricaback;
        System.out.println(total);
    }
    
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long ans = 0;
  long long sum = 0, exc = 0;
  int l = 0, r = 0;
  while (true) {
    while (r < n && (sum + a[r]) == (exc ^ a[r])) {
      ans += r - l + 1;
      sum += a[r];
      exc ^= a[r];
      r++;
    }
    if (r >= n) {
      break;
    }
    do {
      sum -= a[l];
      exc ^= a[l];
      l++;
    } while (l < n && sum != exc);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
import math
import numpy as np
n, d = map(int, input().split())
a = []
cnt = 0
for x in range(n):
    a.append(list(map(int, input().split())))
for i in range(len(a)):
    for j in range(len(a)):
        if i < j:
            dis = np.array(a[i]) - np.array(a[j])
            if np.linalg.norm(dis).is_integer():
                cnt += 1
print(cnt)

Measured memory_bytes: 12392
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++)
    cin >> a[i];
    double sum = 0.0;;    
     for(int i=0;i<n;i++)
     {
         sum += (1/(a[i]*1.0));
     }
     cout << 1/sum;
    return 0;
}

Measured memory_bytes: 256
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

use std::io::Write;

fn run() {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    input! {
        n: usize,
        m: usize,
        e: [(usize1, usize1); m],
        q: usize,
        p: [(usize1, usize, usize); q],
    }
    let mut g = vec![vec![]; n];
    for (a, b) in e {
        g[a].push(b);
        g[b].push(a);
    }
    let mut dp = vec![vec![(0, 0); n]; 11];
    for (i, (v, d, c)) in p.into_iter().enumerate() {
        dp[d][v] = (i + 1, c);
    }
    for d in (1..11).rev() {
        for v in 0..n {
            dp[d - 1][v] = std::cmp::max(dp[d - 1][v], dp[d][v]);
            for &u in &g[v] {
                dp[d - 1][u] = std::cmp::max(dp[d - 1][u], dp[d][v]);
            }
        }
    }
    for v in 0..n {
        writeln!(out, "{}", dp[0][v].1).ok();
    }
}

fn main() {
    run();
}


Measured memory_bytes: 45304
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

func main() {
	defer stdout.Flush()
	N := readInt()
	m := map[int]int{}
	for i := 1; i < N+1; i++ {
		m[i] = 1
	}
	max := 0
	for i := 0; i < N; i++ {
		x := readInt()
		val := m[x]
		m[x+1] = val + 1
		if val > max {
			max = val
		}
	}

	println(N - max)
}

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	i, err := strconv.Atoi(readString())
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}


Measured memory_bytes: 15656
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 INT_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 INT_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<int>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define PI acos(-1)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 


int main()
{
	
	ll n,i,sq,j,f=0;

	cin>>n;

	for(i=n;!f;++i)
	{
		sq = sqrt(i);

		for(j=2;j<=sq;++j)
		{
			if(i%j==0)
				break;
		}

		if(j == (sq+1))
			break;

	}

	cout<<i<<"\n";

	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
n, q = map(int,input().split())
s = input()

tmp = [0 for _ in range(n)]
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        tmp[i] = 1 + tmp[i-1]
    else:
        tmp[i] = tmp[i-1]
#print(tmp)

for i in range(q):
    l, r = map(int,input().split())
    print(tmp[r-1] - tmp[l-1])


Measured memory_bytes: 51104
package main
 
import (
	"fmt"
)
 
func main() {
  var n int
  fmt.Scanf("%d", &n)

  ans := "No"
  if n / 100 == 7 {
    ans = "Yes"
  }
  
  n = n % 100
  if n / 10 == 7 {
    ans = "Yes"
  }
  
  if n % 10 == 7 {
    ans = "Yes"
  }
  fmt.Printf("%s\n", ans)
}

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

int main() {
  int N, K; cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());
  int ans = 0;
  for (int i = 0; i < K; i++) ans += A.at(i);
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<double> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<VS> VSS;  
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;  //ll とdoubleは違う
// cout << << endl;
// cin >> ;
int main(){
    int a,b,c=0,d=0,k=0,n,h,w,m,ans=0;
    string s,s2;
    cin >> n; 
    rep(i,n){
        cin >> a >> b;
        ans += b - a + 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main implements Runnable{
	public static void main (String[] args) {new Thread(null, new Main(), "_cf", 1 << 28).start();}

	public void run() {
		DeoxysS fs = new DeoxysS();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		int A = fs.nextInt();
		int B = fs.nextInt();
		int C = fs.nextInt();
		int x = fs.nextInt();
		int y = fs.nextInt();
		
		long min = (long)1e18;
		for(int AB = 0; AB <= 200000; AB += 2) {
			long tres = (long)AB * C;
			long tx = x - (AB / 2);
			long ty = y - (AB / 2);
			tres += Math.max(0, tx) * A;
			tres += Math.max(0, ty) * B;
			min = Math.min(min, tres);
		}
		out.println(min);

		out.close();
	}
	
	class DeoxysS {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public DeoxysS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public DeoxysS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}

Measured memory_bytes: 23636
#include <stdio.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))



//next_permutation
void nexp(char*a,int cnt){
	int l=cnt-1,r=cnt-1;
	ll t;
	while(--l>=0&&a[l]>a[l+1]);
	if(l>=0){
		while(a[l]>a[r])r--;
		t=a[l];a[l]=a[r];a[r]=t;
	}
	for(l++,r=cnt-1;l<r;l++,r--)t=a[l],a[l]=a[r],a[r]=t;
}


char s[30];
char t[30];
int main(){
	scanf("%s",s);
	ll n=strlen(s);
	if(n<26){
		rep(i,'a','z'+1){
			ll flag=1;
			rep(j,0,n)flag&=(s[j]!=i);
			if(flag){
				s[n]=i;
				puts(s);
				return 0;
			}
		}
	}

	if(strcmp(s,"zyxwvutsrqponmlkjihgfedcba")==0){
		puts("-1");
		return 0;
	}
	
	rep(i,0,n)t[i]=s[i];
	nexp(t,26);
	ll k=0;
	while(t[k]==s[k])k++;
	t[k+1]=0;
	puts(t);
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll h, w, a , b;
    cin >> h >> w >> a >> b;
    if(a > w/2 || b > h/2)
        cout << -1 << endl;
    else
    {
        vector<vector<ll>> G(h, vector<ll>(w, 0));
        for(int i = 0; i < b; i++)
        {
            for(int j = 0; j < a; j++)
            {
                G[i][j] = 1;
            }
        }
        for(int i = b; i < h; i++)
        {
            for(int j = a; j < w; j++)
            {
                G[i][j] = 1;
            }
        }
        for(auto x : G)
        {
            for(auto y : x)
                cout << y;
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 9088
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e15;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  vector<vector<ll>> a(n,vector<ll>(n));
  rep(i,n)rep(j,n) {
    cin >> a[i][j];
  }

  vector<vector<ll>> d(n,vector<ll>(n, INF));
  rep(i,n) { d[i][i] = 0; }
  rep(r,n)rep(c,n) {
    if (r==c) { continue; }
    bool found = false;
    rep(k,n) {
      if (k == r || k == c) { continue; }

      if (a[r][c] > a[r][k] + a[k][c]) { // invalid. a[r][c] must be minimum.
        cout << -1 << endl;
        return 0;
      }
      if (a[r][c] == a[r][k] + a[k][c]) { // a[r][c] is representable by sum of r-k + k-c.
        found = true;
      }
    }
    // cout << "a[r][c]: " << a[r][c] << endl;
    // cout << "found: " << found << endl;
    if (!found) { // a[r][c] is min
      d[r][c] = a[r][c];
    }
  }
  // printtree(d);

  vector<vector<ll>> d2 = d; // copy
  rep(k,n)rep(v,n)rep(u,n) {
    chmin(d2[v][u], d2[v][k] + d2[k][u]);
  }

  // Check the equality of d2 and a.
  bool ok = true;
  rep(r,n)rep(c,n) {
    if (d2[r][c] != a[r][c]) {
      ok = false;
      break;
    }
  }
  if (!ok) { // not valid
    cout << -1 << endl;
    return 0;
  }

  ll ans = 0;
  rep(r,n)rep(c,r) {
    if (d[r][c] != INF) {
      ans += d[r][c];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 2432
#include <stdio.h>

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  char s[n];
  scanf("%s", s);
  if (s[k-1] == 'A') {
    s[k-1] = 'a';
  }
  else if (s[k-1] == 'B') {
    s[k-1] = 'b';
  }else{
    s[k-1] = 'c';
  }
  printf("%s\n", s);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include<math.h>
#include<vector>
#include <set>
using namespace std;
typedef pair<int,int> P;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const int inf = 10e7;

struct unionfind {
  vector<int> d;
  unionfind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }

  bool unit(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }

  bool same(int x, int y) { return find(x) == find(y);}

  int size(int x) { return -d[find(x)];}
};
    int f[inf];

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    unionfind uf(n);

    vector<int> anti[n];
    int a,s;
    rep(i,m){
        cin>>a>>s;
        a--;s--;
        uf.unit(a,s);
        f[s]++;f[a]++;
    }
    rep(i,k){
        cin>>a>>s;
        a--;s--;
        anti[a].push_back(s);
        anti[s].push_back(a);
    }
    
    rep(i,n){
        int cnt=uf.size(i)-f[i]-1;
        for (int y:anti[i]){if (uf.same(i,y))--cnt;}
        cout<<cnt;
      if (i+1 == n) cout << endl;
        else cout << " ";
    }
    }

Measured memory_bytes: 6784
import sys,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
y=lambda:map(int,z().split())
n,m=y()
k={}
p={}
r=0
e=0
def path(r):
    while p[r]>=0:r=p[r]
    return r
for i in range(m):
    a,b=y();a-=1;b-=1;e+=1
    if a in k:
        if b in k:
            va,vb=path(k[a]),path(k[b])
            if va>vb:p[va]=vb
            elif va<vb:p[vb]=va
            else:e-=1
        else:k[b]=k[a]
    else:
        if b in k:k[a]=k[b]
        else:
            k[a]=r
            k[b]=r
            p[r]=-1
            r+=1
print(n-1-e)

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

#define MAX 10000000

void solve(int m,int n){
    vector<bool> bored(MAX,true);
    int i = m;
    while(true){
        if(bored[i]){
            if(n == 0){
                cout << i << endl;
                return;
            }
            n--;
            for(int j = i;j < MAX;j += i){
                bored[j] = false;
            }
        }
        i++;
    }
}

int main(){
    int m,n;
    while(true){
        cin >> m >> n;
        if(!m && !n)return 0;
        solve(m,n);
    }
}


Measured memory_bytes: 4260
A, B = map(int, input().split())

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

G = gcd(A, B)
l = make_divisors(G)
l.remove(1)
if len(l) == 0:
    print(1)
else:
    c = 1
    for i in range(len(l)):
        for j in range(i):
            if not coprime(l[i], l[j]):
                break
        else:
            c += 1
    print(c)

Measured memory_bytes: 42348
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.util.TreeMap;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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

public class Main {
    static int[] w = new int[100010];
    static int[] v = new int[100010];
    static int[][] dp = new int[110][100010];
    static int k;

    static int chmin(int a, int b) {
        if (a > b) {
            a = b;
            return a;
        }
        return a;
    }

    static int chmax(int a, int b) {
        if (a < b) {
            a = b;
            return a;
        }
        return a;
    }

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        int a = fs.nextInt();
        int b = fs.nextInt();

        System.out.println((b - a) * (b - a + 1) / 2 - b);

    }

}


Measured memory_bytes: 80852
n = int(input())
a = input()
a = a.split()

nums = {}

for i in range(len(a)):
  if int(a[i]) not in nums:
    nums[int(a[i])] = 1
  else:
    nums[int(a[i])] += 1

#print(nums)

if len(nums) > 3:
  print("No")
else:
  snums = sorted(nums.items())
  #print(snums)
  if(snums[0][0] == 0 and len(snums) == 1):
    print("Yes")
  elif(snums[0][0] == 0 and len(snums) == 2 and snums[0][1]*2 == snums[1][1] ):
    print("Yes")
  elif(snums[0][0] != 0 and len(snums) == 3 
       and snums[0][1] == snums[1][1] == snums[2][1] ):
    if snums[0][0] ^ snums[1][0] == snums[2][0]:
      print("Yes")
    else:
      print("No")
  else:
    print("No")

Measured memory_bytes: 15268
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    final String RGB = "RGB";
    int n = sc.nextInt();
    String s = sc.next();
    long answer = 0;
    int[][] chcnt = new int[n][3];

    for (int i = 0; i < n; i++) {
      chcnt[i][RGB.indexOf(s.charAt(i))]++;
      if (i != 0) {
        chcnt[i][0] += chcnt[i - 1][0];
        chcnt[i][1] += chcnt[i - 1][1];
        chcnt[i][2] += chcnt[i - 1][2];
      }
    }
    for(int i = 0; i < n; i++){
      int idx = RGB.indexOf(s.charAt(i));
      int idx1 = (idx + 1) % 3;
      int idx2 = (idx + 2) % 3;
      for(int j = i + 1; j < n; j++){
        int nowIdx = RGB.indexOf(s.charAt(j));
        if(idx1 == nowIdx){
          answer += chcnt[n - 1][idx2] - chcnt[j][idx2];
          if(j + (j - i) < n && RGB.indexOf(s.charAt(j + (j - i))) == idx2){
            answer--;
          }
        }
        if(idx2 == nowIdx){
          answer += chcnt[n - 1][idx1] - chcnt[j][idx1];
          if(j + (j - i) < n && RGB.indexOf(s.charAt(j + (j - i))) == idx1){
            answer--;
          }
        }
      }
    }
    System.out.println(answer);

  }
}

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int N,X; cin>>N>>X;
	vector<int> x(N+1);
	for (int i=0; i<N; i++)
		cin>>x[i];
	x[N]=X;
	sort(x.begin(),x.end());
	int ret=x[1]-x[0];
	for (int i=0; i<N; i++)
		ret=__gcd(ret,x[i+1]-x[i]);
	cout<<ret<<"\n";
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll;
const int N = 1e6+10, P = 1e9+7, inv2 = (P+1)/2;
int inv(int x){return x<=1?1:inv(P%x)*(P-(ll)P/x)%P;}
int n,m,k,fac[N],ifac[N],po[N],ipo[N];
int main() {
	ifac[0]=fac[0]=po[0]=ipo[0]=1;
	REP(i,1,N-1) { 
		fac[i]=fac[i-1]*(ll)i%P;
		po[i]=po[i-1]*3ll%P;
	}
	ifac[N-1]=inv(fac[N-1]),ipo[N-1]=inv(po[N-1]);
	PER(i,1,N-2) { 
		ifac[i]=ifac[i+1]*(i+1ll)%P;
		ipo[i]=ipo[i+1]*3ll%P;
	}
	cin>>n>>m>>k;
	int ans = 0, ret = 0;
	REP(j,0,k) ret = (ret+(ll)ipo[j]*ifac[j]%P*fac[n+j-1])%P;
	REP(i,0,m) { 
		ans = (ans+(ll)ipo[i]*ifac[i]%P*ret)%P;
		ret = 3ll*inv2%P*ret%P*(n+i)%P;
		ret = (ret-(ll)ipo[k]*inv2%P*fac[n+i+k]%P*ifac[k])%P;
	}
	ans = (ll)ans*po[m+k]%P*ifac[n-1]%P;
	if (ans<0) ans += P;
	printf("%d\n", ans);
}









Measured memory_bytes: 15872
#include<iostream>

using namespace std;

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

    if(abs(b-a) <= d && abs(c-b) <= d){
        printf("Yes");
    }else if(abs(a-c)<=d){
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
    
}

Measured memory_bytes: 256
import re
def main():
    N = int(input())
    S = input()
    K = int(input())
    nontarget = S[K - 1]
    S = S.replace(nontarget, '0')
    S = re.sub('\D', '*', S)
    S = S.replace('0', nontarget)
    print(S)
main()


Measured memory_bytes: 3316
#include <stdio.h>

int main(){
	int h, w;
	scanf("%d%d", &h, &w);
	for(int i = 0; i < w + 2; i++) putchar('#');
getchar();
	putchar('\n');
	for(int i = 0; i < h; i++){
putchar('#');
	for(int j = 0; j < w; j++){	
		putchar(getchar());
}
		putchar('#');
		putchar('\n');
getchar();
	}
	for(int i = 0; i < w + 2; i++) putchar('#');
	putchar('\n');
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<LL,LL> pa;
typedef long double ld;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
bool u[500010];
int nedge,ap[500010],too[500010],top,n,m,D,S,d[500010],x,y,tp,stk[500010],hed[500010],nxt[500010];
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
void dfs(int x){
	for (int i=hed[x];i;i=hed[x]){
		hed[x]=nxt[i];
		if (u[i]) continue;
		u[i]=u[i^1]=1;
		int y=too[i];
		dfs(y);
	}
	stk[++top]=x;
}
int main(){
	scanf("%d%d",&n,&m);
	if (n==1) return puts("No"),0;
	nedge=1;
	FOR(i,1,m){
		getint(x),getint(y);
		ae(x,y),ae(y,x);
		++d[x],++d[y];
	}
	FOR(i,1,n) if (d[i]&1) return puts("No"),0;
	FOR(i,1,n) if (d[i]>=6) return puts("Yes"),0;
	S=1;
	dfs(S);
	--top;
	assert((top==m));
//	FORD(i,top,1) printf("%d ",stk[i]);
	reverse(stk+1,stk+top+1);
	FOR(i,top+1,top+top) stk[i]=stk[i-top];
	memset(nxt,0,sizeof(nxt));
	FOR(i,1,n) ap[i]=top+top+1;
	nxt[top+top+1]=top*10+10;
	FORD(i,top+top,1){
		int t=ap[stk[i]];
		nxt[i]=min(nxt[i+1],t);
		if (i<=top && ap[stk[i]]<top+i-1){
			if (nxt[ap[stk[i]]+1]<=top+i-1){
				return puts("Yes"),0;
			}
		}
		ap[stk[i]]=i;
	}
	puts("No");
	return 0;
}


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

using namespace std;

typedef long long ll;

ll P[101010], A[101010];
vector <ll> S[101010], V, K;
ll n, m, ans;

ll find(ll p) { return p == P[p]? p : P[p] = find(P[p]); }

int main()
{
	ll i, a, b, k;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=0; i<n; i++){
		scanf("%lld", A+i);
		P[i] = i;
	}
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld", &a, &b);
		P[find(a)] = find(b);
	}
	
	for(i=0; i<n; i++){
		S[find(i)].push_back(A[i]);
		if(i == P[i]) K.push_back(i);
	}
	
	if((K.size() - 1) * 2 > n){
		printf("Impossible\n");
		return 0;
	}
	else if(K.size() == 1){
		printf("0\n");
		return 0;
	}
	
	k = K.size() - 2;
	
	for(int t: K){
		if(S[t].size()){
			sort(S[t].begin(), S[t].end());
			ans += S[t][0];
			for(i=1; i<S[t].size(); i++) V.push_back(S[t][i]);
		}
	}
	
	if(V.size()) sort(V.begin(), V.end());
	
	for(i=0; i<k; i++) ans += V[i];
	
	printf("%lld\n", ans);
	
	return 0;
}

Measured memory_bytes: 8052
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
import random
#####################################
n,k=INPUT()
A=INPUT()
ans=0
for i in A:
    if i>=k:
        ans+=1
print(ans)


Measured memory_bytes: 96124
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [list(map(int, input().split())) for i in range(N)]

def dist(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2)**0.5

row = [0]
col = [1]
data = [dist(xs, ys, xt, yt)]
for i, (xi, yi, ri) in enumerate(xyr, 2):
  d1 = max(0, dist(xi, yi, xs, ys) - ri)
  d2 = max(0, dist(xi, yi, xt, yt) - ri)
  row.extend([0, 1])
  col.extend([i, i])
  data.extend([d1, d2])
  for j in range(i-1, N):
    xj, yj, rj = xyr[j]
    dij = max(0, dist(xi, yi, xj, yj) - ri - rj)
    row.append(i)
    col.append(j+2)
    data.append(dij)

graph = csr_matrix((data, (row, col)), shape=(N+2, N+2))
dist = dijkstra(graph, directed=False, indices=0)
print(dist[1])

Measured memory_bytes: 68696
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P  = pair<int,int>;
using v  = vector<int>;
using vv = vector<v>;
//const int MOD = 1000000007;
const int MOD = 998244353;
const int INF = 1001001001;

int main(){
    int p,q,r;
    cin >>p>>q>>r;
    
    cout << min( p+q, min(q+r, r+p)) << endl;
    
    return 0;
}



Measured memory_bytes: 764
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
vector<bool> used;
vector<ll> dist, a;
int dfs(int v, int d) {
  if(used[v]) return v;
  used[v] = true;
  dist[v] = d;
  return dfs(a[v], d + 1);
}

int getPos(int v, int d) {
  if (d == 0) return v;
  return getPos(a[v], d - 1);
}

int countloop(int v, int d) {
  if(used[v] == true) return d;
  used[v] = true;
  return countloop(a[v], d + 1);
}

int main() {
  ll n, k;
  cin >> n >> k;
  used.resize(n);
  dist.resize(n);
  a.resize(n);
  rep(i, n) {
    cin >> a[i];
    a[i]--;
  }
  int start = dfs(0, 0);
  ll ans = 0;
  if (k <= dist[start]) {
    ans = getPos(0, k);
    cout << ans + 1 << endl;
    return 0;
  }
  
  k -= dist[start];
  used = vector<bool>(n, false);
  ll cnt = countloop(start, 0);
  // cout << cnt << endl;
  ll remain = k % cnt;
  ans = getPos(start, remain);
  cout << ans + 1 << endl;
  return 0;
}

Measured memory_bytes: 6424
package main

import (
	"bufio"
	"fmt"
	"os"
)

var debug = false

var sc = bufio.NewScanner(os.Stdin)

func main() {
	var m, n int
	fmt.Scanf("%d", &n)
	targets := []int{}
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &m)
		targets = append(targets, m)
	}

	res := GetAnswer(n, targets)
	fmt.Printf("%v\n", res)
}

// GetAnswer ...
func GetAnswer(n int, inputs []int) int {
	prt("inputs: n:%d inputs%v", n, inputs)
	mochis := sortAsc(inputs)
	result := 1
	for i := range mochis {
		if i == len(mochis)-1 {
			break
		}
		if mochis[i] != mochis[i+1] {
			result++
		}
	}
	prt("%v\n", result)
	return result
}

func sortAsc(inputs []int) []int {
	prt("bubble sort start: inputs%v", inputs)
	for i := 0; i < len(inputs)-1; i++ {
		for j := len(inputs) - 1; j > i; j-- {
			if inputs[i] < inputs[j] {
				tmp := inputs[i]
				inputs[i] = inputs[j]
				inputs[j] = tmp
				prt("sorting: i=%d, j=%d, %v", i, j, inputs)
			}
		}
	}
	return inputs
}

func prt(format string, inputs ...interface{}) {
	if debug {
		fmt.Printf(format+"\n", inputs...)
	}
}

Measured memory_bytes: 640
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[100010],flag[100010];

int main()
{
    int n;scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);

    flag[1]=-1;flag[n]=1;
    for (int i=2;i<n;i++)
    if (a[i]<0) flag[i]=-1;else flag[i]=1;

    int ans=0;
    for (int i=1;i<=n;i++) ans+=flag[i]*a[i];
    printf("%d\n",ans);
    for (int i=2;i<n;i++)
    {
        if (flag[i]==1)
        {
            printf("%d %d\n",a[1],a[i]);
            a[1]-=a[i];
        }
    }
    for (int i=1;i<n;i++)
    {
        if (flag[i]==-1)
        {
            printf("%d %d\n",a[n],a[i]);
            a[n]-=a[i];
        }
    }
}


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

constexpr int mod = 1e9 + 7;

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

    int ans = 0;
    for(int i = 0; i < 60; i++) {
        int64_t num0 = 0, num1 = 0;
        for(int j = 0; j < n; j++) {
            int64_t b = a[j];
            b >>= i;
            if(b % 2 == 0) num0++;
            else           num1++;
        }
        int64_t add = num0 * num1 % mod;
        for(int j = 0; j < i; j++) {
            add <<= 1;
            add %= mod;
        }
        ans += add;
        ans %= mod;
    }

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

Measured memory_bytes: 2688
import sys
import numpy as np

input = sys.stdin.readline


def main():
    N, W = [int(i) for i in input().strip().split()]
    MAX_V = 10**3 * N

    dp = np.full([N + 1, MAX_V + 1], np.inf)
    dp[0][0] = 0
    for n in range(N):
        w, v = [int(i) for i in input().strip().split()]
        dp[n + 1] = dp[n]
        dp[n + 1][v:] = np.minimum(dp[n][v:], dp[n][:-v] + w)

    ans = np.max(np.where(dp <= W))
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 176708
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,m,i;
    scanf("%d %d",&n,&m);
    for(i=m/n;i>=1;i--)
    {
        if(m%i==0)
        {
            printf("%d\n",i);
            break;
         }
    }
    return 0;
}


Measured memory_bytes: 128
n=int(input())
s=[]
t=1000
p=0
def f9(n,p):
    while n>=9:
        n//=9
        p+=1
        f9(n,p)
    return p
def f6(n,p):
    while n>=6:
        n//=6
        p+=1
        f6(n,p)
    return p    
s.append((n,0))
while s:
    a=s[0][0]
    b=s[0][1]
    if a<6:
        t=min(t,b+a)
    if t>=b+1:
        p=0
        s.append((a-9**f9(a,p),b+1))
        p=0
        s.append((a-6**f6(a,p),b+1))
    s.pop(0)    
print(t)




Measured memory_bytes: 7832
s = gets.chomp

min_c = (?a..?z).reject { |c| s.include?(c) }.min
if min_c
  puts s + min_c
  exit
end

if s == [*(?a..?z)].reverse.join('')
  puts -1
  exit
end

25.times do |i|
  (i+1).times do |j|
    if s[-i-2] < s[-j-1]
      puts s[0..(-i-3)] + s[-j-1]
      exit
    end
  end
end


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

void func();
int sum_digits(int n);
int main(){
    func();
}

void func(){
    int n,a,b;
    cin >> n >> a >> b;
    int ans = 0;
    for(int i = n; i > 0; i--)
    {
        int tmp = sum_digits(i);
        if(a<=tmp && tmp<=b) {
            //cout << i << "\n"; 
            ans+=i;}
    }
    cout << ans << "\n";
}

int sum_digits(int n){
    int sum = 0;
    while(n>0){
        sum += n%10;
        n /= 10;
    }
    return sum;
}



Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
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 main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    const vector<string> c = {"lu", "ru", "ld", "rd"};
    while (1) {
        int N; cin >> N;
        if (N==0) break;
        int a = 0, b = 2, cnt = 0;
        rep(i,N) {
            string S; cin >> S;
            if (S == c[0] || S == c[1]) a++;
            if (S == c[2] || S == c[3]) a--;
            if (a == b) {
                cnt++;
                b = 2 - b;
            }
        }
        cout << cnt << endl;
    }
}


Measured memory_bytes: 3184
// Aizu 1154: Monday-Saturday Prime Factors
// 2017.9.13 bal4u@uu

#include <stdio.h>

#define MAX 300000
#define MAX2 35813

char mk[MAX+5];
int tbl[MAX2+5], len;

int main()
{
	int n, i;
	char *p, *q, *pend;
	int *tp;
	
	for (i = 7; i <= MAX; i += 7) mk[i-1] = mk[i+1] = 1;
	for (p = mk, pend = mk + MAX, i = 0; p <= pend; p++, i++) if (*p) {
		for (q = p + i; q <= pend; q += i) *q = 0;
	}
	for (len = 0, i = 1; i <= MAX; i++) if (mk[i]) tbl[len++] = i; tbl[len] = 0x7fffffff;
	while (scanf("%d", &n) && n > 1) {
		printf("%d:", n);
		for (tp = tbl; *tp <= n; tp++) if (n % *tp == 0) printf(" %d", *tp);
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 2112
n,a,b=map(int,input().split());k=10**9+7;c=(1<<n)%k-1;X=Y=1
for i in range(b):X=X*(n-i)%k;Y=Y*(i+1)%k;c-=X*pow(Y,k-2,k)if i+1 in(a,b) else 0
print(c%k)

Measured memory_bytes: 263412
# coding: utf-8

# https://atcoder.jp/contests/abc119


def leq_search(xs, x, s, t):
    # x以下で最大のindex
    if t-s <= 3:
        res = 0
        for i in range(s, t):
            if xs[i] <= x:
                res = i
        return res

    i = (s+t)//2
    if xs[i] <= x:
        return leq_search(xs, x, i, t)
    else:
        return leq_search(xs, x, s, i)


def geq_search(xs, x, s, t):
    # x以上で最小のindex
    if t-s <= 3:
        res = 0
        for i in range(t-1, s-1, -1):
            if xs[i] >= x:
                res = i
        return res

    i = (s+t)//2
    if xs[i] >= x:
        return geq_search(xs, x, s, i+1)
    else:
        return geq_search(xs, x, i+1, t)


def nearest_search(xs, x, s, t):
    # xにもっとも近いindex
    if t-s <= 3:
        res = s
        for i in range(s, t):
            if abs(x-xs[i]) < abs(x-xs[res]):
                res = i
        return res

    i = (s+t)//2
    if xs[i] <= x:
        return nearest_search(xs, x, i, t)
    else:
        return nearest_search(xs, x, s, i+1)


def main():
    A, B, Q = map(int, input().split())
    s = [None] * A
    t = [None] * B
    xs = [None] * Q
    for i in range(A):
        s[i] = int(input())
    for i in range(B):
        t[i] = int(input())
    for i in range(Q):
        xs[i] = int(input())

    S, T = 0, 1
    st = [[s[i], S, i] for i in range(A)]
    st.extend([[t[i], T, i] for i in range(B)])
    # st = [[s[i], S, i] for i in range(A)].extend([[t[i], T, i] for i in range(B)])
    st = sorted(st, key=lambda x: x[0])
    st_retrieval = [x[0] for x in st]

    # 各神社から最寄りの寺を求める
    s_near_t = [None] * A
    for i in range(A):
        s_near_t[i] = t[nearest_search(t, s[i], 0, B)]

    # 各寺から最寄りの神社を求める
    t_near_s = [None] * B
    for i in range(B):
        t_near_s[i] = s[nearest_search(s, t[i], 0, A)]

    for x in xs:
        # left
        near_i = leq_search(st_retrieval, x, 0, A+B)
        val, mark, i = st[near_i]
        # val: 座標
        # mark: S or T
        # i: 元の列 s or t の中での index
        cand1 = abs(val-x)
        if mark == S:
            near_t = s_near_t[i]
            cand1 += abs(near_t-val)
        else:
            near_s = t_near_s[i]
            cand1 += abs(near_s-val)

        # right
        near_i = geq_search(st_retrieval, x, 0, A+B)
        val, mark, i = st[near_i]
        # val: 座標
        # mark: S or T
        # i: 元の列 s or t の中での index
        cand2 = abs(val-x)
        if mark == S:
            near_t = s_near_t[i]
            cand2 += abs(near_t-val)
        else:
            near_s = t_near_s[i]
            cand2 += abs(near_s-val)
        
        print(min(cand1, cand2))


main()
# print(main())


Measured memory_bytes: 134360
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in range(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,input().strip().split())
ices = []
while True:
    ice = int(input().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)

Measured memory_bytes: 15612
n, m = map(int, input().split())
a = set()
for i in range(m):
    a.add(int(input()))
dp = [0] * (n+1)
dp[0] = 1
if not(1 in a):
    dp[1] = 1

for i in range(2,n+1):
    if i-1 in a:
        dp[i] = dp[i-2]
        dp[i-1] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
#print(dp)
print((dp[n])%1000000007)

Measured memory_bytes: 460020
#include<bits/stdc++.h>
#define int long long
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) a.size()
#define re return 
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define se second
#define fi first
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	string s;
	cin>>s;
	if(s[sz(s)-1]=='s') s+="es";
	else s+='s';
	cout<<s;
	re 0;
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};
 
int main(){
  long long x,a,b;
  cin>>x>>a>>b;
  if(b-a<=0){
    cout<<"delicious"<<endl;
  }else if(b-a<=x){
    cout<<"safe"<<endl;
  }else{
    cout<<"dangerous"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256