1. Factor problem
Factor problem
Given any two positive integers N and m, find the smallest positive integer a so that a and (M-a) are factors of N.
Time limit: 10000
Memory limit: 65536
input
Including two integers n and M. N does not exceed 1000000.
output
Output an integer a to represent the result. If the positive integer satisfying the condition does not exist in a case, output - 1 in the corresponding line
sample input
35 10
sample output
5
#include <stdio.h> int main(int argc, char *argv[]) { int N,M,a=0,t; scanf("%d%d",&N,&M); t=M/2; for(a=1;a<=t;a++) { if( N%a==0 && (N%(M-a)==0) ) { t=-1; break; } } if(t!=-1) printf("-1\n"); else printf("%d\n",a); return 0; }
2. Sum and product of prime numbers
Sum and product of prime numbers
The sum of two prime numbers is S. what is the maximum product of them?
Time limit: 10000
Memory limit: 65536
input
A positive integer S not greater than 10000 is the sum of two prime numbers.
output
An integer that is the maximum product of two prime numbers. The data is guaranteed to have a solution.
sample input
50
sample output
589
#include <bits/stdc++.h> int prime(int h) { if(h < 2) { return 0; } for(int i=2;i<=h/2;++i) { if(!(h%i))return 0; } return 1; } int main( ) { int n; int max=0; int sj=1; int m; scanf("%d",&n); for(int i=2;i<n;++i) { if(prime(i)) { m=n-i; if(prime(m)) { sj=m*i; if(max<sj)max=sj; } } } printf("%d",max); }
3. Extension matching problem
Extension matching problem
There are left parentheses, right parentheses and upper and lower case letters in a string (no more than 100 in length); It is stipulated (like the common arithmetic formula) that any left bracket matches the nearest right bracket from inside to outside. Write a program to find the unmatched left and right parentheses, output the original string, and mark the unmatched parentheses on the next line. The unmatched left bracket is marked with "$" and the unmatched right bracket is marked with " tagging.
Time limit: 3000
Memory limit: 656
input
The input includes multiple groups of data, one line for each group of data, including a string, only left and right parentheses and uppercase and lowercase letters, and the length of the string shall not exceed 100
output
For each group of output data, two lines are output. The first line contains the original input characters, and the second line is composed of "$", "?" And spaces, "$" and "?" Indicates that the corresponding left and right parentheses cannot match.
sample input
((ABCD(x) )(rttyy())sss)(
sample output
((ABCD(x) $$ )(rttyy())sss)( ? ?$
#include<stdio.h> #include<string.h> #include<malloc.h> typedef struct node { char ch[100]; char sign[100]; char index[100]; int length; } Stack; void init(Stack *&s,int n) { s=(Stack*)malloc(n*sizeof(Stack)); int i; for(i=0;i<n;i++) { s->ch[i]=' '; s->sign[i]=' '; s->index[i]=0; } s->length=0; } void push(Stack *&s,char ch ,int index) { if(s->length<100) { s->ch[s->length]=ch; s->index[s->length]=index; if(ch=='(') s->sign[s->length]='$'; if(ch==')') s->sign[s->length]='?'; } s->length++; } void pop(Stack *&s,char ch,int index) { if(s->length>0&&s->ch[s->length-1]=='(') { s->length--; } else { push(s,ch,index); } } int main() { char str[101]; char result[101]; int i,j,k,len,index; Stack *s; while(gets(str)) { len = strlen(str); init(s,len); for(i=0;i<len;i++) { if(str[i]=='(') { push(s,str[i],i); } else if(str[i]==')') { pop(s,str[i],i); } else { continue; } } k = 0; for(j=0;j<len;j++) result[j]=' '; while(k<s->length) { index = s->index[k]; result[index]=s->sign[k]; k++; } printf("%s\n",str); for(i=0;i<len;i++) printf("%c",result[i]); printf("\n"); free(s); } return 0; }
At present, I only know these three questions.