Codeforces Round #323(Div.2) (2/5) (Div.1) (0/5)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

05 10月 2015

A Asphalting Roads

City X consists of n vertical and n horizontal infinite roads, forming n × n intersections. Roads (both vertical and horizontal) are numbered from 1 to n, and the intersections are indicated by the numbers of the roads that form them.

Sand roads have long been recognized out of date, so the decision was made to asphalt them. To do this, a team of workers was hired and a schedule of work was made, according to which the intersections should be asphalted.

Road repairs are planned for n² days. On the i-th day of the team arrives at the i-th intersection in the list and if noneof the two roads that form the intersection were already asphalted they asphalt both roads. Otherwise, the team leaves the intersection, without doing anything with the roads.

According to the schedule of road works tell in which days at least one road will be asphalted.

Input

The first line contains integer n (1 ≤ n ≤ 50) — the number of vertical and horizontal roads in the city.

Next n² lines contain the order of intersections in the schedule. The i-th of them contains two numbers h_i, v_i(1 ≤ h_i, v_i ≤ n), separated by a space, and meaning that the intersection that goes i-th in the timetable is at the intersection of the h_i-th horizontal and v_i-th vertical roads. It is guaranteed that all the intersections in the timetable are distinct.

Output

In the single line print the numbers of the days when road works will be in progress in ascending order. The days are numbered starting from 1.

Sample test(s)

input

2
1 1
1 2
2 1
2 2

output

1 4

input

1
1 1

output

Note

In the sample the brigade acts like that:

On the first day the brigade comes to the intersection of the 1-st horizontal and the 1-st vertical road. As none of them has been asphalted, the workers asphalt the 1-st vertical and the 1-st horizontal road;
On the second day the brigade of the workers comes to the intersection of the 1-st horizontal and the 2-nd vertical road. The 2-nd vertical road hasn't been asphalted, but as the 1-st horizontal road has been asphalted on the first day, the workers leave and do not asphalt anything;
On the third day the brigade of the workers come to the intersection of the 2-nd horizontal and the 1-st vertical road. The 2-nd horizontal road hasn't been asphalted but as the 1-st vertical road has been asphalted on the first day, the workers leave and do not asphalt anything;
On the fourth day the brigade come to the intersection formed by the intersection of the 2-nd horizontal and 2-nd vertical road. As none of them has been asphalted, the workers asphalt the 2-nd vertical and the 2-nd horizontal road.

题目类型：暴力枚举

算法分析：扫一遍，如果此时row[i]和col[i]都没有访问过，则输出此时的下标i，否则跳过

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 166;

bool row[maxn], col[maxn];


int main()
{
//    CPPFF;
    int n;
    cin >> n;
    memset (row, false, sizeof (row));
    memset (col, false, sizeof (col));
    bool is_first = true;
    for (int i = 1; i <= n * n; i++)
    {
        int a, b;
        cin >> a >> b;
        if (!row[a] && !col[b])
        {
            if (is_first)
            {
                is_first = false;
                cout << i;
            }

            else cout << " " << i;
            row[a] = true, col[b] = true;
        }
    }
    cout << endl;

    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 166;

bool row[maxn], col[maxn];

int main()

{

// CPPFF;

int n;

cin >> n;

memset (row, false, sizeof (row));

memset (col, false, sizeof (col));

bool is_first = true;

for (int i = 1; i <= n * n; i++)

{

int a, b;

cin >> a >> b;

if (!row[a] && !col[b])

{

if (is_first)

{

is_first = false;

cout << i;

}

else cout << " " << i;

row[a] = true, col[b] = true;

}

cout << endl;

return 0;

}

B Robot's Task

Robot Doc is located in the hall, with n computers stand in a line, numbered from left to right from 1 to n. Each computer contains exactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the i-th of them, the robot needs to collect at least a_i any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.

The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all n parts of information if initially it is next to computer with number 1.

It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.

Input

The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integers a₁, a₂, ..., a_n(0 ≤ a_i < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.

Output

Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all n parts of information.

Sample test(s)

input

3
0 2 0

output

input

5
4 2 3 0 1

output

input

7
0 3 1 0 5 2 6

output

Note

In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.

In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.

In the third sample the optimal order of collecting parts from computers can look like that: 1->3->4->6->2->5->7.

题目类型：模拟

算法分析：直接从左到右然后从右到左将能够收集的都收集在一起，统计改变方向的次数即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1666;

int aa[maxn];
bool vis[maxn];

int main()
{
//    CPPFF;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> aa[i];

    memset (vis, false, sizeof (vis));
    int tt = 0, res = 0, cnt = 0;
    while (cnt < n)
    {
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && aa[i] <= tt)
            {
                cnt++;
                tt++;
                vis[i] = true;
            }
        }

        if (cnt >= n)
            break;

        res++;
        for (int i = n; i >= 1; i--)
        {
            if (!vis[i] && aa[i] <= tt)
            {
                cnt++;
                tt++;
                vis[i] = true;
            }
        }

        if (cnt >= n)
            break;

        res++;
    }

    cout << res << endl;

    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1666;

int aa[maxn];

bool vis[maxn];

int main()

{

// CPPFF;

int n;

cin >> n;

for (int i = 1; i <= n; i++)

cin >> aa[i];

memset (vis, false, sizeof (vis));

int tt = 0, res = 0, cnt = 0;

while (cnt < n)

{

for (int i = 1; i <= n; i++)

{

if (!vis[i] && aa[i] <= tt)

{

cnt++;

tt++;

vis[i] = true;

}

if (cnt >= n)

break;

res++;

for (int i = n; i >= 1; i--)

{

if (!vis[i] && aa[i] <= tt)

{

cnt++;

tt++;

vis[i] = true;

}

if (cnt >= n)

break;

res++;

}

cout << res << endl;

return 0;

}

BestCoder Round #58(Div.2) (4/4) (Div.1) (3/4)

poj2376

一	二	三	四	五	六	日
« 6月
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

超客的水墨烟雨

Codeforces Round #323(Div.2) (2/5) (Div.1) (0/5)

分类目录

标签云

书签

近期评论