Commits

Aldo Culquicondor  committed 30ab745

primer commit

  • Participants

Comments (0)

Files changed (178)

+*.txt
+*.out
+s=raw_input().split()
+n=int(s[0])
+m=int(s[1])
+pri=[int(x) for x in raw_input().split()]
+rel=[set() for x in range(n)]
+for i in range(m):
+	s=raw_input().split()
+	a=int(s[0])-1
+	b=int(s[1])-1
+	rel[a].add(b)
+	rel[b].add(a)
+rpta=1<<30
+for i in range(n):
+	for j in range(i+1,n):
+		for k in range(j+1,n):
+			if i in rel[j] and i in rel[k] and j in rel[k]:
+				rpta=min(rpta,pri[i]+pri[j]+pri[k])
+if rpta!=1<<30:
+	print rpta
+else:
+	print -1
+s=raw_input()
+if(len(s)==1):
+	print 0
+	exit(0)
+n=0
+for x in s:
+	n+=int(x)
+c=1
+while(len(str(n))!=1):
+	s=str(n)
+	n=0
+	for x in s:
+		n+=int(x)
+	c+=1
+print c
+n=int(raw_input())
+A=[int(x) for x in raw_input().split()]
+r=0
+for i in range(n):
+	r+=A[i]*(i+1)-i
+print r
+#include<vector>
+#include<cstdio>
+
+using namespace std;
+
+int n;
+vector<vector<int> > adj;
+vector<bool> visit;
+vector<int> pi;
+int ciclos;
+
+void dfs(int u)
+{
+//	printf("#%d\n",u+1);
+	visit[u]=1;
+	for(int v:adj[u])
+	{
+		if(!visit[v])
+		{
+			pi[v]=u;
+			dfs(v);
+		}
+		else
+			if(v!=pi[u])
+			{
+	//			printf("#%d %d\n",u+1,v+1);
+				ciclos++;
+			}
+	}
+}
+
+int main()
+{
+	int m;
+	ciclos=0;
+	scanf("%d %d",&n,&m);
+	adj.resize(n);
+	pi.resize(n);
+	visit.assign(n,0);
+	int u,v;
+	for(int i=0;i<m;i++)
+	{
+		scanf("%d%d",&u,&v);
+		u--,v--;
+		adj[u].push_back(v);
+		adj[v].push_back(u);
+	}
+	for(int u=0;u<n;u++)
+		if(!visit[u])
+			dfs(0);
+	//printf("%d\n",ciclos);
+	if(ciclos==2)
+		puts("FHTAGN!");
+	else
+		puts("NO");
+}
+n=int(raw_input())
+dif=n-10
+r=0
+if(dif>0):
+	if(dif<10 or dif==11):
+		r=4
+	elif(dif==10):
+		r=15
+print r
+s=raw_input().split()
+n=int(s[0])
+m=int(s[1])
+k=int(s[2].split('.')[1])
+
+M=dict()
+
+for i in range(n):
+	s=raw_input().split()
+	aug=int(s[1])*k/100
+	if(aug>=100):
+		M[s[0]]=aug
+
+for i in range(m):
+	s=raw_input()
+	if s not in M:
+		M[s]=0
+
+print len(M)
+
+for x in sorted(M):
+	print x,M[x]
+def rank(s):
+	if(s=='6'):
+		return 0
+	if(s=='7'):
+		return 1
+	if(s=='8'):
+		return 2
+	if(s=='9'):
+		return 3
+	if(s=='T'):
+		return 4
+	if(s=='J'):
+		return 5
+	if(s=='Q'):
+		return 6
+	if(s=='K'):
+		return 7
+	return 8
+
+def beat(a,b):
+	if(rank(a)<rank(b)):
+		return 'NO'
+	return 'YES'
+
+tr=raw_input()
+s=raw_input().split()
+c1=s[0]
+c2=s[1]
+if(c1[1]==tr):
+	if(c2[1]==tr):
+		print beat(c1[0],c2[0])
+	else:
+		print 'YES'
+else:
+	if(c1[1]!=c2[1]):
+		print 'NO'
+	else:
+		print beat(c1[0],c2[0])
+#include<cstdio>
+#include<bits/stl_algobase.h>
+
+using std::max;
+
+int M[11][1001],n,a[1001],b[1001],c[1001],d[1001];
+
+int dp(int pos,int har)
+{
+	if(pos==n)
+		return 0;
+	int &ans=M[pos][har];
+	if(ans>=0)
+		return ans;
+	int q=0,este=0;
+	ans=0;
+	while(har>=0 and este<=a[pos])
+	{
+		ans=max(ans,d[pos]*q+dp(pos+1,har));
+		q++;
+		este+=b[pos];
+		har-=c[pos];
+	}
+	return ans;
+}
+
+int main()
+{
+	int har,c0,d0;
+	scanf("%d %d %d %d",&har,&n,&c0,&d0);
+	for(int i=0;i<n;i++)
+		scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
+	int ans=0,q=0;
+	for(int i=0;i<n;i++)
+		for(int j=0;j<=har;j++)
+			M[i][j]=-1;
+	while(har>=0)
+	{
+		ans=max(ans,d0*q+dp(0,har));
+		q++;
+		har-=c0;
+	}
+	printf("%d\n",ans);
+}
+n=int(raw_input())
+S=set([int(x) for x in raw_input().split()])
+A=[x for x in S]
+A.sort()
+t=len(A)-1
+for i in range(t):
+	if(A[i]>1 and A[i]*2>A[i+1] and A[i]!=A[t]):
+		print 'YES'
+		exit(0)
+print 'NO'
+n=int(raw_input())
+for i in range(n/7,-1,-1):
+	if (n-7*i)%4==0:
+		print '4'*((n-7*i)/4)+'7'*i
+		exit(0)
+	if n-7*i<0:
+		break
+print -1
+def islucky(n):
+	if n==0:
+		return 0
+	while n>0:
+		if n%10!=7 and n%10!=4:
+			return 0
+		n/=10
+	return 1
+
+a=raw_input()
+c=0
+for i in a:
+	if i=='4' or i=='7':
+		c+=1
+if islucky(c):
+	print 'YES'
+else:
+	print 'NO'
+a=raw_input().lower()
+b=raw_input().lower()
+if a<b:
+	print -1
+elif a==b:
+	print 0
+else:
+	print 1
+A=raw_input().split()
+
+if len(A)==1:
+	s=A[0]
+	if s[-4:]=='lios' or s[-5:]=='liala' or s[-3:]=='etr' or s[-4:]=='etra' or s[-6:]=='initis' or s[-6:]=='inites':
+		print 'YES'
+	else:
+		print 'NO'
+	exit(0)
+
+#masculine
+vale=1
+i=0
+#adjetives
+while(i<len(A) and A[i][-4:]=='lios'):
+	i+=1
+if(i==len(A) or A[i][-3:]!='etr'):
+	vale=0
+i+=1
+while(i<len(A) and A[i][-6:]=='initis'):
+	i+=1
+if(i!=len(A)):
+	vale=0
+if(vale):
+	print 'YES'
+	exit(0)
+
+#female
+
+vale=1
+i=0
+#adjetives
+while(i<len(A) and A[i][-5:]=='liala'):
+	i+=1
+if(i==len(A) or A[i][-4:]!='etra'):
+	vale=0
+i+=1
+while(i<len(A) and A[i][-6:]=='inites'):
+	i+=1
+if(i!=len(A)):
+	vale=0
+if(vale):
+	print 'YES'
+else:
+	print 'NO'
+#include<iostream>
+#include<set>
+#include<vector>
+
+using namespace std;
+
+int main()
+{
+	string s,ini,fin;
+	cin>>s>>ini>>fin;
+	vector<int> inis,fins;
+	int t=s.size()-ini.size()+1,t1=ini.size();
+	for(int i=0;i<t;i++)
+	{
+		int j;
+		for(j=0;j<t1 and s[i+j]==ini[j];j++);
+		if(j==t1)
+			inis.push_back(i);
+	}
+	t=s.size()-fin.size()+1,t1=fin.size();
+	for(int i=0;i<t;i++)
+	{
+		int j;
+		for(j=0;j<t1 and s[i+j]==fin[j];j++);
+		if(j==t1)
+			fins.push_back(i);
+	}
+	set<string> conj;
+	int i=0,j=0;
+	t1=inis.size();
+	int t2=fins.size(),tt=fin.size();
+	while(i<t1 and j<t2)
+	{
+		while(j<t2 and fins[j]<inis[i])
+			j++;
+		if(j==t2)
+			break;
+		for(int k=j;k<t2;k++)
+		{
+			string t=s.substr(inis[i],fins[k]-inis[i]+tt);
+			conj.insert(t);
+		}
+		i++;
+	}
+	cout<<conj.size()<<endl;
+}
+    #include <cstdio>
+    #include <bitset>
+    using namespace std;
+    bitset<300000001> p;
+    int l, r, R, i, j;
+    int main(){
+            scanf("%d%d", &l, &r); p.set();
+            for (i = 3;(j = i * i) <= r;i += 2) if (p[i]) for (;j <= r;j += i << 1) p[j] = false;
+            for (i = 5;i <= r;i += 4) if (p[i] && l <= i) R++;
+            printf("%d\n", R + (l <= 2 && 2 <= r));
+    }
+#include<iostream>
+#include<bitset>
+
+using namespace std;
+
+bitset<300000001> p;
+
+void erastostenes(int n)
+{
+	p.set();
+	int i,j;
+	for(i=3;(j=i*i)<=n;i+=2)
+		if(p[i])
+			for(;j<=n;j+=i<<1)
+				p[j]=false;
+}
+
+int main()
+{
+	int l,r;
+	cin>>l>>r;
+	erastostenes(r);
+	if(l>r)
+	{
+		cout<<0<<endl;
+		return 0;
+	}
+	int t,count=0;
+	for(long long i=1;i*i<r;i++)
+		for(long long j=i+1;i*i+j*j<=r;j+=2)
+		{
+			t=i*i+j*j;
+			if(t>=l and p[t])
+				count++;
+		}
+	if(2>=l and 2<=r)
+		count++;
+	cout<<count<<endl;
+/*	for(int i=5;i<=r;i+=4) if(p[i]&&l<=i) count++;
+	cout<<count+(l<=2 and 2<=r)<<endl;*/
+	return 0;
+}
+#include<iostream>
+#include<vector>
+#include<map>
+#include<algorithm>
+
+using namespace std;
+
+int main()
+{
+	int n,m;
+	cin>>n>>m;
+	bool R[17][17];
+	vector<string> name(n);
+	map<string,int> ID;
+	for(int i=0;i<n;i++)
+	{
+		cin>>name[i];
+		for(int j=0;j<n;j++)
+			R[i][j]=0;
+		ID[name[i]]=i;
+	}
+	string s;
+	int u,v;
+	for(int i=0;i<m;i++)
+	{
+		cin>>s;
+		u=ID[s];
+		cin>>s;
+		v=ID[s];
+		R[u][v]=1;
+		R[v][u]=1;
+	}
+	vector<int> ans;
+	for(int mask=0;mask<(1<<n);mask++)
+	{
+		vector<int> este;
+		for(int i=0;i<n;i++)
+			if(mask&(1<<i))
+				este.push_back(i);
+		bool vale=1;
+		for(int i=1;i<este.size();i++)
+			for(int j=0;j<i;j++)
+				if(R[este[i]][este[j]])
+				{
+					vale=0;
+					goto sigue;
+				}
+		sigue:
+		if(vale and este.size()>ans.size())
+			ans=este;
+	}
+	cout<<ans.size()<<endl;
+	sort(ans.begin(),ans.end(),
+		[&name](int i,int j) {return name[i]<name[j];}
+	);
+	for(int i=0;i<ans.size();i++)
+		cout<<name[ans[i]]<<endl;
+}
+#include<cstdio>
+#include<iostream>
+#include<vector>
+
+using namespace std;
+
+vector<vector<int> > adj;
+vector<int> dep;
+
+void dfs(int u)
+{
+	for(int v:adj[u])
+	{
+		dep[v]=dep[u]+1;
+		dfs(v);
+	}
+}
+
+int main()
+{
+	int n,t;
+	scanf("%d",&n);
+	adj.resize(n);
+	vector<int> p(n);
+	dep.assign(n,1);
+	for(int i=0;i<n;i++)
+	{
+		scanf("%d",&t);
+		if(t!=-1)
+		{
+			t--;
+			adj[t].push_back(i);
+			p[i]=t;
+		}
+		else
+			p[i]=-1;
+	}
+	for(int i=0;i<n;i++)
+		if(p[i]==-1)
+			dfs(i);
+	int rpta=0;
+	for(int x:dep)
+		rpta=max(rpta,x);
+	cerr<<"hola"<<endl;
+	printf("%d\n",rpta);
+}
+#include<cstdio>
+#include<bits/stl_algobase.h>
+
+using std::max;
+
+int main()
+{
+	int n,a,b;
+	scanf("%d",&n);
+	int cu=0,r=0;
+	for(int i=0;i<n;i++)
+	{
+		scanf("%d %d",&a,&b);
+		cu-=a;
+		cu+=b;
+		r=max(r,cu);
+	}
+	printf("%d\n",r);
+}
+n=int(raw_input())
+cu=0
+r=0
+for i in range(n):
+	s=raw_input().split()
+	cu-=int(s[0])
+	cu+=int(s[1])
+	r=max(cu,r)
+
+print r
+s=raw_input().split()
+n=int(s[0])
+m=int(s[1])
+
+M=['']*n
+for i in range(n):
+	M[i]=raw_input()
+
+dx=[-1,1,0,0]
+dy=[0,0,-1,1]
+
+def valid(i,j):
+	return i>=0 and j>=0 and i<n and j<m
+
+def hay(i,j):
+	for k in range(4):
+		ii=i+dx[k]
+		jj=j+dy[k]
+		if(valid(ii,jj) and M[ii][jj]=='P'):
+			return 1
+	return 0
+
+r=0
+for i in range(n):
+	for j in range(m):
+		if(M[i][j]=='W' and hay(i,j)):
+			r+=1
+print r
+s=raw_input().split()
+n=int(s[0])
+m=int(s[1])-1
+for i in range(n):
+	s=raw_input().split()
+	ini=int(s[0])-1
+	fin=int(s[1])-1
+	t=int(s[2])
+	if ini==fin:
+		r=t
+	elif ini<fin:
+		r=ini
+		while r<t:
+			r+=2*m
+		r+=fin-ini
+	else:
+		r=2*m-ini
+		while r<t:
+			r+=2*m
+		r+=ini-fin
+	print r
+s=raw_input().split()
+n=int(s[0])
+d=int(s[1])
+A=[int(x) for x in raw_input().split()]
+r=0
+for i in range(1,n):
+	if A[i-1]>=A[i]:
+		k=(A[i-1]-A[i])/d+1
+		A[i]+=k*d
+		r+=k
+print r
+from itertools import *
+import sys
+sys.stdin=open("input.txt","r")
+sys.stdout=open("output.txt","w")
+
+ent=raw_input()
+rail=int(raw_input())
+r=''
+if ent=='front':
+	if rail==1:
+		r='L'
+	else:
+		r='R'
+else:
+	if rail==1:
+		r='R'
+	else:
+		r='L'
+
+print r
+from itertools import *
+import sys
+sys.stdin=open('input.txt','r')
+sys.stdout=open('output.txt','w')
+n,k=[int(x) for x in raw_input().split()]
+A=[int(x) for x in raw_input().split()]
+k-=1
+while not A[k]:
+	k=(k+1)%n
+print k+1
+from itertools import*
+import sys
+sys.stdin=open('input.txt','r')
+sys.stdout=open('output.txt','w')
+
+n,k=[int(x) for x in raw_input().split()]
+A=[int(x) for x in raw_input().split()]
+for i in range(len(A)):
+	A[i]=max(A[i]%k,A[i]-k*3)
+print sum(A)
+from itertools import *
+import sys
+sys.stdin=open("input.txt","r")
+sys.stdout=open("output.txt","w")
+
+n=int(raw_input())
+for i in range(n):
+	a=int(raw_input())
+	print 1-a%2
+#include<cstdio>
+#include<vector>
+#include<algorithm>
+
+using namespace std;
+
+int digits(int n)
+{
+	int r=0;
+	while(n)
+	{
+		r++;
+		n/=10;
+	}
+	return r;
+}
+
+int main()
+{
+	int l,r,sup;
+	long long tmp;
+	scanf("%d %d",&l,&r);
+	vector<long long> luck;
+	sup=digits(r);
+	for(int i=digits(l);i<=sup+1;i++)
+	{
+		for(long long j=0;j<(1LL<<i);j++)
+		{
+			tmp=0;
+			for(int k=0;k<i;k++)
+				tmp=tmp*10+(j&(1LL<<k)?4:7);
+			if(tmp>=l)
+				luck.push_back(tmp);
+		}
+	}
+	sort(luck.begin(),luck.end());
+	long long ans=0;
+	int i,ant=l-1;
+	for(i=0;luck[i]<r;i++)
+	{
+	//	printf("#%lli\n",luck[i]);
+		ans+=(luck[i]-ant)*luck[i];
+		ant=luck[i];
+	}
+	ans+=(r-ant)*luck[i];
+	printf("%I64d\n",ans);
+}
+s=raw_input()
+i=0
+ans='9'
+rep=dict()
+while i<len(s):
+	j=i
+	while j<len(s) and (s[j]=='4' or s[j]=='7'):
+		j+=1
+	for k in range(i,j):
+		for r in range(k+1,j+1):
+			if s[k:r] in rep:
+				rep[s[k:r]]+=1
+			else:
+				rep[s[k:r]]=1
+	i=j+1
+try:
+	q=rep[max(rep,key=lambda x:rep[x])]
+except:
+	print -1
+	exit(0)
+for x in rep:
+	if rep[x]==q:
+		ans=min(ans,x)
+print ans
+n,a,b=[int(x) for x in raw_input().split()]
+print max(0,n-max(a,n-b-1))
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<cstdio>
+
+using namespace std;
+
+bool order(string a,string b)
+{
+	int aa,bb;
+	sscanf(a.c_str(),"%d",&aa);
+	sscanf(b.c_str(),"%d",&bb);
+	return aa<bb;
+}
+
+int main()
+{
+	int n,k,aa,bb,r=1<<30;
+	cin>>n>>k;
+	vector<int> p(k);
+	vector<string> A(n);
+	for(int i=0;i<k;i++)
+		p[i]=i;
+	for(int i=0;i<n;i++)
+		cin>>A[i];
+	do
+	{
+		vector<string> B(n);
+		for(int i=0;i<n;i++)
+			for(int j=0;j<k;j++)
+				B[i].push_back(A[i][p[j]]);
+		sort(B.begin(),B.end(),order);
+		sscanf(B[0].c_str(),"%d",&aa);
+		sscanf(B[n-1].c_str(),"%d",&bb);
+		if(bb-aa<r)
+		{
+			r=bb-aa;
+		}
+	} while(next_permutation(p.begin(),p.end()));
+	cout<<r<<endl;
+}
+#include<iostream>
+#include<algorithm>
+
+using namespace std;
+
+long long ceil(long long num,long long den) {
+    if(num%den==0)
+        return num/den;
+    return num/den+1;
+}
+
+void print(int a,int b) {
+    cout<<a<<" "<<b<<"\n";
+}
+
+int main() {
+    int t1,t2,x1,x2,t0;
+    cin>>t1>>t2>>x1>>x2>>t0;
+    if(t1==t0) {
+        if(t1==t2)
+            print(x1,x2);
+        else
+            print(x1,0);
+        return 0;
+    }
+    if(t0==t2) {
+        print(0,x2);
+        return 0;
+    }
+
+    int y1=0,y2=x2;
+    long long tn=t2,td=1;
+    for(int x=1;x<=x1;x++) {
+        long long y = ceil((t0-t1)*(long long)x,t2-t0);
+        if(y>x2)
+            continue;
+        long long txn = (long long)t1*x+(long long)t2*y;
+        long long txd = x+y;
+        long long g = __gcd(txn,txd);
+        txn/=g;
+        txd/=g;
+//        cout<<"# "<<x<<" "<<y<<" "<<tx<<endl;
+        if(txn*td<txd*tn) {
+            tn = txn;
+            td = txd;
+            y1 = x;
+            y2 = y;
+        }
+        else if(txn*td==txd*tn)
+            if(x+y>y1+y2) {
+                y1 = x;
+                y2 = y;
+            }
+    }
+    print(y1,y2);
+}
+def ceil(num,den):
+    if num%den == 0:
+        return num/den
+    return num/den+1
+
+t1, t2, x1, x2, t0 = [int(x) for x in raw_input().split()]
+
+if t1 == t0:
+    if t1 == t2:
+        print x1,x2
+    else:
+        print x1,0
+    exit(0)
+if t0 == t2:
+    print 0,x2
+    exit(0)
+
+y1, y2 = 0, x2
+tt = t2
+
+for x in range(1,x1+1):
+    y = ceil((t0-t1)*x,t2-t0)
+    if y>x2:
+        continue
+    tx = float(t1*x+t2*y)/(x+y)
+#    print '#',x,y,tx
+    if tx<tt:
+        tt = tx
+        y1, y2 = x, y
+    elif tx==tt:
+        if x+y>y1+y2:
+            y1, y2 = x, y
+
+print y1,y2
+#include<iostream>
+#include<vector>
+
+using namespace std;
+
+vector<int> buildpi(string P) {
+    auto m = P.size();
+    vector<int> pi(m);
+    pi[0] = -1;
+    int k = -1;
+    for(int q=1; q<m; q++) {
+        while(k>=0 and P[k+1]!=P[q])
+            k = pi[k];
+        if(P[k+1]==P[q])
+            k++;
+        pi[q] = k;
+    }
+    for(auto &x:pi)
+        x++;
+    return pi;
+}
+
+int main() {
+    string s;
+    cin>>s;
+    auto pi = buildpi(s);
+    int ans = pi[s.size()-1];
+/*    for(auto x:pi)
+        cout<<x<<" ";
+    cout<<endl;*/
+    while(ans>0) {
+        bool found = false;
+        for(int i=s.size()-2;not found and i>=ans;i--)
+            if(pi[i]>=ans)
+                found = true;
+        if(found)
+            break;
+        ans=pi[ans-1];
+    }
+    if(ans==0)
+        cout<<"Just a legend"<<endl;
+    else
+        cout<<s.substr(0,ans)<<endl;
+}
+from math import sqrt
+
+def dist(a,b):
+	return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
+
+n,k=[int(x) for x in raw_input().split()]
+ini=[int(x) for x in raw_input().split()]
+ans=0
+for i in range(n-1):
+	t=[int(x) for x in raw_input().split()]
+	ans+=dist(ini,t)
+	ini=t
+print ans*k/50.0
+n = int(raw_input())
+A = [int(x) for x in raw_input().split()]
+
+A.sort()
+
+i = 1
+k = 0
+B = [1]
+while i<len(A):
+    if A[i]==A[i-1]:
+        B[k] += 1
+    else:
+        k +=1
+        B.append(1)
+    i += 1
+B = [x/2 for x in B]
+
+print sum(B)/2
+M=[]
+M.append(raw_input())
+M.append(raw_input())
+M.append(raw_input())
+
+for i in range(3):
+	for j in range(3):
+		if M[2-i][2-j]!=M[i][j]:
+			print 'NO'
+			exit(0)
+
+print 'YES'
+n=raw_input()
+mini=(1<<31)-1
+digits=[0]*10
+for x in n:
+	digits[int(x)]+=1
+for i in range(1,10):
+	if digits[i]!=0:
+		break
+if digits[i]==0:
+	mini='0'
+else:
+	mini=str(i)+'0'*digits[0]
+	digits[i]-=1
+	while i<10:
+		mini+=str(i)*digits[i]
+		i+=1
+if mini==raw_input():
+	print 'OK'
+else:
+	print 'WRONG_ANSWER'
+n = int(raw_input())
+A = [int(x) for x in raw_input().split()]
+B = [0] * n
+for i,x in enumerate(A):
+    B[x-1] = i + 1
+
+for i in range(n-1):
+    print B[i],
+print B[-1]
+a,c = [int(x) for x in raw_input().split()]
+ans = 0
+fact = 1
+while a or c:
+    ans += ((3+(c%3)-(a%3)) % 3) * fact
+    c /= 3
+    a /= 3
+    fact *= 3
+print ans
+s = raw_input()
+ans = 0
+cn = 0
+ch = ''
+for x in s :
+    if not cn :
+        cn = 1
+        ch = x
+    elif x != ch :
+        ans +=1
+        ch = x
+        cn = 1
+    else:
+        cn += 1
+        if cn == 5 :
+            ans +=1
+            cn = 0
+if cn:
+    ans += 1
+print ans
+n = int(raw_input())
+A = [int(x) for x in raw_input().split()]
+A.sort()
+i = 1
+c = 0
+for x in A:
+    if i > n :
+        break
+    if i == x:
+        i += 1
+        c += 1
+    elif i < x:
+        if x > n :
+            break
+        i = x+1
+        c += 1
+print n-c
+n=int(raw_input())
+A=[int(x) for x in raw_input().split()]
+aa=sum(A)
+while n-aa>0:
+	n-=aa
+i=0
+while 1:
+	n-=A[i]
+	if n<=0:
+		break
+	i=(i+1)%7
+print i+1
+from math import ceil
+n=int(raw_input())
+A=[]
+for i in range(n):
+	A.append([int(x) for x in raw_input().split()])
+B=[]
+m=int(raw_input())
+for i in range(m):
+	B.append([int(x) for x in raw_input().split()])
+ans=0
+for x in A:
+	per=2*(x[0]+x[1])
+	he=x[2]
+	this=1<<30
+	for y in B:
+		if y[0]>=he:
+			hor=ceil(float(per)/y[1])
+			q=int(ceil(hor/(y[0]/he)))
+			this=min(this,q*y[2])
+	ans+=this
+print ans
+
+k=0
+
+def isvowel(s):
+	return s=='a' or s=='e' or s=='i' or s=='o' or s=='u'
+
+def qsch(A):
+	for j in range(len(A)):
+		x=A[j]
+		i=len(x)-1
+		c=0
+		while i>=0:
+			if isvowel(x[i]):
+				c+=1
+			if(c==k):
+				break
+			i-=1
+		if(c<k):
+			return 'NO'
+		A[j]=x[i:]
+	if(A[0]==A[1]==A[2]==A[3]):
+		return 'aaaa'
+	if(A[0]==A[1] and A[2]==A[3]):
+		return 'aabb'
+	if(A[0]==A[2] and A[1]==A[3]):
+		return 'abab'
+	if(A[0]==A[3] and A[1]==A[2]):
+		return 'abba'
+	return 'NO'
+
+n,k=[int(x) for x in raw_input().split()]
+ans='aaaa'
+for i in range(n):
+	A=[]
+	for j in range(4):
+		A.append(raw_input())
+	tt=qsch(A)
+	if ans=='aaaa':
+		ans=tt
+	elif ans!=tt and tt!='aaaa':
+		ans='NO'
+		break
+print ans
+n=int(raw_input())
+
+from fractions import gcd
+
+suma=0
+for i in range(2,n):
+	m=n
+	while(m>0):
+		suma+=m%i
+		m/=i
+g=gcd(suma,n-2)
+print str(suma/g)+"/"+str((n-2)/g)
+from math import asin,pi
+
+n,R,r = [int(x) for x in raw_input().split()]
+
+if R < r:
+    print 'NO'
+    exit(0)
+if R-r < r:
+    if n == 1:
+        print 'YES'
+    else:
+        print 'NO'
+    exit(0)
+
+ang = 2 * asin(float(r)/(R-r))
+if n*ang <= 2*pi or abs(n*ang-2*pi) <= 1e-9:
+    print 'YES'
+else:
+    print 'NO'
+r = [int(x) for x in raw_input().split()]
+c = [int(x) for x in raw_input().split()]
+d = [int(x) for x in raw_input().split()]
+
+def valid(a1, a2, b1, b2) :
+    if len(set([a1,a2,b1,b2])) != 4:
+        return False
+    x = a1+a2==r[0] and b1+b2==r[1]
+    y = a1+b1==c[0] and a2+b2==c[1]
+    z = a1+b2==d[0] and a2+b1==d[1]
+    if x and y and z:
+        print a1,a2
+        print b1,b2
+        return True
+
+enc = False
+
+for a1 in range(1,10):
+    for a2 in range(1,10):
+        for b1 in range(1,10):
+            for b2 in range(1,10):
+                if valid(a1, a2, b1, b2) :
+                    enc = True
+                    break
+            if enc:
+                break
+        if enc:
+            break
+    if enc:
+        break
+if not enc:
+    print -1
+s = raw_input().split('.')
+if len(s)==1:
+    intg = s[0]
+    dcml = ''
+else:
+    intg = s[0]
+    dcml = s[1]
+minus = 0
+if intg[0] == '-':
+    intg = intg[1:]
+    minus = 1
+dcml = dcml[:2]
+if len(dcml)<2:
+    dcml += '0'*(2-len(dcml))
+
+tmp = intg[:len(intg)%3]
+for i in range(len(intg)%3,len(intg),3):
+    tmp += ','+intg[i:i+3]
+if tmp[0] == ',':
+    intg = tmp[1:]
+else:
+    intg = tmp
+
+ans = ''
+if minus:
+    ans += '('
+ans += '$'+intg+'.'+dcml
+if minus:
+    ans += ')'
+print ans
+n=int(raw_input())
+A=[int(x) for x in raw_input().split()]
+mini=0
+for i in range(1,n):
+	if A[i]<=A[mini]:
+		mini=i
+maxi=n-1
+for i in range(n-1,-1,-1):
+	if A[i]>=A[maxi]:
+		maxi=i
+ans=n-mini-1+maxi
+if mini<maxi:
+	ans-=1
+print ans
+#include<cmath>
+#include<cstdio>
+#include<vector>
+
+using namespace std;
+
+struct point
+{
+	int x,y,r;
+	point(){}
+	point(int xx,int yy,int rr=0)
+	{
+		x=xx;
+		y=yy;
+		r=rr;
+	}
+};
+
+double dist(point &a,point &b)
+{
+	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
+}
+vector<point> rad;
+int n;
+
+bool llega(point p)
+{
+	for(int j=0;j<n;j++)
+		if(dist(p,rad[j])<=rad[j].r)
+			return true;
+	return false;
+}
+
+int main()
+{
+	int xa,ya,xb,yb;
+	scanf("%d %d %d %d",&xa,&ya,&xb,&yb);
+	scanf("%d",&n);
+	rad.resize(n);
+	int x,y,r;
+	for(int i=0;i<n;i++)
+	{
+		scanf("%d %d %d",&x,&y,&r);
+		rad[i]=point(x,y,r);
+	}
+	if(xa>xb)
+	{
+		swap(xa,xb);
+		swap(ya,yb);
+	}
+	int ans=0;
+	for(int i=xa;i<=xb;i++)
+		ans+=not llega(point(i,ya));
+	for(int i=xa;i<=xb;i++)
+		ans+=not llega(point(i,yb));
+	if(ya<yb)
+	{
+		for(int i=ya+1;i<yb;i++)
+			ans+=not llega(point(xb,i));
+		for(int i=ya+1;i<yb;i++)
+			ans+=not llega(point(xa,i));
+	}
+	else
+	{
+		for(int i=yb+1;i<ya;i++)
+			ans+=not llega(point(xb,i));
+		for(int i=yb+1;i<ya;i++)
+			ans+=not llega(point(xa,i));
+	}
+	printf("%d\n",ans);
+}
+#include<vector>
+#include<cstdio>
+#include<iostream>
+
+using namespace std;
+vector<int> P(27);
+
+vector<int> operator-(vector<int> a,vector<int> b)
+{
+	if(a.size()!=b.size())
+		return vector<int> ();
+	for(int i=0;i<a.size();i++)
+		a[i]-=b[i];
+	return a;
+}
+
+int val(char c)
+{
+	if(c=='?')
+		return 26;
+	return c-'a';
+}
+
+bool isgood(vector<int> A)
+{
+	int diff=0;
+	for(int i=0;i<26;i++)
+	{
+		if(A[i]>P[i])
+			return false;
+		diff+=P[i]-A[i];
+	}
+	return diff==A[26];
+}
+
+int main()
+{
+	string s,p;
+	cin>>s>>p;
+	vector<int> S[s.size()];
+	for(int i=0;i<s.size();i++)
+		S[i].resize(27);
+	for(int i=0;i<27;i++)
+		S[0][i]=0;
+	S[0][val(s[0])]=1;
+	for(int i=1;i<s.size();i++)
+	{
+		for(int j=0;j<27;j++)
+			S[i][j]=S[i-1][j];
+		S[i][val(s[i])]++;
+	}
+	for(int i=0;i<p.size();i++)
+		P[i]=0;
+	for(int i=0;i<p.size();i++)
+		P[val(p[i])]++;
+	int ans=0;
+	if(p.size()<=s.size())
+		ans=isgood(S[p.size()-1]);
+	for(int i=1;i<=(int)s.size()-(int)p.size();i++)
+		ans+=isgood(S[i+p.size()-1]-S[i-1]);
+	printf("%d\n",ans);
+}
+#include<queue>
+#include<cstdio>
+
+using namespace std;
+int n,l;
+vector<pair<int,int> > adj[100001],adj2[100001];
+int d[100001];
+
+int BFS(int s)
+{
+	queue<int> Q;
+	int pi[n],visit[n];
+	for(int i=0;i<n;i++)
+		d[i]=1<<30,visit[i]=0;;
+	d[s]=0;
+	Q.push(s);
+	int ans=0;
+	while(not Q.empty())
+	{
+		int u=Q.front(),v,w;
+		Q.pop();
+		if(visit[u])
+			continue;
+		visit[u]=1;
+		if(d[u]==l)
+			ans++;
+		for(auto pp:adj[u])
+		{
+			v=pp.first;
+			w=pp.second;
+			if(d[v]>d[u]+w)
+			{
+				d[v]=d[u]+w;
+				pi[v]=u;
+				Q.push(v);
+			}
+		}
+	}
+	return ans;
+}
+
+int main()
+{
+	int m,s;
+	scanf("%d %d %d",&n,&m,&s);
+	s--;
+	int u,v,w;
+	for(int i=0;i<m;i++)
+	{
+		scanf("%d %d %d",&u,&v,&w);
+		u--,v--;
+		adj[u].push_back(make_pair(v,w));
+		adj[v].push_back(make_pair(u,w));
+		adj2[u].push_back(make_pair(v,w));
+	}
+	scanf("%d",&l);
+	int ans=BFS(s);
+	//printf("#%d\n",ans);
+	for(int u=0;u<n;u++)
+		for(auto pp:adj2[u])
+		{
+			v=pp.first;
+			w=pp.second;
+			bool a1,a2;
+			if(a1=(l>d[u] and l<d[u]+w))
+				ans++;
+			if(a2=(l>d[v] and l<d[v]+w))
+				ans++;
+			if(a1 and a2 and l-d[u]+l-d[v]==w)
+					ans--;
+		}
+	printf("%d\n",ans);
+}
+def just47(s):
+    for x in s:
+        if x != '4' and x != '7' :
+            return False
+    return True
+
+n = int(raw_input())
+s = raw_input()
+if just47(s) and sum([int(x) for x in s[:n/2]]) == sum([int(x) for x in s[n/2:]]) :
+    print 'YES'
+else:
+    print 'NO'
+k = int(raw_input())
+l = int(raw_input())
+m = int(raw_input())
+n = int(raw_input())
+d = int(raw_input())
+
+ans = 0
+for i in range(1,d+1):
+    for x in (k,l,m,n):
+        if i%x == 0:
+            ans += 1
+            break
+print ans
+k = int(raw_input())
+A = [int(x) for x in raw_input().split()]
+A.sort(reverse=True)
+
+s = 0
+c = 0
+for x in A:
+    if s >=k:
+        break
+    s += x
+    c += 1
+
+if s>=k:
+    print c
+else:
+    print -1
+n,k,l,c,d,p,nl,np = [int(x) for x in raw_input().split()]
+liquid = k * l
+lemon = c * d
+
+print min(liquid/(nl*n), lemon/n, p/(np*n))
+def allequal(s):
+    c = s[0]
+    for x in s[1:]:
+        if x == '-':
+            pass
+        elif x != c:
+            return False
+    return True
+
+def decre(s):
+    c = s[0]
+    for x in s[1:]:
+        if x == '-':
+            continue
+        elif x >= c:
+            return False
+        c = x
+    return True
+
+class PhBook(object):
+    def __init__(self,name,L):
+        self.tx = 0
+        self.pz = 0
+        self.gl = 0
+        self.name = name
+        for x in L:
+            if allequal(x):
+                self.tx += 1
+            elif decre(x):
+                self.pz += 1
+            else:
+                self.gl += 1
+    def __str__(self):
+        return self.name
+
+n = int(raw_input())
+P = list()
+for i in range(n):
+    s = raw_input().split()
+    c = int(s[0])
+    name = s[1]
+    L = list()
+    for j in range(c):
+        L.append(raw_input())
+    P.append(PhBook(name,L))
+
+def liststr(L):
+    s = L[0]
+    for i in range(1,len(L)):
+        s += ', '+L[i]
+    return s
+
+tx = max(P, key = lambda x: x.tx)
+print 'If you want to call a taxi, you should call: '+liststr([str(x) for x in P if x.tx==tx.tx])+'.'
+pz = max(P, key = lambda x: x.pz)
+print 'If you want to order a pizza, you should call: '+liststr([str(x) for x in P if x.pz==pz.pz])+'.'
+gl = max(P, key = lambda x: x.gl)
+print 'If you want to go to a cafe with a wonderful girl, you should call: '+liststr([str(x) for x in P if x.gl==gl.gl])+'.'
+n,m = [int(x) for x in raw_input().split()]
+A = [''] * n
+suc = set()
+for i in range(n):
+    A[i] = raw_input()
+
+def findmax(c):
+    m = -1
+    for i in range(n):
+        if m < int(A[i][c]) :
+            m = int(A[i][c])
+    for i in range(n):
+        if m == int(A[i][c]):
+            suc.add(i)
+
+for i in range(m):
+    findmax(i)
+print len(suc)
+n, k = [int(x) for x in raw_input().split()]
+A = [int(x) for x in raw_input().split()]
+pos = 0
+while pos < n and A[pos]>0:
+    pos += 1
+ad = k
+while ad < n and A[ad] == A[k-1]:
+    ad +=1
+print min(ad,pos)
+#include<cstdio>
+#include<bits/stl_algobase.h>
+
+using std::min;
+
+int main()
+{
+    int n,A[]={0,0,0,0,0},tmp;
+    scanf("%d",&n);
+    for(int i=0;i<n;i++)
+    {
+        scanf("%d",&tmp);
+        A[tmp]++;
+    }
+    int ans=A[4];
+    tmp=min(A[1],A[3]);
+    ans+=tmp;
+    A[1]-=tmp;
+    A[3]-=tmp;
+    ans+=A[3]+A[2]/2+A[1]/4;
+    A[2]%=2;
+    A[1]%=4;
+    tmp=A[1]+2*A[2];
+    if(tmp>4)
+        ans+=2;
+    else if(tmp>0)
+        ans+=1;
+    printf("%d\n",ans);
+}
+path=list()
+
+def enter(s):
+    if(s=='..'):
+        if path:
+            del path[-1]
+    else:
+        path.append(s)
+
+def thepath():
+    s=str()
+    if(not path):
+        return '/'
+    for x in path:
+        s+='/'+x
+    return s+'/'
+
+n=int(raw_input())
+while n:
+    s=raw_input()
+    if(s=='pwd'):
+        print thepath()
+    else:
+        s=s.split()[1]
+        if s[0]=='/':
+            path=list()
+        for x in s.strip('/').split('/'):
+            if(x):
+                enter(x)
+    n-=1
+#include<cstdio>
+#include<cmath>
+#include<bits/stl_algobase.h>
+
+using std::max;
+
+int n,A[20001];
+
+int calc(int lados)
+{
+    int ans=-1000*n,tmp;
+    if(lados<=2)
+        return ans;
+    for(int i=0;i<n/lados;i++)
+    {
+        tmp=0;
+        for(int j=i;j<n;j+=n/lados)
+            tmp+=A[j];
+        ans=max(ans,tmp);
+    }
+    return ans;
+}
+
+int main()
+{
+    scanf("%d",&n);
+    for(int i=0;i<n;i++)
+        scanf("%d",&A[i]);
+    int ans=calc(n);
+    for(int i=2;i<=sqrt(n);i++)
+        if(n%i==0)
+        {
+            ans=max(calc(i),ans);
+            ans=max(calc(n/i),ans);
+        }
+    printf("%d\n",ans);
+}
+#include<map>
+#include<iostream>
+#include<cstdio>
+#include<set>
+#include<vector>
+
+using namespace std;
+
+typedef pair<string,string> pss;
+
+int main()
+{
+    int n;
+    int d;
+    map<pss, vector<int> > M;
+    set<pss> ans;
+    string s1,s2;
+    int ti;
+    scanf("%d %d",&n,&d);
+    for(int i=0;i<n;i++)
+    {
+        cin>>s1>>s2;
+        scanf("%d",&ti);
+        pss t1(s1,s2),t2(s2,s1);
+        if(M.find(t2)!=M.end())
+        {
+            vector<int> &times=M[t2];
+            for(int i=times.size()-1,tmp=0;i>=0 and tmp<=d;i--)
+            {
+                tmp=ti-times[i];
+                if(tmp<=d and tmp>0)
+                {
+                    ans.insert(pss(min(s1,s2),max(s1,s2)));
+                    break;
+                }
+            }
+        }
+        M[t1].push_back(ti);
+    }
+    printf("%d\n",ans.size());
+    for(auto rel:ans)
+        cout<<rel.first<<" "<<rel.second<<"\n";
+}
+#include<cstdio>
+#include<algorithm>
+
+using namespace std;
+typedef pair<int,int> pii;
+pii mark[100001],tap[100001];
+int n,m;
+
+pii operator+(pii a,pii b)
+{
+    a.first+=b.first;
+    a.second+=b.second;
+    return a;
+}
+
+pii operate(int ini1,int fin1,int ini2,int fin2)
+{
+//    printf("%d %d %d %d: %d\n",ini1,fin1,ini2,fin2,ini1<n?mark[ini1].first:-1);
+    pii ans(0,0);
+    ans.first=min(fin1-ini1,fin2-ini2);
+    int i=ini1,j=ini2;
+    while(i<fin1 and j<fin2)
+    {
+//        printf(">%d %d\n",mark[i].second,tap[j].second);
+        if(mark[i].second==tap[j].second)
+            ans.second++,i++,j++;
+        else if(mark[i].second<tap[j].second)
+            i++;
+        else
+            j++;
+    }
+    return ans;
+}
+
+int main()
+{
+    scanf("%d %d",&n,&m);
+    int t1,t2;
+    pii ans(0,0);
+    for(int i=0;i<n;i++)
+    {
+        scanf("%d %d",&t2,&t1);
+        mark[i]=pii(t1,t2);
+    }
+    sort(mark,mark+n);
+    for(int i=0;i<m;i++)
+    {
+        scanf("%d %d",&t2,&t1);
+        tap[i]=pii(t1,t2);
+    }
+    sort(tap,tap+m);
+    int last1=0,last2=0;
+    int i=0,j=0;
+    while(i<n and j<m)
+    {
+        while(i<n and mark[i].first==mark[last1].first)
+            i++;
+        while(j<m and tap[j].first<mark[last1].first)
+            j++;
+        last2=j;
+        while(j<m and tap[j].first==mark[last1].first)
+            j++;
+        ans=ans+operate(last1,i,last2,j);
+        last1=i;
+        last2=j;
+    }
+    printf("%d %d\n",ans.first,ans.second);
+}
+#include<vector>
+#include<cstdio>
+#include<algorithm>
+
+using namespace std;
+
+int main()
+{
+	int n,t;
+	scanf("%d %d",&n,&t);
+	vector<pair<int,int> > ho(n);
+	for(int i=0;i<n;i++)
+		scanf("%d %d",&ho[i].first,&ho[i].second);
+	sort(ho.begin(),ho.end(),[](pair<int,int> a,pair<int,int> b)
+		{
+			return a.first<b.first;
+		});
+	int ans=2,d;
+	for(int i=0;i<n-1;i++)
+	{
+		d=(ho[i+1].first-ho[i].first)*2-(ho[i+1].second+ho[i].second);
+		if(d==2*t)
+			ans++;
+		else if (d>2*t)
+			ans+=2;
+	}
+	printf("%d\n",ans);
+}
+#include<cstdio>
+#include<vector>
+
+using namespace std;
+typedef pair<int,int> pii;
+
+int main()
+{
+    int n,m,x,y;
+    scanf("%d %d %d %d",&n,&m,&x,&y);
+    int A[100001],B[100001];
+    for(int i=0;i<n;i++)
+        scanf("%d",&A[i]);
+    for(int i=0;i<m;i++)
+        scanf("%d",&B[i]);
+    vector<pii> ans;
+    int i=0,j=0;
+    while(i<n and j<m)
+    {
+        if(A[i]-x<=B[j] and B[j]<=A[i]+y)
+        {
+            ans.push_back(pii(i+1,j+1));
+            i++,j++;
+        }
+        else if(A[i]-x>B[j])
+            j++;
+        else
+            i++;
+    }
+    printf("%d\n",ans.size());
+    for(auto x:ans)
+        printf("%d %d\n",x.first,x.second);
+}
+#include<cstdio>
+#include<algorithm>
+#include<iostream>
+
+using namespace std;
+
+struct obj
+{
+    long long pr;
+    int id;
+    bool t;
+    obj(long long pr,bool t,int id)
+    {
+        this->pr=pr;
+        this->t=t;
+        this->id=id;
+    }
+    obj(){}
+};
+
+bool order(obj a,obj b)
+{
+    if(a.t==b.t)
+        return a.pr>=b.pr;
+    return a.t<b.t;
+}
+
+int main()
+{
+    int n,k;
+    scanf("%d %d",&n,&k);
+    obj A[1001];
+    int pr,t;
+    for(int i=0;i<n;i++)
+    {
+        scanf("%d %d",&pr,&t);
+        A[i]=obj(2LL*pr,t-1,i+1);
+    }
+    sort(A,A+n,order);
+    int i=k;
+    long long ans=0;
+    for(int i=0;i<k-1;i++)
+    {
+        if(A[i].t)
+            ans+=A[i].pr;
+        else
+            ans+=A[i].pr/2;
+    }
+    if(A[k-1].t)
+        for(int i=k-1;i<n;i++)
+            ans+=A[i].pr;
+    else
+    {
+        long long mini=A[k-1].pr;
+        for(int i=k-1;i<n;i++)