Unknown Language Round 2

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
72 Unknown Language Round 2 FINISHED False 10800 475854585 March 20, 2011, 4:10 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 143 ) F Oil PROGRAMMING *special greedy math 2100

After the nationalization of the oil industry, Dr. Mosaddegh wants to dig some oil wells to extract all the oil in Persian Gulf. But Persian Gulf is huge and has an infinite amount of oil. So Dr. Mosaddegh works only on a rectangular plane of size n × m of the Persian Gulf. Each of the cells in this rectangle either contains an infinite amount of oil or nothing. Two cells are considered adjacent if and only if they have a common edge, a path is a sequence c 1 , c 2 , ..., c x of cells so that all of them contain oil and for each i , c i is adjacent to c i - 1 and c i + 1 (if they exist). Two cells are considered connected to each other if and only if there exists a path between them. If we dig a well in a certain cell, we can extract oil from all the cells that are connected to it by oil paths. It is not allowed to dig wells on empty cells. Dr. Mosaddegh also knows that in Persian Gulf, the empty cells form rows and columns. I. e. if some cell is empty, then it's column is completely empty or it's row is completely empty, or both. Help Dr. Mosaddegh find out how many wells he has to dig to access all the oil in that region. In the first line there are two positive integers n and m ( 1 ≤ n , m ≤ 100 ). In the second line there is an integer t ( 0 ≤ t ≤ n ), the number of empty rows. t distinct positive integers follow, these are the numbers of empty rows and are in range 1, n . In the second line there is an integer s ( 0 ≤ s ≤ m ) that shows the number of columns not having any oil. s distinct positive integers follow, these are the numbers of empty columns and are in range of 1, m . Note that rows are numbered from 1 to n (from top to bottom) and columns are numbered from 1 to m (from left to right). A single integer, the minimum number of wells that Dr. Mossadegh has to dig. This is actually finding how many regions are made by removing the given rows and columns.

Tutorials

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
345915 nodchip F March 20, 2011, 5:54 p.m. OK Io TESTS 70 170 4608000 2100
345400 wrong F March 20, 2011, 5:02 p.m. OK Io TESTS 70 170 4608000 2100
3818165 yermak0v F June 3, 2013, 9:29 a.m. OK Io TESTS 70 171 307200 2100
3669345 Omelianenko F May 4, 2013, 1:39 p.m. OK Io TESTS 70 171 307200 2100
13832316 130705009 F Oct. 25, 2015, 2:09 a.m. OK Io TESTS 70 186 204800 2100
64571797 steven1029 F Nov. 9, 2019, 9:25 a.m. OK Io TESTS 70 186 307200 2100
34973699 Stronger2020 F Feb. 6, 2018, 2:29 p.m. OK Io TESTS 70 186 6041600 2100
26329752 CyberZHG F April 13, 2017, 1:45 a.m. OK Io TESTS 70 186 6041600 2100
1125044 ZhouYuChen F Jan. 29, 2012, 9:09 a.m. OK Io TESTS 70 190 4608000 2100
1125036 ZhouYuChen F Jan. 29, 2012, 9:04 a.m. OK Io TESTS 70 190 4608000 2100

remove filters

Back to search problems