NCPC 2011

// WA
// BY taichunmin
// NCPC 2011 pb
#include<iostream>
#include<fstream>
#include<sstream>
using namespace std;
int va[1000000];
int va_c;
int main()
{
    //freopen("pb.in","r",stdin);
    int ta;
    cin>>ta;
    string sa;
    while(ta--)
    {
        int ia,ib;
        cin>>ia;
        cin.get();
        getline(fin,sa);
        va_c=0;
        istringstream ssin(sa);
        while(ssin>>ib)
        {
            bool ba=true;
            for(int k=0;k<va_c;k++)
                if(va[k]>=ib)
                {
                    va[k]=ib;
                    ba=false;
                    break;
                }
            if(ba)va[va_c++]=ib;
        }
        cout<<va_c<<endl;
    }
    return 0;
}
// WA
// BY taichunmin
// NCPC 2011 pd
#include<iostream>
#include<sstream>
#include<fstream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int ia,ib;
struct ta_t
{
    string n;
    int v;
}attr[10];
int fa(string sa)
{
    bool is_num=true;
    for(int i=0;i<sa.size() && is_num;i++)
        if(!('0'<=sa[i] && sa[i]<='9')is_num=false;
    if(is_num)
    {
        istringstream ssin(sa);
        int temp;
        ssin>>temp;
        return temp;
    }
    else
    {
        for(int i=0;i<ia;i++)
            if(attr[i].n==sa)return attr[i].v;
    }
    return 2147483647;
}
int main()
{
    //freopen("pd.in","r",stdin);
    int ta;
    cin>>ta;
    while(ta--)
    {
        cin>>ia>>ib;
        string sa,sname,sx,sy;
        for(int i=0;i<ia;i++)
            cin>>attr[i].n>>attr[i].v;
        cin.get();
        bool ba=true;
        for(int i=0;i<ib;i++)
        {
            getline(cin,sa);
            if(!ba)continue;
            istringstream ssin(sa);
            ssin>>sname;
            bool bb=true;
            while(getline(ssin,sa,'('))
            {
                ssin>>sx;
                getline(ssin,sy,')');
                sy.erase(0,3);
                //cout<<"sy = "<<sy<<endl;
                if(fa(sx)<=fa(sy))
                {
                    bb=false;
                    break;
                }
            }
            if(bb)
            {
                ba=false;
                cout<<sname<<endl;
            }
        }
    }
}
// AC
// BY morris1028
// NCPC 2011 ph
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int A[100000],HASH[1000000],size;
struct Node{
    int v,s;
    int next;
}Node[200000];
int insHash(int v,int index)
{
    int m = v%1000000;
    if(HASH[m]==0) {
        size++;
        HASH[m]=size;
        Node[size].v=v, Node[size].s=index;
        Node[size].next=0;
        return -1;
    }
    int now=HSAH[m],pre=0;
    while(now)
    {
        if(Node[now].v>v || (Node[now].v==v && Node[now].s>index))
            break;
        else pre=now, now=Node[now].next;
    }
    size++;
    if(pre == 0) HASH[m]=size;
    else Node[pre].next=size;
    Node[size].v=v,Node[size].s=index;
    Node[size].next=now;
    return -1;
}
int find(int v,int index)
{
    int m=v%1000000;
    int now=HASH[m], pre=0;
    while(now)
    {
        if(Node[now].v==v && Node[now].s>index)
            return Node[now].s;
        else pre=now, now=Node[now].next;
    }
    return -1;
}
int Print(){
    int now, pre, i=0;
    for(int i=0;i<10;i++)
    {
        now=HASH[i];
        while(now)
        {
            printf("(%d,%d)->",Node[now].v,Node[now].s);
            pre=now, now=Node[now].next;
        }
        puts("===");
    }
    return 0;
}
int main(){
    //freopen("ph.in","r",stdin);
    int n,k,i;
    while(scanf("%d", &n)==1 && n) {
        for(i=0;i<n;i++)
            scanf("%d",&A[i];
        memset(HASH, 0, sizeof(HASH));
        scanf("%d", &k);
        int sum=0,tmp;
        size=1;
        for(i=0;i<n;i++)
        {
            A[i]%=k;
            sum+=A[i];
            sum%=k;
            if(sum<0) sum+=k;
            insHash(sum,i);
        }
        /* Print();*/
        sum=0;
        int flag=0;
        tmp=find(0,-1);
        if(tmp!=-1)
        {
            printf("%d %d\n",1,tmp+1);
            flag=1;
        }
        for(i=0;i<n;i++){
            A[i]%=k;
            sum+=A[i];
            sum%=k;
            if(sum<0) sum+=k;
            tmp=find(sum,i);
            /* printf("%d\n",tmp);*/
            if(tmp!=-1 && flag==0)
            {
                printf("%d %d\n",i+2,tmp+1);
                flag=1;
                break;
            }
        }
        if(flag==0)
            printf("no solutions.\n");
    }
    return 0;
}
/*
7
2 5 1 -4 5 9 3
10
11 -3 1 13 -5 6 1 -8 -4 5
10
*/
// AC
// BY morris1028
// NCPC 2011 pk
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define oo 2147483647
int map[1000][1000],Mt[1000];
int gcd(int x,int y)
{
    int t;
    while(y)
        t=x, x=y, y=t%y;
    return x;
}
int Used[1000], Time[1000], Ans;
int DFS(int T,int now,int start) {
    int last= oo,i,tmp,flag=0,ttry=0;
    Time[now] = T;
    /*printf("%d %d\n",now,T);*/
    for(i=0;i<Mt[now];i++){
        if(Used[map[now][i]]==0) {
            used[map[now][i]]=1;
            tmp=DFS(T+1, map[now][i],0);
            if(tmp>=T) flag=1;
            last=tmp<last?tmp:last;
            ttry++;
        } else {
            tmp=Time[map[now][i]];
            last=tmp<last?tmp:last;
        }
    }
    if(start==1) {
        if(ttry>1)
            Ans++;
    } else {
        Ans += flag;
    }
    /*printf("key : %d %d\nn", now,flag);*/
    return last;
}
int main() {
    //freopen("pk.in","r",stdin);
    int T,i,j,A[1001],n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&A[i]);
        memset(map, 0, sizeof(map));
        memset(Mt, 0, sizeof(Mt));
        memset(Used, 0, sizeof(Used));
        memset(Time, 0, sizeof(Time));
        Ans=0;
        for(i=0;i<n;i++) {
            for(j=i+1;j<n;j++) {
                int tmp=gcd(A[i],A[j]);
                if(tmp!=1) {
                    map[i][Mt[i]++]=j;
                    map[j][Mt[j]++]=i;
                }
            }
        }
        for(i=0;i<n;i++)
            if(Used[i]==0) {
                Used[i] =1,Time[i] = 1;
                DFS(1,i,1);
            }
        printf("%d\n",Ans);
    }
    return 0;
}