forked from cpinitiative/usaco-guide
-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Merge pull request cpinitiative#573 from SansPapyrus683/master
Added solution for Packmen and Magic Ship
- Loading branch information
Showing
3 changed files
with
581 additions
and
13 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,266 @@ | ||
| --- | ||
| id: cf-magship | ||
| source: CF | ||
| title: Magic Ship | ||
| author: Kevin Sheng | ||
| --- | ||
|
|
||
| [Official Editorial](https://codeforces.com/blog/entry/65365) | ||
|
|
||
| <LanguageSection> | ||
|
|
||
| <CPPSection> | ||
|
|
||
| ```cpp | ||
| #include <iostream> | ||
| #include <vector> | ||
| #include <string> | ||
| #include <cmath> | ||
|
|
||
| using std::cin; | ||
| using std::cout; | ||
| using std::endl; | ||
|
|
||
| bool reachable(std::pair<long long, long long> start, | ||
| std::pair<long long, long long> end, | ||
| std::string wind, | ||
| long long time) { | ||
| long long wind_x = 0; | ||
| long long wind_y = 0; | ||
| for (const char& w : wind) { | ||
| switch (w) { | ||
| case 'U': | ||
| wind_y ; | ||
| break; | ||
| case 'D': | ||
| wind_y--; | ||
| break; | ||
| case 'L': | ||
| wind_x--; | ||
| break; | ||
| case 'R': | ||
| wind_x ; | ||
| break; | ||
| } | ||
| } | ||
| // to speed things up, we can skip all the repetitive cycles and just multiply by the total complete amount of cycles | ||
| wind_x *= time / wind.length(); | ||
| wind_y *= time / wind.length(); | ||
| long long remainder = time % wind.length(); | ||
| for (long long i = 0; i < remainder; i ) { | ||
| switch (wind[i]) { | ||
| case 'U': | ||
| wind_y ; | ||
| break; | ||
| case 'D': | ||
| wind_y--; | ||
| break; | ||
| case 'L': | ||
| wind_x--; | ||
| break; | ||
| case 'R': | ||
| wind_x ; | ||
| break; | ||
| } | ||
| } | ||
| start.first = wind_x; | ||
| start.second = wind_y; | ||
| return std::abs(start.first - end.first) | ||
| std::abs(start.second - end.second) <= time; | ||
| } | ||
|
|
||
| /** | ||
| * https://codeforces.com/problemset/problem/1117/C | ||
| * 0 0 | ||
| * 4 6 | ||
| * 3 | ||
| * UUU should output 5 | ||
| * | ||
| * 0 3 | ||
| * 0 0 | ||
| * 3 | ||
| * UDD should output 3 | ||
| */ | ||
| int main() { | ||
| std::pair<long long, long long> at_pos; // i'm not taking any chances with integer overflow | ||
| cin >> at_pos.first >> at_pos.second; | ||
| std::pair<long long, long long> destination; | ||
| cin >> destination.first >> destination.second; | ||
| long long wind_len; | ||
| cin >> wind_len; // won't be using this but oh well | ||
| std::string wind_cycle; | ||
| cin >> wind_cycle; | ||
|
|
||
| long long lo = 0; | ||
| long long hi = 20000000000000000; // just spammed a bunch of 0s, it should be long enough | ||
| long long valid = -1; | ||
| while (lo <= hi) { | ||
| long long mid = (lo hi) / 2; | ||
| if (reachable(at_pos, destination, wind_cycle, mid)) { | ||
| valid = mid; | ||
| hi = mid - 1; | ||
| } else { | ||
| lo = mid 1; | ||
| } | ||
| } | ||
| cout << valid << endl; | ||
| } | ||
| ``` | ||
| </CPPSection> | ||
| <JavaSection> | ||
| ```java | ||
| import java.io.BufferedReader; | ||
| import java.io.IOException; | ||
| import java.io.InputStreamReader; | ||
| import java.util.Arrays; | ||
| /** | ||
| * https://codeforces.com/problemset/problem/1117/C | ||
| * 0 0 | ||
| * 4 6 | ||
| * 3 | ||
| * UUU should output 5 | ||
| * | ||
| * 0 3 | ||
| * 0 0 | ||
| * 3 | ||
| * UDD should output 3 | ||
| */ | ||
| public class MagicShip { | ||
| public static void main(String[] args) throws IOException { | ||
| BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); | ||
| long[] atPos = Arrays.stream(read.readLine().split(" ")).mapToLong(Long::parseLong).toArray(); | ||
| long[] destination = Arrays.stream(read.readLine().split(" ")).mapToLong(Long::parseLong).toArray(); | ||
| read.readLine(); | ||
| char[] winds = read.readLine().toUpperCase().toCharArray(); | ||
| if (!reachable(atPos, destination, Long.MAX_VALUE / 2, winds)) { | ||
| System.out.println(-1); | ||
| System.exit(0); | ||
| } | ||
| long lo = 0; | ||
| long hi = Long.MAX_VALUE / 2; | ||
| long valid = -1; | ||
| while (lo <= hi) { | ||
| long mid = lo / 2 hi / 2; | ||
| if (reachable(atPos, destination, mid, winds)) { | ||
| valid = mid; | ||
| hi = mid - 1; | ||
| } else { | ||
| lo = mid 1; | ||
| } | ||
| } | ||
| System.out.println(valid); | ||
| } | ||
| private static boolean reachable(long[] from, long[] to, long time, char[] windPattern) { | ||
| long windX = 0; | ||
| long windY = 0; | ||
| // calculate the net change by the wind through one cycle | ||
| for (char w : windPattern) { | ||
| switch (w) { | ||
| case 'U': | ||
| windY ; | ||
| break; | ||
| case 'D': | ||
| windY--; | ||
| break; | ||
| case 'L': | ||
| windX--; | ||
| break; | ||
| case 'R': | ||
| windX ; | ||
| break; | ||
| } | ||
| } | ||
| // to speed things up, we can multiply the blown amount by the complete cycle amount | ||
| windX *= time / windPattern.length; | ||
| windY *= time / windPattern.length; | ||
| long remainder = time % windPattern.length; | ||
| for (int i = 0; i < remainder; i ) { // calculate the remaining wind | ||
| switch (windPattern[i]) { | ||
| case 'U': | ||
| windY ; | ||
| break; | ||
| case 'D': | ||
| windY--; | ||
| break; | ||
| case 'L': | ||
| windX--; | ||
| break; | ||
| case 'R': | ||
| windX ; | ||
| break; | ||
| } | ||
| } | ||
| return manhattanDist(new long[] {from[0] windX, from[1] windY}, to) <= time; | ||
| } | ||
| private static long manhattanDist(long[] from, long[] to) { | ||
| return Math.abs(from[0] - to[0]) Math.abs(from[1] - to[1]); | ||
| } | ||
| } | ||
| ``` | ||
|
|
||
| </JavaSection> | ||
|
|
||
| <PySection> | ||
|
|
||
| ```py | ||
| """ | ||
| 0 0 | ||
| 4 6 | ||
| 3 | ||
| UUU should output 5 | ||
| 0 3 | ||
| 0 0 | ||
| 3 | ||
| UDD should output 3 | ||
| """ | ||
| from typing import List | ||
|
|
||
| def reachable(start: List[int], end: List[int], wind: str, time: int): | ||
| start = start.copy() | ||
| wind_x = wind.count("R") - wind.count("L") # count the net changes after one wind cycle | ||
| wind_y = wind.count("U") - wind.count("D") | ||
| cycle_num = time // len(wind) | ||
| wind_x *= cycle_num # speed this up by multiplying by the amount of complete cycles in the time | ||
| wind_y *= cycle_num | ||
|
|
||
| remainder = time % len(wind) | ||
| wind = wind[:remainder] # account for the remaining wind | ||
| wind_x = wind.count("R") - wind.count("L") | ||
| wind_y = wind.count("U") - wind.count("D") | ||
|
|
||
| start[0] = wind_x # apply the changes and see if the manhattan distance is less than the time | ||
| start[1] = wind_y | ||
| return abs(start[0] - end[0]) abs(start[1] - end[1]) <= time | ||
|
|
||
|
|
||
| at_pos = [int(i) for i in input().split()] | ||
| destination = [int(i) for i in input().split()] | ||
| input() | ||
| wind_cycle = input() | ||
|
|
||
|
|
||
| lo = 0 | ||
| hi = 2 * 10**14 | ||
| valid = -1 | ||
| while lo <= hi: | ||
| mid = (lo hi) // 2 | ||
| if reachable(at_pos, destination, wind_cycle, mid): | ||
| valid = mid | ||
| hi = mid - 1 | ||
| else: | ||
| lo = mid 1 | ||
| print(valid) | ||
| ``` | ||
|
|
||
| </PySection> | ||
|
|
||
| </LanguageSection> |
Oops, something went wrong.