akhauriyash/Code-Regression huggingface dataset:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9 + 7

# map(int, input().split())
# list(map(int, input().split()))

N, M = map(int, input().split())
A = set()
for i in range(M):
    a = int(input())
    A.add(a)


dp = [0] * (N + 1)
dp[0] = 1
if not 1 in A:
    dp[1] = 1
for i in range(2, N + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % INF
    if i in A:
        dp[i] = 0
print(dp[N])
# ans = 1
# cur = 0
# for a in A:
#     steps = (a - 1) - cur
#     cur = a + 1


Measured memory_bytes: 17828
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main {

	static void exec(MyScanner in, PrintWriter out) {
		int N = in.nextInt();
		int C = in.nextInt();
		int K = in.nextInt();
		int[] T = new int[N];
		for (int i = 0; i < N; i += 1) {
			T[i] = in.nextInt();
		}
		Arrays.sort(T);
		int bus = 1;
		int c = C - 1;
		int maxT = T[0] + K;
		for (int i = 1; i < N; i += 1) {
			if (c == 0 || T[i] > maxT) {
				c = C - 1;
				bus += 1;
				maxT = T[i] + K;
			} else {
				c -= 1;
			}
		}
		out.println(bus);
	}

	public static void main(String[] args) {
		PrintWriter w = new PrintWriter(System.out);
		exec(new MyScanner(System.in), w);
		w.flush();
	}

	static class MyScanner {
		static final int BUFFER_SIZE = 1024;
		private final InputStream in;
		private final byte[] buffer = new byte[BUFFER_SIZE];
		private int point;
		private int readLength;
		MyScanner(InputStream in) {
			this.in = in;
		}
		private int readByte() {
			if (point < readLength) {
				int result = buffer[point];
				point += 1;
				return result;
			}
			try {
				readLength = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (readLength == -1) {
				return -1;
			}
			point = 1;
			return buffer[0];
		}
		static boolean isPrintableCharExceptSpace(int c) {
			return 33 <= c && c <= 126;
		}
		String next() {
			StringBuilder b = new StringBuilder();
			int c = readByte();
			while (!(c == -1 || isPrintableCharExceptSpace(c))) {
				c = readByte();
			}
			if (c == -1) {
				throw new NoSuchElementException();
			}
			do {
				b.appendCodePoint(c);
				c = readByte();
			} while (c != -1 && isPrintableCharExceptSpace(c));
			return b.toString();
		}
		long nextLong() {
			int c = readByte();
			while (!(c == -1 || isPrintableCharExceptSpace(c))) {
				c = readByte();
			}
			if (c == -1) {
				throw new NoSuchElementException();
			}
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long result = 0L;
			do {
				if (!('0' <= c && c <= '9')) {
					throw new InputMismatchException();
				}
				result = result * 10L + (c - '0');
				c = readByte();
			} while (c != -1 && isPrintableCharExceptSpace(c));
			return minus ? -result : result;
		}
		int nextInt() {
			long n = nextLong();
			if (Integer.MIN_VALUE <= n && n <= Integer.MAX_VALUE) {
				return (int) n;
			}
			throw new InputMismatchException();
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

}


Measured memory_bytes: 23896
n,m = (int(i) for i in input().split())
#print(n,m)

mylist = [[int(i) for i in input().split()] for i in range(m)] 
#print(mylist)

mylist1=[mylist[i][1] for i in range(m) if mylist[i][0]==1]
#print(mylist1)

mylist2=[mylist[i][0] for i in range(m) if mylist[i][1]==n]
#print(mylist2)


if len(set(mylist1) & set(mylist2)) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

using namespace std;
#define forr(i, n) for(ll i = n-1; i >= 0; i--)
#define forn(i, n) for(ll i = 0; i < n; i++)
#define forab(i, a, n) for(ll i = a; i < n; i++)
#define forabr(i, a, b) for(ll i = a; i >= b; i--)
#define endl '\n'
#define f first
#define s second
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(7); cout.setf(ios::fixed);
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

typedef long long ll;
typedef string S;

const ll mod = 1e9 + 7;
const ll Inf = LONG_LONG_MAX;
const double long PI = 3.1415926535;

ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll max(ll a, ll b){if(a > b)return a;return b;}
ll gcd (ll a, ll b) {while (b) {a %= b;swap (a, b);}return a;}
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }

int n;
map<S, bool> m;

int main(){
    fast_io;
    cin >> n;
	forn(i, n){
        S s;
        cin >> s;
        m[s] = 1;
	}
	cout << m.size();
	return 0;
}


Measured memory_bytes: 19244
#    !/usr/bin/env python3
#    encoding: UTF-8
#    Last Modified: 19/Oct/2019 05:32:47 PM


#    ✪ H4WK3yE乡
#    Mohd. Farhan Tahir
#    Indian Institute Of Information Technology (IIIT), Gwalior


import sys
import os
from io import IOBase, BytesIO


def main():
    n = int(input())
    arr = get_array()
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            ans += arr[i] * arr[j]
    print(ans)


BUFSIZE = 8192


class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        py2 = round(0.5)
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2 == 1:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


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


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


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


if __name__ == "__main__":
    main()


Measured memory_bytes: 38896
#include <stdio.h>

int main(void)
{
	int map[10][10] = {{0}};
	int x, y;
	int i, j;
	int size;
	int max;
	int drop;
	
	while (scanf("%d%*c%d%*c%d", &x, &y, &size) != EOF){
		if (size == 1){
			for (i = x - 1; i <= x + 1; i++){
				if (0 <= i && i <= 9){
					map[y][i]++;
				}
			}
			if (y - 1 >= 0) map[y - 1][x]++;
			if (y + 1 < 10) map[y + 1][x]++;
		}
		
		if(size >= 2){
			for (i = x - 1; i <= x + 1; i++){
				for (j = y - 1; j <= y + 1; j++){
					if (0 <= i && i <= 9 && 0 <= j && j <= 9){
						map[j][i]++;
					}
				}
			}
		}
		if (size == 3){
			if (y + 2 < 10) map[y + 2][x]++;
			if (y - 2 >= 0) map[y - 2][x]++;
			if (x + 2 < 10) map[y][x + 2]++;
			if (x - 2 >= 0) map[y][x - 2]++;
		}
	}
	max = drop = 0;
	for (i = 0; i < 10; i++){
		for (j = 0; j < 10; j++){
			if (map[i][j] == 0){
				drop++;
			}
			if (map[i][j] > max){
				max = map[i][j];
			}
		}
	}
	
	printf("%d\n%d\n", drop, max);
	
	return (0);
}

Measured memory_bytes: 0
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }
        public void Solve(ConsoleInput cin)
        {
            var A = cin.ReadInt;
            var B = cin.ReadInt;

            if(A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0)
            {
                WriteLine("Possible");
            }
            else
            {
                WriteLine("Impossible");
            }

        }

        /*public long C(long n, long r)
        {
            if (r == 0 || r == n) return 1L;
            if (n < r) return 0L;
            long[,] Pascal = new long[n + 1, n + 1];
            Pascal[0, 0] = 1;
            for (long i = 1; i <= n; i++)
            {
                Pascal[i, 0] = 1;
                Pascal[i, i] = 1;
                for (long j = 1; j < n; j++)
                {
                    Pascal[i, j] = Pascal[i - 1, j] + Pascal[i - 1, j - 1];
                }
            }
            return Pascal[n, r];
        }*/

        public class ConsoleInput
        {
            private readonly System.IO.TextReader _stream;
            private char _separator = ' ';
            private Queue<string> inputStream;
            public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
            {
                this._separator = separator;
                this._stream = stream;
                inputStream = new Queue<string>();
            }
            public string Read
            {
                get
                {
                    if (inputStream.Count != 0) return inputStream.Dequeue();
                    string[] tmp = _stream.ReadLine().Split(_separator);
                    for (int i = 0; i < tmp.Length; ++i)
                        inputStream.Enqueue(tmp[i]);
                    return inputStream.Dequeue();
                }
            }
            public string ReadLine { get { return _stream.ReadLine(); } }
            public int ReadInt { get { return int.Parse(Read); } }
            public long ReadLong { get { return long.Parse(Read); } }
            public double ReadDouble { get { return double.Parse(Read); } }
            public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
            public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
            public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        }
    }
}


Measured memory_bytes: 13268
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();
    char s[] = sc.next().toCharArray();
    int cntarr[] = new int[n];
    cntarr[0] = 0;
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
      if ('A' == s[i] && 'C' == s[i + 1]) cnt++;
      cntarr[i + 1] = cnt;
    }
    for (int i = 0;i < q;i ++) {
      int l = sc.nextInt();
      int r = sc.nextInt();
      System.out.println(cntarr[r-1]-cntarr[l-1]);
    }
  }
}

Measured memory_bytes: 61904
#include"bits/stdc++.h"
using namespace std;

#define NIL -1
#define MAX (1 << 24)

struct Node {
	int dis = MAX;
	bool flag = false;
	vector<pair<int, int>> d;
};


void dijkstra(vector<Node>& u)
{
	priority_queue<pair<int, int>> PQ;
	u[0].dis = 0;
	PQ.push(make_pair(0, 0));

	while (!PQ.empty())
	{
		pair<int, int> f = PQ.top();
		PQ.pop();
		
		int mini = MAX;
		int n = f.second;
		u[n].flag = true;

		if (u[n].dis < f.first * (-1)) continue;		

		for (int i = 0; i < u[n].d.size(); i++)
		{
			int v = u[n].d[i].first;
			int s = u[n].d[i].second;
			if (u[v].flag) continue;
			if (u[n].dis + s < u[v].dis) {
				u[v].dis = u[n].dis + s;

				PQ.push(make_pair(u[v].dis * (-1), v));
			}
		}
	}
}

int main(void)
{
	int i, N, v, k, c, x;
	cin >> N;
	vector<Node> u(N);
	for (i = 0; i < N; i++)
	{
		cin >> v >> k;
		for (int j = 0; j < k; j++)
		{
			cin >> x >> c;
			u[v].d.push_back(make_pair(x, c));
		}
	}

	
	dijkstra(u);

	for (i = 0; i < N; i++) cout << i << " " << u[i].dis << endl;

	return 0;
}


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

using namespace std;

vector <int> edge[100005];
bool vis[100005];

void dfs(int id) {
	vis[id] = 1;
	for (int i = 0; i < edge[id].size(); i++) {
		int to = edge[id][i];
		if (vis[to]) continue;
		dfs(to);
	}
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	
	int res = 0;
	
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		dfs(i);
		res++;
	}
	
	printf("%d\n", res);
}


Measured memory_bytes: 8960
#include <iostream>

using namespace std;

bool b[3001][3001];

int main() {
	int A, B, C, D, E, F;
	cin >> A >> B >> C >> D >> E >> F;

	for (int i = 0; i < 3001; i++)
		for (int j = 0; j < 3001; j++)
			b[i][j] = false;

	b[0][0] = true;
	for (int i = 0; i < 3001; i++) {
		for (int j = 0; j <= i; j++) {
			if (b[i][j]) {
				if (i + 100 * A <= 3000) b[i + 100 * A][j] = true;
				if (i + 100 * B <= 3000) b[i + 100 * B][j] = true;
				if (i + C <= 3000) b[i + C][j + C] = true;
				if (i + D <= 3000) b[i + D][j + D] = true;
			}
		}
	}

	int ans1 = 0, ans2 = 0;
	double max = 0;
	for (int i = 1; i <= F; i++) {
		for (int j = 0; j <= i; j++) {
			double c = j * 100.0 / ((double)i);
			if (b[i][j] && 100.0 * j <= E * (i - j)) {
				if (max <= c) {
					max = c;
					ans1 = i;
					ans2 = j;
				}
			}
		}
	}
	cout << ans1 << " " << ans2 << endl;
	return 0;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace   std;
#define ff        first
#define ss        second
#define ll        int
#define inf       ((ll)1e18)
#define double    long double
#define ull       unsigned long long
#define mod       1000000007
#define vi        vector<ll>
#define ppi       pair<ll,pair<ll,ll>>
#define pb        push_back
#define mp        make_pair
#define str       string
#define pi        2*acos(0.0)
#define pr(a,x,n) for(int i=x;i<n;i++){cout<<a[i]<<" ";}
#define p(a)      cout<<a;
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define endl      '\n'
#define all(v)    v.begin(), v.end()
#define test      cout<<"THIS_AND_THIS"<<endl;
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
int32_t main(){
	kehsihba();
	ll n,l;cin>>n>>l;
	ll arr[n];
	ll sum=0;
	ll mn=INT_MAX;
	for(int i=1;i<=n;i++){
		ll x=l+i-1;
		arr[i-1]=x;
		sum+=x;
	}
	ll ans=0;
	ll y=INT_MAX;
	for(int i=0;i<n;i++){
		ll x=sum-arr[i];
		if(abs(x-sum)<y){
			ans=x;
			y=abs(x-sum);
		}
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define P pair<int, int>
#define PP pair<P, P>
#define mk make_pair
#define fi first
#define se second
#define V vector<int>
#define VV vector<V>
#define pb push_back
using namespace std;
typedef long long ll;

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int gpx = x2-x1, gpy = y2-y1;
    int x3, y3, x4, y4;

    x3 = x2 - gpy; y3 = y2 + gpx;
    x4 = x1 - gpy; y4 = y1 + gpx;
    
    
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int cards[4][13];
    int x,i,j,c;
    char ch,d;
    for(i=0;i<4;i++){
        for(j=0;j<13;j++){
            cards[i][j]=0;
        }
    }
    scanf("%d",&c);
    for(i=0;i<c;i++){
        scanf("%c",&d);
        scanf("%c %d",&ch,&x);
        if(ch=='S'){
            cards[0][x]=1;
        }
        else if(ch=='H'){
            cards[1][x]=1;
        }
        else if(ch=='C'){
            cards[2][x]=1;
        }
        else if(ch=='D'){
            cards[3][x]=1;
        }
    }
    for(j=1;j<=13;j++){
        if(cards[0][j]!=1){
            printf("S %d\n",j);
        }
    }
    for(j=1;j<=13;j++){
        if(cards[1][j]!=1){
            printf("H %d\n",j);
        }
    }
    for(j=1;j<=13;j++){
        if(cards[2][j]!=1){
            printf("C %d\n",j);
        }
    }
    for(j=1;j<=13;j++){
        if(cards[3][j]!=1){
            printf("D %d\n",j);
        }
    }
    return 0;
}


Measured memory_bytes: 2032
n,m,x =  list(map(int,input().split()))
c = [[]for _ in range(n)]
for i in range(n):
    c[i] = list(map(int,input().split()))
ans = float('inf')
for i in range(1,2**n):#bit
    tmp = 0
    tmpl = [0 for _ in range(m)]

    for j in range(n):#bitごとにみる
        if((i>>j&1)):
            tmp += c[j][0]
            for k in range(1,m+1):
                tmpl[k-1] += c[j][k]
    ok = 0
    for l in range(m):
        if tmpl[l] >= x:
            ok += 1
    if ok >= m:
        ans = min([ans,tmp])

if ans != float('inf'):
    print(ans)
else:
    print(-1)

Measured memory_bytes: 9120
n = int(input())
a = [int(i) for i in input().split()]
x = []
j = 1
for i in range(n):
  if a[i] == j:
    x.append(a[i])
    j += 1

if len(x) == 0:
  print('-1')
else:
  print(n-len(x))


Measured memory_bytes: 24744
h, w = map(int, input().split())
s = []
s.append(list('w' * (w+2)))
d = []
d.append([-1]*(w+2))
sharp = 0
for i in range(h):
    ipt = list('w' + input() + 'w')
    sharp += ipt.count('#')
    s.append(ipt)
    d.append([-1]*(w+2))
s.append(list('w' * (w+2)))
d.append([-1]*(w+2))
queue = [(h, w)]
d[h][w] = 1


while len(queue) > 0 and d[1][1] == -1:
    c = queue.pop(0)
    r = c[0]
    c = c[1]
    dst = d[r][c] + 1
    if s[r-1][c] == '.' and d[r-1][c] == -1:
        queue.append((r-1, c))
        d[r-1][c] = dst

    if s[r+1][c] == '.' and d[r+1][c] == -1:
        queue.append((r+1, c))
        d[r+1][c] = dst

    if s[r][c-1] == '.' and d[r][c-1] == -1:
        queue.append((r, c-1))
        d[r][c-1] = dst

    if s[r][c+1] == '.' and d[r][c+1] == -1:
        queue.append((r, c+1))
        d[r][c+1] = dst

    '''for i in d:
        print(i)
    print(" ")'''
if d[1][1] == -1:
    print(-1)
else:
    print(h * w - sharp - d[1][1])

#print(d[1][1])


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

int main() {
	int n;cin>>n;
  	vector<int> l(n);
  	for(int i=0;i<n;i++){
    	cin>>l[i];
    }
  	sort(l.begin(),l.end());
  	int mysum=0;
  	for(int i=0;i<n-1;i++){
    	mysum+=l[i];
    }
  	if(l[n-1]<mysum){
    	cout<<"Yes"<<endl;
    }else{
    	cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll n,s=0;
  cin >> n;
  ll a[n],b[n];
  for(int i=0;i<n;i++)cin >> a[i];
  for(int i=0;i<n;i++)cin >> b[i];
  for(int i=0;i<n;i++){
    if(a[i]>b[i])s+=a[i]-b[i];
  }
  cout << s << endl;

}

Measured memory_bytes: 256
a,b = map(str,input().split())
a2 = int(a)
b2 = 100*int(b[0:1])+10*int(b[2:3])+int(b[3:4])
if a2 == 0 or b2 == 0:
    ans = 0
else:
    tmp = str(a2*b2)
    l = len(tmp)
    if l <= 2:
        ans = 0
    else:
        ans = int(tmp[0:l-2])
print(ans)

Measured memory_bytes: 9196
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <set>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <time.h>

using namespace std;
typedef long long ll;
#define pl pair<ll,ll>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)
#define dbg(x) cout << #x"="<< (x) << endl
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a) 
#define in(x) cin >> x;
#define all(x) (x).begin(), (x).end()
#define INF 2147483600
#define fi first
#define se second


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

	ll total=a[0];
	ll total2=a[0];
	ll ans=0,ans2=0;
	if(a[0]==0){
		total2=a[0];
		ans+=1;
		total2=1;
		total=total2;
		FOR(i,1,n){
			total+=a[i];
			if(total*total2>=0){
				if(total2>0){
					ans+=total+1;
					total=-1;
				}else{
					ans+=-total+1;
					total=1;
				}
			}
			total2=total;
		}
		total2=a[0];
		ans2+=1;
		total2=-1;
		total=total2;
		FOR(i,1,n){
			total+=a[i];
			if(total*total2>=0){
				if(total2>0){
					ans2+=total+1;
					total=-1;
				}else{
					ans2+=-total+1;
					total=1;
				}
			}
			total2=total;
		}
		cout<<min(ans,ans2)<<endl;
		return 0;
	}else{
		FOR(i,1,n){
			total+=a[i];
			if(total*total2>=0){
				if(total2>0){
					ans+=total+1;
					total=-1;
				}else{
					ans+=-total+1;
					total=1;
				}
			}
			total2=total;
		}

		total2=a[0];
		if(total2>0){
			ans2+=total2+1;
			total2=-1;
		}else{
			ans2+=-total2+1;
			total2=1;
		}
		total=total2;
		FOR(i,1,n){
			total+=a[i];
			if(total*total2>=0){
				if(total2>0){
					ans2+=total+1;
					total=-1;
				}else{
					ans2+=-total+1;
					total=1;
				}
			}
			total2=total;
		}

		cout<<min(ans,ans2)<<endl;
		return 0;
	}
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String scs = sc.nextLine();
		String[] number = scs.split(" ");
		int num1 = Integer.parseInt(number[0]);
		int num2 = Integer.parseInt(number[1]);

		int ans1 = num1 * num2;
		int ans2 = num1 * 2 + num2 * 2;

		System.out.printf("%d %d\n", ans1, ans2);

	}

}

Measured memory_bytes: 17132
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int M = in.nextInt();
            int[] p = new int[N];
            for (int i = 0; i < p.length; i++) {
                p[i] = in.nextInt() - 1;
            }
            int[] x = new int[M];
            int[] y = new int[M];
            for (int i = 0; i < M; i++) {
                x[i] = in.nextInt() - 1;
                y[i] = in.nextInt() - 1;
            }

            UnionFind uf = new UnionFind();
            uf.init(N);
            for (int i = 0; i < M; i++) {
                uf.unite(x[i], y[i]);
            }

            HashMap<Integer, HashSet<Integer>> indexMap = new HashMap<>();
            HashMap<Integer, HashSet<Integer>> pMap = new HashMap<>();
            for (int i = 0; i < N; i++) {
                int root = uf.getRoot(i);
                // Utils.debug(i, root);
                if (indexMap.get(root) == null) {
                    indexMap.put(root, new HashSet<>());
                    pMap.put(root, new HashSet<>());
                }
                indexMap.get(root).add(i);
                pMap.get(root).add(p[i]);
            }

            int count = 0;
            for (Integer root : indexMap.keySet()) {
                HashSet<Integer> indexSet = indexMap.get(root);
                // Utils.debug(root, indexSet);
                for (Integer index : indexSet) {
                    if (pMap.get(root).contains(index)) {
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }
}

class UnionFind {
    private int[] par;
    private int[] rank;

    public void init(int n) {
        par = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    // @Override
    public int getRoot(int x) {
        if (par[x] == x) {
            return x;
        } else {
            par[x] = getRoot(par[x]);
            return par[x];
        }
    }

    // @Override
    public void unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }

    // @Override
    public boolean isSame(int x, int y) {
        return getRoot(x) == getRoot(y);
    }
}

Measured memory_bytes: 136692
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
using namespace std;
#define MM 1000000000
#define MOD MM+7
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

long long pow_mod(long long n,long long k,long long m){
    if (k == 0){
        return 1;
    } else if (k % 2 == 1){
        return pow_mod(n,k-1,m)*n % m;
    } else {
        long long t = pow_mod(n,k/2,m);
        return t*t % m;
    }
}


int main(){
    int n; cin >> n;
    vector<pair<pair<string, int>, int> > P;
    for(int i = 0; i < n; i++){
        string s; int p; cin >> s >> p;
        P.push_back({{s, -p}, i+1});
    }
    sort(P.begin(), P.end());
    for(int i = 0; i < n; i++){
        cout << P[i].second << endl;
    }
}
  



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long

using namespace std;

const int MOD = 1000000007;

int main() {
  ll h, a;
  scanf("%lld %lld", &h, &a);

  int n = 0;

  for (;;) {
    if (h <= 0) {
      break;
    }
    n++;
    h -= a;
  }

  cout << n << endl;
}


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

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int r = sc.nextInt();
        int ans = r * r;
        System.out.println(ans);
    }
}

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


Measured memory_bytes: 21204
import java.util.*;

public class Main{
	public static void main(String args[]){
      Scanner scan = new Scanner(System.in);
      int n = scan.nextInt();
      int[] p = new int[n];
      for(int i=0;i<n;i++) {
        p[i] = scan.nextInt();
      }
      int result=0;
      for(int i=1;i<n-1;i++) {
        if((p[i-1]<p[i] && p[i]<p[i+1])||(p[i-1]>p[i] && p[i]>p[i+1])){
          result++;
        }
      }
      System.out.println(result);
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for(int i = (int)(n); i>=0; --i)
struct fast_ios { fast_ios(){cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast_ios_;

int main()
{
    int X, Y, Z;
    cin >> X >> Y >> Z;
    printf("%d %d %d\n", Z, X, Y);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int v[1 + nmax];
int seen[1 + nmax];
vector<int> g[1 + nmax];

int better(int f1, int f2){
  if(v[f1] < v[f2])
    return f1;
  else
    return f2;
}

int dfs(int node){
  seen[node] = 1;
  int result = node;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(seen[to] == 0)
      result = better(result, dfs(to));
  }
  return result;
}
int used[1 + nmax];

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  for(int i = 1;i <= m; i++){
    int x, y;
    cin >> x >> y;
    x++;
    y++;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  vector<int> bests;

  for(int i = 1;i <= n; i++){
    if(seen[i] == 0){
      int node = dfs(i);
      used[node] = 1;
      bests.push_back(node);
    }
  }

  if(1 < bests.size()){
    ll result = 0;
    for(int i = 0; i < bests.size(); i++)
      result += v[bests[i]];
    vector<int> oth;
    for(int i = 1; i <= n; i++)
      if(used[i] == 0)
        oth.push_back(v[i]);
    sort(oth.begin(), oth.end());
    if((bests.size() - 2) <= oth.size()){
      for(int i = 0; i < (bests.size() - 2); i++)
        result += oth[i];
      cout << result;
    } else
      cout << "Impossible";
  } else
    cout << 0;
  return 0;
}


Measured memory_bytes: 7424
import bisect
N=int(input())
L=list(map(int,input().split()))
R=sorted(L)
point=0
for i in range(N-2):
  for j in range(i+1,N-1):
    p = bisect.bisect_right(R,R[i]+R[j]-1,j+1,N)
    point+=p-(j+1)
    
print(point)

Measured memory_bytes: 3316
#include<stdio.h>
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int a[1000]={0};
    for(int i=0;i<k;i++)
    {
        int m;
        scanf("%d",&m);
        for(int j=0;j<m;j++)
        {
            int h;
            scanf("%d",&h);
            a[h]++;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)
           sum++;
    }
    printf("%d\n",sum);
}


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

map<long long, long long> prime_factor(long long N) {
  map<long long, long long> res;
  for (long i = 2; i * i <= N; i++) {
    while (N % i == 0) {
      res[i]++;
      N /= i;
    }
  }
  if (N != 1) {
    res[N] = 1;
  }
  return res;
}

int main() {

  int N;
  cin >> N;

  map<long long, long long> mp;

  for (int i = 1; i <= N; i++){
    map<long long, long long> m = prime_factor(i);
    for (auto item: m) {
      mp[item.first] += item.second;
    }
  }

  long long answer = 1;

  for (auto item: mp) {
    answer *= (item.second + 1);
    answer %= 1000000007;
  }

  cout << answer <<  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 rep_s(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

#define MOD 1000000007

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

  vi a, b;
  rep(i, n)
  {
    ll _a;
    cin >> _a;
    a.push_back(_a);
  }

  rep(i, m)
  {
    ll _b;
    cin >> _b;
    b.push_back(_b);
  }

  int ans = 0;

  ll a_k = 0;
  int a_index = -1;

  ll b_k = 0;
  int b_index = -1;

  // b読める分だけ読む
  while(b_index + 1 < b.size() && b_k + b[b_index + 1] <= k) {
    b_index++;
    b_k += b[b_index];
  }

  ans = b_index + 1;

  for (int i = 0; i < n; i++)
  {
    a_index++;
    a_k += a[a_index];

    // bを減らす
    while (a_k + b_k > k && b_index >= 0)
    {
      b_k -= b[b_index];
      b_index--;
    }

    if (a_k + b_k > k) {
      break;
    }
    ans = max(ans, a_index + b_index + 2);
  }

  cout << ans << endl;
}


Measured memory_bytes: 5600
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
constexpr int MOD = 1000000007;
constexpr int INF = 2000000000;
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int C[21];
	int T[50001];
	for (int i = 0; i < m; i++) {
		cin >> C[i];
	}
	for (int i = 0; i <= 50000; i++)T[i] = INF;
	T[0] = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j + C[i] <= n; j++) {
			T[j + C[i]] = min(T[j + C[i]], T[j] + 1);
		}
	}
	cout << T[n] << endl;
}

Measured memory_bytes: 3276
using System;
using System.Collections.Generic;
using System.Linq;
namespace AOJ {
    internal class Program {
        public static void Main(string[] args) { new Program().solve(); }
        void solve() {
            var D = new Distance();
            int n = int.Parse(Console.ReadLine());
            var x = Console.ReadLine().Split().Select(v => double.Parse(v)).ToArray();
            var y = Console.ReadLine().Split().Select(v => double.Parse(v)).ToArray();
            if(x.Length != n || y.Length != n) return;//kuso
            Console.WriteLine(D.Manhattan(x, y));
            Console.WriteLine(D.Euclidean(x, y));
            Console.WriteLine(D.Minkowski(x, y, 3D));
            Console.WriteLine(D.Chebyshev(x, y));
        }
    }
    class Distance {
        private static Func <double, double, double> power = (value, p) => Math.Pow(value, p);
        private static Func <double, double, double> between = (x, y) => Math.Abs(y - x);
        //private Func <double[], double[], double[]> sequence=(xArr,yArr)=> xArr.Zip(yArr, (x, y) => between(x, y)).ToArray();
        private Func <double[], double[], double[]> sequence = (xArr, yArr) => {
            var ret = new double[xArr.Length];
            for(int i = 0; i < xArr.Length; ++i) { ret[i] = between(xArr[i], yArr[i]); }
            return ret;
        };
        public double Manhattan(double[] x, double[] y) { return sequence(x, y).Sum(); }
        public double Euclidean(double[] x, double[] y) {
            return power(sequence(x, y).Select(v => power(v, 2)).Sum(), 0.5);
        }
        public double Minkowski(double[] x, double[] y, double p) {
            return power(sequence(x, y).Select(v => power(v, p)).Sum(), 1 / p);
        }
        public double Chebyshev(double[] x, double[] y) { return sequence(x, y).Max(); }
    }
}



Measured memory_bytes: 9964
#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;


int main(){
    int n;
    string s;
    cin>>s;
    n=s.size();
    ll r=0;
    vector<ll>num(2019);
    int x=1;
    ll ans=0;
    num[0]++;
    rep(i,n){
        r+=(s[n-i-1]-'0')*x;
        r%=2019;
        //cout<<r<<endl;
        ans+=num[r];
        num[r]++;
        x=x*10%2019;
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3728
import java.util.Scanner;
import java.util.Arrays;

public class Main{
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
long x=scan.nextLong();

int i=0;
long n=100;
while(n<x){
    n=n+n/100;
    i=i+1;
}

System.out.println(i);


}
}

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


int main()
{
    int R;
    cin >> R;

    if (R >= 0)
    {
        if (R < 1200) cout << "ABC";
        else if (R < 2800)  cout << "ARC";
        else    cout << "AGC";
    }

    return 0;
}



Measured memory_bytes: 256
nums , types = map(int, input().split())
array = list(map(int,input().split()))
array.sort()
type_count = 0
count = 0
result = 0
ary_count = []
array.append(1000000000)

for i in range (nums):
    if array[i] == array[i +1]:
        count += 1
    elif array[i] < array[i +1]:
        ary_count.append(count)
        type_count += 1
        count = 0

ary_count.sort()

if type_count > types:
    for i in range(type_count - types):
        result += ary_count[i]+1
print(result)

Measured memory_bytes: 24836
N = int(input())
ans = 0
if N % 2 == 1:
    A = [0]*N
    for i in range(N):
        A[i] = int(input())
else:  # 要素数を擬似的に奇数にして後の操作を楽にする
    N += 1
    A = [0] * N
    A[N-1] = 10**9+1
    for p in range(N-1):
        A[p] = int(input())
even = set()
for k in range(N//2+1):
    even.add(A[2*k])
# print(even)
B = sorted(A)
for j in range(N // 2):
    if B[(2 * j)+1] in even:
        ans += 1
        #print(A[2 * j])

print(ans)
# print(A)


Measured memory_bytes: 10220
#define ll long long
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    double arr[103];
    double s1=0.0,s2=1.0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        s1+=(1/arr[i]);

    }
    //cout<<s1<<" "<<s2<<endl;
    cout<<setprecision(15)<<fixed<<1/s1<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string ans;
  string A[2];
  cin>>A[0]>>A[1];
  if(A[0].size()<A[1].size()) ans="LESS";
  else if (A[0].size()>A[1].size()) ans="GREATER";
  else if(A[0]<A[1]) ans="LESS";
  else if(A[0]>A[1]) ans="GREATER";
  else ans="EQUAL";
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
	int money;
	scanf("%d",&money);
	int num;
	num=money/500;
	int sum;
	sum=money-500*num;
	int count;
	count=sum/5;
	int ans;
	ans=num*1000+count*5;
	printf("%d\n",ans);
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll N, K, A[4000] = {}, x1 = 0, x2 = 0;

int main() {
	cin >> N >> K;
	rep(i, N) {
		cin >> A[i];
		A[i + N] = A[i];
	}
	rep(i, N) {
		for (int j = i + 1; j < N * 2; j++) {
			if (A[i] > A[j]) {
				if (j < N) {
					x1++;
				}
				else {
					x2++;
				}
			}
		}
	}
	cout << ((x1* K) % 1000000007 + (x2 * ((K * (K - 1) / 2) % 1000000007)) % 1000000007) % 1000000007 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long int a[100010],b[100010];
long long int s[100010];
long long int ans[100010];
long long int f[100010];
long long findd(long long x) { return f[x] == x ? x : f[x] = findd(f[x]); }
int main()
{
    long long int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        s[i]=1;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
    }
    long long int sum=(n-1)*n/2;
    for(int i=m-1;i>=0;i--)
    {
        ans[i]=sum;
        int aa=findd(a[i]);
        int bb=findd(b[i]);
        if(aa!=bb)
        {
            f[bb]=aa;
            sum-=s[aa]*s[bb];
            s[aa]+=s[bb];
        }
    }
    for(int i=0;i<m;i++)
        printf("%lld\n",ans[i]);
//    return 0;
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
using ll         = long long;
constexpr ll MOD = 1000000007;
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REP2(i, x, n) for (ll i = x; i < (n); i++)
const long long INF = numeric_limits<long long>::max();
template <class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
vector<ll> getNums(ll N) {
    vector<ll> num(N);
    REP(i, N) {
        cin >> num[i];
    }
    return num;
}

ll calcDigit(ll n) {
    ll d = 1;
    while (n >= 10) {
        n /= 10;
        d++;
    }
    return d;
}
int main() {
    ll N;
    cin >> N;

    vector<pair<ll, ll> > pairs;
    ll ans = INF;
    for (ll i = 1; i * i <= N; ++i) {
        if ((N % i) == 0) {
            ll a = calcDigit(i);
            ll b = calcDigit(N / i);
            chmin(ans, max(a, b));
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3604
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int bit[]={0x1111110,0x0110000,0x1101101,0x1111001,0x0110011,0x1011011,0x1011111,0x1110010,0x1111111,0x1111011,0};

int main() {
	int n;
	while(cin>>n,n!=-1){
		int b,i,pr=10,nw;
		for(i=0;i<n;i++){
			cin>>nw;
			b=bit[pr]^bit[nw];
			pr=nw;
			int j;
			for(j=0;j<7;j++){cout<<(b&1);b/=16;}
			cout<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
INF = 1000000

N, M = map(int, raw_input().split(" "))

dat = [[INF for _ in xrange(N)] for _ in xrange(N)]
isMinimal = [[True for _ in xrange(N)] for _ in xrange(N)]

for i in xrange(N):
    dat[i][i] = 0

a = [0 for _ in xrange(M)]
b = [0 for _ in xrange(M)]
c = [0 for _ in xrange(M)]
for i in xrange(M):
    a[i], b[i], c[i] = map(int, raw_input().split(" "))
    a[i] -= 1
    b[i] -= 1
    dat[a[i]][b[i]] = c[i]
    dat[b[i]][a[i]] = c[i]

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            if dat[i][j] > dat[i][k] + dat[k][j]:
                dat[i][j] = dat[i][k] + dat[k][j]
                isMinimal[i][j] = False

res = 0
for i in xrange(M):
        res += 0 if isMinimal[a[i]][b[i]] else 1

print res


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

int comp(const void *a, const void *b){
	return *(int *)a-*(int*)b;
}

void dasu(int *card,int s,int num){
	int i;
	for(i=s;i<num-1;i++){
		card[i]=card[i+1];
	}
}

int main(){
	int n,card[2][100],c,score[2],turn,now,i,f;
	char check[200];
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n*2;i++){
			check[i]=1;
		}
		for(i=0;i<n;i++){
			scanf("%d",&card[0][i]);
			check[card[0][i]-1]=0;
		}
		qsort(card[0],n,sizeof(int),comp);
		c=0;
		for(i=0;i<n*2;i++){
			if(check[i]==1){
				card[1][c]=i+1;
				c++;
			}
		}
		turn=1;
		now=0;
		score[0]=n;
		score[1]=n;
		while(score[0]>0 && score[1]>0){
			turn=(turn+1)%2;
			f=1;
			for(i=0;i<score[turn];i++){
				if(card[turn][i]>now){
					now=card[turn][i];
					dasu(card[turn],i,score[turn]);
					score[turn]--;
					f=0;
					break;
				}
			}
			if(f) now=0;
		}
		printf("%d\n%d\n",score[1],score[0]);
	}
    return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	char s[101];
	scanf("%s",s);
	int len=strlen(s),i,flag=0,len1,len2;
	len1=len/2;
	for(i=0;i<len1;i++) // 1st step
	{
		if(s[i]!=s[len-i-1]){
			flag=1;
			cout<<"No";
			return 0;
		}
	}
	for(i=0;i<len1/2;i++)
	{
		if(s[i]!=s[len1-i-1]){
			flag=2;
			cout<<"No";
			return 0;
		}
	}
	len2=len1+1;
	for(i=len2;i<len;i++)
	{
		if(s[i]!=s[len1-(i-len2)-1]){
			flag=3;
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	
}

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

int main (){
    int n;
    int p;
    int count=0;
    cin >> n;
    rep(i,n){
        cin >> p;
        if(p-(i+1)!=0) count++;
    }
    if(count==2 || count==0) cout << "YES" ;
    else cout << "NO";
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#define N 100001
 
typedef struct{
    int par; //parent node
    int l_child; //left child node
    int r_sib; //right child noed
} node;
 
node tree[N];
 
int depth(int);
 
int main(){
  
    int n, id, cnum, lef, child;
    int i, j; 
 
    scanf("%d", &n);
   
    for(i = 0; i < n; i++){
        tree[i].par = -1;
        tree[i].l_child = -1;
        tree[i].r_sib = -1;
    }
   
    for(i = 0; i < n; i++){
        scanf("%d %d", &id, &cnum);

        for(j=0; j<cnum; j++){
            scanf("%d", &child);
 
            if(j == 0) tree[id].l_child = child;
            else tree[lef].r_sib = child;
            tree[child].par = id;
            lef = child;
        }
    }
 
    for(i=0; i<n; i++){ //how the tree looks 
        printf("node %d: parent = %d, depth = %d, ", i, tree[i].par, depth(i));
 
        if(tree[i].par == -1) printf("root, [");
        else if(tree[i].l_child == -1) printf("leaf, [");
        else printf("internal node, [");
        lef = tree[i].l_child;
 
        for(j=0; ; j++){ 
            if(lef == -1) break; //no leaf break needed
            if(j != 0) printf(", ");
            printf("%d", lef);
            lef = tree[lef].r_sib;
        }
        printf("]\n");
    }
   
    return 0;
   
}
 
int depth(n){
 
    if(tree[n].par == -1) return 0;
 
    return depth(tree[n].par) + 1;
}

Measured memory_bytes: 1784