출처: https://train.usaco.org/usacogate

문제 설명

출처 : IOI'96 - Problem 5

...

The first K characters of S are the prefix of S with length K. 

Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives. 

입력

First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of uppercase characters on one or more lines.

The list of primitives is terminated by a line that contains nothing more than a period (`.').

No primitive appears twice in the list.

 

Then, the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceeds 76 letters in length.

 

The "newlines" (line terminators) are not part of the string S.

출력

A single line containing an integer that is the length of the longest prefix that can be composed from the set P.

입력 예

A AB BA CA BBC
.
ABABACABAABC

출력 예

11

문제 풀이

만들려고 하는 문자열 길이의 앞에서 부터 출발해서, 부분 문자열이 존재하는지 검사한다. 단순 double loop를 적용해도 부분 문자열의 수를 N, 만들려고 하는 문자열의 길이를 M이라고 하면 O(NM) 정도로 해결가능해진다.

프로그램 내용

더보기 
... 
	// string target;
	// vector<string> primitives;
    
	dp[0]=1;
	for(int i=0;i< target.size();i++) 
	{
        if(dp[i])
        { 
            for(int j=0;j<primivites.size();j++) 
            {
                if( primivies[j]==target.substr(i,primitives[j].size()) ) 
                {
                    dp[i+primivies[j].size()] = 1;
                }
            }
        }
    }
    ...

 

Chapter 2. Bigger Challenges ( link ) 

저작자표시 비영리 변경금지

'USACO Training' 카테고리의 다른 글

Problem 2.2.3 Preface Numbering  (0) 2021.01.21
Problem 2.1.3 The Castle  (0) 2021.01.07
Problem 2.1.7 Hamming Codes  (0) 2021.01.06
Problem 1.2.5 Greedy Gift Givers - 2  (0) 2021.01.03
Problem 2.1.6 Healthy Holsteins  (0) 2020.02.11

출처: https://train.usaco.org/usacogate

문제 설명

Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I's, V's, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. 

Do not print letters that do not appear in the page numbers specified.

입력

A single line containing the integer N.

출력

The output lines specify, in ascending order of Roman numeral letters, the letter, a single space,
and the number of times that letter appears on preface page numbers. Stop printing letter totals
after printing the highest value letter used to form preface numbers in the specified set.

입력 예

5

출력 예

I 7
V 2

( I, II, III, IV, V) -> I: 1(1)+2(2)+3(3)+1(4) = 7, V : 1(4) + 1(5) = 2

문제 풀이

1 부터 입력받은 숫자까지 Roman 숫자로 표현할때 각 숫자들이 몇번 나오는지 세는 프로그램을 작성한다.

Roman 숫자표현에서 나오는 문자는 7가지 이다.( I - 1, V - 5, X - 10, L - 50, C - 100 , D - 500, M - 1000) 

이런 7개 문자들이 몇번 나오는지 unordered_map<char, int> 형태로 기록한다.

프로그램 내용

더보기

 

...
	string ones[9] = {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    string tens[9] = {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    string hundreds[9] = {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    string thousands[3] = {"M", "MM", "MMM"};
...
    unordered_map<char, int> m;
    for (int i = 1; i <= N; i++) {
        int num = i;
        
        if (num / 1000 > 0) {
            count(m, thousands[num / 1000 - 1]);
            num %= 1000;
        }
        if (num / 100 > 0) {
            count(m, hundreds[num / 100 - 1]);
            num %= 100;
        }
        if (num / 10 > 0) {
            count(m, tens[num / 10 - 1]);
            num %= 10;
        }
        if (num > 0) {
            count(m, ones[num - 1]);
        }
    }
    if (m.find('I') != m.end()) fout << "I " << m['I'] << endl;
    if (m.find('V') != m.end()) fout << "V " << m['V'] << endl;
    if (m.find('X') != m.end()) fout << "X " << m['X'] << endl;
    if (m.find('L') != m.end()) fout << "L " << m['L'] << endl;
    if (m.find('C') != m.end()) fout << "C " << m['C'] << endl;
    if (m.find('D') != m.end()) fout << "D " << m['D'] << endl;
    if (m.find('M') != m.end()) fout << "M " << m['M'] << endl;
...

 

Chapter 2. Bigger Challenges ( link )

저작자표시 비영리 동일조건

'USACO Training' 카테고리의 다른 글

Problem 2.3.1 The Longest Prefix  (0) 2021.04.01
Problem 2.1.3 The Castle  (0) 2021.01.07
Problem 2.1.7 Hamming Codes  (0) 2021.01.06
Problem 1.2.5 Greedy Gift Givers - 2  (0) 2021.01.03
Problem 2.1.6 Healthy Holsteins  (0) 2020.02.11

출처: https://train.usaco.org/usacogate

문제 설명

The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their "outer edges" to keep out the wind and rain.

 

입력

Line 1: Two space-separated integers: M and N
Line 2..: M x N integers, several per line.

출력

Line 1: The number of rooms the castle has.
Line 2: The size of the largest room
Line 3: The size of the largest room creatable by removing one wall
Line 4: The single wall to remove to make the largest room possible

입력 예

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

출력 예

5
9
16
4 1 E

문제 풀이

IOI'94 - Day 1 의 문제이다. N x M maze에서 연결된 방들을 채워가는 Flood fill 알고리즘을 적용하면, 전체 연결된 방을 알 수 있다. 한방에서 연결된 방을 찾아가는 방법은 DFS가 적용된다.  N x M maze를 다루는 연습이 필요한 문제이다. 벽을 제거하면서 값을 비교할때는 항상 계산이 끝난 다음 원래 값으로 변경시키는 과정을 적용해야 한다.

프로그램 내용

더보기 
void fill_cells(int y, int x, int& direction)
{
    if(visited[y][x]) return;
    visited[y][x] = 1;
    before[y][x] = roomNumber;
    direction++;

    if(!(cells[y][x] & 1)) fill_cells(y,x-1, direction); /// Connected Direction: W
    if(!(cells[y][x] & 2)) fill_cells(y-1,x, direction); /// Connected Direction: N
    if(!(cells[y][x] & 4)) fill_cells(y,x+1, direction); /// Connected Direction: E
    if(!(cells[y][x] & 8)) fill_cells(y+1,x, direction); /// Connected Direction: S
};
...

한 방에 도착하면 연결된 벽을 확인하고, 벽으로 막혀 있지 않으면 그 방까지 연결한다.

 /// visit every rooms
    for(int y=1; y <N+1; ++y)
    {
        for(int x=1; x<M+1;++x)
        {
            if(!visited[y][x])
            {
                roomNumber++;
                int tn=0;
                fill_cells(y,x,tn);
                room[roomNumber] = tn;
                if( tn > maxn ) maxn = tn;
            }
        }
    }

    /// remove wall check
    for(int j=1;j<=M;j+=1)
    {
        for(int i=N;i>=1;i-=1)
        {
            if(cells[i][j]&2)if(before[i-1][j] && before[i-1][j]!=before[i][j])
            {
                if( room[before[i-1][j]] + room[before[i][j]] > max2n )
                {
                    max2n = room[before[i-1][j]] + room[before[i][j]];
                    wx = i,wy = j,wd = 'N';
                }
            }

            if(cells[i][j]&4)if(before[i][j+1] && before[i][j+1]!=before[i][j])
            {
                if( room[before[i][j+1]] + room[before[i][j]] > max2n )
                {
                    max2n = room[before[i][j+1]] + room[before[i][j]];
                    wx = i,wy = j,wd = 'E';
                }
            }
        }
    }

전체 방에 대해서 벽을 제거해서 결과값이 최대가 될때마다 제거하는 벽을 기록하는 방법을 적용한다.

 

Chapter 2. Bigger Challenges ( link )

저작자표시 비영리 동일조건

'USACO Training' 카테고리의 다른 글

Problem 2.3.1 The Longest Prefix  (0) 2021.04.01
Problem 2.2.3 Preface Numbering  (0) 2021.01.21
Problem 2.1.7 Hamming Codes  (0) 2021.01.06
Problem 1.2.5 Greedy Gift Givers - 2  (0) 2021.01.03
Problem 2.1.6 Healthy Holsteins  (0) 2020.02.11

+ Recent posts

티스토리툴바