A-Array of Discord
Meaning:
Enter a row of numbers in ascending order. Can you change any digit of one of the numbers so that it is not in order?
Please refer to the official code or the last code for the correct code
Initial ideas:
- If there are two identical numbers, the first one is output after adding one
- If the number of digits of each number is incremented, "impossible" is output
- If there are numbers with the same number of digits, the preceding number becomes the largest or the following number becomes the smallest (for example, 11111112 becomes 91111112, that is, it becomes the largest)
WA, because the classification is too complex and incomplete, and the code is inevitably complex.
and:
Sort in the title does not mean from small to large or from large to small, that is, sort can be from small to large or from large to small.
As long as there is such an arrangement as small, large, small or large, small and large, it is not sort.
Correct idea: after turning a number to the maximum, judge whether it meets the standard as a whole. If it does not meet the standard, turn the second number to the minimum.
Note: different functions are realized by functions, which is convenient for error correction, and the code is concise and clear. Don't be too complicated.
Official answer:
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
const int N=2;
int n, m;
LL w[N];
void out()
{
for (int i = 1; i <= n; ++i) {
printf("%lld ", w[i]);
}
}
LL to_number(string s)
{
LL res = 0;
for (int i = 0; i < s.size(); ++i) {
res = res * 10 + s[i] - '0';
}
return res;
}
void to_big(int u)
{
string s = to_string(w[u]);
for (int i = 0; i < s.size(); ++i) {
if (s[i] != '9') {
s[i] = '9';
break;
}
}
w[u] = to_number(s);
return;
}
void to_small(int u)
{
string s = to_string(w[u]);
if (s.size() == 1) {
w[u] = 0;
return;
}
else {
if (s[0] != '1') {
s[0] = '1';
}
else {
for (int i = 1; i < s.size(); ++i) {
if (s[i] != '0') {
s[i] = 0;
break;
}
}
}
}
w[u] = to_number(s);
}
bool is_sort()
{
int flag = 1;
for (int i = 1; i <= n - 1; ++i) {//It's all the same. It's sort
if (w[i] != w[i + 1]) {
flag = 0;
break;
}
}
if (flag) return false;
flag = 1;
for (int i = 1; i <= n - 1; ++i) {
if (w[i] > w[i + 1]) {
flag = 0;
break;
}
}
if (flag) return false;
return true;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &w[i]);
}
for (int i = 1; i <= n; ++i) {
LL t = w[i];
to_big(i);
if (t != w[i] && is_sort()) {
out();
return 0;
}
w[i] = t;
to_small(i);
if (t != w[i] && is_sort()) {
out();
return 0;
}
w[i] = t;
}
puts("impossible");
return 0;
}
I wrote according to this idea and only passed 86%. Then I changed my idea and tried the string method:
- If the string length is the same, it may be changed
- Judge after modification
The codes are as follows (pass 97.73%)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=115;
string a[N];
int n;
string to_big(string str)
{
for(int i=0;str[i];i++)
{
if(str[i]!='9')
{
str[i]='9';break;
}
}
return str;
}
string to_small(string str)
{
if(str.size()==1) str='0';
else
{
if(str[0]!='1') str[0]='1';
else
{
for(int i=1;str[i];i++)
{
if(str[i]!='0')
{
str[i]='0';break;
}
}
}
}
return str;
}
bool is_sort()
{
for(int i=0;i<n-1;i++)
{
if(a[i].size()==a[i+1].size())
{
for(int j=0;a[i][j];j++)
{
if(a[i][j]>a[i+1][j])//Appear large
{
flag=0;break;
}
}
}
else if(a[i].size()>a[i+1].size())
{
flag=1;break;
}
}
if(flag) return 0;
return 1;
}
void out()
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
//big
for(int i=0;i<n-1;i++)
{
if(a[i].size()==a[i+1].size())
{
string t=a[i];//Save a[i]
a[i]=to_big(a[i]);
if(is_sort())
{
out();return 0;
}
a[i]=t;
}
}
//small
for(int i=1;i<n;i++)
{
if(a[i].size()==a[i-1].size())
{
string t=a[i];
a[i]=to_small(a[i]);
if(is_sort())
{
out();return 0;
}
a[i]=t;
}
}
cout<<"impossible"<<endl;
}
But it's still too complicated. For this question, as long as the string meets the conditions that can be changed, it must meet the meaning of the question, that is, string a and b, if they:
- If the length is 1, and a is not 0 and b is not 9, they can be changed and meet the meaning of the question
- The length is not 1, the first digit of a is not 1, and the first digit of b is not 9. It can be changed and conforms to the meaning of the question
Therefore, the code can be simplified:
Finally
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int n;
string a[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int q=0,w=0;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i].size()==a[j].size())
{
if(a[i].size()==1&&a[i][0]=='0'&&a[j][0]=='9') continue;
if(a[i].size()>1&&a[i][0]=='1'&&a[j][0]=='9') continue;
//Can change
q=i;w=j;break;
}
}
if(q!=0) break;
}
if(q!=0)
{
if((a[q][0]!='1'||a[q].size()==1)&&a[q][0]!='0')//The latter can be reduced
{
a[w][0]=a[q][0]-1;
}
else a[q][0]=a[w][0]+1;
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}
else cout<<"impossible"<<endl;
return 0;
}
Summary:
- Multi write function
- 1015 can use string or long
- Understand the meaning of the question sort, only when there is an inflection point (so n==2 is always impossible)
C-Coin Stacks
Original title
A water problem.
Meaning: n piles of coins, a[i] in each pile, can you choose two piles at a time and take one each to make it finished?
If you can, output yes and the order in which it is taken out.
Idea:
- no with odd sum
- The largest is larger than the sum of all the rest
- The other yes output order is: the number of the two largest output each time, and then sort
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=70;
struct node
{
int num,val;
};
int cmp(node a,node b)
{
if(a.val!=b.val) return a.val>b.val;//From big to small
else return a.num<b.num;
}
node a[N];
int n;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
int sum=0,maxn=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].num=i;
sum+=a[i].val;
maxn=max(maxn,a[i].val);
}
if(sum%2==1)
{
cout<<"no";
return 0;
}
if(maxn>sum-maxn)
{
cout<<"no";
return 0;
}
cout<<"yes"<<endl;
while(sum)
{
sort(a+1,a+n+1,cmp);
cout<<a[1].num<<" "<<a[2].num<<endl;
a[1].val--;
a[2].val--;
sum-=2;
}
return 0;
}