Part of the questions in UPC games 41 and 42
Scene 41
A: LR Constraints
We have N cards arranged in a row from left to right. We will write an integer between 1 and K (inclusive) on each of these cards, which are initially blank.
Given are K restrictions numbered 1 through K. Restriction i is composed of a character ci and an integer ki. If ci is L, the ki-th card from the left in the row must be the leftmost card on which we write
i. If ci is R, the ki-th card from the left in the row must be the rightmost card on which we write i.
Note that for each integer i from 1 through K, there must be at least one card on which we write i.
Find the number of ways to write integers on the cards under the K restrictions, modulo 998244353.
N cards, the numbers above are 1~k, and then there are k restrictions. Each restriction has a letter (ci) and a number (KI). If ci is' L ', it means that the leftmost position i can input is Ki, and if ci is' R', it means that the rightmost position i can input is ki.
Constraints
1≤N,K≤1000
ci is L or R.
1≤ki≤N
ki≠kj if i≠j.
input
Input is given from Standard Input in the following format:
N K
c1 k1
⋮
cK kK
output
Find the number of ways to write integers on the cards under the K restrictions in the Problem Statement, modulo 998244353.
sample input
[[example 1] 3 2 L 1 R 2 [[example 2] 30 10 R 6 R 8 R 7 R 25 L 26 L 13 R 14 L 11 L 23 R 30
sample output
[[example 1] 1 [[example 2] 343921442
Simulate according to the requirements of the topic, and then use the multiplication principle to accumulate the contribution.
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=10005,mod = 998244353;
int vis1[maxn],vis2[maxn];
ll n,k,k1;
ll s[maxn];
char ch;
int main()
{
cin >> n >> k;
for(int i=1;i<=k;i++)
{
cin >> ch >> k1;
vis1[k1]=1;
if(ch=='L')
{
for(ll i=k1+1;i<=n;i++)
{
s[i]++;
}
}
else
{
for(ll i=1;i<k1;i++)
{
s[i]++;
}
}
}
ll ans=1;
for(ll i=1;i<=n;i++)
{
if(!vis1[i]) ans=(ans*s[i])%mod;
}
cout << ans;
return 0;
}
B: LCM of GCDs
We have a red bag, a blue bag, and N card packs. Initially, both bags are empty. Each card pack contains two cards with integers written on them. We know that the i-th card pack contains a card with ai and another with bi.
For each card pack, we will put one of its cards in the red bag, and the other in the blue bag.
After we put all cards in the bags, let X be the greatest common divisor of all integers written on cards in the red bag. Similarly, let Y be the greatest common divisor of all integers written on cards in the blue bag. Our score will be the least common multiple of X and Y.
Find the maximum possible score.
We have a red bag, a blue bag and N card bags. Initially, both bags were empty. Each card bag contains two cards with integers. As we know, the i-th card bag contains an ai card and another bi card.
For each card bag, we will put one card in the red bag and the other in the blue bag.
When we put all the cards in the bag, let X be the greatest common divisor of all the integers on the cards in the red bag. Similarly, let Y be the greatest common divisor of all integers written on the blue card. Our score will be the least common multiple of X and Y.
Find the maximum possible score.
Constraints
All values in input are integers.
1≤N≤50
1≤ai,bi≤109
input
Input is given from Standard Input in the following format:
N
a1 b1
⋮
aN bN
output
Print the maximum possible score.
sample input
[[example 1] 2 2 15 10 6 [[example 2] 5 148834018 644854700 947642099 255192490 35137537 134714230 944287156 528403260 68656286 200621680 [[example 3] 20 557057460 31783488 843507940 794587200 640711140 620259584 1901220 499867584 190122000 41414848 349507610 620259584 890404700 609665088 392918800 211889920 507308870 722352000 156850650 498904448 806117280 862969856 193607570 992030080 660673950 422816704 622015810 563434560 207866720 316871744 63057130 117502592 482593010 366954816 605221700 705015552 702500790 900532160 171743540 353470912
sample output
[[example 1] 10 [[example 2] 238630 [[example 3] 152594452160
Note that n < = 50, there are only two cases for each selection, a [ i ] , b [ i ] a[i],b[i] a[i],b[i],or b [ i ] , a [ i ] b[i],a[i] b[i],a[i], you might as well directly use dfs. Here, in order to prevent invalid backtracking in the search process, we use the set to mark the process we have done, which can greatly reduce the time.
c o d e code code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=105,mod = 998244353;
int a[maxn], b[maxn];
int n;
ll ans = 1;
set<pair<pair<int,int>,int>>st;
void dfs(ll d1,ll d2,int c)
{
if(st.count({{d1, d2}, c}))
{
return ;
}
if(c==n+1)
{
ans=max(ans,d1/__gcd(d1,d2)*d2);
return;
}
st.insert({{d1,d2},c});
dfs(__gcd(d1,(ll)a[c]), __gcd(d2,(ll)b[c]), c+1);
dfs(__gcd(d1,(ll)b[c]), __gcd(d2,(ll)a[c]), c+1);
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
scanf("%d%d", &a[i], &b[i]);
}
dfs(a[1],b[1],2);
cout << ans ;
}
D.Garbage Classification
On the CVBB planet, garbage classification has been gradually executed to help save resources and protect the environment. Nowadays people have to be equipped with knowledge of distinguishing different types of garbage. Now, given the waste compositions of a discarded product, you are asked to determine which category it belongs to.
The waste compositions are represented as a string s consisting of only lowercase letters, where each letter represents a waste composition and has an equal proportion. Each waste composition in that product is in one of the three situations, dry, wet or harmful.
The product can be classified by the following rules:
In case that at least 25% of its compositions is harmful, it is harmful garbage.
In case that at most 10% of its compositions is harmful, it is recyclable garbage.
In other cases, if the proportion of dry compositions in it is at least twice that of wet compositions, it is dry garbage, or otherwise, it is wet garbage.
input
There are multiple test cases. The first line contains an integer T (1≤T≤50), indicating the number of test cases. Test cases are given in the following.
For each test case, the first line contains a non-empty string s (1≤∣s∣≤2000) consisting of only lowercase letters.
The second line contains a string t of length 26, consisting of only characters in {d,w,h}. The i-th character of t represents the situation of the waste composition denoted by the i-th lowercase letter, where 'd', 'w' and 'h' mean dry, wet or harmful respectively.
output
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y (y∈{Harmful,Recyclable,Dry,Wet}) denotes the garbage type of the product in this test case.
sample input
4 dqxxjefgctjgdbqxphff hddhddhhhdhdhwwddhhdwwdhhw iqdvfzzdqsbdevzebego wdhddwwhwhdhhhwwdwdhwdwhhd erkjqzsmchcmbqeasadf dwddddwdwdwhdwhhdhhwwhhwdh mcxkwmxxlhbrymwawhio ddhwhddhwwwdddwdwhwwwhdwdw
sample output
Case #1: Harmful Case #2: Recyclable Case #3: Dry Case #4: Wet
Or a simulation question...
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=100005;
int n,cnt=0;
int m;
int main()
{
string s,s1;
cin >> m;
while(m--)
{
cin >> s1;
cin >> s;
double sum1=0,sum2=0,sum3=0;
int n=s1.length();
for(int i=0;i<n;i++)
{
int k=s1[i]-'a';
if(s[k]=='d')
{
sum1++;
}
else if(s[k]=='w')
{
sum2++;
}
else if(s[k]=='h')
{
sum3++;
}
}
printf("Case #%d: ",++cnt);
//cout << sum1 << " " << sum2 << " " << sum3 << endl;
if(sum3/n>=0.25)
{
printf("Harmful\n");
}
else if(sum3/n<=0.1)
{
printf("Recyclable\n");
}
else
{
if(sum1>=sum2*2)
{
printf("Dry\n");
}
else
{
printf("Wet\n");
}
}
}
return 0;
}
50. Paving roads
Chunchun is a road engineer who is responsible for laying a road of length n.
The main work of road laying is to fill the subsidence surface. The whole section of road can be regarded as n blocks connected end to end. At the beginning, the subsidence depth of block i is di.
Chunchun can select a continuous interval [L,R] every day to fill each area in this interval and reduce its subsidence depth by 1. When selecting an interval, it is necessary to ensure that the subsidence depth of each area in the interval is not 0 before filling.
Chunchun hopes you can help him design a scheme that can change the subsidence depth of the whole section of the road to 0 in the shortest time.
input
The input contains two lines. The first line contains an integer n, which represents the length of the road.
The second line contains n integers, two adjacent numbers are separated by a space, and the ith integer is di.
output
The output contains only an integer, which is the minimum number of days to complete the task.
sample input
6 4 3 2 5 3 5
sample output
9
Greedy, if the adjacent latter is smaller than the former, the filling of the former will cover the latter; On the contrary, the latter needs to be laid again, and the laying amount is a[i]-a[i-1].
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=100005;
int n,tot=0;
ll a[maxn];
int main()
{
int n;
ll ans=0;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n+1;i++)
{
if(i!=1)
{
if(a[i]<a[i-1])
{
ans+=abs(a[i]-a[i-1]);
}
}
}
cout << ans << endl;
return 0;
}
F: Is Today Friday?
No, it's not Friday 😦
TangTang loves Friday and he has made up a list of n days which are all Friday! Each date in this list is formed as "yyyy/mm/dd", where "yyyy" is a four-digit number representing the year, "mm" is a two-digit number representing the month and "dd" is a two-digit number representing the day. TangTang only considers years between 1600 and 9999 (inclusive), so each year in the list always has four digits, but the months and the days may have leading zeros when it's necessary. For example, "August 3rd, 2019" should be formed as "2019/08/03".
To store safely, TangTang ciphered the list using a simple substitution cipher. He substituted each digit by a letter between 'A' and 'J' such that the same digits correspond to the same letter and different digits to different letters.
Unfortunately, TangTang forgot which letter corresponds to which digit. Please help him restore the original list.
input
There are multiple test cases. The first line contains an integer T (1≤T≤10), indicating the number of test cases. Test cases are given in the following.
For each test case, the first line contains an integer n (1≤n≤100000), indicating the number of dates.
Each of the next n lines contains a string in the form of "yyyy/mm/dd", representing a ciphered date, where each digit is substituted by an uppercase letter between 'A' and 'J'.
output
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.
If there is no way to restore the list, then y is "Impossible".
Otherwise, y is a string consisting of ten distinct digits, representing the key to decipher the list. More specifically, the i-th digit in y corresponds to the i-th uppercase letter.
If there are at least two ways, then y is the smallest possible string in the lexicographical order.
Enter the date in the format as shown in the question, and replace each number with the letter between 'A' and 'J', so that the same number corresponds to the same letter and different number of different letters. Find out whether there is A corresponding relationship to ensure that all the entered dates are Friday.
sample input
2 1 CABJ/AI/AC 5 CABJ/AI/AC CABJ/AI/AD CABJ/AI/AE CABJ/AI/AF CABJ/AI/AG
sample output
Case #1: 0123456789 Case #2: Impossible
Here we need to use the Zeiler formula, which is a formula for calculating the week. Given any date, we can use this formula to calculate the day of the week. We can use full permutation to enumerate all correspondence, and then judge whether it is feasible.
Zeiler's formula is as follows:
#include<iostream>
usingnamespacestd;
int main(){
int year,month,day;
while(cin>>year>>month>>day){
if(month<3){
year-=1;
month+=12;
}
charb[7][10]={"sunday","monday","tuesday","wednesday","thursday","friday","saturday"};
int c=int(year/100)，y=year-100*c;
int w=int(c/4)-2*c+y+int(y/4)+(26*(month+1)/10)+day-1;
w=(w%7+7)%7;
cout<<b[w]<<endl;}return 0;}
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=105,mod = 998244353;
int day[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
string s[100005];
bool check(int y,int m,int d)
{
if(y<1600) return 0;
if(m<1||m>12) return 0;
int t=day[m];
if(m==2&&((y%4==0&&y%100!=0)||(y%400==0)))
{
t++;
}
if(d>t) return 0;
if(m<3)
{
y-=1;
m+=12;
}
int c=int(y/100);
y=y-100*c;
int w=(c/4)-2*c+y+(y/4)+(26*(m+1)/10)+d-1;
w=(w%7+7)%7;
return w==5;
}
int main()
{
int t,a[10]={0},y,m,d,fl,ans,cnt=0,n;
cin>> t;
while(t--)
{
ans=0;
cin >> n;
for(int i=0;i<n;i++)
{
cin>> s[i];
}
for(int i=0;i<10;i++)
{
a[i]=i;
}
printf("Case #%d: ",++cnt);
sort(s,s+n);
n=unique(s,s+n)-s;
do
{
fl=1;
for(int i=0;i<n;i++)
{
y=1000*a[s[i][0]-'A']+100*a[s[i][1]-'A']+10*a[s[i][2]-'A']+a[s[i][3]-'A'];
m=10*a[s[i][5]-'A']+a[s[i][6]-'A'];
d=10*a[s[i][8]-'A']+a[s[i][9]-'A'];
if(!check(y,m,d))
{
fl=0;
break;
}
}
if(fl)
{
for(int i=0;i<10;i++) printf("%d",a[i]);
printf("\n");
ans=1;
break;
}
}while(next_permutation(a,a+10));
if(!ans) printf("Impossible\n");
}
return 0;
}
M: Moo
The cows have gotten themselves hooked on a new word game, called "Moo". It is played by a group of cows standing in a long line, where each cow in sequence is responsible for calling out a specific letter as quickly as possible. The first cow who makes a mistake loses.
The sequence of letters in Moo can technically continue forever. It starts like this:
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o
The sequence is best described recursively: let S(0) be the 3-character sequence "m o o". Then a longer sequence S(k) is obtained by taking a copy of the sequence S(k-1), then "m o ... o" with k+2 o's, and then another copy of
the sequence S(k-1). For example:
S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"
As you can see, this process ultimately builds an infinitely long string, and this is the string of characters used for the game of Moo.
Bessie the cow, feeling clever, wishes to predict whether the Nth character of this string will be an "m" or an "o". Please help her out!
Bessie is learning string operation recently. It constructs new strings one by one with the following rules:
S(0) =S(0)= moo
S(1) = S(0) +S(1)=S(0)+ m ++ ooo + S(0) =+S(0)= moo ++ m ++ ooo ++ moo == moomooomoo
S(2) = S(1) +S(2)=S(1)+ m ++ oooo + S(1) =+S(1)= moomooomoo ++ m ++ oooo ++ moomooomoo == moomooomoomoooomoomooomoo
Bessie generates a string in this way. It does not stop until the length of the last generated string is not less than the read integer N.
Through the above observation, we can find that the k-th string is connected by the K-1st string + + m ++ (k+2 o) + + K-1st string.
Now the question is: give an integer N (1 ≤ N ≤ 109), and ask whether the nth character is the letter m or o?
input
* Line 1: A single integer N (1 <= N <= 10^9).
output
* Line 1: The only line of output should contain a single character, which is either m or o.
sample input
11
sample output
m
First calculate the number of strings in which the nth character is contained, then divide the string into three intervals: 1, 2 and 3, and then judge which interval the nth character is in and divide and conquer continuously. Pay attention to boundary treatment.
if(m==0)//Boundary treatment
{
if(x==1)return 'm';
if(x==2)return 'o';
if(x==3)return 'o';
}//Divided into three sections
if(x<=a[m-1])return check(x,m-1);//If in the first interval
if(x>a[m]-a[m-1])return check(x-(a[m]-a[m-1]),m-1);//If in room 3
if(x==a[m-1]+1)return 'm';//If in the second interval
return 'o';//Because the second interval is composed of 1'm 'and k' o '
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=105,mod = 998244353;
int a[100001],t;
inline char check(int x,int m)
{
if(m==0)
{
if(x==1) return 'm';
if(x==2) return 'o';
if(x==3) return 'o';
}
if(x<=a[m-1]) return check(x,m-1);
if(x>a[m]-a[m-1]) return check(x-(a[m]-a[m-1]),m-1);
if(x==a[m-1]+1) return 'm';
return 'o';
}
inline int get(int x)
{
int sum=3;
int k=1;
while(sum<x)
{
sum=sum*2+3+k;
a[k]=sum;
k++;
}
return k-1;
}
int main()
{
int n;
cin >> n;
a[0]=3;
t=get(n);
cout << check(n,t);
}
Scene 42
B: Forest
A forest composed of n points and m edges is given. Each point has a weight val[i]. The cost of adding an additional edge (u,v) is val[u] + val[v], and u and V can only be used once. Add some edges to make the graph connected and find the minimum cost
sample input
7 5 1 2 3 4 5 6 7 3 0 4 0 1 2 1 3 5 6
sample output
7
Obviously, the number of connected blocks x can be obtained by using the union search set. If you want to connect the graph, you need to add at least X-1 edges, then at least 2 * (x-1) points. If
n < 2 ∗ ( x − 1 ) n<2*(x-1) N < 2 * (x − 1) is obviously not connected. We first select the point with the smallest weight of each connected block point, and then greedily select the smallest x-2 points from the remaining points.
c o d e : code: code:
const int N=150005,mod = 998244353;
int a[N],p[N];
vector<int>e[N];
int findl(int x)
{
return p[x]==x ? x : p[x]=findl(p[x]);
}
int main()
{
int n,m,a1,b;
cin >> n >> m;
for(int i=0;i<n;i++)
{
cin >> a[i];
p[i]=i;
}
for(int i=1;i<=m;i++)
{
cin >> a1 >> b;
p[findl(a1)]=findl(b);
}
for(int i=0;i<n;i++)
{
e[findl(i)].push_back(a[i]); //Classify connected blocks and points.
}
vector<int>q;
ll ans=0;
int k=0;
for(int i=0;i<n;i++)
{
if(p[i]!=i) //
{
continue;
}
k++;
sort(e[i].begin(),e[i].end());
ans+=e[i][0];
e[i].erase(e[i].begin()); //Note to delete used points
q.insert(q.end(),e[i].begin(),e[i].end()); //Reinsert into the vector.
}
if(k==1)
{
cout << 0 << endl;
return 0;
}
else if(n<2*(k-1))
{
cout << "Impossible\n";
return 0;
}
sort(q.begin(),q.end());
for(int i=0;i<k-2;i++)
{
ans+=q[i];
}
cout << ans;
return 0;
}
C: Move
After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.
TangTang has n items to move, the i-th of which is of volume vi. He can pack all these items into at most K boxes of the same volume.
TangTang is so clever that he uses the following strategies for packing items:
- Each time, he would put items into a box by the next strategy, and then he would try to fill another box.
- For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.
Now, the question is what is the minimum volume of these boxes required to pack all items.
Put n items into k equal volume boxes. Each time, the strategy is to give priority to the items that can be put into the box, and ask what is the minimum volume of the box
input
There are multiple test cases. The first line contains an integer T (1≤T≤20), indicating the number of test cases. Test cases are given in the following.
For each test case, the first line contains two integers n, K (1≤n,K≤1000), representing the number of items and the number of boxes respectively.
The second line contains n integers v1, v2..., vn(1≤v1,v2,...,vn≤1000), where the i-th integer vi represents the volume of the i-th item.
output
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.
sample input
1 5 3 1 2 3 4 5
sample output
Case #1: 5
Don't dichotomy, because dichotomy should ensure monotonicity. This problem doesn't exist at all. The larger the volume in a certain range, the better. Considering the data range n, K < = 1000 and the volume, we can probably determine the lower bound, that is ∑ i = 1 n a [ i ] / k \sum_{i=1}^na[i]/k Σ i=1n a[i]/k from this point on, it is determined that the minimum volume meeting the requirements is less. I didn't expect O(nm) in the check function...
c o d e : code: code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N],n,m;
bool vis[N];
bool check(int v)
{
memset(vis,0,sizeof(vis));
int ans=0;
for(int i=1;i<=m;i++)
{
int sum=v;
for(int j=n;j>=1;j--)
{
if(vis[j]==0&&a[j]<=sum)
{
sum-=a[j];
vis[j]=true;
ans++;
}
if(sum<=0)break;
}
}
if(ans>=n) return 1;
return 0;
}
int main()
{
int t,cnt=0;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
int sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
int mi=(sum/m);
sort(a+1,a+n+1);
for(int i=mi;i<sum+1;i++)
{
if(check(i))
{
printf("Case #%d: %d\n",++cnt,i);
break;
}
}
}
}
E: Two Arrays
You are given two integer sequences of length N: a1,a2,...,aN and b1,b2,...,bN. Determine if we can repeat the following operation zero or more times so that the sequences a and b become equal.
Operation: Choose two integers i and j (possibly the same) between 1 and N (inclusive), then perform the following two actions simultaneously:
The first line gives N, and then gives two sets A={a1,a2,..., aN} B={b1,b2,..., bN}
Now you can do some operations. Specifically, select an element ai in A and an element bj in B at the same time, add 2 to ai and 1 to bj. Ask whether A and B can be the same through several operations (unlimited operation times).
If Yes, output "Yes"; Otherwise, output "No".
Add 1 to bj.
Constraints
1≤N≤10 000
0≤ai,bi≤109 (1≤i≤N)
All input values are integers.
input
Input is given from Standard Input in the following format:
N
a1 a2 ... aN
b1 b2 ... bN
output
If we can repeat the operation zero or more times so that the sequences a and b become equal, print Yes; otherwise, print No.
sample input
3 1 2 3 5 2 2
sample output
Yes
Thinking problem, for position i, want to achieve a [ i ] = b [ i ] a[i]=b[i] a[i]=b[i], if a [ i ] < b [ i ] a[i]<b[i] Obviously, if a [i] < B [i], we can do it. We need to calculate the operand to complete this situation, that is, sum1=$\sum (b[i]-a[i])/2 $, and make statistics at the same time a [ i ] > b [ i ] a[i]>b[i] When a [i] > b [i], sum2= ∑ a [ i ] − b [ i ] \sum a[i]-b[i] Value of Σ a[i] − b[i] Sum1 > = sum2 is established.
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=25005,mod = 998244353;
ll a[maxn],b[maxn];
int main()
{
ll n,sum=0;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n;i++)
{
cin >> b[i];
}
for(int i=1;i<=n;i++)
{
if(a[i]<b[i]) sum+=(a[i]-b[i])/2;
else sum+=a[i]-b[i];
}
if(sum<=0)
{
cout << "Yes";
}
else
{
cout << "No";
}
}
1: Monetary system
In the country of netizens, there are n currencies with different denominations. The denomination of the I currency is a[i]. You can assume that there are infinite pieces of each currency. For convenience, we record the monetary system with the number of currencies N and the denomination array a[1... N] as (n,a).
In a perfect monetary system, the amount x of each non negative integer should be expressed, that is, for each non negative integer x, there are n non negative integers t[i] satisfying a[i] × The sum of t[i] is X. However, in the country of netizens, the monetary system may be imperfect, that is, the amount x can exist and cannot be expressed by the monetary system. For example, in the monetary system n=3,a=[2,5,9], the amount 1,3 cannot be expressed.
The two monetary systems (n,a) and (m,b) are equivalent if and only if for any nonnegative integer x, it can either be expressed by the two monetary systems or not by any one of them.
Now netizens are going to simplify the monetary system. They hope to find a monetary system (m,b), which satisfies that (m,b) is equivalent to the original monetary system (n,a), and M is as small as possible. They want you to help with this difficult task: finding the smallest M.
input
The first line of input contains an integer T, which represents the number of groups of data. Next, t groups of data are given in the following format.
The first row of each set of data contains a positive integer n. The next line contains n positive integers a[i] separated by spaces.
output
Output a total of T rows. For each group of data, output a positive integer in one row, representing the smallest m in all monetary systems (m,b) equivalent to (n,a).
sample input
2 4 3 19 10 6 5 11 29 13 19 17
sample output
2 5
Give you a monetary system, let you find an equivalent n minimum monetary system. In fact, many items in the original monetary system are made up by some basic "elements", such as 2, 3 and 5. Obviously, 5 can't, because he's made up of 2 and 3. The title also mentions infinite times, which is not a complete backpack. Use the scrolling array to cut one dimension, that is f [ j ] = f [ j ] ∣ f [ j − a [ i ] ] f[j]=f[j]|f[j-a[i]] f[j]=f[j]∣f[j−a[i]].
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=25005,mod = 998244353;
int f[maxn],a[maxn];
int main()
{
int t,n;
cin >> t;
while(t--)
{
cin >> n;
int tt=0;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
sort(a+1,a+n+1);
f[0]=1;
for(int i=1;i<=n;i++)
{
if(!f[a[i]])
{
tt++;
}
else
{
continue;
}
for(int j=a[i];j<=25005;j++)
{
if(f[j-a[i]]) f[j]=1;
else if(f[j]) continue;
}
}
cout << tt << endl;
}
}
K: Times 17
After realizing that there is much money to be made in software development, Farmer John has launched a small side business writing short programs for clients in the local farming industry.
Farmer John's first programming task seems quite simple to him – almost too simple: his client wants him to write a program that takes a number N as input, and prints 17 times N as output. Farmer John has just finished
writing this simple program when the client calls him up in a panic and informs him that the input and output both must be expressed as binary numbers, and that these might be quite large.
Please help Farmer John complete his programming task. Given an input number N, written in binary with at most 1000 digits, please write out the binary representation of 17 times N.
Give you a binary number and let you put it × 17 the output is binary.
input
* Line 1: The binary representation of N (at most 1000 digits).
output
* Line 1: The binary representation of N times 17.
sample input
10110111
sample output
110000100111
I began to want to convert it to hexadecimal (escape) and found that the number was too large. × 17= × (16 + 1), binary × 16, which is followed by + 0000, and then the problem becomes the addition of two binaries. Pay attention to the carry, especially the carry of the first bit.
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=105,mod = 998244353;
string a,ans;
int main()
{
cin >> a;
ans=a+"0000";
a="0000"+a;//Fill in 4 zeros to ensure equal digits
int len=ans.size();
int t=0;
for(int i=len-1;i>0;i--)
{
if((a[i]-'0')+(ans[i]-'0')+t<2)
{
ans[i]=(a[i]-'0')+(ans[i]-'0')+t+'0';
t=0;
}
else
{
ans[i]=(a[i]-'0')+(ans[i]-'0')+t+'0'-2;
t=1;
}
}
if(t==1)
{
ans[0]='0';
ans='1'+ans;
}
cout << ans ;
}
F: Tractor II
After a long day of work, Farmer John completely forgot that he left his tractor in the middle of the field. His cows, always up to no good, decide to play a prank of Farmer John: they deposit N bales of hay (1 <= N <= 50,000) at various locations in the field, so that Farmer John cannot easily remove the tractor without first removing some of the bales of hay.
The location of the tractor, as well as the locations of the N hay bales, are all points in the 2D plane with integer coordinates in the range 1...1000. There is no hay bale located at the initial position of the tractor. When Farmer John drives his tractor, he can only move it in directions that are parallel to the coordinate axes (north, south, east, and west), and it must move in a sequence of integer amounts. For example, he might move north by 2 units, then east by 3 units. The tractor cannot move onto a point occupied by a hay bale.
Please help Farmer John determine the minimum number of hay bales he needs to remove so that he can free his tractor (that is, so he can drive his tractor to the origin of the 2D plane).
After a long day's work, farmer John completely forgot that his tractor was still in the middle of the field. His cows always like to play tricks on him. They leave n heaps of hay in different places on the field. In this way, John must remove some haystacks before he can drive the tractor away.
Both the tractor and the haystack can be regarded as points on a two-dimensional plane, and their coordinates are integers. The coordinates of no haystack are consistent with the initial coordinates of the tractor. When driving the tractor, John can only move several units of length along the coordinate axis. For example, he can move 2 units of length to the north, then 3 units of length to the East, and so on. The tractor cannot move to the point occupied by the haystack.
Please help John calculate the minimum number of piles of hay to move before driving the tractor back to the coordinate origin.
input
* Line 1: Three space-separated integers: N, and the (x,y) starting location of the tractor.
* Lines 2...1+N: Each line contains the (x,y) coordinates of a bale of hay.
output
* Line 1: The minimum number of bales of hay Farmer John must remove in order to open up a path for his tractor to move to the origin.
sample input
7 6 3 6 2 5 2 4 3 2 1 7 3 5 4 6 4
sample output
1
Directly mark the point value of straw pile as 1 and run spfa;
c o d e : code: code:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <vector>
#include <set>
#include <queue>
#include<algorithm>
#define ll long long
using namespace std;
const int N=150005,mod = 998244353;
struct node
{
int x, y;
};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int mp[1101][1101],vis[1010][1010],d[1010][1010];
int n,m,a,b,ex,ey;
void bfs()
{
memset(vis,0,sizeof(vis));
queue<node>q;
// vis[ex][ey]=1;
q.push(node{ex,ey});
while(!q.empty())
{
node t=q.front();
q.pop();
vis[t.x][t.y]=0;
for(int i=0;i<4;i++)
{
int xx=t.x+dx[i];
int yy=t.y+dy[i];
if(xx>=0&&xx<=1001&&yy>=0&&yy<=1001&&d[xx][yy]>d[t.x][t.y]+mp[xx][yy])
{
d[xx][yy]=d[t.x][t.y]+mp[xx][yy];
if(!vis[xx][yy])
{
vis[xx][yy]=1;
q.push(node{xx,yy});
}
}
}
}
}
int main()
{
cin >> n >> ex >>ey;
for(int i=1;i<=n;i++)
{
cin >> a >> b;
mp[a][b]=1;
}
memset(d,0x3f,sizeof(d));
d[ex][ey]=0;
bfs();
cout << d[0][0];
return 0;
}