# ACM Steps

## Chapter One - phase 1

### Section One - basic input and output

It is a summary of the input and output of the classic ACM competition

• P1089: multiple groups of data, one group occupies one line, with two numbers until the end of EOF
• While (CIN > > a > > b) or while (~scanf ('% d% d', & A, & B))
• P1090: the first row is an n, followed by n groups of data. One group occupies one row, with two numbers
• Direct: input and loop control
• P1091: multiple groups of data, one group occupies one line, with two numbers until the end of 0 (no processing)
• While (CIN > > a > > b, a! = "0" |b! = "0") or while (scanf ("% d% d", & A, & B), a|b)
• P1092: multiple groups of data, one row for each group. The first number of each row is n, followed by N data until n=0 (no processing)
• while(scanf("%d",&n),n)
• P1093: group T data, each group has one row of data, the first number of each row is n, followed by N data
• Direct: input and loop control
• P1094: multiple groups of data, one line for each group. The first number of each line is n, followed by N data until the end of EOF
• while(~scanf("%d",&n))
• P1095: P1089, followed by a blank line = > Add '\ n' directly after each group!!! (note)
• putchar('\n') is added directly after each group;
• P1096: P1093, plus a blank line between outputs = > Add '\ n' between two groups of valid data!!! (note)
• In addition to the first group, the first line of each group is wrapped: for (int CAS = 1; CAS < = t; CAS + +) and the head of each group plus if(cas^1)putchar('\n');
• Add if(T)putchar('\n') at the end of while(T--)and each group, except for the last group, which wrap after each group;
• Its common head is the high-precision calculation part of a+b:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

{
if(a.size()<b.size())swap(a,b);
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int i,ii=b.size();
for(i=0;i<ii;i++)
{
a[i]+=b[i]-'0';
if(a[i]>'9')
{
a[i]-=10;
a[i+1]++;
}
}
for(ii=a.size();i<ii;i++)
{
if(a[i]>'9')
{
a[i]-=10;
a[i+1]++;
}
}
if(a[ii]==1)
a+='1';
reverse(a.begin(),a.end());
return a;
}


### Section Two - simple formula

Formula questions that can directly deduce the answers from the data in the questions are divided into blocks similar to the primary school Olympiad of noi

• 1.2.1.Climbing Worm(P1049):
• When a snail climbs a well in Primary School Mathematical Olympiad, it should be noted that the last climb has the following characteristics:
-The starting height is a multiple of u-d, and the starting height plus u is greater than or equal to the well height n
• So we can get the formula: a n s s = ( ( n − u ) / ( u − d ) + b o o l ( ( n − u ) % ( u − d ) ) ) ∗ 2 + 1 anss=((n-u)/(u-d)+bool((n-u)\%(u-d)))*2+1 anss=((n−u)/(u−d)+bool((n−u)%(u−d)))∗2+1
#include<iostream>

using namespace std;

int main()
{
int n,u,d;
while(scanf("%d%d%d",&n,&u,&d),n|u|d)
{
printf("%d\n",((n-u)/(u-d)+bool((n-u)%(u-d)))*2+1);
}
return 0;
}

• 1.2.2.Nasty Hacks(P2317):
• The difference between the first number and the second number minus the third number can be output
#include<iostream>

using namespace std;

int main()
{
int n,r,e,c;
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d",&r,&e,&c);
if(c)
if(c>0)
else
else
puts("does not matter");
}
return 0;
}


• Find the only number that appears odd times in n numbers

• Method 1: sort and scan it again
• Method 2: count with map, and then output odd numbers
• Method 3: use the linked list method to create a new node at the corresponding position after an odd number of occurrences, and delete the existing node after an even number of occurrences

The code here uses method 2

#include<iostream>
#include<map>

using namespace std;

int input()
{
char ch;
while((ch=getchar())<'0'||ch>'9');
int ret=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
ret=(ret<<1)+(ret<<3)+ch-'0';
return ret;
}

int main()
{
int n;
map<int,int>counter;
map<int,int>::iterator counter_i;
while((n=input()))
{
counter.clear();
for(int i=1;i<=n;i++)
counter[input()]++;
for(counter_i=counter.begin();counter_i!=counter.end();counter_i++)
{
if(counter_i->second&1)
{
printf("%d\n",counter_i->first);
break;
}
}
}
return 0;
}


• 1.2.4.Rightmost Digit(P1061):

• In the case of N-th order, only the bottom ten digits of the answer are considered, so the answer is only one of the following:
• 0 (there are 1 kinds): all are 0
• 1 (1): all 1
• 2(4): 2,4,8,6,2. . loop
• 3(4): 3,9,7,1,3. . loop
• 4(2): 4,6,4. . . loop
• 5 (1): all 5
• 6 (1): all 6
• 7(4): 7,9,3,1,7. . loop
• 8(4): 8,4,2,6,8. . loop
• 9(2): 9,1,9. . loop
• Among them, because its index is also n, the answer can only be the bold part above, and only 2, 3, 7 and 8 need to be classified
• be careful!! 0 0 = 1 0^0=1 00=1!!!
#include<iostream>

using namespace std;

int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
switch(n%10)
{
case 0:puts(n?"0":"1");break;
case 1:puts("1");break;
case 2:
switch(n%4)
{
case 2:puts("4");break;
case 0:puts("6");break;
}
break;
case 3:
switch(n%4)
{
case 1:puts("3");break;
case 2:puts("9");break;
case 3:puts("7");break;
case 0:puts("1");break;
}
break;
case 4:puts("6");break;
case 5:puts("5");break;
case 6:puts("6");break;
case 7:
switch(n%4)
{
case 1:puts("7");break;
case 2:puts("9");break;
case 3:puts("3");break;
case 0:puts("1");break;
}
break;
case 8:
switch(n%4)
{
case 2:puts("4");break;
case 0:puts("6");break;
}
break;
case 9:puts("9");break;
}
}
return 0;
}

• 1.2.5.The Seven Percent Solution(P2719):

• You can process the string characters online. If you encounter special characters, output the converted results. Otherwise, directly output the current characters until you encounter the end of '#'
#include<iostream>

using namespace std;

int main()
{
char ch;
while((ch=getchar())^'#')
{
if(ch==' ')
{
putchar('%');
putchar('2');
putchar('0');
continue;
}
if(ch=='!')
{
putchar('%');
putchar('2');
putchar('1');
continue;
}
{
putchar('%');
putchar('2');
putchar('4');
continue;
}
if(ch=='%')
{
putchar('%');
putchar('2');
putchar('5');
continue;
}
if(ch=='(')
{
putchar('%');
putchar('2');
putchar('8');
continue;
}
if(ch==')')
{
putchar('%');
putchar('2');
putchar('9');
continue;
}
if(ch=='*')
{
putchar('%');
putchar('2');
putchar('a');
continue;
}
putchar(ch);
}
return 0;
}


## P3188

• See the summary of [A-C1-S2] above for details
#include<iostream>

using namespace std;

int main()
{
int n,a,b,c;
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d",&a,&b,&c);
if(a>b)
swap(a,b);
if(b>c)
swap(b,c);
if(a>b)
swap(a,b);
if(a==b||b==c)
{
puts("perfect");
continue;
}
if(a*a+b*b==c*c)
{
puts("good");
continue;
}
puts("just a triangle");
}
return 0;
}


# Accessories - Collection

## High precision template (represented by vector_int, range positive integer)

/*
* high-precision 	 Using vector_int represents a positive integer
*
*
* Storage method:
* BigNum_ val;
* val[0]=Digital length;
* val[1]=One digit number;
* val[2]=Ten digits;
* ......
* val[val[0]]=Highest digit;
*
*
* Completed:
* 		transformation: 		 BigNum_trans 	 (val)
* 		transformation: 		 BigNum_trans(val,ret)
* 		transformation: 		 BigNum_trans 	 (str)
* 		transformation: 		 BigNum_trans(str,ret)
* 		transformation: 		 BigNum_trans(val,str)
* 		Input:++ 	 BigNum_input 	 (val)
* 		Output:-- 	 BigNum_output 	 (val)
* 		Comparison: > =, < =, ><
* 		Subtraction:- 	 BigNum_subtract 	 (a,b,ret)
* 		Multiplication:* 	 BigNum_multiply 	 (a,b,ret)
* 		Power:^ 	 BigNum_power 	 (a,b,ret)
* 		Factorial: 		 BigNum_factorial(val,ret)
* 		Digits: 		 BigNum_resize 	 (ret,val) / / decimal operation
* 		Division:/ 	 BigNum_division 	 (a,b,ret)
* 		Remainder:% 	 BigNum_modulo 	 (a,b,ret)
* 		Approximately: 		 BigNum_gcd 		 (a,b)
* 		Small times: 		 BigNum_lcm 		 (a,b)
* 		Approximately: 		 BigNum_gcd 		 (a,b,ret)
* 		Small times: 		 BigNum_lcm 		 (a,b,ret)
*
* hang in the air:
*
*/

#include<bits/stdc++.h>

using namespace std;

#define BigNum_ vector<int>

const BigNum_ BigNum_0  {1, 0};
const BigNum_ BigNum_1  {1, 1};
const BigNum_ BigNum_ERR{1,-1};

BigNum_ BigNum_trans(int val)
{
BigNum_ ret;
for(ret.push_back(0);val;ret[0]++)
{
ret.push_back(val%10);
val/=10;
}
return ret;
}

void BigNum_trans(int val,BigNum_&ret)
{
ret.clear();
for(ret.push_back(0);val;ret[0]++)
{
ret.push_back(val%10);
val/=10;
}
return;
}

BigNum_ BigNum_trans(string str)
{
BigNum_ val;
for(auto it:str)
val.push_back(it-'0');
val.push_back(str.size());
reverse(val.begin(),val.end());
return val;
}

void BigNum_trans(string str,BigNum_&ret)
{
ret.clear();
for(auto it:str)
ret.push_back(it-'0');
ret.push_back(str.size());
reverse(ret.begin(),ret.end());
return;
}

void BigNum_trans(BigNum_ val,string&str)
{
str.clear();
for(int i=val[0];i;i--)
str+=(val[i]+'0');
return;
}

void BigNum_input(BigNum_&val)
{
val.clear();
string str;
cin>>str;
for(auto it:str)
val.push_back(it-'0');
val.push_back(str.size());
reverse(val.begin(),val.end());
return;
}

void operator++(BigNum_&val)
{
val.clear();
string str;
cin>>str;
for(auto it:str)
val.push_back(it-'0');
val.push_back(str.size());
reverse(val.begin(),val.end());
return;
}

void operator++(BigNum_&val,int)
{
val.clear();
string str;
cin>>str;
for(auto it:str)
val.push_back(it-'0');
val.push_back(str.size());
reverse(val.begin(),val.end());
return;
}

void BigNum_output(BigNum_ val)
{
for(int i=val[0];i;i--)
putchar(val[i]+'0');
return;
}

void operator--(BigNum_ val)
{
for(int i=val[0];i;i--)
putchar(val[i]+'0');
return;
}

void operator--(BigNum_ val,int)
{
for(int i=val[0];i;i--)
putchar(val[i]+'0');
return;
}

bool operator>=(BigNum_&val_a,BigNum_&val_b)
{
if(val_a[0]^val_b[0])
return val_a[0]>val_b[0];
for(int i=val_a[0];i;i--)
if(val_a[i]^val_b[i])
return val_a[i]>val_b[i];
return true;
}

bool operator<=(BigNum_&val_a,BigNum_&val_b)
{
if(val_a[0]^val_b[0])
return val_a[0]<val_b[0];
for(int i=val_a[0];i;i--)
if(val_a[i]^val_b[i])
return val_a[i]<val_b[i];
return true;
}

bool operator>(BigNum_&val_a,BigNum_&val_b)
{
if(val_a[0]^val_b[0])
return val_a[0]>val_b[0];
for(int i=val_a[0];i;i--)
if(val_a[i]^val_b[i])
return val_a[i]>val_b[i];
return false;
}

bool operator<(BigNum_&val_a,BigNum_&val_b)
{
if(val_a[0]^val_b[0])
return val_a[0]<val_b[0];
for(int i=val_a[0];i;i--)
if(val_a[i]^val_b[i])
return val_a[i]<val_b[i];
return false;
}

{
ret.clear();
ret.push_back(0);
int i,ii=min(val_a[0],val_b[0]),this_dig,next_dig=0;
for(i=1;i<=ii;i++)
{
this_dig=val_a[i]+val_b[i]+next_dig;
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
for(ii=val_a[0];i<=ii;i++)
{
this_dig=val_a[i]+next_dig;
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
for(ii=val_b[0];i<=ii;i++)
{
this_dig=val_b[i]+next_dig;
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
if(next_dig)
{
ret.push_back(next_dig);
i++;
}
ret[0]=i-1;
return;
}

BigNum_ operator+(BigNum_ val_a,BigNum_ val_b)
{
BigNum_ ret;
ret.push_back(0);
int i,ii=min(val_a[0],val_b[0]),this_dig,next_dig=0;
for(i=1;i<=ii;i++)
{
this_dig=val_a[i]+val_b[i]+next_dig;
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
for(ii=val_a[0];i<=ii;i++)
{
this_dig=val_a[i]+next_dig;
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
for(ii=val_b[0];i<=ii;i++)
{
this_dig=val_b[i]+next_dig;
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
if(next_dig)
{
ret.push_back(next_dig);
i++;
}
ret[0]=i-1;
return ret;
}

void BigNum_subtract(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{
if(val_a<val_b)
{
BigNum_subtract(val_b,val_a,ret);
return;
}
ret=val_a;
for(int i=val_b[0],j;i;i--)
{
ret[i]-=val_b[i];
if(ret[i]<0)
{
for(j=i+1;!ret[j];j++)
ret[j]=9;
ret[j]--;
ret[i]+=10;
}
}
while(!ret[ret[0]]&&ret[0]>1)
ret[0]--;
ret.resize(ret[0]+1);
return;
}

BigNum_ operator-(BigNum_ val_a,BigNum_ val_b)
{
if(val_a<val_b)
return val_b-val_a;
BigNum_ ret;
ret=val_a;
for(int i=val_b[0],j;i;i--)
{
ret[i]-=val_b[i];
if(ret[i]<0)
{
for(j=i+1;!ret[j];j++)
ret[j]=9;
ret[j]--;
ret[i]+=10;
}
}
while(!ret[ret[0]]&&ret[0]>1)
ret[0]--;
ret.resize(ret[0]+1);
return ret;
}

void BigNum_multiply(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{
ret.clear();
ret.push_back(val_a[0]+val_b[0]);
for(int i=1,ii=ret[0],this_dig,next_dig=0;i<=ii;i++)
{
this_dig=next_dig;
for(int j=1;j<=i;j++)
if(val_a[0]>=j&&val_b[0]>=i-j+1)
this_dig+=val_a[j]*val_b[i-j+1];
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
ret[0]-=!ret[ret[0]];
return;
}

BigNum_ operator*(BigNum_ val_a,BigNum_ val_b)
{
BigNum_ ret;
ret.push_back(val_a[0]+val_b[0]);
for(int i=1,ii=ret[0],this_dig,next_dig=0;i<=ii;i++)
{
this_dig=next_dig;
for(int j=1;j<=i;j++)
if(val_a[0]>=j&&val_b[0]>=i-j+1)
this_dig+=val_a[j]*val_b[i-j+1];
next_dig=this_dig/10;
this_dig%=10;
ret.push_back(this_dig);
}
ret[0]-=!ret[ret[0]];
return ret;
}

void BigNum_power(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{
if(val_b[0]==1)
{
if(val_b[1]==0)
{
ret=BigNum_1;
return;
}
if(val_b[1]==1)
{
ret=val_a;
return;
}
}
if(val_a[0]==1)
if(val_a[1]==1||!val_a[1])
{
ret=val_a;
return;
}
BigNum_ half_b,double_a;
int this_dig,next_dig=0;
half_b=val_b;
for(int i=half_b[0];i;i--)
{
this_dig=next_dig;
next_dig=half_b[i]&1?5:0;
half_b[i]=half_b[i]/2+this_dig;
}
while(!half_b[half_b[0]])
half_b[0]--;
double_a=val_a*val_a;
if(val_b[1]&1)
{
// ret=(double_a^half_b)*val_a;
BigNum_ temp;
BigNum_power(double_a,half_b,temp);
BigNum_multiply(temp,val_a,ret);
}
else
{
// ret=double_a^half_b;
BigNum_power(double_a,half_b,ret);
}
return;
}

BigNum_ operator^(BigNum_ val_a,BigNum_ val_b)
{
if(val_b[0]==1)
{
if(val_b[1]==0)
return BigNum_1;
if(val_b[1]==1)
return val_a;
}
if(val_a[0]==1)
if(val_a[1]==1||!val_a[1])
return val_a;
BigNum_ half_b,double_a;
int this_dig,next_dig=0;
half_b=val_b;
for(int i=half_b[0];i;i--)
{
this_dig=next_dig;
next_dig=half_b[i]&1?5:0;
half_b[i]=half_b[i]/2+this_dig;
}
while(!half_b[half_b[0]])
half_b[0]--;
double_a=val_a*val_a;
if(val_b[1]&1)
return (double_a^half_b)*val_a;
else
return double_a^half_b;
}

void BigNum_factorial(BigNum_&val,BigNum_&ret)
{
ret=BigNum_1;
for(BigNum_ i={1,1};i<=val;i=i+BigNum_1)
ret=ret*i;
return;
}

void BigNum_resize(BigNum_&ret,int val)
{
reverse(ret.begin(),ret.end());
ret.pop_back();
ret.resize(val);
ret.push_back(val);
reverse(ret.begin(),ret.end());
return;
}

void BigNum_division(BigNum_ val_a,BigNum_&val_b,BigNum_&ret)
{
if(val_a<val_b)
{
ret=BigNum_ {1,0};
return;
}
if(val_b==BigNum_0)
{
ret=BigNum_ERR;
return;
}
ret.clear();
ret.push_back(val_a[0]-val_b[0]+1);
BigNum_resize(ret,ret[0]);
for(int i=val_a[0],ii=val_b[0];i>=ii;i--)
{
BigNum_resize(val_b,i);
while(val_a>=val_b)
{
val_a=val_a-val_b;
ret[i-ii+1]++;
}
}
while(!ret[ret[0]]&&ret[0]>1)
ret[0]--;
ret.resize(ret[0]+1);
return;
}

BigNum_ operator/(BigNum_ val_a,BigNum_ val_b)
{
if(val_a<val_b)
return BigNum_ {1,0};
if(val_b==BigNum_0)
return BigNum_ERR;
BigNum_ ret;
ret.push_back(val_a[0]-val_b[0]+1);
BigNum_resize(ret,ret[0]);
for(int i=val_a[0],ii=val_b[0];i>=ii;i--)
{
BigNum_resize(val_b,i);
while(val_a>=val_b)
{
val_a=val_a-val_b;
ret[i-ii+1]++;
}
}
while(!ret[ret[0]]&&ret[0]>1)
ret[0]--;
ret.resize(ret[0]+1);
return ret;
}

void BigNum_modulo(BigNum_ val_a,BigNum_&val_b,BigNum_&ret)
{
if(val_a<val_b)
{
ret=val_a;
return;
}
if(val_b==BigNum_0)
{
ret=BigNum_ERR;
return;
}
BigNum_resize(ret,ret[0]);
for(int i=val_a[0],ii=val_b[0];i>=ii;i--)
{
BigNum_resize(val_b,i);
while(val_a>=val_b)
val_a=val_a-val_b;
}
ret=val_a;
while(!ret[ret[0]]&&ret[0]>1)
ret[0]--;
ret.resize(ret[0]+1);
return;
}

BigNum_ operator%(BigNum_ val_a,BigNum_ val_b)
{
if(val_a<val_b)
return val_a;
if(val_b==BigNum_0)
return BigNum_ERR;
BigNum_ ret;
for(int i=val_a[0],ii=val_b[0];i>=ii;i--)
{
BigNum_resize(val_b,i);
while(val_a>=val_b)
val_a=val_a-val_b;
}
ret=val_a;
while(!ret[ret[0]]&&ret[0]>1)
ret[0]--;
ret.resize(ret[0]+1);
return ret;
}

BigNum_ BigNum_gcd(BigNum_ val_a,BigNum_ val_b)
{
while(val_a>BigNum_0)
{
swap(val_a,val_b);
val_a=val_a%val_b;
}
return val_b;
}

void BigNum_gcd(BigNum_ val_a,BigNum_ val_b,BigNum_&ret)
{
while(val_a>BigNum_0)
{
swap(val_a,val_b);
val_a=val_a%val_b;
}
ret=val_b;
return;
}

BigNum_ BigNum_lcm(BigNum_ val_a,BigNum_ val_b)
{
return val_a*val_b/BigNum_gcd(val_a,val_b);
}

void BigNum_lcm(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{
ret=val_a*val_b/BigNum_gcd(val_a,val_b);
return;
}

int main()
{

// //test_used:
// BigNum_ a,b,c;

// (BigNum_trans(321))--;cout<<endl<<endl;
//(BigNum_trans("321"))--;cout<<endl<<endl;

// while(true)
// {

// 	a++;
// 	b++;
// BigNum_input(a);
// BigNum_input(b);
// BigNum_output(a);
// BigNum_output(b);

// cout<<"(a>b)="<<(a>b)<<endl;
// cout<<"(a<b)="<<(a<b)<<endl;
// cout<<"(a>=b)="<<(a>=b)<<endl;
// cout<<"(a<=b)="<<(a<=b)<<endl;

// a--;
// if(a==b)
// 	cout<<"=";
// if(a<b)
// 	cout<<"<";
// if(a>b)
// 	cout<<">";
// b--;cout<<endl;

// // c=a+b;
// a--;cout<<"+";b--;cout<<"=";c--;cout<<endl;

// // c=a-b;
// BigNum_subtract(a,b,c);
// a--;cout<<"-";b--;cout<<"=";c--;cout<<endl;

// // c=a*b;
// BigNum_multiply(a,b,c);
// a--;cout<<"x";b--;cout<<"=";c--;cout<<endl;

// // c=a/b

// // c=a^b;
// BigNum_power(a,b,c);
// a--;cout<<"^";b--;cout<<"=";c--;cout<<endl;

// // c=a!;
// BigNum_factorial(a,c);
// a--;cout<<"!=";c--;cout<<endl;

// // c=a/b;
// BigNum_division(a,b,c);
// a--;cout<<"/";b--;cout<<"=";c--;cout<<endl;

// // c=a%b;
// BigNum_modulo(a,b,c);
// a--;cout<<"%";b--;cout<<"=";c--;cout<<endl;

// c=BigNum_gcd(a,b);
// BigNum_gcd(a,b,c);
// cout<<"gcd(";a--;cout<<",";b--;cout<<")=";c--;cout<<endl;

// // c=BigNum_lcm(a,b);
// BigNum_lcm(a,b,c);
// cout<<"lcm(";a--;cout<<",";b--;cout<<")=";c--;cout<<endl;

// }

return 0;
}


Keywords: Algorithm acm

Added by dico on Thu, 17 Feb 2022 21:11:01 +0200