CodeForces - 574A
Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.
There are n candidates, including Limak. We know how many citizens are going to vote for each candidate. Nowi-th candidate would get ai votes. Limak is candidate number1. To win in elections, he must get strictly more votes than any other candidate.
Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?
Input
The first line contains single integer n (2 ≤ n ≤ 100) - number of candidates.
The second line contains n space-separated integersa1, a2, ..., an (1 ≤ ai ≤ 1000) - number of votes for each candidate. Limak is candidate number 1.
Note that after bribing number of votes for some candidate might be zero or might be greater than1000.
Output
Example
Note
In the first sample Limak has 5 votes. One of the ways to achieve victory is to bribe4 citizens who want to vote for the third candidate. Then numbers of votes would be9, 1, 7, 2, 8 (Limak would have 9 votes). Alternatively, Limak could steal only 3 votes from the third candidate and1 vote from the second candidate to get situation 9, 0, 8, 2, 8.
In the second sample Limak will steal 2 votes from each candidate. Situation will be7, 6, 6, 6.
In the third sample Limak is a winner without bribing any citizen.
嗯，還是得給自己打氣，加油
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int digit[105];
int main()
{
priority_queue<int> qu;
int n;
scanf("%d",&n);
scanf("%d",&digit[1]);
for(int i=2;i<=n;i++)
{
scanf("%d",&digit[i]);
qu.push(digit[i]);
}//資料讀入
int sum=0;
while(qu.empty()==0)
{
int gg=qu.top();
qu.pop();
if(digit[1]>gg)
break;
digit[1]++;
gg--;
qu.push(gg);
sum++;
}
printf("%d\n",sum);
return 0;
}
CodeForces - 574B
Do you know a story about the three musketeers? Anyway, you will learn about its origins now.
Richelimakieu is a cardinal in the city of Bearis. He is tired of dealing with crime by himself. He needs three brave warriors to help him to fight against bad guys.
There are n warriors. Richelimakieu wants to choose three of them to become musketeers but it's not that easy. The most important condition is that musketeers must know each other to cooperate efficiently. And they shouldn't be too well known because they could be betrayed by old friends. For each musketeer hisrecognition is the number of warriors he knows, excluding other two musketeers.
Help Richelimakieu! Find if it is possible to choose three musketeers knowing each other, and what is minimum possible sum of their recognitions.
Input
The first line contains two space-separated integers, n andm (3 ≤ n ≤ 4000,0 ≤ m ≤ 4000) — respectively number of warriors and number of pairs of warriors knowing each other.
i-th of the following m lines contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n,ai ≠ bi). Warriorsai andbi know each other. Each pair of warriors will be listed at most once.
Output
Example
5 6
1 2
1 3
2 3
2 4
3 4
4 5
2
7 4
2 1
3 6
5 1
1 7
-1
Note
In the first sample Richelimakieu should choose a triple 1, 2, 3. The first musketeer doesn't know anyone except other two musketeers so his recognition is0. The second musketeer has recognition 1 because he knows warrior number 4. The third musketeer also has recognition1 because he knows warrior 4. Sum of recognitions is0 + 1 + 1 = 2.
The other possible triple is 2, 3, 4 but it has greater sum of recognitions, equal to1 + 1 + 1 = 3.
In the second sample there is no triple of warriors knowing each other.
表示識别度 差不多就等于離散數學中的識别度
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int digit[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&digit[i]);
while(digit[i]%2==0)digit[i]=digit[i]/2;
while(digit[i]%3==0)digit[i]=digit[i]/3;
}
digit[n+1]=digit[n];
int flag=0;
for(int i=1;i<=n;i++)
{
if(digit[i]!=digit[i+1])
{
flag=1;
break;
}
}
if(flag)
printf("NO\n");
else printf("YES\n");
return 0;
}
CodeForces - 574C
Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There aren players (including Limak himself) and right now all of them have bids on the table.i-th of them has bid with size ai dollars.
Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?
Input
First line of input contains an integer n (2 ≤ n ≤ 105), the number of players.
The second line contains n integer numbersa1, a2, ..., an (1 ≤ ai ≤ 109) — the bids of players.
Output
Example
4
75 150 75 50
Yes
3
100 150 250
No
Note
In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.
It can be shown that in the second sample test there is no way to make all bids equal.
一心隻想約掉他的最大公因數之後看看是否一樣就沒了
哎 網上題解說這個是因為既然可以翻兩倍也可以翻3倍說明說這個數也是可以通過翻兩倍或者是翻三倍達到的那麼就可以選擇約掉
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int digit[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&digit[i]);
while(digit[i]%2==0)digit[i]=digit[i]/2;
while(digit[i]%3==0)digit[i]=digit[i]/3;
}
digit[n+1]=digit[n];
int flag=0;
for(int i=1;i<=n;i++)
{
if(digit[i]!=digit[i+1])
{
flag=1;
break;
}
}
if(flag)
printf("NO\n");
else printf("YES\n");
return 0;
}