Задача о коридоре и дверях
Помогите перевести из C++ в C#. Я не спец в C# и не понимаю почему переведенный код работает через одно место
Группа людей должна пройти по коридору, где есть пустые комнаты и двери. Когда человек проходит впервые раз в журнал записывается о#, где # номер двери, когда другой человек во второй раз проходит двери, он ее закрывает и записывается з#
Рабочий код С++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <clocale>
#include <utility>
#define pb push_back
#define mp std::make_pair
std::string get_str(long long number) {
std::string res = "";
while (number > 0) {
res += char(number % 10 + '0');
number /= 10;
}
for (size_t i = 0; i < res.size() / 2; ++i)
std::swap(res[i], res[res.size() - i - 1]);
return res;
}
int main() {
setlocale(LC_ALL, "Russian");
std::string hallway; int N;
std::cin >> hallway >> N;
std::vector<bool> door(N, 0); int cnt = 1;
std::vector<std::pair<long long, int>> report;
long long motion = 1;
for (size_t i = 0; i < hallway.size(); ++i) {
if (hallway[i] == '|') {
int amount_door = 0;
size_t j = i;
while (j < hallway.size() && hallway[j] == '|') {
++amount_door;
++j;
}
for (size_t num = 0; num < N; ++num) {
j = 0;
long long motion_to = motion + num * (N + 1);
while (j < amount_door) {
report.pb(mp(motion_to, cnt + j));
++j;
}
}
i += amount_door;
cnt += amount_door;
}
motion += N;
}
std::sort(report.begin(), report.end(), [](const std::pair<long long, int>& a, const std::pair<long long, int>& b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
});
std::string ans = "";
for (size_t i = 0; i < report.size(); ++i) {
size_t dn = report[i].second;
ans += (door[dn - 1] ? 'з' : 'о') + get_str(dn) + ' ';
door[dn - 1] = (door[dn - 1] ? 0 : 1);
std::cout << dn << '\n';
}
std::cout << ans << '\n';
return 0;
}
Входные данные:
_|_|_|__|__|_
10
Выход:
о1 о2 з1 о3 з2 о1 з3 о2 з1 о4 о3 з2 о1 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 з5 з4 з3 о5 о4 з5 з4 о5 з5
И это правильно
Нерабочий код C#
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
internal static class Program
{
public static void Resize<T>(this List<T> list, int newSize, T value = default(T))
{
if (list.Count > newSize)
list.RemoveRange(newSize, list.Count - newSize);
else if (list.Count < newSize)
{
for (int i = list.Count; i < newSize; i++)
{
list.Add(value);
}
}
}
public static void Swap<T>(this List<T> list1, List<T> list2)
{
List<T> temp = new List<T>(list1);
list1.Clear();
list1.AddRange(list2);
list2.Clear();
list2.AddRange(temp);
}
public static List<T> InitializedList<T>(int size, T value)
{
List<T> temp = new List<T>();
for (int count = 1; count <= size; count++)
{
temp.Add(value);
}
return temp;
}
public static List<List<T>> NestedList<T>(int outerSize, int innerSize)
{
List<List<T>> temp = new List<List<T>>();
for (int count = 1; count <= outerSize; count++)
{
temp.Add(new List<T>(innerSize));
}
return temp;
}
public static List<List<T>> NestedList<T>(int outerSize, int innerSize, T value)
{
List<List<T>> temp = new List<List<T>>();
for (int count = 1; count <= outerSize; count++)
{
temp.Add(InitializedList(innerSize, value));
}
return temp;
}
private static void Main(String[] args)
{
string hallway;
int N;
hallway = Console.ReadLine();
N = int.Parse(Console.ReadLine());
List<bool> door = InitializedList(N, false);
int cnt = 1;
List<Tuple<long, int>> report = new List<Tuple<long, int>>();
long motion = 1;
for (int i = 0; i < hallway.Length; ++i)
{
if (hallway[i] == '|')
{
int amount_door = 0;
int j = i;
while (j < hallway.Length && hallway[j] == '|')
{
++amount_door;
++j;
}
for (int num = 0; num < N; ++num)
{
j = 0;
long motion_to = motion + num * (N + 1);
while (j < amount_door)
{
report.Add(Tuple.Create(motion_to, cnt + j));
++j;
}
}
i += amount_door;
cnt += amount_door;
}
motion += N;
}
report.Sort((Tuple<long, int> a, Tuple<long, int> b) =>
{
if (a.Item1 == b.Item1)
{
if (a.Item2 < b.Item2)
{
return 1;
}
return 0;
}
if (a.Item1 < b.Item1)
{
return 1;
}
return 0;
});
string ans = "";
for (int i = 0; i < report.Count; ++i)
{
int dn = report[i].Item2;
int dan = dn;
string res = "";
while (dan > 0)
{
res += (char)(dan % 10 + '0');
dan /= 10;
}
for (int j = 0; j < res.Length / 2; ++j)
{
StringBuilder sb = new StringBuilder(res);
char temp = sb[res.Length - j - 1];
sb[res.Length - j - 1] = res[j];
sb[j] = temp;
res = sb.ToString();
}
ans += (door[dn - 1] ? 'з' : 'o') + res + ' ';
door[dn - 1] = (door[dn - 1] ? 0 : 1) != 0;
}
Console.Write(ans);
Console.Write('\n');
}
}
Входные данные:
_|_|_|__|__|_
10
Выход:
o5 o3 з3 o3 o4 з4 o4 з4 o4 з4 o4 з4 o4 з4 з5 o5 з5 o5 з5 o5 з5 o5 з3 o3 з3 o3 o1 з1 o1 з1 o1 з1 o1 з1 o1 o2 з5 з2 o2 з2 o2 з2 o2 з2 o2 з3 o3 з3 з2 з1
И это НЕ правильно
Мне кажется у меня проблемы в C# с сортировкой
Так же был сделан код на C#, но он слишком много времени занимает 25/26 Time limit exceeded. Если возможно, то его желательно улучшить. Проблема, что входные данные безграничны, но тесты сделаны, чтоб можно было проверить код за 11 секунд. Мне сказали "идеальный код за 6 секунд справляется" и мне сказали "это задача на паттерны".
using System;
using System.Collections.Generic;
internal static class Program
{
private static void Main(String[] args)
{
string hallway; int n;
hallway = Console.ReadLine();
n = Convert.ToInt32(Console.ReadLine());
List<bool> open = new List<bool>(hallway.Length);
for(int i = 0;i<hallway.Length;i++){
open.Add(false);
}
List<int> door = new List<int>();
for(int i = 0;i<hallway.Length;i++){
door.Add(-1);
}
List<int>pos = new List<int>();
for(int i = 0;i<n;i++){
pos.Add(-1);
}
int cnt = 1;
int lim = 1;
int first = 0;
string str = "";
while(first < n){
if(hallway.Length <= pos[first]){
++first;
continue;
}
for(int i = first; i < lim; ++i){
int cur_pos = pos[i] + 1;
if(cur_pos > hallway.Length) continue;
while(cur_pos < hallway.Length && (hallway[cur_pos] == '|')){
if(door[cur_pos] == -1){
door[cur_pos] = cnt;
++cnt;
}
if(open[cur_pos] == true){
str+="з" + door[cur_pos].ToString() + " ";
open[cur_pos] = false;
}
else{
str+="о" + door[cur_pos].ToString() + " ";
open[cur_pos] = true;
}
++cur_pos;
}
pos[i] = cur_pos;
}
lim = Math.Min(n,lim+1);
}
Console.WriteLine(str);
}
}
Ответы (1 шт):
Автор решения: aepot
→ Ссылка
Методом дедукции и телепатии написал вот такое решение.
private static void Main(string[] args)
{
string hallway = "_|_|_|__|__|_";
int n = 10;
hallway = hallway.Replace("|_", "|");
int[] doorIndexes = hallway.Select((c, i) => c == '|' ? i : -1).Where(x => x >= 0).ToArray();
bool[] doorState = new bool[doorIndexes.Length];
List<string> log = new List<string>();
for (int step = -n; step < hallway.Length; step++)
{
for (int member = n; member > 0; member--)
{
int position = step + member;
if (position >= 0 && position < hallway.Length && hallway[position] == '|')
{
int doorIndex = Array.IndexOf(doorIndexes, position);
doorState[doorIndex] = !doorState[doorIndex];
log.Add((doorState[doorIndex] ? "о" : "з") + (doorIndex + 1));
}
}
}
string result = string.Join(" ", log);
string expected = "о1 о2 з1 о3 з2 о1 з3 о2 з1 о4 о3 з2 о1 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 з5 з4 з3 о5 о4 з5 з4 о5 з5";
Console.WriteLine(expected);
Console.WriteLine(result);
Console.WriteLine(expected == result);
Console.ReadKey();
}
Вывод в консоль.
о1 о2 з1 о3 з2 о1 з3 о2 з1 о4 о3 з2 о1 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 з5 з4 з3 о5 о4 з5 з4 о5 з5
о1 о2 з1 о3 з2 о1 з3 о2 з1 о4 о3 з2 о1 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 о1 з5 з4 з3 о2 з1 о5 о4 о3 з2 з5 з4 з3 о5 о4 з5 з4 о5 з5
True
C++ и C# - очень разные языки, когда дело касается обработки данных.