patcodes.md
#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
for (int i = 0; i<1000000000; i++){
if (n == 1){
cout<<'0'<<endl;
return 0;
}
else{
if(n%2 == 0){
n = n * 0.5;
}
else{
n = (3 * n+1)*0.5;
};
if (n==1){
cout<<i+1<<endl;
return 0;
}
}
}
}
# include <stdio.h>
# include <iostream>
# include <string>
using namespace std;
int main(){
string n;
cin>>n;
int sum = 0;
for (int i=0;i<int(n.size());i++){
sum += n[i] - '0';
}
string sum1 = to_string(sum);
for (int i = 0; i< int(sum1.size());i++){
if (sum1[i] == '0') cout<<"ling";
if (sum1[i] == '1') cout<<"yi";
if (sum1[i] == '2') cout<<"er";
if (sum1[i] == '3') cout<<"san";
if (sum1[i] == '4') cout<<"si";
if (sum1[i] == '5') cout<<"wu";
if (sum1[i] == '6') cout<<"liu";
if (sum1[i] == '7') cout<<"qi";
if (sum1[i] == '8') cout<<"ba";
if (sum1[i] == '9') cout<<"jiu";
if (i != int(sum1.size())-1) cout<<" ";
}
return 0;
}
# include <stdio.h>
# include <iostream>
# include <string>
using namespace std;
int substr(string a){
int pexist = 0,ppos = 0;
for (int i = 0;i<a.size();i++){
if (a[i] == 'P'){
pexist = 1;
ppos = i;
}
if (pexist == 1 && a[i] == 'T' && i > ppos+1){
for (int j = 0;j<a.size();j++){
if (a[j]!= 'P' && a[j]!= 'A' && a[j]!= 'T'){
return 0;
}
}
return 1;
}
}
return 0;
}
int judge(string n){
if (substr(n) == 1){
int ppos = n.find('P');
int tpos = n.find('T');
if (ppos*(tpos-ppos-1)==n.size()-tpos-1){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
else{
cout<<"NO"<<endl;
}
return 0;
}
int main(){
int num;
cin>>num;
string n[num];
for (int i = 0;i<num;i++){
cin>>n[i];
}
for (int i = 0;i<num;i++){
judge(n[i]);
}
}
# include <stdio.h>
# include <iostream>
# include <string>
using namespace std;
int main(){
int num;
cin>>num;
string n[num*2];
int score[num];
int count = 0;
for (int i = 0;i<num*3;i++){
if (i%3 == 2){
cin>>score[(i-2)/3];
}
else{
cin>>n[count++];
}
}
int max,min,maxpos,minpos;
max = min = score[0];
maxpos = minpos = 0;
for (int i = 0;i<num;i++){
if (score[i]>max){
max = score[i];
maxpos = i;
}
if (score[i]<min){
min = score[i];
minpos = i;
}
}
cout<<n[maxpos * 2]<<' '<<n[maxpos * 2+1]<<endl;
cout<<n[minpos * 2]<<' '<<n[minpos * 2+1]<<endl;
}
#include <iostream>
#include <algorithm>
using namespace std;
int findanddel(int num[], int j,int n){
for (int i = 0;i<n;i++){
if (num[i] == j){
num[i] = 1;
}
}
return 0;
}
int main(){
int n;
cin>>n;
int num[n];
for (int i = 0;i<n;i++){
cin>>num[i];
}
for (int i = 0;i<n;i++){
int k = num[i];
while(k!=1){
if (k%2 == 0){
k = k/2;
findanddel(num,k,n);
}
else{
k = (k*3+1)/2;
findanddel(num,k,n);
}
}
}
sort(num,num + n);
for (int i = n-1;i>=0;i--){
if (num[i] == 1) break;
else if (i!=n-1) cout<<' ';
cout<<num[i];
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int a[3];
for(int i = 0;i<3;i++){
a[i] = n%10;
n = n/10;
}
for (int i = 0; i<a[2]; i++){
cout<<'B';
}
for (int i = 0; i<a[1]; i++){
cout<<'S';
}
int count = 0;
for (int i = 0; i<a[0]; i++){
cout<<++count;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int min(int a,int b){
if(a<b)return a;
else return b;
}
int main(){
int n;
cin>>n;
vector <int> su;
su.push_back(2);
for (int i = 2;i<n+1;i++){
int judge = 1;
for (int j = 0; j<su.size();j++){
if (i%su[j] == 0){
judge = 0;
}
if (su[j] > sqrt(n)) break;
}
if (judge == 1){
su.push_back(i);
}
}
int count = 0;
for (int i = 1;i<su.size();i++){
if(su[i]>n)break;
if(su[i]-su[i-1]==2){
count++;
}
}
cout<<count;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int num[n];
for (int i = 0;i<n;i++){
cin>>num[i];
}
for (int i = 0;i<n;i++){
cout<<num[(i-m+n*100)%n];
if (i!=n-1) cout<<' ';
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <sstream>
using namespace std;
int main(){
string str;
getline(cin,str);
str = str+" ";
vector<string> strSplit;
vector<char>s;
for (int i = 0;i<str.size()+1;i++){
if (str[i]!=' '&&i!=str.size()) s.push_back(str[i]);
else {
string a;
for (int j = 0;j<s.size();j++){
a = a+s[j];
}
s.clear();
strSplit.push_back(a);
}
}
for (int i = 1;i<strSplit.size();i++){
if(i!=strSplit.size()-1) cout<<strSplit[strSplit.size()-i-1]<<" ";
else cout<<strSplit[strSplit.size()-i-1];
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int main(){
int tmp;
vector<int>num;
vector<int>num2;
while(cin>>tmp){
if(tmp == 0) {
cout<<"0 0";
return 0;
}
num.push_back(tmp);
cin>>tmp;
num2.push_back(tmp);
if(tmp == 0) break;
}
for(int i = 0;i<int(num2.size());i++){
if (num2[i] == 0 && i == 0) {
cout<<"0 0";
break;
}
if (num2[i]>0) cout<<num2[i]*num[i]<<' '<<num2[i]-1;
if (i!=int(num2.size()-1) && num2[i+1]!=0) cout<<' ';
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int cmp(string a, string b){
if(a.size()>b.size()) return 1;
else if(a.size()<b.size()) return -1;
else {
for (int i = 0;i<a.size();i++){
if (a[i]!=b[i]){
if (a[i]>b[i]) return 1;
if (a[i]<b[i]) return -1;
}
}
return 0;
}
}
string add2(string a,string b){
if (a == "0") return b;
if (b == "0") return a;
string c;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string a1(32-a.size(),'0');
string b1(32-b.size(),'0');
a = a + a1;
b = b + b1;
int jinwei = 0;
for (int i = 0;i<32;i++){
char tmp;
tmp = a[i]+b[i]-48+jinwei;
if (tmp>'9'){
tmp -= 10;
jinwei = 1;
}
else jinwei = 0;
c += tmp;
}
reverse(c.begin(), c.end());
int j = 0;
string d;
for(int i = 0;i<c.size();i++){
if (c[i]!='0') j=1;
if (j==1) d += c[i];
}
return d;
}
string abs(string a){
if (a[0] != '-') return a;
else {
string b;
for (int i = 1;i<a.size();i++){
b += a[i];
}
return b;
}
}
string sub2(string a,string b){
string c;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string a1(32-a.size(),'0');
string b1(32-b.size(),'0');
a = a + a1;
b = b + b1;
int jinwei = 0;
for (int i = 0;i<32;i++){
char tmp;
tmp = a[i]-b[i]+48-jinwei;
if (tmp<'0'){
tmp += 10;
jinwei = 1;
}
else jinwei = 0;
c += tmp;
}
reverse(c.begin(), c.end());
int j = 0;
string d;
for(int i = 0;i<c.size();i++){
if (c[i]!='0') j=1;
if (j==1) d += c[i];
}
return d;
}
string sub(string a,string b){
if (a== "0") {
if (abs(b) == b) return "-"+abs(b);
else return abs(b);
}
if (b == "0") return a;
int big = cmp(abs(a), abs(b));
if (big == 0) return "0";
else if (big == 1){
if (abs(a)==a && abs(b)==b) return sub2(a,b);
else if (abs(a)!=a && abs(b)==b) return "-"+add2(abs(a),b);
else if (abs(a)==a && abs(b)!=b) return add2(a,abs(b));
else return "-"+sub2(abs(a),abs(b));
}
else {
if (abs(a)==a && abs(b)==b) return "-"+sub2(b,a);
else if (abs(a)!=a && abs(b)==b) return sub2(b,abs(a));
else if (abs(a)==a && abs(b)!=b) return sub2(abs(b),a);
else return sub2(abs(b),abs(a));
}
return "0";
}
string add(string a,string b){
if (a[0] == '-' && b[0] == '-') return "-"+add2(abs(a), abs(b));
else if (a[0] != '-' && b[0] == '-') return sub(a,abs(b));
else if (a[0] == '-' && b[0] != '-') return sub(b,abs(a));
else return add2(abs(a), abs(b));
}
string judge(string a,string b,string c){
string result = sub(add(a,b),c);
if (result[0] == '-' || result == "0" ) return "false";
else return "true";
}
string output(string a,string b,string c,int num){
return "Case #" + to_string(num) + ": "+judge(a,b,c);
}
int main(){
int n;
cin>>n;
string a[n],b[n],c[n];
if (n!=0){
for (int i=0;i<n;i++){
cin>>a[i]>>b[i]>>c[i];
}
for (int i=0;i<n;i++){
cout<<output(a[i],b[i],c[i],i+1)<<endl;
}
}
return 0;
}
int main1(){
string a,b,c;
cin>>a>>b>>c;
string result = sub(add(a,b),c);
cout<<result<<" "<<output(a,b,c,1)<<endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
cout<<"Enter Please"<<endl;
int n;
cin>>n;
int num[n];
for (int i = 0;i<n;i++){
cin>>num[i];
}
int a1,a2,a3,a5;
float a4 = 0.0;
a1 = a2 = a3 = a5 =0;
int count4 = 0;
int count2 = 1;
int judge2 = 0;
for (int i = 0;i<n;i++){
if (num[i] % 10 == 0) a1 += num[i];
if (num[i] % 5 == 1) {
judge2 = 1;
a2 += count2 * num[i];
count2 = count2 * (-1);
}
if (num[i] % 5 == 2) a3 += 1;
if (num[i] % 5 == 3) {
a4 += num[i];
count4 +=1;
}
if (num[i] % 5 == 4) {
if (a5<num[i]) a5 = num[i];
}
}
a4 = a4/count4;
string a11=a1>0?to_string(a1):"N";
string a21=judge2 == 1?to_string(a2):"N";
string a31=a3>0?to_string(a3):"N";
string a51=a5>0?to_string(a5):"N";
if (a4 >0){
cout<<a11<<' '<<a21<<' '<<a31<<' '<<fixed<<setprecision(1)<<a4<<' '<<a51;
}
else{
cout<<a11<<' '<<a21<<' '<<a31<<' '<<'N'<<' '<<a51;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
vector <int> su;
su.push_back(2);
int i = 1;
while(su.size()<n+1){
i++;
int judge = 1;
for (int j = 0; j<su.size();j++){
if (i%su[j] == 0){
judge = 0;
}
if (su[j] > sqrt(i)) break;
}
if (judge == 1){
su.push_back(i);
}
}
for (int i = m-1;i<su.size()-1;i++){
cout<<su[i];
if ((i-m+2)%10 == 0 && i != su.size()-2)cout<<endl;
else if (i != su.size()-2) cout<<' ';
else break;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
const int MAXN=10000000;
int prime[MAXN];
bool vis[MAXN] = {0};
int Prime(int n,int m)
{
int cnt=0;
for(int i=2;i<n;i++)
{
if(!vis[i])
prime[cnt++]=i;
for(int j=0;j<cnt&&i*prime[j]<n;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
if (cnt>m)break;
}
return cnt;
}
int main(){
int m,n,count = 0;
cin>>m>>n;
Prime(10000000,n+5);
for(int i = 0;count<n+2;i++){
if(vis[i] == 0){
if (count>m) {
printf("%d",i);
if ((count-m)%10 == 0)printf("\n");
else if (count!=n+1)printf(" ");
}
count++;
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
unsigned long int cmp(string a,string b){
if (a.size()>b.size()) return b.size();
else return a.size();
}
int main(){
string a,b,c,d;
cin>>a>>b>>c>>d;
char day,hour;
int minute = 0;
int count = 0;
for (int i = 0;i<cmp(a,b);i++){
if (a[i] == b[i] && a[i]>='A' && a[i]<='G' && count == 0) {
day = a[i];
count++;
continue;
}
if (a[i] == b[i] && a[i]>='A' && a[i]<='N' && count == 1) {
hour = a[i];
count++;
break;
}
if (a[i] == b[i] && a[i]>='0' && a[i]<='9' && count == 1) {
hour = a[i];
count++;
break;
}
}
for (int i = 0;i<cmp(c,d);i++){
if (c[i] == d[i] && c[i]>='A' && c[i]<='Z') {
minute = i;
break;
}
if (c[i] == d[i] && c[i]>='a' && c[i]<='z') {
minute = i;
break;
}
}
if (day == 'A') cout<<"MON ";
if (day == 'B') cout<<"TUE ";
if (day == 'C') cout<<"WED ";
if (day == 'D') cout<<"THU ";
if (day == 'E') cout<<"FRI ";
if (day == 'F') cout<<"SAT ";
if (day == 'G') cout<<"SUN ";
if (hour >='A') cout<<hour-'A'+10<<':'<<setfill('0')<<setw(2)<<minute;
else cout<<setfill('0')<<setw(2)<<hour<<':'<<setfill('0')<<setw(2)<<minute;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
int id,d,c,sgn,total;
} student;
bool cmp(student a,student b)
{
if(a.sgn!=b.sgn)return a.sgn<b.sgn;
else if(a.total!=b.total)return a.total>b.total;
else if(a.d!=b.d)return a.d>b.d;
else return a.id<b.id;
}
int main(){
int num,l,h;
cin>>num>>l>>h;
student students[num];
for (int i = 0;i<num;i++){
cin>>students[i].id>>students[i].d>>students[i].c;
}
int failcount = 0;
for (int i = 0;i<num;i++){
students[i].total = students[i].d + students[i].c;
if (students[i].d>=h && students[i].c>=h) students[i].sgn = 0;
else if (students[i].d>=h && students[i].c<h && students[i].c>=l) {
students[i].sgn = 1;}
else if (students[i].c>=l && students[i].d>=l && students[i].d>=students[i].c) students[i].sgn = 2;
else if (students[i].c>=l && students[i].d>=l) students[i].sgn = 3;
else {
students[i].sgn = 4;
failcount ++;
}
}
sort(students, students+num, cmp);
student tmp;
for (int j = 0;j<num;j++)
{
if (students[j].c == students[j+1].c && students[j].d == students[j+1].d && students[j].id > students[j+1].id ){
tmp = students[j];
students[j] = students[j+1];
students[j+1] = tmp;
}
}
cout<<num-failcount<<endl;
for (int j = 0;j<num-failcount;j++)
{
cout<<students[j].id<<" "<<students[j].d<<" "<<students[j].c<<endl;;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct bign{
int len;
int d[1000];
bign(){
len = 0;
memset(d,0,sizeof(d));
}
};
bign convert1(string n){
bign a;
for(int i = 0;i<n.size();i++){
a.d[a.len++] = (int)(n[n.size()-1-i]-'0');
}
return a;
}
bign devide(bign a,int b,int &r){
bign q;
r = 0;
q.len = a.len;
for(int i = a.len-1;i>=0;i--){
r = 10 * r + a.d[i];
if (r<b) q.d[i] = 0;
else {
q.d[i] = r/b;
r = r%b;
}
}
while (q.len >= 2 && q.d[q.len-1] == 0){q.len--;}
return q;
}
int main(){
string n;
cin>>n;
int b,r=0;
scanf("%d",&b);
bign q = devide(convert1(n),b,r);
for(int i = 0;i<q.len;i++){
printf("%d",q.d[q.len-1-i]);
}
printf(" %d",r);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int a[4];
int a1,a2,judge = 0;
while((n!=6174 && n!= 0) || (n==6174 && judge == 0)){
judge = 1;
a[0] = n/1000;
a[1] = (n-a[0]*1000)/100;
a[2] = (n-a[0]*1000-a[1]*100)/10;
a[3] = n%10;
sort(a,a+4);
a1 = a[3] + a[2] * 10 + a[1] * 100 + a[0] * 1000;
a2 = a[0] + a[1] * 10 + a[2] * 100 + a[3] * 1000;
n = a2-a1;
printf("%04d - %04d = %04d\n",a2,a1,n);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
double amount,totalprice;
} moon;
bool cmp(moon a,moon b){
return (a.totalprice/a.amount)>(b.totalprice/b.amount);
}
int main(){
int n;
double d,money;
cin>>n>>d;
vector<moon>mooncake;
mooncake.resize(n);
for(int i = 0;i<n;i++){scanf("%lf",&mooncake[i].amount);}
for(int i = 0;i<n;i++){scanf("%lf",&mooncake[i].totalprice);}
sort(mooncake.begin(),mooncake.end(),cmp);
for(int i = 0;i<n;i++){
if (d>mooncake[i].amount){d -=mooncake[i].amount;money+=mooncake[i].totalprice;}
else{
money+=mooncake[i].totalprice/mooncake[i].amount * d;
break;
}
}
printf("%.2lf",money);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
string k;
cin>>k;
int rst[10] = {};
for(int i = 0;i<k.size();i++){
rst[int(k[i]-'0')]++;
}
for(int i = 0;i<10;i++){
if (rst[i]>0)cout<<i<<":"<<rst[i]<<endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int a,b,c,d;
vector<int>result;
cin>>a>>b>>d;
c = a + b;
while (c/d > 0){
result.push_back(c-d*(c/d));
c = (c-c%d)/d;
}
result.push_back(c);
for (int i = result.size()-1;i>-1;i--){
cout<<result[i];
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int num[10];
for(int i = 0;i<10;i++){scanf("%d",&num[i]);}
for(int i = 1;i<10;i++){
if (num[i]>0){cout<<i;num[i]-=1;break;}
}
for(int i = 0;i<10;i++){
while(num[i]>0){cout<<i;num[i]-=1;}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
double num[2];
string input;
cin>>input;
int pose = 0;
for(int i = 1;i<input.size();i++){
if(input[i]=='E') {
pose = i;
break;
}
}
num[0] = 10*(input[1]-'0');
for(int i = 3;i<pose;i++){
num[0]+=input[i]-'0';
num[0] = num[0]*10;
}
long long a = (long long)num[0]/10;
for(int i = pose+2;i<input.size();i++){
num[1]+=input[i]-'0';
num[1] = num[1]*10;
}
int b = (int)num[1]/10;
if (input[0] == '-') cout<<'-';
if (input[pose+1] == '-'){
cout<<"0.";
for(int i = 0;i<b-1;i++){cout<<'0';}
cout<<a;}
else{
if (b>=(to_string(a).size())-1)
cout<<fixed<<setprecision(0)<<a*pow(10, b-(to_string(a).size())+1);
else{
for(int i = 0;i<b+1;i++){
cout<<to_string(a)[i];
}
cout<<'.';
for(int i = b+1;i<to_string(a).size();i++){
cout<<to_string(a)[i];
}
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
double num[2];
string input;
cin>>input;
int pose = 0;
for(int i = 1;i<input.size();i++){
if(input[i]=='E') {
pose = i;
break;
}
}
vector<char>nums;
nums.push_back(input[1]);
for(int i = 3;i<pose;i++){
nums.push_back(input[i]);
}
for(int i = pose+2;i<input.size();i++){
num[1]+=input[i]-'0';
num[1] = num[1]*10;
}
int b = (int)num[1]/10;
if (input[0] == '-') cout<<'-';
if (input[pose+1]=='+'){
if (nums.size()<=b+1){
for(int i = 0;i<nums.size();i++){
cout<<nums[i];
}
for(int i = 0;i<b+1-nums.size();i++){
cout<<0;
}
}
else{
for(int i = 0;i<b+1;i++){
cout<<nums[i];
}
cout<<'.';
for(int i = b+1;i<nums.size();i++){
cout<<nums[i];
}
}
}
else{
cout<<"0.";
for(int i = 0;i<b-1;i++){
cout<<0;
}
for(int i = 0;i<nums.size();i++){
cout<<nums[i];
}
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
struct node{
int key;
int next,add;
};
int main(){
int head,n,k;
scanf("%d %d %d",&head,&n,&k);
int key,add,next;
node a[100010];
for(int i = 0;i<n;i++){
scanf("%d %d %d",&add,&key,&next);
a[add].key = key;
a[add].add = add;
a[add].next = next;
}
vector <vector<int>> seq;
int p = head;
for(int i = 0;i<n && p!=-1 ;i++){
vector <int> temp(2);
seq.push_back(temp);
seq[i][0] = a[p].key;
seq[i][1] = a[p].add;
p = a[p].next;
}
for (int i = 0;i<seq.size()-k+1;i+=k){
reverse(seq.begin()+i, seq.begin()+i+k);
}
for(int i = 0;i<seq.size()-1;i++){
printf("%05d %d %05d\n",seq[i][1],seq[i][0],seq[i+1][1]);
}
int m = (int)seq.size();
printf("%05d %d %d\n",seq[m-1][1],seq[m-1][0],-1);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
char a;
cin>>n>>a;
if (n == 1){
cout<<a<<endl<<0;
return 0;
}
int m = sqrt((n+1)/2);
int left = n+1-2*m*m;
for (int i = m;i>1;i--){
for (int j = 0;j<m-i;j++){
cout<<' ';
}
for (int j =0;j<2*i-1;j++){
cout<<a;
}
cout<<endl;;
}
for (int j = 0;j<m-1;j++){
cout<<' ';
}
cout<<a<<endl;
for (int i = 2;i<m+1;i++){
for (int j = 0;j<m-i;j++){
cout<<' ';
}
for (int j =0;j<2*i-1;j++){
cout<<a;
}
cout<<endl;;
}
cout<<left;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
char name[20];
int date;
} man;
bool cmp(man a,man b)
{
return a.date<b.date;
}
int main(){
int n;
cin>>n;
man people[n];
int a,b,c;
for (int i = 0;i<n;i++){
scanf("%s %d/%d/%d" ,people[i].name,&a,&b,&c);
people[i].date = a*10000+b*100+c;
}
sort(people, people+n,cmp);
int max = 0,min = n-1;
for(int i = 0;i<n;i++){
if (i == 0) {
if (people[0].date>18140905) max = 0;}
else{
if (people[i].date>18140905 && people[i-1].date<=18140905) max = i;
if (people[i-1].date<=20140906 && people[i].date>20140906) min = i-1;
}
}
cout<<min-max+1<<' '<<people[max].name<<' '<<people[min].name;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring> //strlen
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
char a[1000],b[1000];
int hashtable[128] = {};
scanf("%s %s",b,a);
int lena = (int)strlen(a);
int lenb = (int)strlen(b);
for(int i = 0;i<lena;i++){
if (a[i]>='A' && a[i]<='Z')hashtable[a[i]-'A']+=1;
else if (a[i]>='a' && a[i]<='z')hashtable[a[i]-'a']+=1;
else if (a[i]>='0' && a[i]<='9')hashtable[a[i]-'0'+26]+=1;
else if (a[i]=='_')hashtable[36]+=1;
}
for(int i = 0;i<lenb;i++){
int t = 0;
if (b[i]>='A' && b[i]<='Z')t=b[i]-'A';
else if (b[i]>='a' && b[i]<='z')t=b[i]-'a';
else if (b[i]>='0' && b[i]<='9')t=b[i]-'0'+26;
else if (b[i]=='_')t=36;
if (hashtable[t]==0) {
if (b[i]>='a' && b[i]<='z')cout<<(char)(b[i]-'a'+'A');
else cout<<b[i];
hashtable[t]+=1;}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,p,max = 0,tmp = 1;
long long maxnum = 0;
cin>>n>>p;
vector<long long>a;
a.resize(n);
for(int i = 0;i<n;i++){scanf("%lld",&a[i]);}
sort(a.begin(),a.end());
for(int i = 0;i<n;i++){
maxnum = a[i] * p;
tmp = (int)(upper_bound(a.begin()+i+1, a.end(), (long long)a[i] * p) - a.begin() - i);
if (max < tmp){
max = tmp;
}
}
cout<<max;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,p,max = 1;
cin>>n>>p;
vector<long long>a;
a.resize(n);
for(int i = 0;i<n;i++){scanf("%lld",&a[i]);}
sort(a.begin(),a.end());
int maxpos = 0;
for(int i = 0;i<n;i++){
while(a[maxpos]<=(long long)a[i]*p && maxpos<n){
if(maxpos>=n)break;
if(maxpos-i+1>=max)max = maxpos - i+1;
maxpos++;
}
}
cout<<max;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
int judge = 0;
cin>>n;
const int num = n;
int weight[17] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char id[num][19];
for(int i = 0;i<num;i++){
scanf("%s",id[i]);
id[i][18] = '0';
}
for(int i = 0;i<n;i++){
int sum = 0;
for(int j = 0;j<17;j++){
if (id[i][j]>='0'&& id[i][j]<='9'){
sum += weight[j]*(int)(id[i][j]-'0');
}
else {
id[i][18] = '1';
break;
}
}
if ( (sum%11 == 0&&id[i][17] == '1' )
|| (sum%11 == 1&&id[i][17] == '0' )
|| (sum%11 == 2&&id[i][17] == 'X' )
|| (sum%11 == 3&&id[i][17] == '9' )
|| (sum%11 == 4&&id[i][17] == '8' )
|| (sum%11 == 5&&id[i][17] == '7' )
|| (sum%11 == 6&&id[i][17] == '6' )
|| (sum%11 == 7&&id[i][17] == '5' )
|| (sum%11 == 8&&id[i][17] == '4' )
|| (sum%11 == 9&&id[i][17] == '3' )
|| (sum%11 == 10&&id[i][17] == '2' )
)
{
continue;}
else {
id[i][18] = '1';
}
}
for(int i = 0;i<num;i++){
if (id[i][18]=='1') {
judge = 1;
for (int j=0;j<18;j++){
cout<<id[i][j];
}
cout<<endl;
}
else continue;
}
if (judge == 0) {cout<<"All passed";return 0;}
else return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
int a[100000] = {};
int b,c;
for (int i = 0;i<n;i++){
cin>>b>>c;
a[b]+=c;
}
int max = 0,pos = 0;
for (int i = 0;i<100000;i++){
if(max<a[i]) {
max = a[i];
pos = i;
}
}
cout<<pos<<' '<<a[pos];
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring> //strlen
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
char a[1000],b[1000];
bool hashtable[128] = {0};
hashtable[50]=false;
scanf("%s %s",a,b);
int lena = (int)strlen(a);
int lenb = (int)strlen(b);
for(int i = 0;i<lena;i++){
if (a[i]>='A' && a[i]<='Z'){
hashtable[a[i]-'A']=true;}
else if (a[i]>='a' && a[i]<='z')hashtable[a[i]-'a']=true;
else if (a[i]>='0' && a[i]<='9')hashtable[a[i]-'0'+26]=true;
else if (a[i]=='_')hashtable[36]=true;
else if (a[i]==',')hashtable[37]=true;
else if (a[i]=='.')hashtable[38]=true;
else if (a[i]=='-')hashtable[39]=true;
else if (a[i]=='+')hashtable[40]=true;
}
for(int i = 0;i<lenb;i++){
int t = 0,shift = 1;
if (b[i]>='A' && b[i]<='Z'){t=b[i]-'A';shift = 0;}
else if (b[i]>='a' && b[i]<='z')t=b[i]-'a';
else if (b[i]>='0' && b[i]<='9')t=b[i]-'0'+26;
else if (b[i]=='_')t=36;
else if (b[i]==',')t=37;
else if (b[i]=='.')t=38;
else if (b[i]=='-')t=39;
else if (b[i]=='+')t=40;
if (hashtable[t]==false) {
if (hashtable[40] == true && b[i]>='A' && b[i]<='Z'){
continue;
}
else cout<<b[i];
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
typedef long long LL;
using namespace std;
typedef struct{
LL up,down;
} fractionnum;
LL maxfactor(LL a,LL b){
a = abs(a);
if (b!= 0) return maxfactor(b, a%b);
else return a;
}
fractionnum yue(fractionnum a){
if (a.up == 0){a.down = 1;return a;}
if (a.down < 0){a.down = -a.down;a.up = -a.up;}
long long max = maxfactor(a.down, a.up);
if (max == a.down){
a.up = a.up/a.down;
a.down = 1;
}
else if (max > 1){
a.up = a.up/max;
a.down = a.down/max;
}
return a;
}
fractionnum pluss(fractionnum a,fractionnum b){
fractionnum temp;
temp.down = a.down * b.down;
temp.up = a.up * b.down + a.down * b.up;
return yue(temp);
}
fractionnum minuss(fractionnum a,fractionnum b){
b.up = -1 * b.up;
return pluss(a,b);
}
fractionnum multi(fractionnum a,fractionnum b){
fractionnum temp;
temp.down = a.down * b.down;
temp.up = a.up * b.up;
return yue(temp);
}
fractionnum devide(fractionnum a,fractionnum b){
fractionnum temp;
temp.down = a.down * b.up;
temp.up = a.up * b.down;
return yue(temp);
}
void printpartition(fractionnum a){
a = yue(a);
if (a.up<0)printf("(-");
if (maxfactor(abs(a.down), a.up) == a.down){
printf("%lld",abs(a.up)/a.down);
}
else{
if (abs(a.up)>a.down){
printf("%lld %lld/%lld",abs(a.up)/a.down,abs(a.up) % a.down,a.down);}
else {printf("%lld/%lld",abs(a.up),a.down);}
}
if (a.up<0)printf(")");
}
int main(){
fractionnum a,b;
scanf("%lld/%lld",&a.up,&a.down);
scanf("%lld/%lld",&b.up,&b.down);
printpartition(a);printf(" + ");
printpartition(b);printf(" = ");
printpartition(pluss(a, b));printf("\n");
printpartition(a);printf(" - ");
printpartition(b);printf(" = ");
printpartition(minuss(a, b));printf("\n");
printpartition(a);printf(" * ");
printpartition(b);printf(" = ");
printpartition(multi(a, b));printf("\n");
printpartition(a);printf(" / ");
printpartition(b);printf(" = ");
if (b.up == 0){printf("Inf\n");}
else {printpartition(devide(a, b));printf("\n");}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a;a.resize(n);
vector<int>b;b.resize(n);
int bpos = 0,judge = 0;
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
for(int i = 0;i<n;i++){
scanf("%d",&b[i]);
if(judge == 0 && b[i]<b[i-1]){bpos = i;judge = 1;}
}
judge = 0;
for(int i = bpos+1;i<n;i++){
if(b[i]!=a[i]){judge = 1;break;}
}
if (judge == 1){
cout<<"Merge Sort\n";
int key = 0;
for(int seg = 2;seg<2*n;seg=seg*2){
for(int i = 0;i<n;i+=seg){
if (i+seg<n) sort(a.begin()+i,a.begin()+i+seg);
else sort(a.begin()+i,a.end());
}
if (key == 1){
for(int i = 0;i<n;i++){
cout<<a[i];
if (i!=n-1)cout<<' ';
}
break;
}
judge = 1;
for(int i = 0;i<n;i++){if(a[i]!=b[i]){judge = 0;break;}}
if (judge == 1)key = 1;
}
}
else {
cout<<"Insertion Sort\n";
for(int i = 0;i<bpos;i++){
if (b[i]>b[bpos] && judge == 0){
cout<<b[bpos]<<' ';
judge +=1;}
cout<<b[i]<<' ';
}
for(int i = bpos+1;i<n;i++){
cout<<b[i];
if(i!=n-1)cout<<' ';
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
char a;
cin>>n>>a;
for (int i =0;i<n;i++){
cout<<a;
}
cout<<endl;
int t;
if (n%2 == 0) t = n/2;
else t = n/2+1;
for (int i =0;i<t-2;i++){
cout<<a;
for (int j =0;j<n-2;j++){
cout<<' ';
}
cout<<a<<endl;;
}
for (int i =0;i<n;i++){
cout<<a;
}
cout<<endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int g1,s1,k1,g2,s2,k2,g3,s3,k3;
scanf("%d.%d.%d %d.%d.%d",&g1,&s1,&k1,&g2,&s2,&k2);
int sum1,sum2,diff;
sum1 = g1 * 17 * 29 + s1 * 29 + k1;
sum2 = g2 * 17 * 29 + s2 * 29 + k2;
if (sum1>sum2){
diff = sum1-sum2;
g3 = diff/(17*29);
s3 = (diff-g3*17*29)/29;
k3 = diff - g3 * 17 * 29 - s3 * 29;
printf("-%d.%d.%d",g3,s3,k3);
}
else if (sum1<sum2){
diff = sum2-sum1;
g3 = diff/(17*29);
s3 = (diff-g3*17*29)/29;
k3 = diff - g3 * 17 * 29 - s3 * 29;
printf("%d.%d.%d",g3,s3,k3);
}
else{
cout<<"0.0.0";
return 0;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring> //strlen
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,k;
int hundred[101] = {};
scanf("%d",&n);
int score[n];
for(int i = 0;i<n;i++){
scanf("%d",&score[i]);
hundred[score[i]]+=1;}
scanf("%d",&k);
int query[k];
for(int i = 0;i<k;i++){scanf("%d",&query[i]);}
for(int i = 0;i<k;i++){
printf("%d",hundred[query[i]]);
if (i<k-1)cout<<' ';
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
char a[1000],b[1000];
scanf("%s %s",a,b);
int hash[128] = {};
int lena = (int)strlen(a);
int lenb = (int)strlen(b);
for(int i = 0;i<lena;i++) hash[(int)a[i]]+=1;
int judge = 1,left = 0;
for(int i = 0;i<lenb;i++){
hash[(int)b[i]]-=1;
if (hash[(int)b[i]]<0) judge = 0;
}
int num = 0;
if (judge == 0){
cout<<"No ";
for(int i = 0;i<128;i++){
if(hash[i] < 0)num += hash[i];
}
}
else{
cout<<"Yes ";
for(int i = 0;i<128;i++){
if(hash[i] > 0)num += hash[i];
}
}
cout<<abs(num);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
string a;
cin>>a;
vector<int>p;p.resize(a.size());
vector<int>t;t.resize(a.size());
int countp=0,countt = 0;
long long count=0;;
for(int i = 0;i<a.size();i++){
if(a[i] == 'P')countp+=1;
if(a[i] == 'A')p[i] = countp;
}
for(int i = a.size()-1;i>=0;i--){
if(a[i] == 'T')countt+=1;
if(a[i] == 'A')t[i] = countt;
}
for(int i = 0;i<a.size();i++){
if(a[i] == 'A')count+=(long long)p[i]*t[i];
}
cout<<count%1000000007;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,m;
cin>>n;
long long a[n][3];
for (int i = 0;i<n;i++){
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
cin>>m;
int b[m];
for (int i = 0;i<m;i++){
cin>>b[i];
}
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if (b[i] == a[j][1]){
cout<<a[j][0]<<' '<<a[j][2]<<endl;
break;
}
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
char a[1000];
cin.getline(a,1000);
int hash[27] = {};
int lena = (int)strlen(a);
for(int i = 0;i<lena;i++) {
if (a[i]>='a'&&a[i]<='z') hash[(int)(a[i]-'a')]+=1;
if (a[i]>='A'&&a[i]<='Z') hash[(int)(a[i]-'A')]+=1;
}
int max = 0;
char maxchar;
for(int i = 0;i<27;i++){
if(hash[i] > max) {max = hash[i];maxchar = (char)(i+'a');}
}
cout<<maxchar<<' ';
cout<<max;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
char a[1000];
cin.getline(a,1000);
int hash[52] = {};
int lena = (int)strlen(a);
for(int i = 0;i<lena;i++) {
if (a[i]>='a'&&a[i]<='z') hash[(int)(a[i]-'a')]+=1;
if (a[i]>='A'&&a[i]<='Z') hash[(int)(a[i]-'A'+26)]+=1;
}
for(int i = 0;i<lena;i++) {
int judge = 0;
if (hash['P'-'A'+26]>0) {cout<<'P';hash['P'-'A'+26]-=1;judge = 1;}
if (hash['A'-'A'+26]>0) {cout<<'A';hash['A'-'A'+26]-=1;judge = 1;}
if (hash['T'-'A'+26]>0) {cout<<'T';hash['T'-'A'+26]-=1;judge = 1;}
if (hash['e'-'a']>0) {cout<<'e';hash['e'-'a']-=1;judge = 1;}
if (hash['s'-'a']>0) {cout<<'s';hash['s'-'a']-=1;judge = 1;}
if (hash['t'-'a']>0) {cout<<'t';hash['t'-'a']-=1;judge = 1;}
if (judge == 0)break;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
char a[50000];
cin.getline(a,50000);
int hash[6] = {};
int lena = (int)strlen(a);
int sum = 0;
for(int i = 0;i<lena;i++) {
if (a[i]=='P'){hash[0]++;sum+=1;}
else if (a[i]=='A'){hash[1]++;sum+=1;}
else if (a[i]=='T'){hash[2]++;sum+=1;}
else if (a[i]=='e'){hash[3]++;sum+=1;}
else if (a[i]=='s'){hash[4]++;sum+=1;}
else if (a[i]=='t'){hash[5]++;sum+=1;}
}
for(int i = 0;i<lena;i++) {
if (hash[0]>0) {cout<<'P';hash[0]-=1;sum-=1;}
if (hash[1]>0) {cout<<'A';hash[1]-=1;sum-=1;}
if (hash[2]>0) {cout<<'T';hash[2]-=1;sum-=1;}
if (hash[3]>0) {cout<<'e';hash[3]-=1;sum-=1;}
if (hash[4]>0) {cout<<'s';hash[4]-=1;sum-=1;}
if (hash[5]>0) {cout<<'t';hash[5]-=1;sum-=1;}
if (sum <= -1)break;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <map>
#include <string>
using namespace std;
int toint(string a){
int b = 0;
for(int i = 0;i<a.size();i++){
b = b*10 + (int)(a[i] - '0');
}
return b;
}
int main(){
string a[13] = {"tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string b[13] = {"tret","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
map<string,int> str2int;
string int2str[169];
for(int i = 0;i<169;i++){
string temp;
if (i/13 != 0 && i%13 != 0)
temp = b[i/13]+" "+a[i%13];
else if (i/13 == 0) temp = a[i%13];
else temp = b[i/13];
int2str[i] = temp;
str2int[temp] = i;
}
int n;
string str;
scanf("%d%*c",&n);
while(n--){
getline(cin,str);
if(str[0]>='0'&&str[0]<='9'){
int temp = toint(str);
cout<<int2str[temp]<<endl;
}
else{
cout<<str2int[str]<<endl;
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a;a.resize(n);
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
vector<int>left;left.resize(n);
vector<int>right;right.resize(n);
vector<int>result;result.resize(n);
int max = a[0],min = a[n-1];
left[0] = 1;right[n-1] = 1;
for(int i = 0;i<n;i++){
if (a[i]>=max){max = a[i];left[i] = 1;}
else {left[i] = 0;}
}
for(int i = n-1;i>=0;i--){
if (a[i]<=min){min = a[i];right[i] = 1;}
else {right[i] = 0;}
}
int count = 0;
for(int i = 0;i<n;i++){
if (left[i] == 1 && right[i] == 1){
result[count++] = a[i];}
}
printf("%d\n",count);
vector<int>finalresult;finalresult.resize(count);
for(int i = 0;i<count;i++){finalresult[i] = result[i];}
for(int i = 0;i<count;i++){
printf("%d",result[i]);
if (i<count - 1)printf(" ");
}
printf("\n");
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>team;
team.resize(1000);
for(int i = 0;i<n;i++){
int a,b,c;
scanf("%d-%d %d",&a,&b,&c);
team[a]+=c;
}
int max = 0,mteam = 0;
for(int i = 0;i<1000;i++){
if (team[i]>max){max = team[i];mteam = i;}
}
cout<<mteam<<' '<<max;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int cmp(string a,string b){
if(a.size()>b.size()) return (int)b.size();
else return (int)a.size();
}
string max(string a,string b){
if(a.size()<b.size()) return b;
else return a;
}
int main(){
string a,b,c;
cin>>a>>b;
for(int i = 0;i<cmp(a,b);i++){
if(i%2==0){
int temp = (a[a.size()-i-1]+b[b.size()-i-1]-'0'-'0')%13;
if (temp<10) c.push_back((char)(temp+'0'));
else if (temp==10) c.push_back('J');
else if (temp==11) c.push_back('Q');
else if (temp==12) c.push_back('K');
}
else{
c.push_back((char)((10-a[a.size()-i-1]+b[b.size()-i-1])%10+'0'));
}
}
for(int i = cmp(a,b);i<max(a,b).size();i++){
c.push_back(max(a,b)[max(a,b).size()-i-1]);
}
for(int i = 0;i<c.size();i++){
cout<<c[c.size()-1-i];
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
vector<double>a;a.resize(n);
for(int i = 0;i<n;i++){
scanf("%lf",&a[i]);
}
double finalproduct = 0.0;
for(int i = 0;i<n;i++){
finalproduct += a[i] * (i+1) * (n-i);
}
printf("%.02lf",finalproduct);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int main(){
int a,b,result;
string op;
cin>>a>>b;
result = a+b;
op = to_string(result);
int judge = 1;
for(int i = 0;i<op.size();i++){
if (i%3 == op.size()%3 && judge == 0){
cout<<',';
i-=1;
judge = 1;
}
else {
cout<<op[i];
if (op[i] == '-')judge = 1;
else judge = 0;
}
}return 0;
}
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;
struct node{
int v,weight;
node(int _v,int _w):v(_v),weight(_w){};
};
int n,m,s,u;
vector<node>adj[maxn];
int dis[maxn];
int weight[maxn],pathnum[maxn] = {0},teamnum[maxn] = {0};
bool vis[maxn] = {false};
void Dj(int s){
fill(dis,dis+maxn,INF);
dis[s] = 0;pathnum[s] = 1;teamnum[s] = weight[s];
for(int i = 0;i<n;i++){
int MIN = INF,k = -1;
for(int j = 0;j<n;j++){
if (dis[j] < MIN && vis[j] == false){
MIN = dis[j];
k = j;
}
}
if (k == -1)return;
vis[k] = true;
for(int j = 0;j<adj[k].size();j++){
int v = adj[k][j].v;
if (vis[v] == false){
if(dis[v] > dis[k] + adj[k][j].weight)
{
dis[v] = dis[k] + adj[k][j].weight;
pathnum[v] = pathnum[k];
teamnum[v] = teamnum[k] + weight[v];
}
else if (dis[v] == dis[k] + adj[k][j].weight)
{
if (teamnum[v] < teamnum[k] + weight[v])
{
teamnum[v] = teamnum[k] + weight[v];
}
pathnum[v] += pathnum[k];
}
}
}
}
}
int main(){
scanf("%d %d %d %d",&n,&m,&s,&u);
for(int i = 0;i<n;i++){scanf("%d",&weight[i]);}
for(int i = 0;i<m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
adj[a].push_back(node(b,c));
adj[b].push_back(node(a,c));
}
Dj(s);
printf("%d %d\n",pathnum[u],teamnum[u]);
return 0;
}
#include <queue>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
struct Node{
int layer;
vector<int>child;
};
vector<Node>tree;
void inorder(int root){
queue<int>q;
q.push(root);
tree[root].layer = 1;
while(!q.empty()){
int front = q.front();
q.pop();
for(int i = 0;i<tree[front].child.size();i++){
q.push(tree[front].child[i]);
tree[tree[front].child[i]].layer = tree[front].layer + 1;
}
}
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
tree.resize(n+1);
for(int i = 0;i<m;i++){
int childsize,number;
scanf("%d %d",&number,&childsize);
tree[number].child.resize(childsize);
for(int j = 0;j<childsize;j++){
scanf("%d",&tree[number].child[j]);
}
}
inorder(1);
vector<int>count(n+1);
int maxlayer = 0;
for(int i = 0;i<n+1;i++){
if (tree[i].child.size() == 0) count[tree[i].layer]++;
if (tree[i].layer > maxlayer) maxlayer = tree[i].layer;
}
for (int i = 1;i<maxlayer+1;i++){
printf("%d",count[i]);
if (i<maxlayer) printf(" ");
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int main(){
string a;
int sum = 0;
cin>>a;
for (int i = 0;i<a.size();i++){
sum += a[i]-'0';
}
string result = to_string(sum);
for (int i = 0;i<result.size();i++){
switch (result[i]-'0'){
case 0:cout<<"zero";break;
case 1:cout<<"one";break;
case 2:cout<<"two";break;
case 3:cout<<"three";break;
case 4:cout<<"four";break;
case 5:cout<<"five";break;
case 6:cout<<"six";break;
case 7:cout<<"seven";break;
case 8:cout<<"eight";break;
case 9:cout<<"nine";break;
}
if (i!=result.size()-1)cout<<' ';
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
char name[20];
int date1,date2;
} man;
bool cmp1(man a,man b)
{
return a.date1<b.date1;
}
bool cmp2(man a,man b)
{
return a.date2>b.date2;
}
int main(){
int n;
cin>>n;
man people[n];
int a,b,c,d,e,f;
for (int i = 0;i<n;i++){
scanf("%s %d:%d:%d %d:%d:%d" ,people[i].name,&a,&b,&c,&d,&e,&f);
people[i].date1 = a*10000+b*100+c;
people[i].date2 = d*10000+e*100+f;
}
sort(people, people+n,cmp1);
cout<<people[0].name<<' ';
sort(people, people+n,cmp2);
cout<<people[0].name<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n,flag = 0;
scanf("%d",&n);
int a[n],dp[n],posstart[n];
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
if (a[i]>=0)flag = 1;
}
if (flag == 0){
printf("0 %d %d",a[0],a[n-1]);
return 0;
}
dp[0] = a[0];
for(int i = 1;i<n;i++){
if (dp[i-1]+a[i] > a[i]){
dp[i] = dp[i-1]+a[i];
posstart[i] = posstart[i-1];
}
else{
dp[i] = a[i];
posstart[i] = i;
}
}
int maxendpos = 0;
for (int i = 0;i<n;i++){
if (dp[i] > dp[maxendpos]){
maxendpos = i;
}
}
printf("%d %d %d",dp[maxendpos],a[posstart[maxendpos]],a[maxendpos]);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a;a.resize(n);
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
}
int finalproduct = 0,now = 0;
for(int i = 0;i<n;i++){
if (a[i]>now)finalproduct+= 6 * (a[i]-now) + 5;
else finalproduct+= 4 * (-a[i]+now) + 5;
now = a[i];
}
printf("%d",finalproduct);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
long long convert(string a,int k){
long long num = 0;
for(int i = (int)a.size()-1;i>=0;i--){
int temp = 0;
if (a[i] >= '0' && a[i]<='9')temp = a[i] - '0';
else temp = a[i] - 'a' + 10;
if (k<=temp)return 0;
num += temp * pow(k, (a.size()-1-i));
}
return num;
}
int maxradix(string a){
int radix = 0;
for(int i = 0;i<a.size();i++){
if (a[i] >= '0' && a[i]<='9'){
if ((a[i]-'0')>radix) radix = a[i]-'0';
}
else {
if ((a[i]-'a'+10)>radix) radix = a[i]-'a'+10;
}
}
return radix;
}
int main(){
int tag,radix;
string a,b;
cin>>a>>b>>tag>>radix;
long long anum;
if (tag == 1){
anum = convert (a,radix);
}
else{
anum = convert (b,radix);
b = a;
}
int left = 0,right = max(maxradix(b),radix)+1,sgn = 0;
while(left<=right){
int mid = (left + right)/2;
if (anum < convert(b, mid)) right = mid-1;
else if (anum > convert(b, mid)) left = mid+1;
else {cout<<mid;sgn = 1;break;}
}
if (sgn == 0)cout<<"Impossible";
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
double a[3][3];
int pos[3];
for (int i = 0;i<3;i++){
for (int j = 0;j<3;j++){
cin>>a[i][j];
}
double max = 0;
for (int j = 0;j<3;j++){
if (a[i][j]>max){
max = a[i][j];
pos[i] = j;
}
}
}
for (int i = 0;i<3;i++){
if (pos[i] == 0) cout<<"W ";
else if (pos[i] == 1) cout<<"T ";
else if (pos[i] == 2) cout<<"L ";
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<(a[1][pos[1]] * a[0][pos[0]] *a[2][pos[2]] * 0.65 - 1)*2;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int now;
typedef struct{
int id;
int grade[4];
int rank[4];
} student;
bool cmp(student a,student b)
{
return a.grade[now]>b.grade[now];
}
int main(){
int n,m;
cin>>n>>m;
student stu[n],stuchk[m];
for(int i = 0;i<n;i++){
cin>>stu[i].id>>stu[i].grade[0]>>stu[i].grade[1]>>stu[i].grade[2];
stu[i].grade[3] = stu[i].grade[0]+stu[i].grade[1]+stu[i].grade[2];
}
for(int i = 0;i<m;i++){
cin>>stuchk[i].id;
}
for(now = 0;now<4;now++){
sort(stu, stu+n, cmp);
for(int i = 0;i<n;i++){
if (i == 0) stu[i].rank[now] = i;
if (stu[i].grade[now]!=stu[i-1].grade[now]) stu[i].rank[now] = i;
else stu[i].rank[now] = stu[i-1].rank[now];
}
}
int toop[4] = {3,0,1,2};
for(int i = 0;i<m;i++){
int sgn = 0;
for(int j = 0;j<n;j++){
if (stuchk[i].id == stu[j].id){
int min = n,minsgn = 5;
for(int k = 0;k<4;k++){
if (stu[j].rank[toop[k]]<min) {
min = stu[j].rank[toop[k]];
minsgn = toop[k];}
}
cout<<min+1<<' ';
switch (minsgn){
case 0:{cout<<"C"<<endl;break;}
case 1:{cout<<"M"<<endl;break;}
case 2:{cout<<"E"<<endl;break;}
case 3:{cout<<"A"<<endl;break;}
default:continue;
}
sgn = 1;
break;
}
}
if (sgn == 0)cout<<"N/A"<<endl;
}
return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1010;
int n,m,k;
vector<int>graph[maxn];
bool BFS(int start,int end,int nopass){
queue<int>q;
bool vis[maxn] = {false};
q.push(start);vis[start] = true;
while(!q.empty()){
int top = q.front();q.pop();
if (top == end)return true;
for(int i = 0;i<graph[top].size();i++){
int temp = graph[top][i];
if (temp != nopass && vis[temp] == false){
q.push(temp);
vis[temp] = true;
}
}
}
return false;
}
int getNum(int nopass){
int count = 0;
for(int i = 1;i<graph[nopass].size();i++){
if (!BFS(graph[nopass][0], graph[nopass][i], nopass)){
count ++;
int a = graph[nopass][0];
int b = graph[nopass][i];
graph[a].push_back(b);
graph[b].push_back(a);
}
}
return count;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i<m+1;i++){
int temp1,temp2;
scanf("%d%d",&temp1,&temp2);
graph[temp2].push_back(temp1);
graph[temp1].push_back(temp2);
}
int query[k];
for(int i = 0;i<k;i++){scanf("%d",&query[i]);}
for(int i = 0;i<k;i++){printf("%d\n",getNum(query[i]));}
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1010;
int father[maxn];
bool vis[maxn];
vector<int>g[maxn];
void init(int n){
for(int i = 1;i<=n;i++){
father[i] = i;
vis[i] = false;
}
}
int findfather(int k){
int a = k;
while(father[k]!=k){
k = father[k];
}
while(father[a]!=a){
int z = father[a];
father[a] = k;
a = z;
}
return k;
}
void Union(int a,int b){
int faa = findfather(a);
int fab = findfather(b);
if (faa != fab) father[a] = b;
}
int main(){
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
init(n);
for(int i = 1;i<m+1;i++){
int temp1,temp2;
scanf("%d%d",&temp1,&temp2);
g[temp1].push_back(temp2);
g[temp2].push_back(temp1);
}
int cur;
for(int i = 0;i<k;i++){
scanf("%d",&cur);
init(n);
for(int ii = 1;ii <= n;ii++){
for(int jj = 0;jj<g[ii].size();jj++){
int u = ii,v = g[ii][jj];
if (u!=cur && v != cur){
Union(u, v);
}
}
}
int count= 0;
for(int i = 1;i<=n;i++){
if (i == cur)continue;
int fai = findfather(i);
if (vis[fai] == false){
count++;
vis[fai] = true;
}
}
printf("%d\n",count-1);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
bool isPrime(int n)
{
if (n<1)return false;
for(int i=2;i<(int)sqrt(1.0*n)+1;i++)
{
if(n % i == 0)return false;
}
return true;
}
int convert(string a,int k1,int k2){
int num = 0;
for(int i = (int)a.size()-1;i>=0;i--){
int temp = 0;
if (a[i] >= '0' && a[i]<='9')temp = a[i] - '0';
num += temp * pow(k1, (a.size()-1-i));
}
vector<int>tempvec;
if (k2 == 10) return num;
else{
while(num>=k2){
tempvec.push_back(num % k2);
num /= k2;
}
tempvec.push_back(num);
}
num = 0;
for(int i = 0;i<tempvec.size();i++){
num = num * 10 + tempvec[tempvec.size()-i-1];
}
return num;
}
int main(){
vector<int>n1;
vector<int>d;
int temp = 1,count = 0;
while(temp>0){
scanf("%d",&temp);
if (temp<0)break;
if (count % 2 == 1) d.push_back(temp);
else n1.push_back(temp);
count++;
}
for(int i = 0;i<n1.size();i++){
if (isPrime(n1[i]) == false)printf("No\n");
else{
string str = to_string(convert(to_string(n1[i]),10,d[i]));
reverse(str.begin(),str.end());
if (isPrime(convert(str,d[i],10))) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct {
int time[4];
bool online = 0;
}record;
typedef struct {
string name;
vector<record>records;
}client;
bool cmp(record a,record b){
if(a.time[0]!=b.time[0])return a.time[0]<b.time[0];
else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1];
else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2];
else return a.time[3]<b.time[3];
}
bool cmpname(client a,client b){
return a.name<b.name;
}
int main(){
int toll[24],n;
for(int i = 0;i<24;i++){cin>>toll[i];}
cin>>n;
vector<client>clients;
for(int i = 0;i<n;i++){
string temp;
char temp2[100];
record temp1;
cin>>temp;
int k = 0;
int sgn = 0;
for(int i = 0;i<clients.size();i++){
if (clients[i].name == temp){k = i;sgn = 1;}
}
if (sgn == 0){
clients.resize(clients.size()+1);
clients[clients.size()-1].name = temp;
k = (int)clients.size()-1;
}
scanf("%d:%d:%d:%d %s",&temp1.time[0],&temp1.time[1],&temp1.time[2],&temp1.time[3],temp2);
if (temp2[1] == 'n') temp1.online = 1;
else temp1.online = 0;
clients[k].records.push_back(temp1);
}
sort(clients.begin(),clients.end(),cmpname);
for(int i = 0;i<clients.size();i++){
double totalmoney = 0;
sort(clients[i].records.begin(),clients[i].records.end(),cmp);
while(clients[i].records[clients[i].records.size()-1].online == 1){
clients[i].records.pop_back();
}
while(clients[i].records[0].online == 1 && clients[i].records[1].online == 1){
clients[i].records.erase(clients[i].records.begin());
}
bool k = 1;
int printname = 0;
for(int j = 0;j<clients[i].records.size();j++){
record temp;
if (k==clients[i].records[j].online){
if(printname == 0){
cout<<clients[i].name<<' '<<setw(2)<< setfill('0')<<clients[i].records[0].time[0]<<endl;
printname = 1;
}
cout<<setw(2)<< setfill('0')<<clients[i].records[j].time[1]<<':'<<setw(2)<< setfill('0')<<clients[i].records[j].time[2]<<':'<<setw(2)<< setfill('0')<<clients[i].records[j].time[3]; k = !k;
if(clients[i].records[j].online == 1){
temp = clients[i].records[j];
cout<<' ';
}
else{
int time = (clients[i].records[j].time[1]*1440+clients[i].records[j].time[2]*60+clients[i].records[j].time[3])-(temp.time[1]*1440+temp.time[2]*60+temp.time[3]);
double money = 0;
double start,end;
for(int day = temp.time[1];
day<clients[i].records[j].time[1]+1;day++){
for(int hour = temp.time[2];
hour < clients[i].records[j].time[2]+1;hour++){
if (temp.time[1]==clients[i].records[j].time[1] && temp.time[2]==clients[i].records[j].time[2]){
start = temp.time[3];end = clients[i].records[j].time[3];
}
else if (day == temp.time[1] && hour == temp.time[2]){start = temp.time[3];end = 60;}
else if (day == clients[i].records[j].time[1] && hour == clients[i].records[j].time[2]){start = 0;end = clients[i].records[j].time[3];}
else {start = 0;end = 60;}
money = money + (double)toll[hour] * (end-start) / 100;
}
}
cout<<' '<<time<<" $"<<fixed<<setprecision(2)<<money<<endl;
totalmoney = totalmoney + money;
}
}
}
if (totalmoney > 0){
cout<<"Total amount: $"<<fixed<<setprecision(2)<<totalmoney<<endl;
}
}
return 0;
}
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
5
a 01:01:01:03 on
a 01:02:00:01 once_flag
CYLL 01:28:15:41 once_flag
a 01:05:02:24 once_flag
a 01:02:00:02 off_t
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct {
int time[4];
char name[100];
bool online = 0;
}record;
bool cmp(record a,record b){
if(a.time[0]!=b.time[0])return a.time[0]<b.time[0];
else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1];
else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2];
else return a.time[3]<b.time[3];
}
bool cmpname(record a,record b){
if (strcmp(a.name,b.name)!=0) return strcmp(a.name,b.name)<0;
else if(a.time[0]!=b.time[0])return a.time[0]<b.time[0];
else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1];
else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2];
else return a.time[3]<b.time[3];
}
int main(){
int toll[24],n;
for(int i = 0;i<24;i++){cin>>toll[i];}
cin>>n;
vector<record>recs;
for(int i = 0;i<n;i++){
string temp;
char temp2[100];
record temp1;
scanf("%s %d:%d:%d:%d %s",temp1.name,&temp1.time[0],&temp1.time[1],&temp1.time[2],&temp1.time[3],temp2);
if (temp2[1] == 'n') temp1.online = 1;
else temp1.online = 0;
recs.push_back(temp1);
}
sort(recs.begin(),recs.end(),cmpname);
vector<record>recs4real;
for(int i = 0;i<recs.size()-1;i++){
if (strcmp(recs[i].name,recs[i+1].name)==0 && recs[i].online == 1 && recs[i+1].online == 0){
recs4real.push_back(recs[i]);
recs4real.push_back(recs[i+1]);
i = 1+i;
}
}
char tempname[20];
int time = 0;
double totalmoney = 0;
for(int i = 0;i<recs4real.size();i+=2){
if (strcmp(recs4real[i].name,tempname) != 0){
printf("%s %02d\n",recs4real[i].name,recs4real[i].time[0]);
sscanf(recs4real[i].name,"%s",tempname);
}
int passtime = (recs4real[i+1].time[1]*1440+recs4real[i+1].time[2]*60+recs4real[i+1].time[3])-(recs4real[i].time[1]*1440+recs4real[i].time[2]*60+recs4real[i].time[3]);
double money = 0;
double start,end;
for(int day = recs4real[i].time[1];
day<recs4real[i+1].time[1]+1;day++){
for(int hour = recs4real[i].time[2];
hour < recs4real[i+1].time[2]+1;hour++){
if (recs4real[i].time[1]==recs4real[i+1].time[1] && recs4real[i].time[2]==recs4real[i+1].time[2]){
start = recs4real[i].time[3];end = recs4real[i+1].time[3];
}
else if (day == recs4real[i].time[1] && hour == recs4real[i].time[2]){start = recs4real[i].time[3];end = 60;}
else if (day == recs4real[i+1].time[1] && hour == recs4real[i+1].time[2]){start = 0;end = recs4real[i+1].time[3];}
else {start = 0;end = 60;}
money = money + (double)toll[hour] * (end-start) / 100;
}
}
totalmoney += money;
printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n",recs4real[i].time[1],recs4real[i].time[2],recs4real[i].time[3],recs4real[i+1].time[1],recs4real[i+1].time[2],recs4real[i+1].time[3],passtime,money);
if (strcmp(recs4real[i].name,recs4real[i+2].name) != 0){
printf("%s $%.2f\n","Total amount:",totalmoney);
totalmoney = 0;
}
}
return 0;
}
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;
struct edge{
int v,length;
edge(int _a,int _b):v(_a),length(_b){};
};
int cmax,n,sp,m;
int bikenum[maxn],dis[maxn];
bool vis[maxn] = {};
vector<edge>adj[maxn];
vector<int>pre[maxn],best,tempbest;
void Dj(int start){
fill(dis,dis+maxn,INF);
dis[start] = 0;
for(int ii = 0;ii<n;ii++){
int k = -1,MIN = INF;
for(int i = 0;i<n;i++){
if (dis[i]<MIN && vis[i] == false){
MIN = dis[i];
k = i;
}
}
if (k == -1)return;
vis[k] = true;
for(int i = 0;i<adj[k].size();i++){
int v = adj[k][i].v;
if (vis[v] == false && dis[v] > dis[k] + adj[k][i].length){
dis[v] = dis[k] + adj[k][i].length;
pre[v].clear();
pre[v].push_back(k);
}else if(dis[v] == dis[k] + adj[k][i].length){
pre[v].push_back(k);
}
}
}
}
int minneed = INF,minremain = INF;
void DFS(int now){
if (now == 0){
tempbest.push_back(0);
int need = 0,remain = 0;
for(int i = (int)tempbest.size()-2;i>=0;i--){
int n = bikenum[tempbest[i]] - cmax/2;
if (n > 0){
remain += n;
}
else{
if (remain > -n ){
remain = remain + n;
}
else{
need = need - n - remain;
remain = 0;
}
}
}
if (need < minneed){
minneed = need;
minremain = remain;
best = tempbest;
}else if (need == minneed && remain < minremain){
minneed = need;
minremain = remain;
best = tempbest;
}
tempbest.pop_back();
return;
}
tempbest.push_back(now);
for(int i = 0;i<pre[now].size();i++){
DFS(pre[now][i]);
}
tempbest.pop_back();
}
int main(){
scanf("%d %d %d %d",&cmax,&n,&sp,&m);
for(int i = 1;i<=n;i++){scanf("%d",&bikenum[i]);}
for(int i = 0;i<m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
adj[a].push_back(edge(b,c));
adj[b].push_back(edge(a,c));
}
Dj(0);
DFS(sp);
printf("%d ",minneed);
for(int i = 0;i<best.size();i++){
printf("%d",best[best.size() - 1- i]);
if (i<best.size()-1)printf("->");
}
printf(" %d",minremain);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int c,d;
cin>>c>>d;
vector<int>result;
while (c/d > 0){
result.push_back(c-d*(c/d));
c = (c-c%d)/d;
}
result.push_back(c);
int judge = 1;
for(int i = 0;i<(result.size()+1)/2;i++){
if (result[i]!=result[result.size()-1-i]){
cout<<"No";
judge = 0;
break;
}
}
if (judge == 1){
cout<<"Yes";
}
cout<<endl;
for(int i = 0;i<result.size();i++){
cout<<result[result.size()-1-i];
if (i<result.size()-1) cout<<' ';
}
return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
}Node;
vector<int>layer(0),post(30),in(30);
node* create(int postL,int postR,int inL,int inR){
if (postL>postR)return NULL;
node* root = new node;
root->data = post[postR];
int k;
for(k = inL;k<inR;k++){
if (post[postR] == in[k]){
break;
}
}
int leftnum = k-inL;
root->lchild = create(postL, postL+leftnum-1, inL, k-1);
root->rchild = create(postL+leftnum,postR-1,k+1,inR);
return root;
}
void layerorder(node* root,vector<int>&layer){
queue<node*>q;
q.push(root);
node *now = new node;
while(!q.empty()){
layer.push_back(q.front()->data);
now = q.front();
q.pop();
if (now->lchild != NULL)q.push(now->lchild);
if (now->rchild != NULL)q.push(now->rchild);
}
}
int main(){
int n;
scanf("%d",&n);
post.resize(n);in.resize(n);
for(int i = 0;i<n;i++){scanf("%d",&post[i]);}
for(int i = 0;i<n;i++){scanf("%d",&in[i]);}
node* root = new node;
root = create(0, n-1, 0, n-1);
layerorder(root, layer);
for(int i = 0;i<n;i++){
printf("%d",layer[i]);
if (i<n-1) printf(" ");
}
return 0;
}
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100000;
int n;
vector<int>g[maxn];
int father[maxn];
bool vis[maxn] = {false};
bool isfather[maxn] = {false};
void init(int n){
for(int i = 1;i<n+1;i++){
father[i] = i;
}
}
int findfather(int n){
int a = n;
while(father[n]!=n){
n = father[n];
}
while(a!=father[a]){
int z = father[a];
father[a] = n;
a = z;
}
return n;
}
void Union(int a,int b){
int faa = findfather(a);
int fab = findfather(b);
if (faa != fab){father[faa] = fab;}
}
int countblock(){
for(int i = 1;i<n+1;i++){
isfather[findfather(i)] = true;
}
int count = 0;
for(int i = 1;i<n+1;i++){
if (isfather[i] == true)count++;
}
return count;
}
int maxdepth = 0;
vector<int>temp,ans;
void DFS(int start,int depth,int pre){
if (depth > maxdepth){
temp.clear();
temp.push_back(start);
maxdepth = depth;
}else if (depth == maxdepth){
temp.push_back(start);
}
for(int i = 0;i<g[start].size();i++){
if (g[start][i] == pre)continue;
DFS(g[start][i], depth+1, start);
}
}
int main(){
scanf("%d",&n);
init(n);
for(int i = 0;i<n-1;i++){
int a,b;
scanf("%d %d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
Union(a,b);
}
int blocks = countblock();
if (blocks!=1){
printf("Error: %d components",blocks);
}
else{
DFS(1, 1, -1);
ans = temp;
DFS(ans[0], 1, -1);
for(int i = 0;i<temp.size();i++){
ans.push_back(temp[i]);
}
sort(ans.begin(),ans.end());
for(int i = 0;i<ans.size();i++){
if (ans[i]!=ans[i-1])printf("%d\n",ans[i]);
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <set>
#include <map>
#include <string>
using namespace std;
int main(){
int n,m;
map<string,set<int>>books;
int tempid;
string temp;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d%*c",&tempid);
getline(cin,temp);books[temp].insert(tempid);
getline(cin,temp);books[temp].insert(tempid);
getline(cin,temp);
int start = 0;
for(int i = 0;i<temp.size();i++){
if (temp[i] == ' '){
books[temp.substr(start,i-start)].insert(tempid);
start = i+1;
}
}
books[temp.substr(start,temp.size()-start)].insert(tempid);
getline(cin,temp);books[temp].insert(tempid);
getline(cin,temp);books[temp].insert(tempid);
}
scanf("%d",&m);
for(int i = 0;i<m;i++){
scanf("%d: ",&tempid);
getline(cin,temp);
cout<<tempid<<": "<<temp<<endl;
if (books.find(temp) == books.end())printf("Not Found\n");
else{
for(set<int>::iterator it = books[temp].begin();it!=books[temp].end();it++){
printf("%07d\n",*it);
}
}
}
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
bool check (string a){
if (a.size() == 1) return true;
for (int i = 0;i<a.size()/2+1;i++){
if (a[i]!=a[a.size()-1-i]) return false;
}
return true;
}
string plusn (string a){
string b = a;
reverse(a.begin(), a.end());
string c;
c.resize(a.size()+1);
int p = 0;
for(int i = (int)a.size()-1;i>=0;i--){
int temp = (int)(a[i]+b[i]+p - '0' - '0');
c[i+1] = (char)(temp % 10 +'0');
p = (temp - temp % 10) / 10;
}
if (p!=0){
c[0] = (char)( p +'0');
return c;
}
else {
string d;
d.resize(c.size()-1);
for(int i = 0;i<c.size()-1;i++){
d[i] = c[i+1];
}
return d;
}
}
int main(){
int k;
string a;
cin>>a>>k;
int count = 0;
while(check(a)!=1 && count<k){
a = plusn(a);
count += 1;
}
cout<<a<<"\n"<<count;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct {
int score,localrank,rank,group;
string id;
}student;
bool cmp1(student a,student b){
if (a.group != b.group) return a.group < b.group;
else return a.score>b.score;
}
bool cmp(student a,student b){
return a.score>b.score;
}
int main(){
int n;
cin>>n;
vector<student>students;
for(int i = 0;i<n;i++){
int temp;
cin>>temp;
student tempstu;
tempstu.id.resize(30);
for(int j=0;j<temp;j++){
cin>>tempstu.id>>tempstu.score;
tempstu.group = i+1;
students.push_back(tempstu);
}
}
sort(students.begin(), students.end(), cmp1);
int count = 0;
for(int i = 0;i<students.size();i++){
if (i>0){
if (students[i].group == students[i-1].group){
if (students[i].score!=students[i-1].score) students[i].localrank = i-count;
else students[i].localrank = students[i-1].localrank;
}
else{
count = i;
students[i].localrank = i-count;
}
}
else{
students[i].localrank = 0;
}
}
sort(students.begin(), students.end(), cmp);
for(int i = 0;i<students.size();i++){
if (i == 0) students[i].rank = i;
if (students[i].score!=students[i-1].score) students[i].rank = i;
else students[i].rank = students[i-1].rank;
}
cout<<students.size()<<endl;
for(int i = 0;i<students.size();i++){
cout<<students[i].id<<' '<<students[i].rank+1<<' '<<students[i].group<<' '<<students[i].localrank+1<<endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b>>c;
cout<<'#';
int result[6]={a/13,a-a/13*13,b/13,b-b/13*13,c/13,c-c/13*13};
for (int i = 0;i<6;i++){
if (result[i]<10) cout<<result[i];
else cout<<(char)(result[i]-10+'A');
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <string.h>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct {
int id,score;
char name[10];
}stu;
bool cmpid(stu a,stu b){
return a.id<b.id;
}
bool cmpscore(stu a,stu b){
if (a.score == b.score) return a.id<b.id;
else return a.score<b.score;
}
bool cmpname(stu a,stu b){
if (strcmp(a.name,b.name) == 0) return a.id<b.id;
else return strcmp(a.name,b.name)<0;
}
int main(){
int n,k;
cin>>n>>k;
stu student[n];
for(int i = 0;i<n;i++){
scanf("%d %s %d",&student[i].id,student[i].name,&student[i].score);
}
switch (k){
case 1:sort(student, student+n, cmpid);break;
case 2:sort(student, student+n, cmpname);break;
case 3:sort(student, student+n, cmpscore);break;
}
for(int i = 0;i<n;i++){
cout<<setw(6)<<setfill('0')<<student[i].id<<' '<<student[i].name<<' '<<student[i].score<<endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int lena,lenb;
scanf("%d",&lena);
int a[lena+1];
for(int i = 0;i<lena;i++){scanf("%d",&a[i]);}
scanf("%d",&lenb);
int b[lenb+1];
for(int i = 0;i<lenb;i++){scanf("%d",&b[i]);}
a[lena] = b[lenb] = 0x7fffffff;
int median = (lena + lenb + 1)/2;
int pa=0,pb=0,k=2;
for(int i = 0;i<median;i++){
if (a[pa]<b[pb]){pa+=1;k=0;}
else {pb+=1;k=1;}
}
if (k == 0){cout<<a[pa-1];}
else if (k == 1){cout<<b[pb-1];}
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;
struct node {
int v,dis,cost;
node(int _v,int _dis,int _cost):v(_v),dis(_dis),cost(_cost){};
};
int n,m,s,d;
int dis[maxn],cost[maxn][maxn];
bool vis[maxn] = {false};
vector<node>adj[maxn];
vector<int>pre[maxn],best,tempbest;
void Dj(int start){
fill(dis,dis+maxn,INF);
dis[start] = 0;
for(int ii = 0;ii<n;ii++){
int MIN = INF,k = -1;
for(int i = 0;i<n;i++){
if (vis[i] == false && dis[i]<MIN){
k = i;
MIN = dis[k];
}
}
if (k == -1)return;vis[k] = true;
for(int i = 0;i<adj[k].size();i++){
int v = adj[k][i].v;
if (dis[v] > dis[k] + adj[k][i].dis){
dis[v] = dis[k] + adj[k][i].dis;
pre[v].clear();
pre[v].push_back(k);
}else if (dis[v] == dis[k] + adj[k][i].dis){
pre[v].push_back(k);
}
}
}
}
int getCost(){
int tempcost = 0;
for(int i = 1;i<tempbest.size();i++){
tempcost += cost[tempbest[i-1]][tempbest[i]];
}
return tempcost;
}
int minCost = INF;
void DFS(int k){
if (k == s){
tempbest.push_back(k);
int temp = getCost();
if(temp<minCost){
minCost = temp;
best = tempbest;
}
tempbest.pop_back();
return;
}
tempbest.push_back(k);
for(int i = 0;i<pre[k].size();i++){
DFS(pre[k][i]);
}
tempbest.pop_back();
}
int main(){
scanf("%d %d %d %d",&n,&m,&s,&d);
for(int i = 0;i<m;i++){
int c1,c2,dis,tempcost;
scanf("%d %d %d %d",&c1,&c2,&dis,&tempcost);
adj[c1].push_back(node(c2,dis,tempcost));
adj[c2].push_back(node(c1,dis,tempcost));
cost[c1][c2] = cost[c2][c1] = tempcost;
}
Dj(s);
DFS(d);
for(int i = 0;i<best.size();i++){
printf("%d ",best[best.size()-1-i]);
}
printf("%d %d",dis[d],minCost);
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
string a;
cin>>a;
int length = a.size();
int lines = (length+2)/3;
int width = length - lines*2;
for (int i = 0;i<lines-1;i++){
cout<<a[i];
for(int j = 0;j<width;j++){
cout<<' ';
}
cout<<a[a.size()-1-i]<<endl;
}
for (int i = 0;i<width+2;i++){
cout<<a[lines-1+i];
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct node{
int data;
int next;
bool flag;
};
int main(){
node a[100010];
int s1,s2,n;
scanf("%d %d %d",&s1,&s2,&n);
for (int i = 0;i<100010;i++){
a[i].flag = 0;
}
int add,next;
for(int i = 0;i<n;i++){
scanf("%d %*c %d",&add,&next);
a[add].next = next;
}
int p = s1;
while(p!=-1){a[p].flag = 1;p = a[p].next;}
p = s2;
while(p!=-1){
if (a[p].flag == 1)break;
p = a[p].next;
}
if (p!=-1)printf("%05d",p);
else printf("-1");
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
double price,distance;
} station;
bool cmp(station a,station b){
if (abs(a.distance-b.distance)>0.01)return a.distance<b.distance;
else return a.price<b.price;
}
bool cmp2(station a,station b){
if (abs(a.price-b.price)>0.01)return a.price<b.price;
else return a.distance<b.distance;
}
int main(){
double cmax,distance,davg,n;
scanf("%lf%lf%lf%lf",&cmax,&distance,&davg,&n);
vector<station>gas;
gas.resize(n);
for(int i = 0;i<n;i++){scanf("%lf %lf",&gas[i].price,&gas[i].distance);}
sort(gas.begin(), gas.end(), cmp);
double maxdistance = 0,k = -1;
double totalmoney = 0;
int judgeall = 1;
double nowleft = 0;
for(int i = 0;i<n;i++){
if (i == k){
judgeall = 0;
if(distance < (cmax * davg + gas[i].distance)){
totalmoney += gas[i].price * ((distance-gas[i].distance) /davg-nowleft);
break;}
int judge = 0;
double minprice = 100;
for(int j = i+1;j<n;j++){
if(gas[j].distance <= (nowleft * davg + cmax * davg + gas[i].distance)){
if (gas[j].price < minprice){minprice = gas[j].price;k = j;judge = 1;
}
}
}
if (judge == 0){printf("The maximum travel distance = %.2lf",maxdistance+cmax*davg);judgeall = 1;break;}
if(minprice<gas[i].price){
totalmoney += gas[i].price * ((gas[k].distance - gas[i].distance) /davg - nowleft);
nowleft = 0;
}
else{
totalmoney += gas[i].price * (cmax - nowleft);
nowleft = cmax - (gas[k].distance - gas[i].distance)/davg;
}
maxdistance += gas[k].distance - gas[i].distance;
}
else if (k<0){
int sgn = 0;
for(int j = 0;j<n;j++){if (gas[j].distance<0.00001)sgn = 1;}
if (sgn == 1){k = 0;i-=1;}
else {cout<<"The maximum travel distance = 0.00";break;}
}
}
if (judgeall == 0)printf("%.2lf",totalmoney);
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 50000;
struct node {
int v,w;
node(int _v,int _w):v(_v),w(_w){}
};
vector<node>adj[maxn];
int vis[maxn] = {0},nodeWeight[maxn] = {0},gs[maxn] = {0},gcount[maxn] = {0},gleader[maxn] ={-1},gleaderweight[maxn] ={0};
void DFS(int u,int depth,int group){
vis[u] = group;
gcount[group]++;
for(int i = 0;i<adj[u].size();i++){
gs[group] += adj[u][i].w/2;
if (vis[adj[u][i].v] == 0)
DFS(adj[u][i].v,depth+1,group);
}
}
int DFSTravel(int n){
int group = 1;
for(int i = 0;i<maxn;i++){
if (vis[i]==0 && adj[i].size()>0){
DFS(i,1,group);
group +=1;
}
}
return group;
}
void process(char a[],char b[],int w){
int anum = 0,bnum = 0;
for(int i = 0;i<3;i++){
anum = anum*26 + (int)(a[i]-'A');
bnum = bnum*26 + (int)(b[i]-'A');
}
adj[anum].push_back(node(bnum,w));
adj[bnum].push_back(node(anum,w));
}
void getsum(int k){
int sum = 0;
for(int i = 0;i<adj[k].size();i++){
sum += adj[k][i].w;
}
nodeWeight[k] = sum;
}
void str(int i,char c[4]){
int count = 2;
while(count>=0){
int a = i%26;
i = i/26;
c[count--] = (char)(a+'A');
}
}
int main(){
int n,k;
scanf("%d %d",&n,&k);
for(int i = 0;i<n;i++){
char a[4],b[4];
int w;
scanf("%s %s %d",a,b,&w);
process(a,b,w);
}
int group = DFSTravel(n);
for(int i = 0;i<maxn;i++){
if (adj[i].size()!=0){
getsum(i);
if (nodeWeight[i]>gleaderweight[vis[i]]){
gleaderweight[vis[i]] = nodeWeight[i];
gleader[vis[i]] = i;
}
}
}
int countgroup = 0;
for(int i = 0;i<group;i++){
if (gcount[i]>2 && gs[i]>k)countgroup++;
}
printf("%d\n",countgroup);
for(int i = 0;i<group;i++){
if (gcount[i]>2 && gs[i]>k){
char c[4];
str(gleader[i],c);
printf("%s %d\n",c,gcount[i]);
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int main(){
int n;
cin>>n;
string a[n],b[n];
vector<int>c;
c.resize(n);
int sgn = 0,count = 0;
for(int i = 0;i<n;i++){
cin>>a[i]>>b[i];
}
for(int i = 0;i<n;i++){
for(int j = 0;j<b[i].size();j++){
if (b[i][j] == 'l') {
b[i][j] = 'L';
c[i] = 1;
sgn = 1;}
if (b[i][j] == '1') {
b[i][j] = '@';
c[i] = 1;
sgn = 1;}
if (b[i][j] == '0') {
b[i][j] = '%';
c[i] = 1;
sgn = 1;}
if (b[i][j] == 'O') {
b[i][j] = 'o';
c[i] = 1;
sgn = 1;}
}
if (c[i] == 1) count++;
}
if (sgn == 0 && n == 1 ) cout<<"There is 1 account and no account is modified";
else if (sgn == 0 && n > 1 ) cout<<"There are "<<n<<" accounts and no account is modified";
else{
cout<<count<<endl;
for(int i = 0;i<n;i++){
if (c[i]>0){
cout<<a[i]<<' '<<b[i]<<endl;
}
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
char name[20],class1[20];
int score;
char gender;
}man;
bool cmp(man a,man b)
{
if(a.score>b.score)
{
return true;
}
return false;
}
int main(){
int n;
cin>>n;
man people[n];
for (int i = 0;i<n;i++){
scanf("%s %s %s %d" ,people[i].name,&people[i].gender,people[i].class1,&people[i].score);
}
sort(people, people+n,cmp);
int m = 1,f = 1,k = 0,mi = 0,fi = 0;
for(int i = 0;i<n;i++){
if(people[i].gender == 'F'){
cout<<people[i].name<<' '<<people[i].class1<<endl;
fi = i;
f = 0;
break;
}
}
if (f == 1){
cout<<"Absent"<<endl;
k = 1;
}
for(int i = 0;i<n;i++){
if(people[n-1-i].gender == 'M'){
cout<<people[n-1-i].name<<' '<<people[n-1-i].class1<<endl;
mi = n-1-i;
m = 0;
break;
}
}
if (m == 1){
cout<<"Absent"<<endl;
k = 1;
}
if(k == 1) cout<<"NA";
else cout<<abs(people[fi].score-people[mi].score);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
char name[20],class1[20];
int score;
}man;
bool cmp(man a,man b)
{
if(a.score>b.score)
{
return true;
}
return false;
}
int main(){
int n;
cin>>n;
man tmp,m,f;
char gender;
m.score = 101;
f.score = -1;
for (int i = 0;i<n;i++){
scanf("%s %c %s %d" ,tmp.name,&gender,tmp.class1,&tmp.score);
if(gender == 'F' && tmp.score>f.score) f = tmp;
else if(gender == 'M' && tmp.score<m.score) m = tmp;
}
if (f.score == -1) cout<<"Absent";
else cout<<f.name<<' '<<f.class1;
cout<<endl;
if (m.score == 101) cout<<"Absent";
else cout<<m.name<<' '<<m.class1;
cout<<endl;
if (m.score == 101 || f.score == -1)cout<<"NA";
else cout<<abs(f.score-m.score);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
bool cmpmax(int a,int b){return a>b;}
int main(){
int n,m;
cin>>n;
vector<int>a;a.resize(n);
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
cin>>m;
vector<int>b;b.resize(m);
for(int i = 0;i<m;i++){scanf("%d",&b[i]);}
sort(a.begin(),a.end(),cmpmax);
sort(b.begin(),b.end(),cmpmax);
int length = 0,amount = 0;
if (m<n)length = m;
else length = n;
for(int i = 0;i<length;i++){
if(a[i]>0&&b[i]>0)amount+=a[i]*b[i];
else break;
}
for(int i = 0;i<length;i++){
if(a[n-i-1]<0&&b[m-i-1]<0)amount+=a[n-i-1]*b[m-i-1];
else break;
}
cout<<amount;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
bool cmp(string a,string b){
return a+b<b+a;
}
int main(){
int n;
cin>>n;
vector<string>a;
a.resize(n);
for(int i = 0;i<n;i++){
cin>>a[i];
}
sort(a.begin(),a.end(),cmp);
int judge = 0;
for(int i = 0;i<n;i++){
if (judge == 0){
for(int j= 0;j<a[0].size();j++){
if (a[0][j] == '0' && judge == 0)continue;
else {judge = 1;printf("%c",a[0][j]);}
}
}
else cout<<a[i];
}
if (judge == 0)cout<<0;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
const int maxnum = 26*26*26*10+1;
int convert(char temp[]){
int result = 0;
for(int i = 0;i<3;i++){
result = result * 26 + (int)(temp[i] - 'A');}
result = result * 10 +(int)(temp[3] - '0');
return result;
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
vector<int>students[maxnum];
for(int i = 0;i<k;i++){
int cnum,cstudents;
scanf("%d%d",&cnum,&cstudents);
for(int j = 0;j<cstudents;j++){
char n[100];
scanf("%s",n);
students[convert(n)].push_back(cnum);
}
}
for(int i = 0;i<n;i++){
char temp[20];
scanf("%s",temp);
int id = convert(temp);
printf("%s %d",temp,(int)students[id].size());
sort(students[id].begin(),students[id].end());
for(int j = 0;j<students[id].size();j++){
printf(" %d",students[id][j]);
}
if (i<n-1) printf("\n");
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1010;
char S[maxn];
int dp[maxn][maxn] = {};
int main(){
cin.getline(S,maxn);
int len = (int)strlen(S),ans = 1;
for(int i = 0;i<len;i++){
dp[i][i] = 1;
if (i<len-1 && S[i] == S[i+1]){
dp[i][i+1] = 1;
ans = 2;
}
}
for (int L = 3;L<=len;L++){
for(int i = 0;i+L-1<len;i++){
int j = i+L-1;
if (S[i] == S[j] && dp[i+1][j-1] == 1){
dp[i][j] = 1;
ans = L;
}
}
}
printf("%d",ans);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
int num[100001] = {};
int input[n];
for(int i = 0;i<n;i++){
int a;
scanf("%d",&a);
input[i] = a;
num[a]+=1;
}
int judge = 0;
for(int i = 0;i<n;i++){
if (num[input[i]]==1){cout<<input[i];judge = 1;break;}
}
if (judge == 0)cout<<"None";
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
vector<int>pre,preM,post,postM,origin;
int countn,n;
struct node{
int data;
node* lchild;
node* rchild;
}*root;
void insert(node* &root,int data){
if (root == NULL){
root = new node;
root ->data = data;
root ->lchild = root->rchild = NULL;
return;
}
if (data >= root->data)insert(root->rchild,data);
else insert(root->lchild, data);
}
void preOrder(node* root,vector <int>&vi){
if (root == NULL) return;
vi.push_back(root->data);
preOrder(root->lchild,vi);
preOrder(root->rchild,vi);
}
void preOrderM(node* root,vector <int>&vi){
if (root == NULL) return;
vi.push_back(root->data);
preOrderM(root->rchild,vi);
preOrderM(root->lchild,vi);
}
void postOrder(node* root,vector <int>&vi){
if (root == NULL) return;
postOrder(root->lchild,vi);
postOrder(root->rchild,vi);
vi.push_back(root->data);
}
void postOrderM(node* root,vector <int>&vi){
if (root == NULL) return;
postOrderM(root->rchild,vi);
postOrderM(root->lchild,vi);
vi.push_back(root->data);
}
int main(){
scanf("%d",&n);
origin.resize(n);
node* root = NULL;
for(int i = 0;i<n;i++){
scanf("%d",&origin[i]);
insert(root, origin[i]);
}
preOrder(root,pre);
preOrderM(root,preM);
postOrder(root,post);
postOrderM(root,postM);
if (origin == pre){
printf("YES\n");
for (int i = 0;i<n;i++){
printf("%d",post[i]);
if (i<n-1)printf(" ");
}
printf("\n");
}
else if (origin == preM){
printf("YES\n");
for (int i = 0;i<n;i++){
printf("%d",postM[i]);
if (i<n-1)printf(" ");
}
printf("\n");
}
else printf("NO");
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int>a;a.resize(n);
vector<int>b;b.resize(n+1);
vector<int>result;result.resize(n+1);
vector<int>resultpos;resultpos.resize(n+1);
int temp = 0;
b[0] = 0;
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
temp+=a[i];
b[i+1] = temp;
}
for(int i = 0;i<n;i++){
resultpos[i] = (int)(lower_bound(b.begin()+i, b.end(), (m+b[i])) - b.begin());
result[i] = b[resultpos[i]] - b[i];
if (result[i]<temp && result[i]>=m) temp = result[i];
}
for(int i = 0;i<n;i++){
if (result[i]==temp) printf("%d-%d\n",i+1,resultpos[i]);
}
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n,m,l;
scanf("%d %d",&n,&m);
int hashtable[n+1];
fill(hashtable, hashtable+n+1, -1);
for(int i = 0;i<m;i++){
int temp;
scanf("%d",&temp);
hashtable[temp] = i;
}
scanf("%d",&l);
int a[l],dp[l];
int count = 0;
for(int i = 0;i<l;i++){
int temp;
scanf("%d",&temp);
if (hashtable[temp] > -1)a[count++] = hashtable[temp];
}
int ans = -1;
for(int i = 0;i<count;i++){
dp[i] = 1;
for(int j = 0;j<i;j++){
if (a[j] <= a[i] && dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
}
}
ans = max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n,m,l;
scanf("%d %d",&n,&m);
int a[m+1];
for(int i = 1;i<m+1;i++){
scanf("%d",&a[i]);
}
scanf("%d",&l);
int b[l+1];
for(int i = 1;i<l+1;i++){
scanf("%d",&b[i]);
}
int dp[m+1][l+1];
fill(dp[0]+1, dp[0]+(m+1)*(l+1)+1, 0);
for (int i = 1;i<m+1;i++){
for(int j = 1;j<l+1;j++){
int maxk = max(dp[i-1][j],dp[i][j-1]);
if (a[i] == b[j]){
dp[i][j] = maxk + 1;
}else{
dp[i][j] = maxk;
}
}
}
printf("%d",dp[m][l]);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
const int maxnum = 26*26*26*10+1;
int convert(char temp[]){
int result = 0;
for(int i = 0;i<3;i++){
result = result * 26 + (int)(temp[i] - 'A');}
result = result * 10 +(int)(temp[3] - '0');
return result;
}
void convertchar(int id,char result[]){
result[3] = (char)(id % 10 + '0');
id = id/10;
result[2] = (char)(id % 26 + 'A');
id /= 26;
result[1] = (char)(id % 26 + 'A');
id /= 26;
result[0] = (char)(id + 'A');
}
int main(){
int n,k;
scanf("%d %d",&n,&k);
vector<int>classes[k];
for(int i = 0;i<n;i++){
char temp[20];
int temp2;
scanf("%s %d",temp,&temp2);
int id = convert(temp);
for(int j = 0;j<temp2;j++){
int cid;
scanf("%d",&cid);
classes[cid-1].push_back(id);
}
}
for(int i = 0;i<k;i++){
printf("%d %d\n",i+1,(int)classes[i].size());
sort(classes[i].begin(),classes[i].end());
for(int j = 0;j<classes[i].size();j++){
char temp[20];
convertchar(classes[i][j],temp);
printf("%s\n",temp);
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int hashtable[1005] = {};
int coin[n];
int temp;
for(int i = 0;i<n;i++){
cin>>temp;
coin[i] = temp;
hashtable[temp] += 1;
}
sort(coin,coin+n);
for(int i = 0;i<n;i++){
if ((coin[i])>(m/2)) break;
if (hashtable[m-coin[i]] >= 1){
if (coin[i] == m-coin[i]){
if (hashtable[coin[i]]>=2){
cout<<coin[i]<<' '<<m-coin[i];
return 0;}
else break;
}
cout<<coin[i]<<' '<<m-coin[i];
return 0;
}
}
cout<<"No Solution";
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int coin[n];
int temp;
for(int i = 0;i<n;i++){
cin>>temp;
coin[i] = temp;
}
sort(coin,coin+n);
for(int i = 0;i<n;i++){
int pos = (int)(upper_bound(coin+i+1, coin+n, m-coin[i])-coin-1);
if (coin[pos]+coin[i]==m && i!=pos){
cout<<coin[i]<<' '<<coin[pos]<<endl;
return 0;
}
}
cout<<"No Solution";
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int>coin;
coin.resize(n);
for(int i = 0;i<n;i++){scanf("%d",&coin[i]);}
sort(coin.begin(),coin.end());
int i=0,j=n-1,judge = 0,k=1;
while(i<j){
k = 1;
if((coin[i]+coin[j])==m){cout<<coin[i]<<' '<<coin[j];return 0;}
else if((coin[i]+coin[j])>m){
j-=1;
}
else{
i+=1;
}
}
cout<<"No Solution";
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
string n;
cin>>n;
vector<int>a;a.resize(n.size());a[0] = 0;
for(int i = 0;i<n.size();i++){a[i] = (int)(n[i]-'0');}
int count = 0;
for(int i = 0;i<a.size();i++){
int b4 = a[0];
for(int j = 1;j<i;j++){
b4 = b4 * 10 + a[j];
}
if (a[i]>1){
if (i == 0){count += pow(10, (a.size()-1-i));}
else {count+= pow(10, (a.size()-1-i)) * (b4+1);}
}
else if (a[i] == 1){
int after = 0;
for(int j = i+1;j<a.size();j++){
after = after * 10 + a[j];
}
if (i == 0){count += after+1;}
else {count+= pow(10, (a.size()-1-i)) * (b4)+ after + 1;}
}
}
cout<<count;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n;
cin>>n;
int a = 1, ans = 0;
int left, right, now;
while(n/a!=0){
left = n/(a*10);
now = n/a % 10;
right = n % a;
if (now == 0)ans += left *a;
else if (now == 1)ans += left * a + right + 1;
else ans += (left + 1) *a;
a*= 10;
}
cout<<ans;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int hashtable[128] = {};
string a,b;
getline(cin,a);
getline(cin,b);
for(int i = 0;i<b.size();i++){hashtable[(int)b[i]] = 1;}
for(int i = 0;i<a.size();i++){
if (hashtable[(int)a[i]] == 0)cout<<a[i];
}
return 0;
}
#include <stack>
#include <cstdio>
#include <vector>
using namespace std;
int main(){
int m,n,k;
scanf("%d %d %d",&m,&n,&k);
for (int i = 0;i<k;i++){
bool flag = true;
stack<int>st;
while(!st.empty()){st.pop();}
int temp = 0;
vector<int>a(n);
for(int k = 0;k<n;k++){scanf("%d",&a[k]);}
for(int j = 1;j<n+1;){
st.push(j++);
if (st.size()>m){flag = false;}
while (!st.empty() && st.top() == a[temp] && st.size()<=m){
st.pop();
temp++;
}
}
if ((!st.empty()) || flag == false)printf("NO\n");
else printf("YES\n");
}
}
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct node{
int key = 1000000;
int next,add;
int judge = 0;
};
bool cmp(node a,node b){
if (a.judge == 0 || b.judge == 0)return a.judge>b.judge;
else return a.key<b.key;
}
int main(){
node a[100010];
int n,head;
scanf("%d %d",&n,&head);
int key,add,next;
for(int i = 0;i<n;i++){
scanf("%d %d %d",&add,&key,&next);
a[add].key = key;
a[add].add = add;
a[add].next = next;
}
int p = head,count = 0;
while(p!=-1){
a[p].judge = 1;
p = a[p].next;
count ++;
}
if (count == 0){printf("0 -1");return 0;}
sort(a,a+100010,cmp);
printf("%d %05d\n",count,a[0].add);
for(int i = 0;i<count;i++){
if (i<count-1){
printf("%05d %d %05d\n",a[i].add,a[i].key,a[i+1].add);}
else printf("%05d %d -1\n",a[i].add,a[i].key);
}
return 0;
}
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,s;
struct Node {
int weight;
vector<int>child;
};
vector<Node>tree;
vector<int>temp;
vector<vector<int>>ans;
void DFS(int &root,int &sum){
if (tree[root].child.size() == 0 || sum >= s){
if (sum == s && tree[root].child.size() == 0){
ans.push_back(temp);
}
if(temp.size()>0){
sum -= tree[temp[temp.size()-1]].weight;}
temp.pop_back();
return;
}
for(int i = 0;i<tree[root].child.size();i++){
temp.push_back(tree[root].child[i]);
sum += tree[tree[root].child[i]].weight;
DFS(tree[root].child[i],sum);
}
sum -= tree[root].weight;
temp.pop_back();
}
bool cmp(vector<int>a,vector<int>b){
int i = 0;
while(tree[a[i]].weight == tree[b[i]].weight && i<a.size()-1 && i<b.size()-1){
i++;
}
return tree[a[i]].weight > tree[b[i]].weight;
}
int main(){
scanf("%d %d %d",&n,&m,&s);
tree.resize(n);
for(int i = 0;i<n;i++){scanf("%d",&tree[i].weight);}
for(int i = 0;i<m;i++){
int num,childsize;
scanf("%d %d",&num,&childsize);
tree[num].child.resize(childsize);
for(int j = 0;j<childsize;j++){
scanf("%d",&tree[num].child[j]);
}
}
int sum = tree[0].weight;
int root = 0;
DFS(root, sum);
sort(ans.begin(), ans.end(), cmp);
for(int i = 0;i<ans.size();i++){
printf("%d",tree[0].weight);
for(int j = 0;j<ans[i].size();j++){
printf(" %d",tree[ans[i][j]].weight);
}
printf("\n");
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <map>
#include <string>
using namespace std;
int main(){
int m,n;
scanf("%d%d",&m,&n);
vector<int>screen(n*m);
map<int,int>count;
for(int i = 0;i<n*m;i++){
scanf("%d",&screen[i]);
count[screen[i]] = 0;
}
for(int i = 0;i<n*m;i++){
count[screen[i]] += 1;
}
int max = 0,maxpos = 0;
for(int i = 0;i<n*m;i++){
if (count[screen[i]] > max){
max = count[screen[i]];
maxpos = screen[i];
}
}
printf("%d",maxpos);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
string name;
int age,money;
} bill;
bool cmp(bill a,bill b){
if (a.money!=b.money){return a.money>b.money;}
else if (a.age!=b.age){return a.age<b.age;}
return a.name<b.name;
}
int main(){
int n,k;
cin>>n>>k;
vector <bill>people;
people.resize(n);
int query[k][3];
for(int i = 0;i<n;i++){
people[i].name.resize(20);
scanf("%s %d %d",&people[i].name[0],&people[i].age,&people[i].money);
}
for(int i = 0;i<k;i++){
scanf("%d%d%d",&query[i][0],&query[i][1],&query[i][2]);
}
sort(people.begin(),people.end(),cmp);
int valid[1000] = {};
vector<bill>peoples;
for(int i = 0;i<n;i++){
if (valid[people[i].age]<100) {
peoples.push_back(people[i]);
valid[people[i].age] += 1;}
}
for(int i = 0;i<k;i++){
printf("Case #%d:\n",i+1);
int judge = 0;
for(int j = 0;j<peoples.size();j++){
if (peoples[j].age<=query[i][2] && peoples[j].age>=query[i][1] && judge < query[i][0]){
printf("%s %d %d\n",peoples[j].name.c_str(),peoples[j].age,peoples[j].money);
judge++;
}
if (judge == query[i][0])break;
}
if (judge == 0){
printf("None");
}
}
return 0;
}
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct man{
int num = 0,rank;
bool win = true;
};
int main(){
int np,ng;
scanf("%d %d",&np,&ng);
vector<man>a(np);
vector<int>turn(np);
vector<int>rturn(np);
for(int i = 0;i<np;i++){scanf("%d",&a[i].num);}
for(int i = 0;i<np;i++){
scanf("%d",&turn[i]);
rturn[turn[i]] = i;
}
vector<man>b(np);
for(int i = 0;i<np;i+=1){b[i] = a[turn[i]];}
vector<man>temp(3);
int pos[3];
int sgn = 1;
int asd = 10;
while (sgn !=0 && asd-- >0){
int count = 0,countall = 0;
for(int i = 0;i<np;i++){
if (b[i].win == true){
temp[count] = b[i];
pos[count] = i;
count++;countall++;
}
if (count == 3 || i == np-1 ){
count = 0;
if (temp[0].num == max(temp[0].num,max(temp[1].num,temp[2].num))){
b[pos[1]].win = 0;b[pos[2]].win = 0;
}
else if (temp[1].num == max(temp[0].num,max(temp[1].num,temp[2].num))){
b[pos[0]].win = 0;b[pos[2]].win = 0;
}
else {b[pos[0]].win = 0;b[pos[1]].win = 0;}
temp.clear();
temp[0].num = 0;
temp[1].num = 0;
temp[2].num = 0;
}
}
for(int i = 0;i<np;i++){
if(b[i].win == 0 && b[i].rank == 0){
b[i].rank = (countall+2)/3+1;
}
else if (b[i].win == 1 && b[i].rank == 0 && countall == 1){
sgn = 0;
b[i].rank = 1;
break;
}
}
}
for(int i = 0;i<np;i++){
printf("%d",b[rturn[i]].rank);
if (i<np-1){printf(" ");}
}
cout<<endl;
return 0;
}
A1057
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int>stack;
int process(char c[]){
int ans = 0,len = (int)strlen(c);
for(int i = 5;i<len;i++){
ans = ans * 10 + c[i]-'0';
}
return ans;
}
int getmedian(int p){
vector<int>a = stack;
sort(a.begin(),a.end());
return a[p/2];
}
int main(){
int n;
scanf("%d%*c",&n);
while (n-- >= 0){
int p = (int)stack.size()-1;
char c[20];
cin.getline(c,20);
if (c[1] == 'o'){
if (p == -1)printf("Invalid\n");
else {
printf("%d\n",stack[p]);
stack.erase(stack.begin()+p);
}
}
else if (c[1] == 'u'){
int t;
t = process(c);
stack.push_back(t);
}
else if (c[1] == 'e'){
if (p == -1)printf("Invalid\n");
else {
printf("%d\n",getmedian(p));
}
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
long long g1,s1,k1,g2,s2,k2,g3,s3,k3;
scanf("%lld.%lld.%lld %lld.%lld.%lld",&g1,&s1,&k1,&g2,&s2,&k2);
long long sum1,sum2,diff;
sum1 = g1 * 17 * 29 + s1 * 29 + k1;
sum2 = g2 * 17 * 29 + s2 * 29 + k2;
diff = sum1+sum2;
g3 = diff/(17*29);
s3 = (diff-g3*17*29)/29;
k3 = diff - g3 * 17 * 29 - s3 * 29;
printf("%lld.%lld.%lld",g3,s3,k3);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxsize = 10000;
vector<bool>hashtable(maxsize,true);
vector<LL>prime;
void getPrime(LL n,vector<LL>&prime){
hashtable[0] = false;
hashtable[1] = false;
for(int i = 2;i<n;i++){
if (hashtable[i] == true){
for (int j = 2;j<n/i+1 && j<maxsize/i+1;j+=1){
hashtable[j*i] = false;}
}
}
for(int i = 0;i<n;i++){
if (hashtable[i] == true)prime.push_back(i);
}
}
int main(){
LL n;
scanf("%lld",&n);
if (n>1){
getPrime((LL)sqrt(1.0 * n),prime);
vector<int>countprime(prime.size(),0);
int judge = 0;
LL m=n;
for(int i = 0;i<prime.size();i++){
if (n % prime[i] == 0){
n /= prime[i];
countprime[i]++;
judge = i;
i --;
}
}
if (n!= 1){prime.push_back(n);countprime.push_back(1);}
printf("%lld=",m);
for(int i = 0;i<prime.size();i++){
if (countprime[i] == 1){
printf("%lld",prime[i]);
}
else if (countprime[i] > 1){
printf("%lld^%d",prime[i],countprime[i]);
}
if (countprime[i] > 0 && i!= judge)printf("*");
}
}
else{printf("1=1");}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
string convert(string a,int k,int &length){
int temp = 0,judge1 = 0;
for(int i = 0;i<a.size();i++){
if (a[i]!='0'){temp = i;judge1 = 1;break;}
}
a = a.substr(temp,a.size()-temp);
int dotpos;
if (a.find(".") != string::npos) {
dotpos = (int)a.find(".");
if (dotpos == 0){
int judge0 = 0;
for (int i = 1; i<a.size(); i++) {
if (a[i]!='0'){length = 1-i;judge0 = 1;break;}
}
if (judge0 == 0)length = 0;
}
else{
length = dotpos;
}
}
else {length = (int)a.size();}
if (judge1 == 0){length = 0;}
string result;
dotpos = (int)a.find(".");
if (dotpos != string::npos) a.erase(a.begin()+dotpos);
int start = 0;
while(a[start]=='0'){start++;}
result = a.substr(start,k);
while (result.length()<k) {result = result + "0";}
return result;
}
int main(){
int n,alength,blength;
string a,b;
scanf("%d",&n);
cin>>a>>b;
string resa = convert(a, n, alength);
string resb = convert(b, n, blength);
if (resa == resb && alength == blength)
cout<<"YES 0."<<resa<<"*10^"<<alength;
else{
cout<<"NO 0."<<resa<<"*10^"<<alength;
cout<<" 0."<<resb<<"*10^"<<blength;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
double similarity(set<int>a,set<int>b){
int same = 0;
for(set<int>::iterator it = a.begin();it!=a.end();it++){
if (b.find(*it)!=b.end())same++;
}
int diff = (int)(a.size()+b.size()) - same;
return (double)(same*1.0/diff);
}
int main(){
int n;
scanf("%d",&n);
set<int> st[n];
for(int i = 0;i<n;i++){
int temp,temp1;
scanf("%d",&temp);
for(int j = 0;j<temp;j++){
scanf("%d",&temp1);
st[i].insert(temp1);
}
}
scanf("%d",&n);
for(int i = 0;i<n;i++){
int temp,temp1;
double simi;
scanf("%d %d",&temp,&temp1);
simi = similarity(st[temp-1], st[temp1-1]);
printf("%.01lf%%\n",simi*100);
}
return 0;
}
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,countn = 0;
vector<int>tree;
vector<int>v;
void inorder(int root){
if (root>n)return;
inorder(2 * root);
tree[root] = v[countn++];
inorder(2 * root + 1);
}
int main(){
scanf("%d",&n);
v.resize(n);tree.resize(n+1);
for (int i = 0;i<n;i++){
scanf("%d",&v[i]);
}
sort(v.begin(), v.end());
inorder(1);
for(int i = 1;i<n+1;i++){
printf("%d",tree[i]);
if (i<n)printf(" ");
}
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
struct node{
int data,height;
node *lchild, *rchild;
}*root;
node* newNode(int v){
node *Node = new node;
Node->data = v;
Node->height = 1;
Node->lchild = Node->rchild = NULL;
return Node;
}
int getHeight(node* root){
if (root == NULL)return 0;
return root-> height;
}
int getBalanceFactor(node* root){
return getHeight(root->lchild) - getHeight(root->rchild);
}
void updateHeight(node* root){
root->height = max(getHeight(root->lchild),getHeight(root->rchild)) + 1;
}
void L(node* &root){
node* temp = root->rchild;
root->rchild = temp->lchild;
temp->lchild = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void R(node* &root){
node* temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void insert(node* &root,int v){
if (root == NULL){
root = newNode(v);
return;
}
if (v < root->data){
insert(root->lchild,v);
updateHeight(root);
if (getBalanceFactor(root) == 2){
if (getBalanceFactor(root->lchild) == 1){
R(root);
}
else if (getBalanceFactor(root->lchild) == -1){
L(root->lchild);
R(root);
}
}
}
else{
insert(root->rchild,v);
updateHeight(root);
if (getBalanceFactor(root) == -2){
if (getBalanceFactor(root->rchild) == -1){
L(root);
}
else if (getBalanceFactor(root->rchild) == 1){
R(root->rchild);
L(root);
}
}
}
}
node* create(int data[],int n){
node* root = NULL;
for(int i = 0;i<n;i++){
insert(root,data[i]);
}
return root;
}
int main(){
int n,tree[20];
scanf("%d",&n);
for(int i = 0;i<n;i++){scanf("%d",&tree[i]);}
node* root = create(tree, n);
printf("%d",root->data);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
int main(){
int n,count=0,judge = 0;
cin>>n;
vector<int>a;
vector<int>position;
a.resize(n);
position.resize(n);
for(int i = 0;i<n;i++){scanf("%d",&a[i]);position[a[i]] = i;}
for(int i = 0;i<n;i++){
if (a[0] == 0){
judge = 0;
for(int j =1;j<n;j++){
if (a[j]!=j){
swap(a[0], a[j]);
position[0] = j;
position[a[0]] = 0;
count+=1;
judge = 1;break;}
}
if (judge == 0)break;
}
swap(a[position[position[0]]],a[position[0]]);
swap(position[position[0]],position[0]);
count++;
}
cout<<count;
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
const int maxv = 110;
int w[maxn], dp[maxn] = {};
bool choice[maxn][maxv];
bool cmp(int a,int b){return a>b;}
int main(){
int n,m;
scanf("%d %d",&n,&m);
int a[n];
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(w+1,w+n+1,cmp);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <map>
#include <string>
using namespace std;
bool cmp(const pair<string,int>& a,const pair<string,int>& b){
if (a.second != b.second)return a.second > b.second;
else return a.first<b.first;
}
int main(){
string str;
getline(cin,str);
map<string,int>count;
int start = 0,end = (int)str.size()-1,judge = 0;
for(int i = 0;i<str.size();i++){
if ((str[i]>='0'&&str[i]<='9') || (str[i]>='a'&&str[i]<='z') || (str[i]>='A'&&str[i]<='Z')){
if (judge == 0){start = i;judge = 1;}
}
else{
end = i;
string temp = str.substr(start,end-start);
transform(temp.begin(), temp.end(), temp.begin(), ::tolower);
count[temp] = 0;
judge = 0;
}
}
if (judge == 1){
end = (int)str.size();
string temp = str.substr(start,end-start);
transform(temp.begin(), temp.end(), temp.begin(), ::tolower);
count[temp] = 0;
}
for(int i = 0;i<str.size();i++){
if ((str[i]>='0'&&str[i]<='9') || (str[i]>='a'&&str[i]<='z') || (str[i]>='A'&&str[i]<='Z')){
if (judge == 0){start = i;judge = 1;}
}
else{
end = i;
string temp = str.substr(start,end-start);
transform(temp.begin(), temp.end(), temp.begin(), ::tolower);
count[temp] ++;
judge = 0;
}
}
if (judge == 1){
end = (int)str.size();
string temp = str.substr(start,end-start);
transform(temp.begin(), temp.end(), temp.begin(), ::tolower);
count[temp] ++;
}
int max = 0;
string maxstr;
vector<pair<string,int>> count2(count.begin(), count.end());
sort(count2.begin(),count2.end(),cmp);
max = count2.begin()->second;
maxstr = count2.begin()->first;
cout<<maxstr;
printf(" %d",max);
return 0;
}
#include <cstdio>
#include <vector>
#include <math.h>
#include <cstring>
using namespace std;
const int maxn = 1021;
const int INF = 0x3fffffff;
struct edge {
int v,length;
edge(int _a,int _b):v(_a),length(_b){};
};
vector<edge>adj[maxn];
int n,m,k,ds,dis[maxn];
bool vis[maxn];
void DFS(int start,int total){
fill(dis, dis+maxn, INF);
fill(vis, vis+maxn, 0);
dis[start] = 0;
for(int ii = 0;ii<total;ii++){
int k = -1,MIN = INF;
for(int i = 1;i<=total;i++){
if (dis[i]<MIN && vis[i] == false){
MIN = dis[i];
k = i;
}
}
if (k == -1)return;
vis[k] = true;
for(int i = 0;i<adj[k].size();i++){
int v = adj[k][i].v;
if (vis[v] == false && dis[v] > dis[k] + adj[k][i].length){
dis[v] = dis[k] + adj[k][i].length;
}
}
}
}
bool ok(int i,int total){
DFS(i, total);
for(int j = 1;j<=n;j++){
if (dis[j] > ds)return false;
}
return true;
}
void process(char a[],char b[],int length){
int aa = 0,bb = 0;
if (a[0] == 'G'){
if (a[1] == '1' && a[2] == '0')aa = 10+n;
else {aa = a[1]-'0'+n;}
}
else{
int len = (int)strlen(a);
for (int i = 0;i<len;i++){
aa = aa * 10 + a[i]-'0';
}
}
if (b[0] == 'G'){
if (b[1] == '1' && b[2] == '0')bb = 10+n;
else {bb = b[1]-'0'+n;}
}
else{
int len = (int)strlen(b);
for (int i = 0;i<len;i++){
bb = bb * 10 + b[i]-'0';
}
}
adj[aa].push_back(edge(bb,length));
adj[bb].push_back(edge(aa,length));
}
int main(){
scanf("%d %d %d %d",&n,&m,&k,&ds);
int total = m + n;
for(int i = 0;i<k;i++){
char a[5],b[5];
int length;
scanf("%s %s %d",a,b,&length);
process(a,b,length);
}
double maxavd = 0,maxd = 0;
int k = 0,judge = 0;
for (int i = n+1;i<=total;i++){
if (ok(i,total)){
judge = 1;
double min = INF,avd = 0;
for(int j = 1;j<=n;j++){
avd += dis[j];
if (dis[j] < min)min = dis[j];
}
avd = avd/n;
if (min > maxd || (min == maxd && maxavd > avd)){
maxavd = avd;
maxd = min;
k = i-n;
}
}
}
if (judge == 0)printf("No Solution");
else printf("G%d\n%.01lf %.01lf",k,(double)round(maxd*10)/10,(double)round(maxavd*10)/10);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;
typedef struct{
int p[6] = {-2,-2,-2,-2,-2,-2};
int dp[6] = {0,0,0,0,0,0};
int score = 0,rank,id,pnum;
} stu;
bool cmp(stu a,stu b){
if (a.score!=b.score) return a.score>b.score;
else if(a.pnum!=b.pnum) return a.pnum>b.pnum;
else return a.id<b.id;
}
int main(){
int n,k,m;
cin>>n>>k>>m;
int pro[k+1];
int sub[m][3];
vector<stu>student;
student.resize(n+1);
for(int i = 0;i<k;i++){cin>>pro[i];}
for(int i = 0;i<m;i++){scanf("%d %d %d",&sub[i][0],&sub[i][1],&sub[i][2]);}
for(int i = 0;i<m;i++){
if (student[sub[i][0]].p[sub[i][1]] < sub[i][2]){
student[sub[i][0]].p[sub[i][1]] = sub[i][2];
}
student[sub[i][0]].dp[sub[i][1]] = 1;
}
for(int i = 0;i<n+1;i++){
for(int j = 0;j<6;j++){
if (student[i].p[j]>-1){
student[i].score = student[i].p[j]+student[i].score;}
}
student[i].id = i;
int pn = 0;
for(int j = 1;j<k+1;j++){if(student[i].p[j] == pro[j-1]) pn++;}
student[i].pnum = pn;
}
sort(student.begin(),student.end(),cmp);
for(int i = 0;i<n+1;i++){
if (i == 0){student[i].rank = 0;}
else if (student[i].score != student[i-1].score){student[i].rank = i;}
else student[i].rank = student[i-1].rank;
int judgeall = 0,judgeall2 = 0;
for(int j = 1;j<k+1;j++){
if (student[i].p[j] == -1) judgeall = 1;
if (student[i].p[j] != -2) judgeall2 = 1;
}
if (student[i].score>0){
cout<<student[i].rank+1<<' '<<setw(5)<<setfill('0')<<student[i].id<<' '<<student[i].score<<' ';
for(int j = 1;j<k+1;j++){
if (student[i].dp[j] > 0 && student[i].p[j]>0) cout<<student[i].p[j];
else if (student[i].dp[j] > 0)cout<<0;
else cout<<'-';
if (j<k)cout<<' ';
else cout<<endl;
}
}
else if (judgeall == 0 && judgeall2 == 1){
cout<<student[i].rank+1<<' '<<setw(5)<<setfill('0')<<student[i].id<<' '<<student[i].score<<' ';
for(int j = 1;j<k+1;j++){
if (student[i].dp[j] > 0)cout<<0;
else cout<<'-';
if (j<k)cout<<' ';
else cout<<endl;
}
}
}
return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1010;
struct node{
int v,layer = 0;
node(int _v,int _layer):v(_v),layer(_layer){};
};
vector<node>g[maxn];
bool visit[maxn] = {false};
int n,l;
void init(){
for(int i = 0;i<n+1;i++){
visit[i] = false;
}
}
bool in(int frien,int host){
for(int i = 0;i<g[host].size();i++){
if (g[host][i].v == frien)return true;
}
return false;
}
int BFS(int start){
int count = -1;
node s = node(start, 0);
queue<node>q;
q.push(s);visit[start] = true;
while(!q.empty()){
node front = q.front();
int layer = front.layer+1;
if (layer > l+1)break;
q.pop();count++;
int v = front.v;
for(int i = 0;i<g[v].size();i++){
if (visit[g[v][i].v] == false){
q.push(node(g[v][i].v,layer));
visit[g[v][i].v] = true;
}
}
}
return count;
}
int main(){
scanf("%d%d",&n,&l);
for(int i = 1;i<n+1;i++){\
int isize;
scanf("%d",&isize);
for(int j = 0;j<isize;j++){
int temp;
scanf("%d",&temp);
if (!in(i,temp)){
g[temp].push_back(node(i,0));
}
}
}
int k;
scanf("%d",&k);
int query[k];
for(int i = 0;i<k;i++){scanf("%d",&query[i]);}
for(int i = 0;i<k;i++){
printf("%d\n",BFS(query[i]));
init();
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int main(){
int n;
cin>>n;
vector<string> input;
for(int i = 0;i<n+1;i++){
string temp;
getline(cin,temp);
input.push_back(temp);
}
int issuffix = 1,count = 0;
while(issuffix == 1){
for(int i = 1;i<n;i++){
if (input[i][input[i].size()-count-1] != input[i+1][input[i+1].size()-count-1]){
issuffix = 0;
break;
}
}
if (issuffix == 1) count++;
}
if(count==0)cout<<"nai";
else{
for(int i = 0;i<count;i++){
cout<<input[1][input[1].size()-count+i];
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
bool isPrime(int n){
if (n <= 1)return false;
for(int i = 2;i<(int)sqrt(1.0*n)+1;i++){
if (n % i == 0)return false;
}
return true;
}
int getPrime(int n){
if (isPrime(n))return n;
int i = 1;
while (isPrime(n+i) == false) {
i+=1;
}
return n+i;
}
int main(){
int n,size;
cin>>n>>size;
size = getPrime(size);
vector<bool>hash(size,false);
int temp;
for(int i = 0;i<n;i++){
scanf("%d",&temp);
if (hash[temp%size] == false){
hash[temp%size] = true;
printf("%d",temp%size);
}
else{
int j;
for(j = 1;j<size;j++){
if (hash[(temp+j*j)%size]==false){
hash[(temp+j*j)%size] = true;
printf("%d",(temp+j*j)%size);
break;
}
}
if (j >= size)printf("-");
}
if (i<n-1) printf(" ");
}
return 0;
}
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
struct Node{
int amount = 0;
double price;
vector<int>child;
};
vector<Node>tree;
void inorder(int root,double price,double rate){
queue<int>q;
q.push(root);
tree[root].price = price;
while(!q.empty()){
int front = q.front();
q.pop();
for(int i = 0;i<tree[front].child.size();i++){
q.push(tree[front].child[i]);
tree[tree[front].child[i]].price = tree[front].price * (1.0 + rate/100);
}
}
}
int main(){
int n;
double price,rate;
scanf("%d %lf %lf",&n,&price,&rate);
tree.resize(n);
for(int i = 0;i<n;i++){
int childsize;
scanf("%d",&childsize);
if (childsize > 0){
tree[i].child.resize(childsize);
for(int j = 0;j<childsize;j++){
scanf("%d",&tree[i].child[j]);
}
}
else{
scanf("%d",&tree[i].amount);
}
}
inorder(0, price, rate);
double sum = 0;
for(int i = 0;i<n;i++){
if (tree[i].amount>0)
sum += tree[i].amount * tree[i].price;
}
printf("%.01lf",sum);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
typedef struct{
int ge,gi,admited = 0,id,rank,school;
vector<int>app;
} stu;
bool cmp(stu a,stu b){
if ((a.ge+a.gi)!=(b.ge+b.gi)) return (a.ge+a.gi)>(b.ge+b.gi);
else return a.ge>b.ge;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
int school[m];
stu student[n];
for(int i = 0;i<m;i++){cin>>school[i];}
for(int i = 0;i<n;i++){
student[i].app.resize(k);
student[i].id = i;
cin>>student[i].ge>>student[i].gi;
for(int j = 0;j<k;j++){cin>>student[i].app[j];}
}
vector<vector<int>>admit;
admit.resize(m);
sort(student,student+n,cmp);
for(int i = 0;i<n;i++){
if(i == 0)student[i].rank = 0;
else if ((student[i].gi + student[i].ge) <(student[i-1].gi + student[i-1].ge))student[i].rank = i;
else if (student[i].ge<student[i-1].ge)student[i].rank = i;
else student[i].rank = student[i-1].rank;
}
for (int j = 0;j<n;j++){
for (int i = 0;i<k;i++){
if (school[student[j].app[i]]>0 && student[j].admited == 0){
school[student[j].app[i]] -=1;
admit[student[j].app[i]].push_back(student[j].id);
student[j].admited = 1;
student[j].school = student[j].app[i];
}
if (student[j-1].rank == student[j].rank && student[j].admited == 0 && student[j-1].admited == 1){
admit[student[j-1].school].push_back(student[j].id);
student[j].admited = 1;
student[j].school = student[j-1].school;
}
}
}
for(int i = 0;i<m;i++){
sort(admit[i].begin(),admit[i].end());
for(int j = 0;j<admit[i].size();j++){
cout<<admit[i][j];
if (j<admit[i].size()-1)cout<<' ';
}
cout<<endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
typedef struct{
long up,down;
} fractionnum;
long maxfactor(long a,long b){
a = abs(a);
if (b!= 0) return maxfactor(b, a%b);
else return a;
}
fractionnum plus1(fractionnum a,fractionnum b){
if (a.up == 0)return b;
if (b.up == 0)return a;
fractionnum temp;
temp.down = a.down * b.down;
temp.up = a.up * b.down + a.down * b.up;
if (temp.up == 0) temp.down = 1;
long max = maxfactor(temp.up, temp.down);
if (max > 1) {
temp.up = temp.up / max;temp.down = temp.down/max;}
return temp;
}
void printpartition(fractionnum a){
if (abs(maxfactor(a.down, a.up)) == a.down){
printf("%ld",a.up/a.down);
}
else{
if (abs(a.up)>a.down){
printf("%ld %ld/%ld",a.up/a.down,a.up%a.down,a.down);}
else {printf("%ld/%ld",a.up,a.down);}
}
}
int main(){
int n;
cin>>n;
vector<fractionnum>a(n);
fractionnum result;
result.up = 0;result.down = 1;
for(int i = 0;i<n;i++){
scanf("%ld/%ld",&a[i].up,&a[i].down);
result = plus1(result,a[i]);
}
printpartition(result);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
int main(){
string num;
cin>>num;
int sgn = 0,zero = 0,zeropos = 0,wansgn = 0;
if(num[0] == '-'){
cout<<"Fu ";
sgn = 1;
}
for(int i = 0+sgn;i<num.size();i++){
if (num.size()-i == 5 && num[i] == '0' && num.size()<9)
{
int k = 0;
for(int j = i+1;j<num.size();j++){
if(num[j] !='0') k=1;
}
if(k == 0){cout<<" Wan";return 0;}
}
if (num[i]!='0'){
if (zero == 1){
if(zeropos == 4){
cout<<"Wan ";
}
if(zeropos != 6){
cout<<"ling ";zero = 0;
}
}
switch(num[i]-'0'){
case 1:{cout<<"yi";break;}
case 2:{cout<<"er";break;}
case 3:{cout<<"san";break;}
case 4:{cout<<"si";break;}
case 5:{cout<<"wu";break;}
case 6:{cout<<"liu";break;}
case 7:{cout<<"qi";break;}
case 8:{cout<<"ba";break;}
case 9:{cout<<"jiu";break;}
}
if(i < num.size()-1)cout<<' ';
switch(num.size()-i-1){
case 0:break;
case 1:{cout<<"Shi";break;}
case 2:{cout<<"Bai";break;}
case 3:{cout<<"Qian";break;}
case 4:{cout<<"Wan";break;}
case 5:{cout<<"Shi";break;}
case 6:{cout<<"Bai";break;}
case 7:{cout<<"Qian";break;}
case 8:{cout<<"Yi";break;}
}
int k = 0;
for(int j = i+1;j<num.size();j++){
if(num[j]!='0') k=1;
}
if(i < num.size()-1 && k == 1)cout<<' ';
}
else{
if (zero == 0) zeropos = num.size()-i-1;
zero = 1;
if (num.size()-i-1 == 4 && (num.size()<9)){
cout<<"Wan ";
}
if (num.size() == 1) cout<<"ling";
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
typedef struct{
int score;
char name[20],id[20];
} stu;
bool cmp(stu a,stu b){
return a.score>b.score;
}
int main(){
int n,a,b,judge = 0;
cin>>n;
stu student[n];
for(int i = 0;i<n;i++){scanf("%s %s %d",student[i].name,student[i].id,&student[i].score);}
cin>>a>>b;
sort(student,student+n,cmp);
for (int i = 0;i<n;i++){
if(student[i].score >=a && student[i].score <=b){
cout<<student[i].name<<' '<<student[i].id<<endl;
judge = 1;}
}
if (judge == 0){cout<<"NONE";}
return 0;
}
#include <cstdio>
#include <stdio.h>
#include <stack>
#include <vector>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
stack<int>st;
vector<int>pre,in;
struct Node{
int data;
Node* lchild;
Node* rchild;
}*root;
int op(string a){
if (a[1] == 'o'){
int temp = st.top();
st.pop();
in.push_back(temp);
return temp;
}
else{
int temp = 0;
char tempstr[a.size()+1];
for (int i = 0;i<a.size();i++){
tempstr[i] = a[i];
}
sscanf(tempstr,"Push %d",&temp);
st.push(temp);
pre.push_back(temp);
return temp;
}
}
Node* create(int preL,int preR,int inL,int inR){
if (preL > preR)return NULL;
Node* no = new Node;
no->data = pre[preL];
int k,leftnum;
for(k = inL;k<=inR;k++){
if (pre[preL] == in[k]){
leftnum = k - inL;break;
}
}
no->lchild = create(preL+1, preL+leftnum, inL, k-1);
no->rchild = create(preL+leftnum+1, preR, k+1, inR);
return no;
}
void postorder(Node* &root,int realroot){
if (root == NULL)return;
if (root->lchild != NULL)postorder(root->lchild,realroot);
if (root->rchild != NULL)postorder(root->rchild,realroot);
printf("%d",root->data);
if (root->data != realroot)printf(" ");
}
int main(){
int n,temp = 0,realroot = 0;
string a;
scanf("%d%*c",&n);
pre.clear();
in.clear();
while(temp!=n){
getline(cin,a);
temp = op(a);
if (st.empty())realroot = temp;
}
while(!st.empty()){
in.push_back(st.top());
st.pop();
}
root = create(0,n-1,0,n-1);
postorder(root, realroot);
return 0;
}
#include <cstdio>
#include <stdio.h>
#include <stack>
#include <vector>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
struct node{
int data,layer,lchild = -1,rchild = -1;
}tree[31];
stack<int>st;
int op(string a,string b,int tempb4){
if (a[1] == 'o'){
int temp = st.top();
st.pop();
if (b[1] == 'o'){
tree[temp].lchild = tempb4;
}
else{
tree[temp].lchild = -1;
tree[temp].rchild = -1;
}
return temp;
}
else{
int temp = 0;
char tempstr[a.size()+1];
for (int i = 0;i<a.size();i++){
tempstr[i] = a[i];
}
sscanf(tempstr,"Push %d",&temp);
st.push(temp);
if (b[1] == 'o'){
tree[tempb4].rchild = temp;
}
else{
tree[tempb4].lchild = temp;
}
return temp;
}
}
void postorder(int &root,int realroot){
if (root == -1) return;
if (tree[root].lchild != -1)postorder(tree[root].lchild,realroot);
if (tree[root].rchild != -1)postorder(tree[root].rchild,realroot);
printf("%d",tree[root].data);
if (tree[root].data != realroot)printf(" ");
}
int main(){
int n,temp = 0,realroot = 0;
string a,b;
scanf("%d%*c",&n);
for(int i = 0;i< n*2;i++){
b = a;
getline(cin,a);
temp = op(a,b,temp);
tree[temp].data = temp;
if (st.empty())realroot = temp;
}
for(int i = 1;i<n+1;i++){
printf("%d %d %d %d %d\n",i,tree[i].data,tree[i].layer,tree[i].lchild,tree[i].rchild);
}
int root = 1;
return 0;
}
#include <cstdio>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 210;
const int INF = 0x3fffffff;
int n,k;
map<string,int>citynum;
map<int,string>citynum2;
int Graph[maxn][maxn],happness[maxn],dis[maxn];
vector<int>pre[maxn],best,tempbest;
bool vis[maxn];
void Dj(int start){
fill(vis, vis+maxn, false);
fill(dis, dis+maxn, INF);
dis[start] = 0;
for(int ii = 0;ii<n;ii++){
int k = -1,MIN = INF;
for(int i = 0;i<n;i++){
if (vis[i] == false && dis[i] < MIN){
k = i;
MIN = dis[i];
}
}
if (k == -1)return;
vis[k] = true;
for(int i = 0;i<n;i++){
if (vis[i] == false && Graph[k][i] < INF){
if (dis[i] > dis[k] + Graph[k][i]){
dis[i] = dis[k] + Graph[k][i];
pre[i].clear();
pre[i].push_back(k);
}else if (dis[i] == dis[k] + Graph[k][i]){
pre[i].push_back(k);
}
}
}
}
}
void getcost(int &cost,int &hap,int &avhap){
cost = hap = avhap = 0;
reverse(tempbest.begin(), tempbest.end());
for(int i = 1;i<(int)tempbest.size();i++){
cost += Graph[tempbest[i]][tempbest[i-1]];
hap += happness[tempbest[i]];
}
avhap = hap/((int)tempbest.size()-1);
reverse(tempbest.begin(), tempbest.end());
}
int mincost = INF,maxhappness = 0,maxavhap = 0,leastnum = 0;
void DFS(int start){
if (start == 0){
tempbest.push_back(start);
int cost,hap,avhap;
getcost(cost,hap,avhap);
if (cost<mincost){
mincost = cost;
maxhappness = hap;
maxavhap = avhap;
best = tempbest;
leastnum = 1;
}
else if (cost == mincost && hap > maxhappness){
maxhappness = hap;
maxavhap = avhap;
best = tempbest;
leastnum +=1;
}
else if (cost == mincost && hap == maxhappness && avhap > maxavhap){
maxavhap = avhap;
best = tempbest;
leastnum +=1;
}
else if (cost == mincost){
leastnum +=1;
}
tempbest.pop_back();
return;
}
tempbest.push_back(start);
for(int i = 0;i<pre[start].size();i++){
DFS(pre[start][i]);
}
tempbest.pop_back();
}
int main(){
fill(Graph[0], Graph[0] + (maxn * maxn), INF);
scanf("%d %d",&n,&k);
string temp;
char temp1[5];
scanf("%s\n",temp1);
temp = temp1;
citynum[temp] = 0;
citynum2[0] = temp;
for (int i = 0;i<n-1;i++){
int a;
scanf("%s %d",temp1,&a);
temp = temp1;
citynum[temp] = i+1;
citynum2[i+1] = temp;
happness[i+1] = a;
}
for (int i = 0;i<k;i++){
int a;
char temp1[5],temp2[5];
string from,to;
scanf("%s %s %d",temp1,temp2,&a);
from = temp1;
to = temp2;
Graph[citynum[from]][citynum[to]] = a;
Graph[citynum[to]][citynum[from]] = a;
}
Dj(0);
DFS(citynum["ROM"]);
printf("%d %d %d %d\n",leastnum,mincost,maxhappness,maxavhap);
reverse(best.begin(), best.end());
for(int i = 0;i<best.size();i++){
cout<<citynum2[best[i]];
if (i<best.size()-1)printf("->");
}
return 0;
}
#include <queue>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
struct Node{
int amount = 0;
double price;
vector<int>child;
};
vector<Node>tree;
double inorder(int root,double price,double rate){
double max = 0;
queue<int>q;
q.push(root);
tree[root].price = price;
while(!q.empty()){
int front = q.front();
if (tree[front].price>max)max = tree[front].price;
q.pop();
for(int i = 0;i<tree[front].child.size();i++){
q.push(tree[front].child[i]);
tree[tree[front].child[i]].price = tree[front].price * (1.0 + rate/100);
}
}
return max;
}
int main(){
int n,root;
double price,rate;
scanf("%d %lf %lf",&n,&price,&rate);
tree.resize(n);
for(int i = 0;i<n;i++){
int fa;
scanf("%d",&fa);
if (fa != -1)tree[fa].child.push_back(i);
else root = i;
}
double max = inorder(root, price, rate);
int count = 0;
for(int i = 0;i<n;i++){
if (abs(tree[i].price - max) < 0.01)count ++;
}
printf("%.02lf %d",max,count);
return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
struct Node{
int x,y,z;
}no;
int pixel[1300][200][100] = {};
bool inq[1300][200][100] = {false};
int m,n,l,t;
int X[6] = {0,0,0,0,1,-1};
int Y[6] = {0,0,1,-1,0,0};
int Z[6] = {1,-1,0,0,0,0};
bool judge(int x,int y,int z){
if (x<0 || x>=m ||y<0 || y>=n ||z<0 || z>=l)return false;
if (pixel[x][y][z] == 0 || inq[x][y][z] == true)return false;
return true;
}
int BFS(int x,int y,int z){
no.x = x;no.y = y;no.z = z;
queue<Node>qu;
qu.push(no);
inq[x][y][z] = true;
int total = 0;
while (!qu.empty()){
Node top = qu.front();
qu.pop();total++;
for(int i = 0;i<6;i++){
int newx = top.x+X[i];
int newy = top.y+Y[i];
int newz = top.z+Z[i];
if (judge(newx,newy,newz)){
no.x = newx;no.y = newy;no.z = newz;
qu.push(no);
inq[newx][newy][newz] = true;
}
}
}
if (total >= t)return total;
else return 0;
}
int main(){
scanf("%d%d%d%d",&m,&n,&l,&t);
int ans = 0;
for(int z = 0;z<l;z++){
for(int x = 0;x<m;x++){
for (int y = 0;y<n;y++){
scanf("%d",&pixel[x][y][z]);
}
}
}
for(int z = 0;z<l;z++){
for(int x = 0;x<m;x++){
for (int y = 0;y<n;y++){
if (pixel[x][y][z] == 1 && inq[x][y][z] == false){
ans += BFS(x, y, z);
}
}
}
}
printf("%d",ans);
}
#include <cstdio>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
struct node{
int x,y,z;
} Node;
int n,m,slice,T;
int pixel[1290][130][61];
bool inq[1290][130][61] = {false};
int X[6] = {0,0,0,0,1,-1};
int Y[6] = {0,0,1,-1,0,0};
int Z[6] = {1,-1,0,0,0,0};
bool judge(int x,int y,int z){
if (x >= n|| x<0 || y >= m || y<0 || z>=slice || z<0)return false;
if (pixel[x][y][z] == 0 || inq[x][y][z] == true)return false;
return true;
}
int BFS(int x,int y,int z){
int tot = 0;
queue<node>Q;
Node.x = x;Node.y = y;Node.z = z;
Q.push(Node);
inq[x][y][z] = true;
while(!Q.empty()){
node top = Q.front();
Q.pop();
tot++;
for (int i = 0;i<6;i++){
int newX = top.x + X[i];
int newY = top.y + Y[i];
int newZ = top.z + Z[i];
if (judge(newX, newY, newZ)){
Node.x = newX;
Node.y = newY;
Node.z = newZ;
Q.push(Node);
inq[newX][newY][newZ] = true;
}
}
}
if (tot >= T) return tot;
else return 0;
}
int main(){
scanf("%d%d%d%d",&n,&m,&slice,&T);
for(int z = 0;z<slice;z++){
for (int x = 0;x<n;x++){
for(int y = 0;y<m;y++){
scanf("%d",&pixel[x][y][z]);
}
}
}
int ans = 0;
for(int z = 0;z<slice;z++){
for (int x = 0;x<n;x++){
for(int y = 0;y<m;y++){
if (pixel[x][y][z] == 1 && inq[x][y][z] == false){
ans += BFS(x, y, z);
}
}
}
}
printf("%d\n",ans);
return 0;
}
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
struct Node{
int layer;
vector<int>child;
};
vector<Node>tree;
void inorder(int root){
queue<int>q;
q.push(root);
tree[root].layer = 1;
while(!q.empty()){
int front = q.front();
q.pop();
for(int i = 0;i<tree[front].child.size();i++){
q.push(tree[front].child[i]);
tree[tree[front].child[i]].layer = tree[front].layer + 1;
}
}
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
tree.resize(n+1);
for(int i = 0;i<m;i++){
int childsize,number;
scanf("%d %d",&number,&childsize);
tree[number].child.resize(childsize);
for(int j = 0;j<childsize;j++){
scanf("%d",&tree[number].child[j]);
}
}
inorder(1);
vector<int>count(n+1);
for(int i = 0;i<n+1;i++){
count[tree[i].layer]++;
}
int max = 0,maxpos = 0;
for(int i = 0;i<n+1;i++){
if (count[i]>=max) {
max = count[i];
maxpos = i;
}
}
printf("%d %d",max,maxpos);
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
typedef struct{
string id;
int time,in;
}rec;
typedef struct{
int time = 0;
string id;
}car;
bool cmptimecar(car a,car b){
if (a.time!=b.time) return a.time<b.time;
else return a.id>b.id;
}
bool cmptime(rec a,rec b){
return a.time<b.time;
}
bool cmpid(rec a,rec b){
if (a.id!=b.id)return a.id<b.id;
else return a.time<b.time;
}
int main(){
int n,k;
cin>>n>>k;
vector<rec>records;
vector<car>cars;
int query[k];
int h,m,s;
for(int i = 0;i<n;i++){
rec temp;
char temp1[4];
temp.id.resize(10);
scanf("%s %d:%d:%d %s",&temp.id[0],&h,&m,&s,temp1);
temp.time = h*3600+m*60+s;
if(temp1[0] == 'i')temp.in = 1;
else temp.in = 0;
records.push_back(temp);
}
for(int i = 0;i<k;i++){
scanf("%d:%d:%d",&h,&m,&s);
query[i] = h*3600+m*60+s;
}
sort(records.begin(),records.end(),cmpid);
for(int i = 0;i<records.size();i++){
if (i == 0 && records[0].in == 0){
records.erase(records.begin()+i);i -=1;}
else if (records[i].id != records[i-1].id && records[i].in == 0){
records.erase(records.begin()+i);i-=1;}
else if (records[i].id == records[i-1].id && records[i].in == records[i-1].in){
if (records[i].in == 1){records.erase(records.begin()+i-1);i-=1;}
else {records.erase(records.begin()+i);i-=1;}
}
}
for (int i = 0;i<records.size();i++){
if (i == 0 || records[i].id != records[i-1].id){
car temp;
temp.id = records[i].id;
temp.time-=records[i].time;
cars.push_back(temp);
}
else {
if (records[i].in == 0) cars[cars.size()-1].time += records[i].time;
else cars[cars.size()-1].time -= records[i].time;}
}
sort(cars.begin(),cars.end(),cmptimecar);
sort(records.begin(),records.end(),cmptime);
int i = 0,result = 0;
for(int j = 0;j<records.size();j++){
if (records[j].time>query[i]) {cout<<result<<endl;i+=1;}
if (records[j].in == 1)result += 1;
else result -=1;
}
for (int i = 0;i<cars.size();i++){
cout<<cars[cars.size()-1-i].id<<' ';
if(cars[cars.size()-1-i].time != cars[cars.size()-2-i].time)break;
}
printf("%0*d:%0*d:%0*d",2,cars[cars.size()-1].time/3600,2,(cars[cars.size()-1].time%3600)/60,2,(cars[cars.size()-1].time%60));
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
typedef long long LL;
const int maxsize = 1000000;
vector<bool>hashtable(maxsize,true);
vector<LL>prime;
void getPrime(LL n,vector<LL>&prime){
hashtable[0] = false;
hashtable[1] = false;
for(int i = 2;i<=n;i++){
if (hashtable[i] == true){
for (int j = 2;j<n/i+1 && j<maxsize/i+1;j+=1){
hashtable[j*i] = false;}
}
}
for(int i = 0;i<n;i++){
if (hashtable[i] == true)prime.push_back(i);
}
}
int main(){
LL n;
scanf("%lld",&n);
LL m = n;
getPrime((LL)sqrt(1.0 * n)+1,prime);
vector<int>countprime(prime.size(),0);
vector<vector<LL>>result;
for(int i = 0;i<prime.size();i++){
if (n % prime[i] == 0){
n /= prime[i];
countprime[i]++;
i --;
}
}
if (n!= 1){prime.push_back(n);countprime.push_back(1);}
int count = 0,max = -1,pos = -1;
for(int i = 0;i<prime.size() && prime[i]<=m;i++){
LL mm = m;
if (countprime[i] > 0 && prime[i] == mm){
cout<<"1\n"<<prime[i];
return 0;
}
else if (countprime[i] > 0 && mm % (prime[i]+1) != 0 && mm % (prime[i]-1) != 0){
int judge = 0;
for (int j = i+1;j<prime.size() && prime[j]<=m;j++){
judge += countprime[j];
}
if (judge == 0 && max == -1){
cout<<"1\n"<<prime[i];
return 0;
}
}
else if (countprime[i] > 0 && (mm % (prime[i]+1) == 0 || mm % (prime[i]-1) == 0)){
count+=1;
result.resize(count);
LL temp = prime[i];
while(mm % (temp) == 0 && temp>=2){
mm /= temp;
result[count-1].push_back(temp--);
}
reverse(result[count-1].begin(), result[count-1].end());
temp = prime[i]+1;
while(mm % (temp) == 0){
mm /= temp;
result[count-1].push_back(temp++);
}
if (max < (int)result[count-1].size()){
max = (int)result[count-1].size();
pos = count-1;
}
}
}
printf("%d\n",max);
for(int i = 0;i<result[pos].size();i++){
printf("%lld",result[pos][i]);
if (i<result[pos].size()-1)printf("*");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
struct node{
int key;
int next,add;
};
int main(){
int head,n;
scanf("%d %d",&head,&n);
int key,add,next;
node a[100010];
int hashtable[10001] = {};
for(int i = 0;i<n;i++){
scanf("%d %d %d",&add,&key,&next);
a[add].key = key;
a[add].add = add;
a[add].next = next;
}
vector <vector<int>> seq1;
vector <vector<int>> seq2;
int p = head;
for(int i = 0;i<n && p!=-1 ;i++){
vector <int> temp(2);
temp[0] = a[p].key;
temp[1] = a[p].add;
if (hashtable[abs(a[p].key)] == 0){
hashtable[abs(a[p].key)] = 1;
seq1.push_back(temp);
}
else{
seq2.push_back(temp);
}
p = a[p].next;
}
int m = (int)seq1.size();
for(int i = 0;i<m-1;i++){
printf("%05d %d %05d\n",seq1[i][1],seq1[i][0],seq1[i+1][1]);
}
if (m>0)printf("%05d %d %d\n",seq1[m-1][1],seq1[m-1][0],-1);
m = (int)seq2.size();
for(int i = 0;i<m-1;i++){
printf("%05d %d %05d\n",seq2[i][1],seq2[i][0],seq2[i+1][1]);
}
if (m>0)printf("%05d %d %d\n",seq2[m-1][1],seq2[m-1][0],-1);
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int init[100],heap[101],insert[100],seq[100];
void print(int a[],int n){
for(int i = 0;i<n;i++){
printf("%d",a[i]);
if (i<n-1)printf(" ");
}
printf("\n");
}
void print2(int a[],int n){
for(int i = 0;i<n;i++){
printf("%d",a[i+1]);
if (i<n-1)printf(" ");
}
printf("\n");
}
bool cmp(int a[],int b[],int n){
for(int i = 0;i<n;i++){
if (a[i]!=b[i])return false;
}
return true;
}
bool cmp2(int a[],int b[],int n){
for(int i = 0;i<n;i++){
if (a[i+1]!=b[i])return false;
}
return true;
}
int judgeinsert = 0;
bool insertionSort(int insert[],int n){
for(int i = 1;i<n;i++){
for(int j = 0;j<i;j++){
if (insert[i]<insert[j]) swap(insert[i],insert[j]);
}
if (judgeinsert == 1){
print(insert,n);
return 1;
}
if (cmp(insert,seq,n)){
printf("Insertion Sort\n");
judgeinsert = 1;
}
}
return 0;
}
void dj(int low,int high){
int i = low,j = 2*i;
while(j<=high){
if (j+1<=high && heap[j+1]>heap[j])j = j+1;
if (heap[i]<heap[j]){
swap(heap[i],heap[j]);
i = j;
j = 2*i;
}
else break;
}
}
void createHeap(){
for(int i = n/2;i>=1;i--){
dj(i,n);
}
}
int judgeheap = 0;
void heapSort(){
createHeap();
for(int i = n;i>1;i--){
swap(heap[i],heap[1]);
dj(1, i-1);
if (judgeheap == 1){
print2(heap,n);
return;
}
if (cmp2(heap,seq,n)){
printf("Heap Sort\n");
judgeheap = 1;
}
}
}
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&init[i]);
insert[i] = init[i];
heap[i+1] = init[i];
}
for(int i = 0;i<n;i++){
scanf("%d",&seq[i]);
}
bool isinsert = insertionSort(insert, n);
if (!isinsert){
heapSort();
}
return 0;
}
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,countn = 0,countnn = 0;
int weight[110],in[110];
struct node{
int data,lchild,rchild;
}root,tree[110];
void inorder(int root){
if (root == -1 || root >= n)return;
inorder(tree[root].lchild);
in[countn++] = root;
inorder(tree[root].rchild);
}
void layerorder(int root){
queue<int>q;
q.push(root);
while(!q.empty()){
int top = q.front();q.pop();
printf("%d",tree[top].data);
countnn++;
if (countnn < n)printf(" ");
if (tree[top].lchild != -1)
q.push(tree[top].lchild);
if (tree[top].rchild != -1)
q.push(tree[top].rchild);
}
}
int main(){
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%d %d",&tree[i].lchild,&tree[i].rchild);
}
for (int i = 0;i<n;i++){scanf("%d",&weight[i]);}
sort(weight,weight+n);
inorder(0);
for(int i = 0;i<n;i++){
tree[in[i]].data = weight[i];
}
layerorder(0);
return 0;
}
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
struct node{
int data;
int lchild = -1,rchild = -1;
int root = 0;
};
void layerOrder(int root,vector<node>tree,int size){
queue<int>q;
q.push(root);
int count = 0;
while(!q.empty()){
int tmp = q.front();
printf("%d",tmp);
q.pop();count++;
if (count < size)printf(" ");
if (tree[tmp].lchild != -1)q.push(tree[tmp].lchild);
if (tree[tmp].rchild != -1)q.push(tree[tmp].rchild);
}
printf("\n");
}
int num = 0;
void inOrder(int root,vector<node>tree,int size){
if (tree[root].lchild != -1) inOrder(tree[root].lchild,tree,size);
printf("%d",root);num++;
if (num<size)printf(" ");
if (tree[root].rchild != -1) inOrder(tree[root].rchild,tree,size);
}
int main(){
int n;
scanf("%d%*c",&n);
vector<node>tree(n);
for(int i = 0;i<n;i++){
char temp1,temp2;
scanf("%c %c%*c",&temp1,&temp2);
tree[i].data = i;
if (tree[i].root == 0)tree[i].root = 2;
if (temp2>='0' && temp2 <= '9'){
tree[i].lchild = (int)(temp2 - '0');
tree[tree[i].lchild].root = 1;
}
if (temp1>='0' && temp1 <= '9'){
tree[i].rchild = (int)(temp1 - '0');
tree[tree[i].rchild].root = 1;
}
}
int root;
for(int i = 0;i<n;i++){
if (tree[i].root == 2)root = i;
}
layerOrder(root,tree,n);
inOrder(root,tree,n);
return 0;
}
#include <queue>
#include <vector>
#include <cstdio>
#include <math.h>
using namespace std;
int n,k,p;
vector <int> ans,fac,temp;
void init(){
int i = 0;
while (pow(i,p)<=n){
fac.push_back(pow(i,p));
i++;
}
}
int maxfacsum = -1;
void DFS(int index,int nowk,int facsum,int sum){
if (sum == n && nowk == k){
if (facsum > maxfacsum){
ans = temp;maxfacsum = facsum;
}
return;
}
if (sum > n || nowk >k) return;
if (index - 1 >= 0){
temp.push_back(index);
DFS(index,nowk+1,facsum+index,sum+fac[index]);
temp.pop_back();
DFS(index-1,nowk,facsum,sum);
}
}
int main(){
scanf("%d %d %d",&n,&k,&p);
init();
DFS((int)fac.size()-1,0,0,0);
if (maxfacsum>-1){
printf("%d = %d^%d",n,ans[0],p);
for(int i = 1;i<ans.size();i++){
printf(" + %d^%d",ans[i],p);
}
}
else printf("Impossible");
return 0;
}
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
int n,k,p,maxsum = -1;
vector<int> fac,ans,temp;
int power(int x){
int ans = 1;
for(int i = 0;i<p;i++){
ans *= x;
}
return ans;
}
void init(){
int i = 0,temp = 0;
while(temp<=n){
fac.push_back(temp);
temp = power(++i);
}
}
void DFS(int index,int nowK,int sum,int facsum){
if (sum == n && nowK == k){
if (facsum > maxsum){
ans = temp;
maxsum = facsum;
}
return;
}
if (sum > n || nowK > k)return;
if (index - 1 >= 0){
temp.push_back(index);
DFS(index, nowK+1, sum+fac[index], facsum+index);
temp.pop_back();
DFS(index-1,nowK,sum,facsum);
}
}
int main(){
scanf("%d%d%d",&n,&k,&p);
init();
DFS((int)fac.size()-1, 0, 0, 0);
if (maxsum == -1)printf("Impossible\n");
else{
printf("%d = %d^%d",n,ans[0],p);
for(int i = 1;i<ans.size();i++){
printf(" + %d^%d",ans[i],p);
}
}
return 0;
}
#include <queue>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
struct Node{
int amount = 0;
double price;
vector<int>child;
};
vector<Node>tree;
void inorder(int root,double price,double rate){
queue<int>q;
q.push(root);
tree[root].price = price;
while(!q.empty()){
int front = q.front();
q.pop();
for(int i = 0;i<tree[front].child.size();i++){
q.push(tree[front].child[i]);
tree[tree[front].child[i]].price = tree[front].price * (1.0 + rate/100);
}
}
}
int main(){
int n;
double price,rate;
scanf("%d %lf %lf",&n,&price,&rate);
tree.resize(n);
for(int i = 0;i<n;i++){
int childsize;
scanf("%d",&childsize);
if (childsize > 0){
tree[i].child.resize(childsize);
for(int j = 0;j<childsize;j++){
scanf("%d",&tree[i].child[j]);
}
}
else{
tree[i].amount = 1;
}
}
inorder(0, price, rate);
double sum = 10000000000;
for(int i = 0;i<n;i++){
if (tree[i].amount>0 && sum > tree[i].price)
sum = tree[i].price;
}
int count = 0;
for(int i = 0;i<n;i++){
if (tree[i].amount>0 && abs(sum - tree[i].price)<0.0001)
count++;
}
printf("%.04lf %d",sum,count);
return 0;
}
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int father[3000];
void init(int n){
n = n*2;
while(n-->=0){father[n] = n;}
}
int findFather(int a){
while(a!=father[a]){
a = father[a];
}
return a;
}
void Union (int a,int b){
int faa = findFather(a);
int fab = findFather(b);
if (faa != fab){
if (fab < faa) father[faa] = fab;
else father[fab] = faa;
}
}
bool cmp(int a,int b){
return a>b;
}
int main(){
int n,temp1,temp2;
scanf("%d",&n);
init(n+1);
for(int i = 0;i<n;i++){
cin>>temp1;
int k = i + n + 2;
char c;
cin>>c;
for(int j = 0;j<temp1;j++){
cin>>temp2;
Union(k,temp2);
}
}
int count[3000] = {};
for(int i = n+2;i<2*n+2;i++){
count[findFather(i)]++;
}
sort(count,count+3000,cmp);
int sum = 0;
for(int i = 0;i<3000;i++){
if (count[i] == 0){
sum = i;break;
}
}
printf("%d\n",sum);
for(int i = 0;i<sum;i++){
printf("%d",count[i]);
if (i<sum-1)printf(" ");
}
return 0;
}
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cstdio>
using namespace std;
struct node{
double num;
char op;
bool flag;
};
string str;
stack<node>s;
queue<node>q;
map<char,int>op;
void convert(){
double num;
node temp;
for(int i = 0;i<str.size();){
if (str[i] >= '0' && str[i]<= '9'){
temp.flag = true;
temp.num += (double)(str[i++]-'0');
while(i<str.size() && str[i] >= '0' && str[i]<= '9'){
temp.num = temp.num * 10 + (double)(str[i]-'0');
i++;
}
q.push(temp);
}
else{
temp.flag = false;
while(!s.empty() && op[str[i]] <= op[s.top().op]){
q.push(s.top());
s.pop();
}
temp.op = str[i];
s.push(temp);
i++;
}
}
while(!s.empty()){
q.push(s.top());
s.pop();
}
}
double cal(){
double temp1,temp2;
node cur,temp;
while(!q.empty()){
cur = q.front();
q.pop();
if (cur.flag == true) s.push(cur);
else{
temp2 = s.top().num;
s.pop();
temp1 = s.top().num;
s.pop();
temp.flag = true;
if (cur.op == '+') temp.num = temp1 + temp2;
else if (cur.op == '-') temp.num = temp1 - temp2;
else if (cur.op == '*') temp.num = temp1 * temp2;
else temp.num = temp1 / temp2;
s.push(temp);
}
}
return s.top().num;
}
int main(){
op['+'] = op['-'] = 1;
op['*'] = op['/'] = 2;
while(getline(cin,str),str !="0"){
for(string::iterator it = str.end(); it!= str.begin();it--){
if (*it == ' ') str.erase(it);
}
while(!s.empty()) s.pop();
convert();
printf("%.02f",cal());
}
}
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct node{
int data;
node* next;
};
node* create(int array[],int size){
node *p,*pre,*head;
head = new node;
head -> next = NULL;
pre = head;
for(int i = 0;i<size;i++){
p = new node;
p->data = array[i];
p->next = NULL;
pre->next = p;
pre = p;
}
return head;
}
int search(node* head,int x){
int count = 0;
node *p = head->next;
while (p!= NULL){
if (p->data == x) count ++;
p = p->next;
}
return count;
}
void insert(node* head,int pos,int x){
node *q = head;
while(pos-- > 0){q = q->next;}
node *p = new node;
p->next = q->next;
q->next = p;
p->data = x;
}
void del(node* head,int x){
node *p = head->next;
node *pre = head;
while(p!=NULL){
if (p->data == x){
pre->next = p->next;
delete p;
p = pre->next;
}
else{
pre = p;
p = p->next;
}
}
}
int main(){
int array[5] = {1,2,3,4,5};
node* L = create(array, 5);
L = L->next;
while (L!= NULL){
printf("%d ",L->data);
L = L->next;
}
}