首页 > 代码库 > Generalized Matrioshkas UVA 11111

Generalized Matrioshkas UVA 11111

说说:

题意就是一个大整数中包含几个小整数,且小整数的和要大于大整数。同时小整数中也可能包含其他小整数,依次类推。要求判断整个的包含关系是否正确。只是题目给的说明不是很清楚。首先给你一个序列,比如:-9     -7     -2    2     -3     -1     -2    2    1    3    7    9  其中9的范围就是-9到9之间,并且只包含了7.如果序列为-9 -7 7 -2 2 9 则9中就包含了7和2两个数字,显然这种情况是不合法的。解法的话,无非就是建立两个栈,一个用来存储输入的数,另一个用来标记内含的整数会不会不合法就可以了。

源代码:

#include <stdio.h>
#define MAXN 10000000+5
int stack[MAXN];//存储数据
int calculate[MAXN];//标记数据是否合理

int main(){
  int p,wrong,val;
  char c;
 // freopen("data","r",stdin);
  while(1){
   p=wrong=0;
   do{
    scanf("%d%c",&val,&c);
    if(val<0){//插入负数
     stack[p]=calculate[p]=val;
     p++;
    }
    else{//插入正数
     if(stack[p-1]!=-val){//如果和当前栈顶不匹配
       wrong=1;
     }
     p--;
     if(p-1>=0){
     calculate[p-1]+=val;//在栈不为空的情况下,对标记数据是否合理的栈进行修改
     if(calculate[p-1]>=0)
      wrong=1;
    }
   }
   }while(c!='\n');

   if(wrong||p!=0)
    printf(":-( Try again.\n");
   else 
    printf(":-) Matrioshka!\n");

   if((c=getchar())==EOF)
    break;
   else 
    ungetc(c,stdin);
  }

  return 0;
}


Generalized Matrioshkas UVA 11111