Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. Of course there are certain requirements.
Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang's selection any two of them who are still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.
Input
The first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤ 10000000)
Output
The output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep.
Sample Input
4 1 2 3 4 5 6 1 6 4 1 2 3 4 5 6 7 8
Sample Output
4 2
Hint
A and B are friends(direct or indirect), B and C are friends(direct or indirect),
then A and C are also friends(indirect).In the first sample {1,2,5,6} is the result.
In the second sample {1,2},{3,4},{5,6},{7,8} are four kinds of answers.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x7ffffff
#define P pair<int,int>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int n,f[10000010],nub[10000010],mx=1;
int fd(int x){if(x!=f[x])f[x]=fd(f[x]);return f[x];
}
int main()
{while(cin>>n){mx=1;for(int i=1;i<=10000001;i++){f[i]=i;nub[i]=1;}for(int i=1;i<=n;i++){int a,b;cin>>a>>b;int f1=fd(a),f2=fd(b);if(f1!=f2){f[f1]=f2;nub[f2]+=nub[f1];if(nub[f2]>mx);mx=nub[f2];}}printf("%dn",mx);}return 0;
}Write a program to read in a list of integers and determine whether or not each number is prime. A number, n, is prime if its only divisors are 1 and n. For this problem, the numbers 1 and 2 are not considered primes.
Input
Each input line contains a single integer. The list of integers is terminated with a number<= 0. You may assume that the input contains at most 250 numbers and each number is less than or equal to 16000.
Output
The output should consists of one line for every number, where each line first lists the problem number, followed by a colon and space, followed by "yes" or "no".
Sample Input
1 2 3 4 5 17 0
Sample Output
1: no 2: no 3: yes 4: no 5: yes 6: yes
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x7ffffff
#define P pair<int,int>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int isprime[100010] = {1, 1, 0};
void prime()
{for (int i=2; i<=100005; i++){if (!isprime[i]){for (int j=i+i; j<=100005; j+=i)isprime[j] = 1;}}
}
int main ()
{int n, ct=1;prime();while (scanf ("%d", &n) !=EOF){if (n <= 0) break;if (n == 2 || isprime[n])printf ("%d: non", ct++);else if (!isprime[n])printf ("%d: yesn", ct++);}return 0;
}You've got an n × m matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by 1. Each element can be increased an arbitrary number of times.
You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not.
A matrix is prime if at least one of the two following conditions fulfills:
Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 500) — the number of rows and columns in the matrix, correspondingly.
Each of the following n lines contains m integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed 105.
The numbers in the lines are separated by single spaces.
Output
Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 0.
Examples
Input
3 3 1 2 3 5 6 1 4 4 1
Output
1
Input
2 3 4 8 8 9 2 9
Output
3
Input
2 2 1 3 4 2
Output
0
Note
In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.
In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.
In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 2.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x7ffffff
#define P pair<int,int>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int prime[100010],mp[510][510],sumc[510],sumr[510];
int isprime[100010],ct;
void Prime(){ct=0;isprime[0]=isprime[1]=1;for(int i=2; i<100010; i++){if(!isprime[i])prime[ct++]=i;for(int j=0;j<ct&&prime[j]*i<100010; j++){isprime[i*prime[j]] = 1;if(i%prime[j]==0)break;}}
}
int main()
{int n,m;scanf("%d%d",&n,&m);Prime();for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&mp[i][j]);for(int i=0;i<n;i++){int sum=0;for(int j=0;j<m;j++){if(isprime[mp[i][j]]){int tmp=lower_bound(prime,prime+ct,mp[i][j])-prime;sumr[j]+=(prime[tmp]-mp[i][j]);sumc[i]+=(prime[tmp]-mp[i][j]);}}}sort(sumr,sumr+m);sort(sumc,sumc+n);cout<<((sumr[0]<sumc[0])?sumr[0]:sumc[0])<<endl;return 0;
}Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
Input
The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.
Output
The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.
Sample Input
2 3 3 1 2 2 3 1 3 4 2 1 2 3 4
Sample Output
Scenario #1: Suspicious bugs found!Scenario #2: No suspicious bugs found!
Hint
Huge input,scanf is recommended.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x7ffffff
#define P pair<int,int>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int t,ct=1,m,n,f[2010],pre[2010];
int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);
}
int main()
{scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){f[i]=i;pre[i]=0;}int fg=0,a,b,c,d;for(int i=0;i<m;++i){scanf("%d%d",&a,&b);if(fd(a)==fd(b))fg=1;c=pre[a];d=pre[b];if(c){c=fd(c);b=fd(b);if(c!=b)f[c]=b;}if(d){d=fd(d);a=fd(a);if(d!=a)f[a]=d;} pre[a]=b;pre[b]=a;}printf("Scenario #%d:n",ct++);if(fg)printf("Suspicious bugs found!n");elseprintf("No suspicious bugs found!n");printf("n");}return 0;
}
Some time ago Mister B detected a strange signal from the space, which he started to study.
After some transformation the signal turned out to be a permutation p of length n or its cyclic shift. For the further investigation Mister B need some basis, that's why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.
Let's define the deviation of a permutation p as .
Find a cyclic shift of permutation p with minimum possible deviation. If there are multiple solutions, print any of them.
Let's denote id k (0 ≤ k < n) of a cyclic shift of permutation pas the number of right shifts needed to reach this shift, for example:
Input
First line contains single integer n (2 ≤ n ≤ 106) — the length of the permutation.
The second line contains n space-separated integers p 1, p2, ..., p n (1 ≤ p i ≤ n) — the elements of the permutation. It is guaranteed that all elements are distinct.
Output
Print two integers: the minimum deviation of cyclic shifts of permutation p and the id of such shift. If there are multiple solutions, print any of them.
Examples
Input
3 1 2 3
Output
0 0
Input
3 2 3 1
Output
0 1
Input
3 3 2 1
Output
2 1
Note
In the first sample test the given permutation p is the identity permutation, that's why its deviation equals to 0, the shift id equals to 0 as well.
In the second sample test the deviation of p equals to 4, the deviation of the 1-st cyclic shift (1, 2, 3) equals to 0, the deviation of the 2-nd cyclic shift (3, 1, 2) equals to 4, the optimal is the 1-st cyclic shift.
In the third sample test the deviation of p equals to 4, the deviation of the 1-st cyclic shift (1, 3, 2) equals to 2, the deviation of the 2-nd cyclic shift (2, 1, 3) also equals to 2, so the optimal are both 1-st and 2-nd cyclic shifts.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x7ffffff
#define P pair<int,int>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int n,ct,sub,id,p[1000010],fg[1000010];
ll sum,jg;
int main(){scanf("%d",&n);for (int i=1; i<=n; i++) {scanf("%d",&p[i]);sum+=fabs(p[i]-i);fg[(p[i]-i+n)%n]++;if(p[i]>i) sub++;else ct++;}jg=sum;for(int i=1; i<n; i++){sum+=ct-sub-1;sum+=(p[n-i+1]-1)-(n-p[n-i+1]);ct=ct+fg[i]-1;sub=sub-fg[i]+1;if (sum<jg){jg=sum;id=i;}}printf("%lld %dn", jg, id);return 0;
}Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.
Input
The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.
Output
Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).
Sample Input
4 11 8.02 7.43 4.57 5.39
Sample Output
2.00
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x7ffffff
#define P pair<int,int>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int N,K;
double p[10010];
int pd(double mid){int ct=0;for(int i=0;i<N;i++)ct+=int(p[i]/mid);return ct>=K;
}
int main(){cin>>N>>K;for(int i=0;i<N;i++)cin>>p[i];double l=0,r=1000000,mid;for(int i=0;i<100;i++){mid=(l+r)/2;if(pd(mid))l=mid;elser=mid;}printf("%.2fn",floor(l*100)/100);return 0;
}
本文发布于:2024-01-28 23:07:52，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170645447910957.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
