Oracle
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 79 Accepted Submission(s): 41
The
youngest and most beautiful is Psyche, whose admirers, neglecting the
proper worship of the love goddess Venus, instead pray and make
offerings to her. Her father, the king, is desperate to know about her
destiny, so he comes to the Delphi Temple to ask for an oracle.
The oracle is an integer n without leading zeroes.
To
get the meaning, he needs to rearrange the digits and split the number
into <b>two positive integers without leading zeroes</b>,
and their sum should be as large as possible.
Help him to work out the maximum sum. It might be impossible to do that. If so, print `Uncertain`.
For each test case, the single line contains an integer n (1≤n<1010000000).
112
233
1
35
Uncertain
In the first example, it is optimal to split $ 112 $ into $ 21 $ and $ 1 $, and their sum is $ 21 + 1 = 22 $.
In the second example, it is optimal to split $ 233 $ into $ 2 $ and $ 33 $, and their sum is $ 2 + 33 = 35 $.
In the third example, it is impossible to split single digit $ 1 $ into two parts.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 10000005
char str[N];
char result[N];
char b[];
int cmp(char a,char b)
{
return a>b;
}
void reverse( char *s ) /*将字符串逆置*/
{
int length;
int i = ;
char temp;
length = strlen( s );
while( i < length - i - )
{
temp = s[i];
s[i] = s[length - i - ];
s[length - i - ] = temp;
i++;
}
}
void AddBigNum( char* s1, char* s2, char* result )
{
int len1 = strlen( s1 );
int len2 = strlen( s2 );
int acc = , temp, i; /*acc为进位标记*/
if( s1 == NULL || s2 == NULL || result == NULL )
{
return;
}
reverse( s1 );
reverse( s2 );
for( i = ; i < len1 && i < len2; i++ )
{
temp = s1[i] - '' + s2[i] - '' + acc; /*计算每位的实际和*/
result[i] = temp % + ''; /*通过求余数来确定每位的最终值*/
if( temp >= ) /*通过这个if..else..条件来判断是否有进位，并设置进位值*/
acc = ;
else
acc = ;
}
if( i < len1 ) /*两个加数位数不同*/
{
for( ; i < len1; i++ )
{
temp = s1[i] - '' + acc; /*依旧要考虑进位，比如9999 + 1的情况*/
result[i] = temp % + '';
if( temp >= )
acc = ;
else
acc = ;
}
}
if( i < len2 )
{
for( ; i < len2; i++ )
{
temp = s2[i] - '' + acc;
result[i] = temp % + '';
if( temp >= )
acc = ;
else
acc = ;
}
}
if( acc == ) /*考虑如:123 + 911 = 1034的情况，如果不增加这个条件会得到结果为034，进位被舍弃*/
result[i++] = '';
result[i] = '\0';
reverse( result );
}
int main()
{
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%s",str);
int len = strlen(str);
sort(str,str+len,cmp);
if(len==)
{
printf("Uncertain\n");
}
else
{
bool flag = true;
int ans = ;
for(int i=len-; i>=; i--)
{
if(str[i]!='')
{
ans = i;
break;
}
}
if(ans==)
{
printf("Uncertain\n");
continue;
}
b[] = str[ans];
int id = ;
for(int i=; i<len; i++)
{
if(i==ans) continue;
str[id++] = str[i];
}
str[id]='\0';
AddBigNum(str,b,result);
printf("%s\n",result);
}
}
return ;
}
Arrange
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 74 Accepted Submission(s): 30
This has drawn the fury of his mother, Venus. The goddess then throws before Psyche a great mass of mixed crops.
There are n heaps of crops in total, numbered from 1 to n.
Psyche needs to arrange them in a certain order, assume crops on the i-th position is Ai.
She is given some information about the final order of the crops:
1. the minimum value of A1,A2,...,Ai is Bi.
2. the maximum value of A1,A2,...,Ai is Ci.
She wants to know the number of valid permutations. As this number can be large, output it modulo 998244353.
Note that if there is no valid permutation, the answer is 0.
For each test case, the first line of input contains single integer n (1≤n≤105).
The second line contains n integers, the i-th integer denotes Bi (1≤Bi≤n).
The third line contains n integers, the i-th integer denotes Ci (1≤Ci≤n).
3
2 1 1
2 2 3
5
5 4 3 2 1
1 2 3 4 5
0
In the first example, there is only one valid permutation (2,1,3) .
In the second example, it is obvious that there is no valid permutation.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const long long mod = ;
const int N = ;
int b[N],c[N];
long long dp[N];
int main()
{
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
int n;
scanf("%d",&n);
int MIN = ;
int MAX = -;
bool flag = true;
for(int i=;i<=n;i++){
scanf("%d",&b[i]);
if(b[i]<||b[i]>n) flag = false;
if(b[i]>MIN) flag = false;
MIN = min(MIN,b[i]);
}
for(int i=;i<=n;i++){
scanf("%d",&c[i]);
if(c[i]<MAX) flag = false;
if(c[i]<||c[i]>n) flag = false;
MAX = max(MAX,c[i]);
if(c[i]<b[i]) flag = false;
}
if(!flag||c[]!=b[]) printf("0\n");
else{
memset(dp,,sizeof(dp));
dp[] = ;
int num = ;
for(int i=;i<=n;i++){
if(c[i]==c[i-]&&b[i-]==b[i]) {
dp[i] = dp[i-]*(c[i]-b[i]-num+)%mod;
}
else if(b[i]<b[i-]&&c[i-]==c[i]||b[i]==b[i-]&&c[i-]<c[i]){
dp[i] = dp[i-];
}
num++;
}
printf("%I64d\n",dp[n]);
}
}
return ;
}