Google code jam: Problem A. Store Credit

2795 단어
Problem
You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).
Input
The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:
  • One line containing the value C, the amount of credit you have at the store.
  • One line containing the value I, the number of items in the store.
  • One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
  • Each test case will have exactly one solution.

  • Output
    For each test case, output one line containing "Case #x: "followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.
    Limits
    5 ≤ C ≤ 1000 1 ≤ P ≤ 1000
    Small dataset
    N = 10 3 ≤ I ≤ 100
    Large dataset
    N = 50 3 ≤ I ≤ 2000
    Sample
    Input
    Output 3
    100
    3
    5 75 25
    200
    7
    150 24 79 50 88 345 3
    8
    8
    2 1 9 4 4 56 90 3

     
    내 코드:
    #include <stdio.h>
    #include <iostream.h>
    int item[2001];
    //#define SMALL
    #define LARGE //No.1
    int main()
    {
    #ifdef SMALL
    	freopen("A-small-practice.in","r",stdin);//No.2
    	freopen("A-small-practice.out","w",stdout);
    #endif
    
    #ifdef LARGE
    	freopen("A-large-practice.in","r",stdin);
    	freopen("A-large-practice.out","w",stdout);
    #endif
    
     	int N;
    	cin>>N;
        
    	int i,j,k;
    	for(i=0;i<N;i++)
    	{
    		int C;
    		cin>>C;
    		int I;
    		cin>>I;
    		for(j=0;j<I;j++)
    		{
    			cin>>item[j];
    		}
    		for(j=0;j<I-1;j++)
    			for(k=j+1;k<I;k++)
    			{
    				if(C == item[j]+item[k]) 
    				{
    					cout<<"Case #"<<i+1<<": "<<j+1<<" "<<k+1<<endl;
    					goto END;//No.3
    				}
    			}
    		END:;	
    	}
    
    
    	return 0;
    }

    이 프로그램의 사고방식은 거품으로 정렬하는 것과 유사하다.j, k 두 변수로 두 개의 그룹을 두루 훑어보다.시간 복잡도는 O (n^2)
    No.1 #define 매크로 정의로 소규모 데이터와 대규모 데이터 구분
    No.2 위에서 언급한freopen()을 사용하여 표준 입력 출력 흐름의 대상을 수정하고 키보드와 화면에서 두 개의 파일로 변경합니다.
    No.3 goto 함수로 두 층의 순환을 뛰어넘는다.goto 함수의 문법에 주의하세요.

    좋은 웹페이지 즐겨찾기